Cyclic Redundancy Check (CRC)

The cyclic redundancy check is the error-detecting code used in the trailer of almost every link-layer frame: Ethernet's 32-bit frame check sequence (FCS) is a CRC, and so are the checks in Wi-Fi, HDLC and PPP. It treats the frame as a long binary polynomial, divides it by a fixed generator polynomial using arithmetic modulo 2, and sends the remainder. The receiver repeats the division over the whole received frame; a non-zero remainder means an error.

A CRC is preferred over parity and the Internet checksum because, for the same number of check bits, it catches far more error patterns, in particular all burst errors of length up to the number of check bits when the generator has a constant term, which is how errors on real links tend to look. It is also cheap in hardware: a shift register with a few XOR gates computes it at line rate.

Three tasks recur: compute the transmitted frame (do the division), decide whether a received frame is accepted, and decide which error patterns a given generator detects.

A bit string $b_{k-1} \ldots b_1 b_0$ is the polynomial $b_{k-1}x^{k-1} + \cdots + b_1 x + b_0$ with coefficients in $\{0, 1\}$. For example 1011 is $x^3 + x + 1$ and 10011 is $x^4 + x + 1$. The degree is the highest power with coefficient 1.

Degree versus length. A generator of degree $r$ has $r + 1$ bits and produces $r$ check bits. CRC-32 has a degree-32 generator (33 bits) and a 32-bit FCS.

At each step, if the leading bit of the current window is 1, XOR the generator into it (the quotient bit is 1); if it is 0, XOR zeros (the quotient bit is 0). Then move one position right. The last $r$ bits after the final step are the remainder. Only the remainder matters; the quotient is discarded.

Bit strings are indexed from the left starting at 1; XOR acts bit by bit.

For the software shown ($m$ message bits, degree $r\ge1$ generator), copying/appending and storage cost $\Theta(m+r)$. Best time is $\Theta(m+r)$; worst time is $O(mr+m+r)$ bit operations, with average requiring a bit distribution. A table-driven version can process a byte per step. Streaming hardware instead uses an $r$-bit shift register with feedback XORs, typically processing one input bit per clock; that is a different cost/storage model.

Why the frame divides evenly. Appending $r$ zeros is multiplication by $x^r$. Write $x^r M(x) = Q(x)G(x) + R(x)$ with $\deg R < r$. Then

because $R + R = 0$ modulo 2. So $G(x)$ divides every correct frame.

When an error is missed. The receiver divides $T(x) + E(x)$; since $G \mid T$, the remainder is that of $E(x)$ alone. An error is undetected exactly when $G(x)$ divides $E(x)$. Every undetected-error case follows from this.

Detection guarantees (for a generator of degree $r$):

Parity is the special case $G(x) = x + 1$. The remainder of $x M(x)$ divided by $x + 1$ is $M(1)$, the number of 1s in the message modulo 2: a one-bit CRC with generator 11 is an even parity bit.

Message 11010110, generator 1011 ($x^3 + x + 1$, $r = 3$). Append three zeros: 11010110000. XOR 1011 under the leading 1 at positions 1, 2, 3, 4, 6 and 8 (Figure 1); the windows starting at positions 5 and 7 begin with 0, so their quotient bits are 0. Quotient 11110101, remainder 111. Transmitted frame: 11010110111.

Message 101101, generator 10011 ($x^4 + x + 1$). Append four zeros: 1011010000. The division, with the five-bit window under each leading 1:

Positions 2, 4 and 6 begin with 0, so the quotient is 101010. The remainder is the last four bits, 1110, and the frame is 1011011110.

The receiver of Example 1 divides 11010110111 by 1011 and gets remainder 000: accepted. If bit 5 flips (received 11011110111), the remainder is non-zero: rejected. If the error pattern is 00000101100, which is $x^2 G(x)$, the received word 11010011011 leaves remainder 000 and the error is not detected: an error that is a multiple of the generator always escapes.

$G(x) = x^3 + x + 1$ has a constant term and degree 3, so it catches every burst of length 3 or less. It is not divisible by $x + 1$ (it has three terms, so $G(1) = 1$), so it does not catch every odd-weight error: the error pattern 1011 itself (weight 3) is missed. $G(x) = (x + 1)(x^3 + x + 1) = x^4 + x^3 + x^2 + 1$ (11101) does catch all odd-weight errors and all bursts up to length 4.

$G(x) = x^4 + x + 1$, so $r = 4$. A burst of length $b \ge 2$ has its first and last bits set, so there are $2^{b-2}$ patterns of each length.

Shifting a burst multiplies it by $x^i$, which does not change whether $G$ divides it, so these counts hold at every position in the frame. The undetected fractions are $1/8 = 2^{-(r-1)}$ for $b = r + 1 = 5$, and $1/16 = 2/32 = 2^{-r}$ for the longer bursts, as in the table of detection guarantees.

A two-bit error $x^i(x^j + 1)$ escapes exactly when $G$ divides $x^j + 1$. For this generator the smallest such $j$ is 15, so every two-bit error in a frame of at most 15 bits is caught, while two flipped bits exactly 15 positions apart escape. Because $G$ has three terms, $G(1) = 1$: $x + 1$ is not a factor, and the weight-3 error 10011 escapes.

CRC-32 uses the degree-32 generator with hexadecimal coefficients 04C11DB7 (top bit implicit). Real implementations also preset the register to all ones, process each byte least significant bit first, and complement the result, so the FCS is not the plain remainder of the textbook division. The standard check value is: the CRC-32 of the nine ASCII bytes "123456789" is CBF43926.

Common misconceptions.