Detecting errors

CRC: detecting bursts of errors

A more robust detector

On a real channel, errors often come in bursts: several consecutive bits damaged at once (a scratch on a disk, a brief interference). The parity bit is very bad at this. The CRC (Cyclic Redundancy Check) is a much more powerful detector, used everywhere: Ethernet, ZIP, hard drives.

The idea: a binary division

The CRC treats the data block as a large binary number and divides it by an agreed fixed number, the generator polynomial. The remainder of this division is the CRC, appended to the end of the message. On reception, the division is redone: if the remainder is not zero, an error has occurred.

Computation with a shift register (binary division, XOR):

data    ->  [   shift register    ]  -> for each incoming bit:
              b0  b1  b2  b3            (shift left, then XOR with the
               ^                         generator polynomial if the outgoing bit is 1)
               |__ XOR feedback

after all bits have been fed in, the register contents = the CRC
(on reception, the division is replayed: nonzero remainder -> error detected)

Why it detects bursts so well

Thanks to its algebraic properties, a well-chosen CRC detects all error bursts shorter than its length, and the vast majority of longer bursts. A 32-bit CRC lets an undetected error through with a probability of about 1 in 4 billion: negligible in practice.

Detecting, not correcting

Like the parity bit, the CRC detects without correcting: when an error is spotted, the protocol simply asks for the block to be retransmitted. This is the right choice when retransmission is easy (a network), less so when it is impossible (a signal from a space probe, where correcting on the spot is preferred).

Classic pitfall