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.

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 every Ethernet frame ever sent.

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.

      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 something is wrong and asks for it again. 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 read about, not read

      Peterson and Brown's paper is behind IEEE's paywall. The bibliographic details here are confirmed across citation databases, and the burst theorem and its proof were derived independently for this page and then checked by exhausting every burst, which is stronger evidence than a citation would have been. But the paper itself has not been opened, and a PDF that a search engine offered under its title turned out to be a student's lecture slides about it rather than the paper.

      Sources