Cyclic redundancy check (CRC) step by step

A cyclic redundancy check (CRC) treats the bits of a frame as the coefficients of a polynomial and divides it by a fixed generator polynomial, using arithmetic modulo 2, in which adding and subtracting are both XOR. The remainder of that division, r bits long for a generator of degree r, travels after the data. The receiver divides what it got by the same generator, and a remainder of zero means the frame is accepted. Ethernet, Wi-Fi, PPP, PNG images and gzip files all carry CRCs, for two reasons: the division needs nothing but shifts and XORs, which hardware does as fast as the bits arrive, and a well-chosen generator catches whole classes of errors, such as every burst of up to r damaged bits, without exception. This lesson does the division by hand and in code, proves those guarantees by trying every error pattern, and builds CRC-32 from scratch until it matches Python’s zlib.crc32.

Bits as a polynomial, division as XOR

Read the message 1001110101 as a polynomial whose coefficients are its bits, highest power first. Its ten bits stand for the powers from x⁹ down to x⁰ = 1, and the 1s pick out the terms:

The generator 1011 is x³ + x + 1, of degree r = 3. In arithmetic modulo 2 there are no carries and no borrows: 1 + 1 is 0, so adding and subtracting are the same operation, XOR. Long division then becomes simple: wherever the leading bit of what is left is 1, XOR the generator in under it; wherever it is 0, move on.

The sender appends r zeros to the message, which multiplies it by $x^r$ and leaves room for r bits at the end, then divides. The r-bit remainder is the CRC, and it replaces the zeros:

Long division, step by step

The program prints every XOR of the division, with the generator lined up under the bit where it applies:

"""CRC by long division modulo 2: message 1001110101, generator 1011 (x^3 + x + 1), every XOR step printed."""


def mod2_divide(dividend, generator, trace=False):
    """Long division with XOR instead of subtraction; returns the remainder (len(generator) - 1 bits)."""
    bits = list(dividend)
    if trace:
        print(f"dividend {dividend}")
    for i in range(len(bits) - len(generator) + 1):
        if bits[i] == "1":  # the leading bit is 1: XOR the generator in at this position
            for j, g in enumerate(generator):
                bits[i + j] = "0" if bits[i + j] == g else "1"
            if trace:
                print(f"{'XOR ' + generator:>{9 + i + len(generator)}}  at bit {i}")
                print(f"         {''.join(bits)}")
    return "".join(bits[-(len(generator) - 1) :])


def crc_remainder(message, generator, trace=False):
    """The CRC: append len(generator) - 1 zeros, then divide."""
    return mod2_divide(message + "0" * (len(generator) - 1), generator, trace)


message, generator = "1001110101", "1011"
crc = crc_remainder(message, generator, trace=True)
print(f"remainder {crc}: the sender transmits {message} {crc}")

received = message + crc
print(f"\nthe receiver divides {received} by {generator}: remainder {mod2_divide(received, generator)}")
damaged = received[:4] + ("0" if received[4] == "1" else "1") + received[5:]
print(f"with bit 4 damaged, {damaged}: remainder {mod2_divide(damaged, generator)}")

dividend 1001110101000
     XOR 1011  at bit 0
         0010110101000
       XOR 1011  at bit 2
         0000000101000
            XOR 1011  at bit 7
         0000000000100
remainder 100: the sender transmits 1001110101 100

the receiver divides 1001110101100 by 1011: remainder 000
with bit 4 damaged, 1001010101100: remainder 010

Three XORs were needed, at bits 0, 2 and 7 (counting from 0 at the left). At every other position the leading bit was already 0, so the generator was skipped, exactly where ordinary long division would write a 0 in the quotient. The quotient itself is never used; only the remainder, 100, matters. The receiver divided the 13 bits it got and found 000. With a single bit damaged, the remainder came out as 010, and the frame would be dropped.

