Cyclic redundancy check

The formula

R(x) = ( M(x) · xⁿ ) mod G(x) Treat the message bits as coefficients of a polynomial M(x), shift it left by n bits, divide by the degree-n generator G(x), and keep the n-bit remainder. That remainder is the CRC.

T(x) = M(x) · xⁿ + R(x) Appending the remainder to the message makes the transmitted frame exactly divisible by G(x). The receiver divides what it got; a nonzero remainder means the frame took a hit.

E(x) mod G(x) ≠ 0 → error detected An error pattern E(x) slips through only if it happens to be divisible by the generator. Everything about choosing a good polynomial is about making that divisibility rare for the errors your channel actually produces.

All the arithmetic runs over GF(2) — coefficients are 0 or 1, and both addition and subtraction are XOR. No carries, no borrows. That is why the whole thing reduces to shifts and XOR gates and runs at line rate in cheap silicon.

A worked division, small enough to do on a napkin:

Message M = 11010011101100,  generator G = 1011  (x³ + x + 1, a 3-bit CRC)
Append three zeros:  11010011101100 000
XOR-divide by 1011:  remainder = 100
Transmit:            11010011101100 100
Receiver divides the whole 17 bits by 1011 → remainder 000 → frame accepted

Sanity numbers for checking an implementation, all computed against the ASCII string 123456789:

CRC-32 (poly 0x04C11DB7, reflected, init 0xFFFFFFFF, final XOR 0xFFFFFFFF): 0xCBF43926
CRC-16/CCITT-FALSE (poly 0x1021, init 0xFFFF): 0x29B1
CRC-16/MODBUS (poly 0x8005 reflected to 0xA001, init 0xFFFF): 0x4B37

If your code produces those three, you have the parameters right. If it doesn't, keep reading.

Where you meet it

Modbus RTU on the DAQ bench. Every frame between your PLC or power analyzer and the host ends in two CRC bytes, low byte first, computed with the reflected 0xA001 polynomial. When a new serial driver "almost works" — good frames interleaved with timeouts — swapped CRC byte order is the first thing to check.
Firmware load verification. Flight software and test-set firmware reviews record the CRC-32 of the released image in the build record. Load the box, read the image back, recompute, compare against the paper. A one-line procedure that has caught wrong-version loads at more than one CDR-adjacent meeting.
CAN bus on the vehicle or test stand. Every classic CAN frame carries a 15-bit CRC computed and checked in silicon. You never touch it — until the bus analyzer starts logging error frames and you learn that CRC errors on CAN usually mean termination or ground offset problems, not data problems.
Archives and telemetry decom. ZIP, gzip, and PNG all seal their payloads with the same CRC-32 Ethernet uses. A telemetry ground station flags frames whose CRC fails and hands you the gap report; the CRC is why you can trust the frames it kept.

How it works

The transmitter clocks message bits through an n-bit shift register with XOR taps at the generator's coefficients; whatever is in the register when the last bit leaves is the CRC. Software does the same thing eight bits at a time with a 256-entry lookup table. Either way the cost is trivial, which is why a CRC rides on practically every frame ever framed.

What an n-bit CRC guarantees, for any generator whose lowest term is 1 (a nonzero x⁰ coefficient — true of every standard polynomial) ^[1]:

Every burst error of n bits or shorter is caught. A burst starting at bit offset i is E(x) = xⁱ · B(x), and a degree-n generator with a +1 term cannot divide xⁱ · B(x) when B(x) spans fewer than n+1 bits. This is the property CRCs were built for — real channels fail in bursts, not in isolated bits.
Longer bursts slip through at a rate of about 2⁻ⁿ. For CRC-32 that is one undetected garbage frame in roughly 4.3 billion corrupted frames.
A generator with (x + 1) as a factor catches every odd number of bit errors — a parity bit built into the algebra.

What is not guaranteed is the Hamming distance — the minimum number of scattered bit errors that can sneak past — because it depends on frame length. Koopman's exhaustive search results show the standard Ethernet CRC-32 holds HD=6 out to 268 bits of data but only HD=4 out to 91,607 bits ^[6]. Same polynomial, same code, different protection depending on how long your frame is. If you are designing a new protocol instead of implementing an old one, pick the polynomial for your frame length; the legacy standards were not optimal even when they were chosen ^[5]^[6].

