CRC detection of burst errors

A burst error of length b is a run of corrupted bits where the first and last bits are in error (the bits in between may or may not be). A CRC with an r-bit remainder detects every burst of length ≤ r.

CRC-5 setup

Generator G(x) = x⁵ + x² + 1 → 100101 (degree 5, so 5 check bits). Data = 11010011101100 (14 bits).

Sender

Append 5 zeros: 1101001110110000000 and divide by 100101 (modulo-2). The remainder is 01110. Transmitted codeword = 1101001110110001110 (19 bits).

Receiver, no error

Dividing the codeword by 100101 gives remainder 00000, so no error is found.

Burst of 3 errors

Take a burst error of length 3: bits 5, 6 and 7 are inverted.

 sent     1101001110110001110
 error    0000111000000000000   (E(x), burst length 3)
 received 1101110110110001110

Dividing the received word by 100101 gives remainder 01111 ≠ 0, so the error is detected.

Why a burst of 3 is always detected

The received word is T(x) + E(x). T(x) is divisible by G(x), so the remainder equals E(x) mod G(x). A burst of length 3 has the form E(x) = xᵏ·B(x), where B(x) has degree 2 (less than 5). G(x) has a constant term 1, so it shares no factor with xᵏ. Therefore G(x) can divide E(x) only if it divides B(x), which is impossible because B(x) has a lower degree than G(x). So E(x) is never divisible by G(x) and the remainder is non-zero.

General rule for an r-bit CRC: all bursts of length ≤ r are detected; a burst of length r+1 is missed with probability 2^−(r−1); longer bursts are missed with probability 2^−r.

Answer: the 3-bit burst gives the non-zero remainder 01111, so it is detected.