Two slips are easy to make by hand: appending as many zeros as the generator has bits (4 here) instead of its degree (3), and dropping the leading zeros of the remainder. The remainder always has exactly r bits: 011 is not 11.

Why a damaged frame leaves a remainder

Write M(x) for the message, G(x) for the generator and R(x) for the remainder of $M(x)\,x^r$ divided by G(x). The sender transmits

Dividing T(x) by G(x) leaves R(x) from the first term and R(x) from the second, and R(x) + R(x) = 0 modulo 2, so T(x) is an exact multiple of G(x). If noise flips some bits, the receiver gets T(x) + E(x), where E(x) has a 1 at every flipped position. Since T(x) leaves no remainder, the receiver’s remainder is the remainder of E(x) alone. That gives the one rule behind every guarantee: a CRC misses an error exactly when G(x) divides the error pattern E(x). W. W. Peterson and D. T. Brown worked out what this means for different generators in their 1961 paper on cyclic codes, and the guarantees below follow from it.

What a generator always catches

Each guarantee is a statement about which polynomials G(x) cannot divide:

• Every single-bit error, if G(x) has at least two terms. A single error is $E(x) = x^i$, and a generator such as x³ + x + 1, with a constant term, divides no power of x.
• Every burst of length r or less. A burst is a run of damage whose first and last bits are both flipped; it is $x^i$ times a polynomial of degree below r with a constant term, which G(x), of degree r, cannot divide. A burst of length r + 1 slips through only if it is exactly the generator, a fraction $2^{-(r-1)}$ of such bursts, and longer bursts slip through at a rate of $2^{-r}$ (RFC 3385 gives these figures).
• Every odd number of flipped bits, if x + 1 is a factor of G(x). Such a G(x) has an even number of terms and evaluates to 0 at x = 1, while an error with an odd number of terms evaluates to 1, so it can never be a multiple.
• Every two-bit error, as long as the codeword is no longer than the generator’s period, the smallest k for which G(x) divides $x^k + 1$: two flips k bits apart make $E(x) = x^i\,(x^k + 1)$. For 1011 the period is 7, so in a longer codeword two flips 7, 14 or any multiple of 7 bits apart are missed.

The program checks each claim on every error pattern of a 20-bit codeword:

"""What a CRC catches, measured on every error pattern of a 20-bit codeword (message and CRC together)."""
from itertools import combinations

N = 20  # bits in the codeword


def remainder(value, generator):
    """Polynomial division modulo 2 on integers (bit k is the coefficient of x^k)."""
    while value.bit_length() >= generator.bit_length():
        value ^= generator << (value.bit_length() - generator.bit_length())
    return value


def missed(errors, generator):
    """How many of the error patterns leave a remainder of zero, so the receiver accepts the damaged frame."""
    return sum(remainder(e, generator) == 0 for e in errors)


def with_weight(w):
    """Every pattern of exactly w flipped bits."""
    return [sum(1 << p for p in flips) for flips in combinations(range(N), w)]


def bursts(b):
    """Every burst of length b: the first and last flipped bits are b - 1 apart; the bits between are anything."""
    out = []
    for start in range(N - b + 1):
        if b == 1:
            out.append(1 << start)
            continue
        for middle in range(2 ** (b - 2)):
            out.append(((1 << (b - 1)) | (middle << 1) | 1) << start)
    return out


G3 = 0b1011  # x^3 + x + 1: r = 3 check bits
print("generator x^3 + x + 1 (r = 3), bursts:")
for b in range(1, 8):
    errs = bursts(b)
    m = missed(errs, G3)
    print(f"  length {b}: {len(errs):4} patterns, {m:3} missed ({m / len(errs):.3f})")

two = with_weight(2)
gaps = sorted({(e.bit_length() - 1) - (e & -e).bit_length() + 1 for e in two if remainder(e, G3) == 0})
print(f"two flipped bits anywhere: {missed(two, G3)} of {len(two)} missed, all with the bits {gaps} apart")

