CRC
Not a probability. Every burst up to the degree of the generator is caught, all of them, and the page tries them rather than telling you.
New to checksums? Start here
The trick is to stop reading the message as a number and read it as a polynomial: each bit is a coefficient, so a byte becomes a polynomial whose terms are the bits that are set. That sounds like a detour and it is the whole idea, because polynomials can be divided, and division leaves a remainder.
So you divide the message by a polynomial both ends agreed on and send the remainder along with it. The receiver divides the same way and expects the same remainder. The arithmetic is done in a field where adding is exclusive or, which means no carries, which means the division is a few lines of shifting.
Bits come back wrong
A bit written to a disc, sent down a wire or held in memory sometimes comes back as the other one. A scratch, a cosmic ray, a bad connector. You cannot prevent it and you cannot ask the sender, because the sender is a scratched disc or a satellite that has already moved on.
So you send more than the message. The extra part is chosen so that a corrupted message is not a valid one, which is how a machine can notice; and if there is enough of it, chosen so that only one original could have produced what arrived, which is how a machine can repair. The machines here differ in how much extra, and in what they promise back for it.
The machine for this idea on its own is Hamming, if you would rather press it than read about it.
A word, a generator, and a burst
1 The message, as the coefficients of a polynomial
Twelve bits. Not a number to this machine: the coefficients of a polynomial of degree eleven, where bit k is the coefficient of xk and the only values a coefficient can take are 0 and 1.
2 Divide by the generator, in arithmetic with no carries
The generator is 10011, which is x^4 + x + 1. Its lowest bit is 1, so x is not a factor of it, and that is the hinge the whole guarantee turns on rather than a detail: a generator divisible by x could not catch a burst that had simply been shifted along.
Long division, with XOR where subtraction would go, because 1 + 1 = 0 and nothing carries. That is the entire operation, and it is why this fits in hardware on the frame check sequence on an Ethernet frame.
3 The remainder rides along as the check
Four check bits, marked c, follow the twelve message bits, marked m. A receiver does not compare anything against a stored copy. It divides the whole word and asks whether anything is left over.
message 101000111100check 0100burst length 3remainder 1111
4 Corrupt a run of bits and see which lengths cannot hide
A burst 3 long, and the remainder came out 1111 rather than 0000, so it is caught. At this length it could not have been anything else: every burst of 4 or fewer is detected, and the page tried all 4,773 of them when it loaded.
Every burst, by length
Counted when the page loaded, not sampled: every burst of that length at every position it fits, over a spread of messages.
Checked when this page loaded, by trying them rather than trusting the proof: 4,773 bursts of length 4 or less, at every position, over a spread of messages, and 0 escaped. One bit past the theorem, at length 5, 12.50% escaped, against the one in 8 the arithmetic predicts. Longer than that, 6.25%, against one in 16.
Why the guarantee has an edge rather than a slope
Most error checks are probabilistic and are described that way, a check digit catching most transpositions and a hash catching almost everything. A CRC is not like that at one end. Below a certain length, nothing gets through at all, and the reason is short enough to hold in your head.
A burst of length b is an error polynomial E(x) = xi · E1(x), where the xi is just how far along the word the burst sits and E1 has degree b − 1. The check misses an error exactly when the generator divides E. The generator has a nonzero constant term, so it cannot divide xi, which leaves E1. And if b is no larger than the degree, E1 is smaller than the generator, so it cannot be divided by it either. There is nowhere for the error to hide.
And the edge is genuinely sharp
One bit past the theorem the guarantee does not soften, it stops. At length degree + 1 exactly one burst in 2degree−1 escapes, and beyond that exactly one in 2degree. With the degree-four generator on this page that is 12.5% at length five and 6.25% at every length after, and those figures are counted above rather than quoted: the page exhausts every burst when it loads and prints what it found.
This is the same shape as Hamming, one machine earlier on the chronology. Both give a guarantee that is exact inside its range and a defined failure just outside it, and both are small enough that the boundary can be shown rather than described. What differs is what they buy: Hamming spends three bits of seven to correct a single error and name where it was; a CRC spends four bits of sixteen and corrects nothing at all, in exchange for a promise about whole runs of damage.
Which is the right trade depends on what breaks. A scratch, a burst of line noise, a dropout: those damage runs, not scattered single bits, which is why a compact disc scatters the data before writing it and why the check on an Ethernet frame is a CRC and not a Hamming code.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every burst of length 4 or less is detected, all 4,773 of them | yes | not a probability and not a sample: every burst at every position over a spread of messages |
| at length 5 exactly one burst in 8 escapes, which is 12.50 per cent | yes | 516 of 4,128 is 12.50 per cent |
| and beyond it exactly one in 16 at every length, not on average | yes | 7 lengths checked, every one at 6.25 per cent |
| the guarantee stops rather than fading: nought, then 12.50, then 6.25 per cent | yes | a fade would show intermediate rates between them and there are none |
| the generator has a nonzero constant term, which is what the proof turns on | yes | without it the generator could divide x^i and a burst could hide in the shift alone |
| a codeword divides exactly, so the receiver runs the same division rather than a different check | yes | 5 messages, every remainder nought |
What is real here, and what is not
Degree four is a teaching size, not a real one
Four check bits are chosen because every burst on a sixteen-bit word can actually be tried, which is the only reason the numbers above are counts rather than estimates. Real protocols use far wider generators: CRC-32 on an Ethernet frame gives thirty-two check bits, so its guarantee covers bursts up to thirty-two and only a tiny fraction of longer bursts escape. The mechanism is identical and the arithmetic on this page is the arithmetic there.
A CRC detects. It does not correct, and it is not a hash
There is no way to recover the message from a failed check; the receiver knows only that the word it got is not a valid codeword. What happens next belongs to the surrounding system rather than to the CRC: discard, retry, report, or recover from some other redundancy. The choice is not not to the CRC. It is also not a security measure. A CRC is trivially forgeable: anyone can alter a message and recompute the check to match, which is why protocols that need to resist tampering carry a signature as well.
The counts are over a spread of messages, not every message
The page walks the 4,096 possible messages in steps of 97, so about forty-three of them, at every burst length and every position. That is a deliberate limit and it is safe for a reason: what gets divided is the error polynomial, not the message, so the burst behaviour does not depend on which message was sent. The zero at short lengths is exact for every message tried, and the theorem above is what carries it to the rest.
Nothing here is a channel
Bursts are placed with a slider. There is no noise model, no probability that a burst of a given length arrives, and no retransmission. What the page can say is which errors this check can and cannot see; what fraction of real damage looks like a short burst is a question about a wire, not about a polynomial.
The 1961 paper was derived before it was read, and now it has been read
The burst theorem and its proof were worked out independently for this page and then checked by exhausting every burst, because Peterson and Brown's paper is behind IEEE's paywall and eight routes to it refused: the publisher, two university mirrors, a citation index that timed out, and a search engine that offered a PDF under the paper's exact title which turned out to be a student's lecture slides. The ninth worked. The whole January 1961 issue of the Proceedings of the IRE is a scan on worldradiohistory.com, and the paper runs from page 228 to page 235 of it.
Nothing from it is quoted here, and that is a property of the scan rather than a choice. The issue is set in two columns and the OCR reads straight across both, so Theorem 5 comes out with the first half of its own sentence spliced into the middle of a different proof. Every fragment is a mixture of two paragraphs that were never adjacent. So the theorems are stated below in this page's words, and the page you would check them against is 228 of the linked scan.
Reading it turned the independent derivation into a check. Their Theorem 5 is the guarantee at the top of this page: a cyclic code whose generator has degree n − k detects every burst of length n − k or less. Their proof factors the error exactly the way the argument above does, as E(X) = XiE1(X) with E1 of degree b − 1, and rules out the generator dividing Xi. Their Theorem 6 is the far side of the edge: past the guarantee the undetected fraction is one in 2n−k−1 at length n − k + 1 and one in 2n−k at every length beyond. For the degree-four generator here that is one in eight and then one in sixteen, which is the 12.5% and 6.25% counted above. Nothing on this page changed when the paper arrived, which is the only outcome that would say the derivation was worth doing.