Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

Search:

CA216      CA249      CA318

CA400      CA651      CA668


Polynomial codes for error detection

Also called CRC (Cyclic Redundancy Check)
Data is sent with a checksum.
When arrives, checksum is recalculated. Should match the one that was sent.

Bitstring represents polynomial.
e.g. 110001 represents:
1 . x5 + 1 . x4 + 0 . x3 + 0 . x2 + 0 . x1 + 1 . x0
= x5 + x4 + x0

The order of a polynomial is the power of the highest non-zero coefficient. This is polynomial of order 5.

Special case: We don't allow bitstring = all zeros.
Easy to use framing or stuffing to make framed-and-stuffed transmission never all-zero,
while still allowing payload within it to be all-zero.




Modulo 2 arithmetic

We are going to define a particular field (or here), in fact the smallest field there is, with only 2 members.

We define addition and subtraction as modulo 2 with no carries or borrows.
This means addition = subtraction = XOR.
Here's the rules for addition:

0 + 0 = 0 
0 + 1 = 1
1 + 0 = 1 
1 + 1 = 0
Multiplication:
0 * 0 = 0 
0 * 1 = 0
1 * 0 = 0 
1 * 1 = 1 
Subtraction: if 1+1=0, then 0-1=1, hence:
0 - 0 = 0 
0 - 1 = 1
1 - 0 = 1 
1 - 1 = 0
Long division is as normal, except the subtraction is modulo 2.

Example

No carry or borrow:
011 + (or minus)
110
---
101
Consider the polynomials:
x + 1 +
x2 + x
-------------
x2 + 2x + 1
= x2 + 1
We're saying the polynomial arithmetic is modulo 2 as well, so that:
2 xk = 0
for all k.




What does this mean?

Just consider this as a set of rules which, if followed, yield certain results.

When the checksum is re-calculated by the receiver, we should get the same results.

All sorts of rule sets could be used to detect error.

It is useful here that the rules define a well-behaved field.

Consider the polynomials with x as isomorphic to binary arithmetic with no carry.
It is just easier to work with abstract x so we don't make the mistake of starting to add, say. 3 x3 to get x4 + x3 if we were thinking of x=2.
We work in abstract x and keep "the coefficients of each power nicely isolated" (in mod 2, when we add two of same power, we get zero, not another power).



multiplication

Multiply 110010 by 1000
Multiply (x5 + x4 + x) by x3
= x8 + x7 + x4
= 110010000
i.e. Just add 3 zeros

In general, to multiply by xk, add k zeros.



division

x2 + 1 = (x+1)(x+1)
(since 2x=0)

Do long division:
Divide (x+1) into x2 + 1
Divide 11 into 101
Subtraction mod 2
Get 11, remainder 0

11 goes into 10 once, remainder 1
A goes into B if it has the same number of bits



Polynomial factors and primes

If a polynomial has no factors other than 1 and itself, it is a prime polynomial or an Irreducible Polynomial.
x2 + 1 (= 101) is not prime
This is not read as "5", but can be seen as the "5th pattern" when enumerating all 0,1 patterns.

Polynomial primes do not correspond to integer primes.

Note any bitstring ending in 0 represents a polynomial that is not prime since it has x as a factor (see above).
All primes look like 1....1




Error detection with CRC

Consider a message 110010 represented by the polynomial M(x) = x5 + x4 + x
Consider a generating polynomial G(x) = x3 + x2 + 1 (1101)
This is used to generate a 3 bit CRC = C(x) to be appended to M(x).
Note this G(x) is prime.

Steps:

  1. Multiply M(x) by x3 (highest power in G(x)). i.e. Add 3 zeros. 110010000

  2. Divide the result by G(x). The remainder = C(x).
    1101 long division into 110010000 (with subtraction mod 2)
    = 100100 remainder 100

    Special case: This won't work if bitstring = all zeros. We don't allow such an M(x).
    But M(x) bitstring = 1 will work, for example. Can divide 1101 into 1000.

    If: x div y gives remainder c
    that means: x = n y + c
    Hence (x-c) = n y
    (x-c) div y gives remainder 0
    Here (x-c) = (x+c)
    Hence (x+c) div y gives remainder 0
    110010000 + 100 should give remainder 0.

  3. Transmit 110010000 + 100
    To be precise, transmit: T(x) = x3M(x) + C(x)
    = 110010100

  4. Receiver end: Receive T(x). Divide by G(x), should have remainder 0.

Note if G(x) has order n - highest power is xn,
then G(x) will cover (n+1) bits
and the remainder will cover n bits.
i.e. Add n bits to message.




