Cyclic Redundancy Code with example

Cyclic Redundancy Check (CRC) is an error detecting code. The sender treats the data bits as a binary polynomial, divides it (modulo-2, i.e. XOR) by an agreed generator polynomial G(x), and appends the remainder (the CRC) to the data. The receiver divides the whole received frame by G(x): a zero remainder means no error (probably), a non-zero remainder means error.

Procedure

1. Choose generator of r+1 bits (degree r).
2. Append r zeros to the data.
3. Divide (XOR division) by the generator; the r-bit remainder is the CRC.
4. Send data + CRC (data followed by the CRC).

Example

Data = 1101011011, generator = 10011 (x^4 + x + 1), r = 4. Message after appending 4 zeros: 11010110110000.

 11010110110000
 10011                    XOR
 -------------
 01001110110000
  10011                   XOR  (bring down, leading bit 1)
 -------------
 00000010110000
       10011
 -------------
 00000000101000
         10011
 -------------
 00000000001110   remainder

CRC = 1110. Transmitted frame: 11010110111110.

Check at the receiver

Divide 11010110111110 by 10011: the remainder is 0000, so the frame is accepted. If a bit changes (for example the third bit flips), the remainder is not zero and the error is detected.

Properties

Detects all single-bit and double-bit errors, all odd numbers of errors (if G has factor x+1), all burst errors shorter than r+1 bits, and most longer bursts. Implemented with shift registers and XOR gates. Common generators: CRC-16 (x^16 + x^15 + x^2 + 1), CRC-CCITT (x^16 + x^12 + x^5 + 1), CRC-32 (Ethernet).