The gotcha that costs the most lab hours: the polynomial is only one of five parameters. A full CRC spec is polynomial, input bit-reflection, output bit-reflection, initial register value, and final XOR. CRC-32 as deployed reflects everything, starts the register at all-ones, and inverts the result. Two implementations can share a polynomial and agree on nothing. This is why the 123456789 check values above exist — compare against those before you compare against the device.

The all-ones initial value is not decoration. A register initialized to zero cannot see leading zero bytes — prepend as many 0x00 bytes as you like and the CRC is unchanged. Starting from 0xFFFF or 0xFFFFFFFF closes that hole.

A useful side effect of the algebra: run the CRC over the message plus its appended CRC bytes and you get a constant that depends only on the parameter set, not the data. For standard CRC-32 that residue is 0x2144DF1C (little-endian CRC bytes, after the final inversion — i.e. what a standard crc32() call returns over the whole frame; the raw register before the final XOR holds 0xDEBB20E3). Receiver firmware often checks against that constant instead of recomputing and comparing — one register compare per frame. It also makes a decent self-test: if a whole-frame pass through your routine doesn't land on the magic value, the implementation is wrong somewhere.

Hardware CRC peripherals deserve one more line of suspicion. Many microcontroller CRC units default to the right polynomial with the wrong reflection settings, so the silicon disagrees with the software library on every byte. Run the 123456789 check against the peripheral before wiring it into a protocol.

And the mistake that gets made in reviews: a CRC is not a security feature. The operation is linear over GF(2), so anyone who can flip message bits can flip CRC bits to match; forging a frame with a valid CRC takes algebra, not effort. CRCs defend against noise, not adversaries. If tampering is in your threat model, you want a cryptographic hash or a MAC. Same warning in the other direction: a CRC tells you a frame is bad, not which bit is bad and not how to fix it — detection only, no correction, and it does nothing about frames that never arrived.

History

The CRC has a birthday and a byline. In January 1961, W. Wesley Peterson and D. T. Brown published "Cyclic Codes for Error Detection" in the Proceedings of the IRE, laying out the polynomial-division framing and the burst-error guarantees engineers still quote ^[1]^[2]. Peterson had taken his doctorate at Michigan in 1954 and gone to IBM; the same year as the paper he published Error-Correcting Codes, the book generally counted as the start of algebraic coding theory ^[2]^[3]. He spent the rest of his career at the University of Hawaii, collected the Shannon Award in 1981, and in 1999 the Japan Prize — its citation names the coding theory behind reliable digital communication, broadcasting, and storage ^[2]^[3]. Not many mathematical objects that run on every Ethernet port trace to one clearly identified paper.

The specific 32-bit polynomial in your NIC has a defense pedigree. In 1975, Kenneth Brayer at MITRE and Joseph Hammond, James Brown, and Shyan-Shiang Liu at Georgia Tech, working for Rome Laboratory and the Air Force's AUTODIN-II effort, evaluated degree-32 polynomials against recorded military channel error patterns and selected 0x04C11DB7 for its detection performance ^[1]^[4]. Ethernet adopted it, IEEE 802.3 standardized it, and ZIP, gzip, and PNG carried it into every file system on earth.

The story didn't stop there. In 1993 Guy Castagnoli and colleagues ran a hardware-assisted search of the 32-bit design space and produced better polynomials, one of which — CRC-32C, 0x1EDC6F41 — was adopted by iSCSI and later baked into x86 processors as a dedicated instruction ^[1]^[5]. In 2002 Philip Koopman at Carnegie Mellon completed the first exhaustive search of all 32-bit polynomials, confirming that several long-standardized choices leave error-detection performance on the table ^[5]^[6]. Sixty-plus years on, polynomial selection is still an open engineering trade, not a settled default.

Related tools

/tools/thermal-noise-floor — the noise floor that produces the bit errors your CRC exists to catch
/tools/snr-enob — link SNR sets the raw bit-error rate arriving ahead of the CRC check
/tools/link-budget — margin in the budget decides how often the CRC has work to do

Sources

Written by HE in our own words from the cited sources — engineering judgment included, your stamp still required. All entries →