Example


Another example of calculating CRC.
3rd line should read 11010110110000
Transmit: 11010110111110
Here G(x) = x4+x+1 which is prime.


Errors

An error is the same as adding some E(x) to T(x)
e.g. add 1010011000001110000
will flip the bits at the locations where "1" is in the error bitstring.
Instead of T(x) arriving, T(x)+E(x) arrives.

In general, each 1 bit in E(x) corresponds to a bit that has been flipped in the message.
If there are k 1 bits in E(x), k single-bit errors have occurred.
A burst error looks like 1....1


Detecting errors

Far end receives T(x)+E(x)
T(x) is multiple of G(x) (remainder zero)
Hence remainder when you divide (T(x)+E(x)) by G(x)
= remainder when you divide E(x) by G(x)

e.g. remainder when divide (1000+n) by 10
= remainder when you divide n by 10

If remainder when you divide E(x) by G(x) is zero, the error will not be detected.


In general, if you are unlucky enough that E(x) is a multiple of G(x), the error will not be detected.
Otherwise, it will. All other error patterns will be caught.


1 bit error

A 1 bit error is the same as adding E(x) = xk to T(x)
e.g. add 0000001000000000000
will flip the bit at that location only.

Is this detected?
The remainder when you divide E(x) by G(x) is never zero with our prime G(x) = x3 + x2 + 1
because E(x) = xk has no prime factors other than 1 and x.
Hence error detected.

In general, if G(x) is not equal to xi for any i (including 0)
then all 1 bit errors will be detected.


2 adjacent bit errors

E(x) = xk + xk+1
= xk (x+1)
Prime factors x,(x+1)
Not divisible by our prime G(x) = x3 + x2 + 1

In general, if G(x) is not equal to xi for any i (including 0)
or xi(x+1) for any i (including 0)
then all 2 adjacent bit errors detected.



Any 2 bit error

E(x) = xi + xj where i > j (to its left)
= xj (xi-j + 1)

Detected if (xk+1) cannot be divided by G(x) for any k up to frame length.

For example, it is true (though no proof provided here) that G(x) = x15+x14+1 will not divide into any (xk+1) for k < 32768
Hence can add 15 bits to each block of 32 k bits and can detect any 1-bit or 2-bit error.
This G(x) represents 1100000000000001. This is prime.

If G(x) will not divide into any (xk+1) for k up to the frame length, then all 2 bit errors will be detected.



Odd no. of errors

First note that (x+1) multiplied by any polynomial can't produce a polynomial with an odd number of terms:

So if there are an odd no. of errors, E(x) contains an odd no. of terms.
E(x) can't be divided by (x+1)
If we make G(x) not prime but a multiple of (x+1), then E(x) can't be divided by G(x).
Can detect all odd no. of errors.

e.g. CRC-8 = x8+x2+x+1 (=100000111) which is not prime.
See its factors.
It equals (x+1) (x7+x6+x5+x4+x3+x2+1)

If G(x) is a multiple of (x+1) then all odd no. of errors are detected.



Burst of length k

[good bits][burst start]....[burst end][good bits]
... [burst lhs at xi+k-1] .... [burst rhs at xi] ....
E(x) = xi+k-1 + ... + xi
= xi ( xk-1 + ... + 1 )
If G(x) contains a +1 term, it will not have xi as a factor. If also G(x) is of order k or greater, then:
( xk-1 + ... + 1 ) / G(x) is a fraction, and xi cannot cancel out, so
xi ( xk-1 + ... + 1 ) / G(x) can't give remainder 0.

If G(x) contains a +1 term and has order n (highest power is xn) it detects all burst errors of up to and including length n.


Burst of length k+1

Where G(x) is order k.
E(x) = xi ( xk + ... + 1 )
( xk + ... + 1 ) is only divisible by G(x) if they are equal.
i.e. The burst pattern of k+1 bits = the G(x) pattern of k+1 bits.
By definition, burst starts and ends with 1, so whether it matches depends on the (k+1)-2 = k-1 intermediate bits.
This matches G(x) by chance with probability (1/2)k-1

If G(x) contains a +1 term and has order n, the chance of it failing to detect a burst of length n+1 is (1/2)n-1



Some CRC polynomials that are actually used

Some CRC polynomials


Hardware

These calculations look complex but can actually all be carried out with very simple operations that can be embedded in hardware.

Recall Data Link layer often embedded in network hardware.




Links



Feeds      w2mind.org

On Internet since 1987.