G4 = 0b11101  # (x + 1)(x^3 + x + 1) = x^4 + x^3 + x^2 + 1: r = 4
odd = [e for w in (1, 3, 5) for e in with_weight(w)]
print(f"\nodd numbers of flipped bits (1, 3 or 5): {len(odd):,} patterns")
print(f"  missed by x^3 + x + 1: {missed(odd, G3)}")
print(f"  missed by (x + 1)(x^3 + x + 1): {missed(odd, G4)}")

generator x^3 + x + 1 (r = 3), bursts:
  length 1:   20 patterns,   0 missed (0.000)
  length 2:   19 patterns,   0 missed (0.000)
  length 3:   36 patterns,   0 missed (0.000)
  length 4:   68 patterns,  17 missed (0.250)
  length 5:  128 patterns,  16 missed (0.125)
  length 6:  240 patterns,  30 missed (0.125)
  length 7:  448 patterns,  56 missed (0.125)
two flipped bits anywhere: 19 of 190 missed, all with the bits [7, 14] apart

odd numbers of flipped bits (1, 3 or 5): 16,664 patterns
  missed by x^3 + x + 1: 2034
  missed by (x + 1)(x^3 + x + 1): 0

The run matches the theory to the last pattern. With r = 3, bursts of length 1, 2 and 3 were all caught; bursts of length 4 got through at 17 of 68, a quarter, which is $2^{-(3-1)}$; bursts of length 5 to 7 got through at exactly an eighth, $2^{-3}$. Two flipped bits were missed only when they were 7 or 14 positions apart. And 1011 missed 2,034 of the 16,664 patterns with an odd number of flips, while (x + 1)(x³ + x + 1) = x⁴ + x³ + x² + 1, which has x + 1 as a factor, missed none of them.

Real generators are chosen with these rules in mind. PPP’s default 16-bit check uses x¹⁶ + x¹² + x⁵ + 1, whose four terms make x + 1 a factor, so it catches every odd number of errors. CRC-32 has 15 terms, so it gives no blanket guarantee for odd errors; instead it catches every burst of up to 32 bits, and RFC 3385, summarising measurements of the Ethernet generator, reports a minimum distance of 4 for frames of 4,096 to 12,144 bits and 5 for frames of 512 to 2,048 bits, so every error of up to three bits in a full-size Ethernet frame is caught.

CRC-32 as Ethernet computes it

A CRC that a standard defines adds three details to the plain division:

• A starting value. The 32-bit register starts as 0xFFFFFFFF instead of 0. Without it, extra zero bytes at the start of a frame would not change the CRC at all.
• Reflection. Ethernet sends the bits of each byte least significant first, so CRC-32 feeds each byte into the division in that order. Software then shifts right instead of left and uses the generator with its bits reversed: 0x04C11DB7 becomes 0xEDB88320.
• A final XOR. The remainder is complemented, XORed with 0xFFFFFFFF, before it is sent.

Together these parameters define the CRC that catalogues call CRC-32/ISO-HDLC, the one that Ethernet’s frame check sequence, PPP’s 32-bit FCS, PNG images and gzip files use. Its check value, the CRC of the nine ASCII bytes 123456789, is 0xCBF43926: the quickest test of any implementation.

"""CRC-32 bit by bit, from the generator polynomial, checked against zlib.crc32 and the standard check value."""
import random
import zlib

# The terms of the 32-bit generator (RFC 1662 appendix C.3; RFC 3385 lists the same one for IEEE 802.3).
TERMS = [32, 26, 23, 22, 16, 12, 11, 10, 8, 7, 5, 4, 2, 1, 0]
POLY = sum(1 << t for t in TERMS if t < 32)  # x^32 is implied
REFLECTED = int(f"{POLY:032b}"[::-1], 2)  # the same bits in reverse order, for least-significant-bit-first data
print(f"generator 0x{POLY:08X}, reflected 0x{REFLECTED:08X}, {len(TERMS)} terms")


