Polynomial Codes For Error Detection - Dr. Mark Humphrys

• W.W. Peterson and D.T. Brown, "Cyclic codes for error detection", Proceedings of the IRE, Volume 49, pages 228-235, Jan 1961.
• W.W. Peterson, Error Correcting Codes, MIT Press 1961.

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

011 + (or minus) 110 --- 101

x + 1 + x2 + x ------------- x2 + 2x + 1 = x2 + 1

2 xk = 0

• Digital Communications course by Richard Tervo
  • Intro to polynomial codes
  • CGI script for polynomial codes

• CRC Error Detection Algorithms

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

• Digital Communications course by Richard Tervo
  • polynomial factors
  • polynomial primes
    • excludes 5, 17, etc.,
    • includes 25, 55, etc.
  • integer primes
  • CGI script for polynomial factoring

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.

• Digital Communications course by Richard Tervo
  • Error detection with CRC

• Some CRC polynomials that are actually used
  • e.g. The 802.3 (Ethernet) polynomial adds 32 bits to the message.

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:

• e.g. (x+1) (x7+x6+x5) = x8+x7+x6 + x7+x6+x5 = x8+x5

• In general, (x+1) ( xp1+...+xpn ) = xp1+1+...+xpn+1 + xp1+...+xpn If all these powers are different - even no. of terms. If any pair pi = pj+1, these cancel out, still even no. of terms. Can't get 3 the same power (why not?)

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

• CRC-8: x8+x2+x+1
  • [Factors] = (x+1) (x7+x6+x5+x4+x3+x2+1)
  • Used in: 802.16 (along with error correction).

• CRC-CCITT: x16+x12+x5+1
  • [Factors] = (x+1) (x15+x14+x13+x12+x4+x3+x2+x+1)
  • Used in: HDLC, SDLC, PPP default

• IBM-CRC-16 (ANSI): x16+x15+x2+1
  • [Factors] = (x+1) (x15+x+1)

• 802.3: x32+x26+x23+x22 +x16+x12+x11+x10 +x8+x7+x5+x4+x2+x+1
  • [Factors] = Prime
  • Append 32 bits to the message.
  • Detects all bursts of length 32 or less.
  • Probability of not detecting burst of length 33 = (1/2)31 = 1 in 2 billion. And remember, won't get such a burst on every message. Burst itself very rare.
  • Used in: Ethernet, PPP option

Recall Data Link layer often embedded in network hardware.

• Digital Communications course by Richard Tervo
  • CGI script for polynomial hardware design

• To explore: On UNIX: man cksum