def crc32_bitwise(data):
    """Init 0xFFFFFFFF, every byte fed in least significant bit first, final XOR 0xFFFFFFFF."""
    crc = 0xFFFFFFFF
    for byte in data:
        crc ^= byte
        for _ in range(8):
            crc = (crc >> 1) ^ REFLECTED if crc & 1 else crc >> 1
    return crc ^ 0xFFFFFFFF


check = b"123456789"
print(f"check value: bitwise 0x{crc32_bitwise(check):08X}, zlib.crc32 0x{zlib.crc32(check):08X}")

rng = random.Random(3385)
messages = [rng.randbytes(rng.randrange(0, 1519)) for _ in range(300)]
same = sum(crc32_bitwise(m) == zlib.crc32(m) for m in messages)
print(f"{same} of {len(messages)} random messages of 0 to 1,518 bytes agree")

# A frame carries its CRC least significant byte first (RFC 1662). Run the CRC over frame and CRC together:
residues = {zlib.crc32(m + zlib.crc32(m).to_bytes(4, "little")) for m in messages}
print("CRC over message plus its CRC:", ", ".join(f"0x{r:08X}" for r in sorted(residues)))
print(f"without the final XOR: 0x{residues.pop() ^ 0xFFFFFFFF:08X}")

generator 0x04C11DB7, reflected 0xEDB88320, 15 terms
check value: bitwise 0xCBF43926, zlib.crc32 0xCBF43926
300 of 300 random messages of 0 to 1,518 bytes agree
CRC over message plus its CRC: 0x2144DF1C
without the final XOR: 0xDEBB20E3

The 15 terms of the generator, the list that RFC 1662 prints and RFC 3385 gives for IEEE 802.3, become 0x04C11DB7, and reversed 0xEDB88320. The bit-by-bit version gives the check value 0xCBF43926 and agrees with zlib.crc32 on all 300 random messages of 0 to 1,518 bytes, so Python’s standard library computes exactly this CRC.

The last two lines show what a receiver really compares. Because of the final XOR, the CRC computed over a frame together with its own CRC (sent least significant byte first, as PPP and Ethernet send it) is not zero but a constant, the residue: 0x2144DF1C for every one of the 300 messages, or 0xDEBB20E3 without the final XOR, the “good final FCS value” that RFC 1662’s code tests for. A receiver can check a frame by running the CRC over everything it received, FCS included, and comparing the result with that constant, as RFC 1662’s code does; a network card then normally strips the four FCS bytes before software sees the frame.

Software usually processes a byte at a time with a table of 256 precomputed values (RFC 1662’s appendix gives one), which replaces eight steps of the bit loop above with one lookup; network cards compute the CRC in hardware as the bits arrive.

Interview questions

Why does the sender append r zero bits before dividing by the generator? Appending r zeros multiplies the message by $x^r$, which shifts it left and leaves r empty places at the end. The remainder of that division, which has at most r bits, then fills those places: adding the remainder (XOR) to the shifted message makes the whole codeword an exact multiple of the generator, without touching a single message bit. The receiver checks precisely that: a codeword that leaves a zero remainder is accepted.

Key takeaways

• A CRC is the remainder of the message, with r zeros appended, divided by a generator of degree r, using XOR in place of subtraction; the receiver divides everything it got and expects zero.
• A CRC misses an error exactly when the generator divides the error pattern, which is what all its guarantees rest on.
• A generator of degree r with a constant term catches every single-bit error and every burst of up to r bits; longer bursts slip through at about $2^{-r}$.
• An x + 1 factor catches every odd number of errors; CRC-32’s generator does not have one, but it has a minimum distance of at least 4 on full-size Ethernet frames.
• CRC-32 starts from 0xFFFFFFFF, works least significant bit first with 0xEDB88320, ends with a final XOR, and has the check value 0xCBF43926 for 123456789; zlib.crc32 computes it.
• A CRC catches accidental damage only: use a keyed MAC to detect tampering.