CRC: Division That Catches Bursts

in reviewThis lesson is complete and being validated before release - details may still change.

Cyclic redundancy check

Loading interactive demo…

Two long divisions side by side. The sender's pane starts with the message and appended zeros, takes one row per message bit, and ends with the remainder; the receiver's pane starts with what arrived and ends with its own remainder, zero when the word is a multiple of the generator. Tap a received bit to start the burst there; the sliders set its length and the chips its shape and the code.Take the tour, or press and explore. Legend:

The panel beside the stage is the real CyclicRedundancyCheck class from the published library executing in your browser, with the current line highlighted.

The window: the position being divided and the degree places after it.
A window the divisor was XORed into, because its lead bit was 1.
The remainder, behind the message in the transmitted word.
A bit the burst flipped, and a nonzero remainder at the receiver.
A zero remainder at the receiver: the word passes.
Rows the run has not reached yet, ghosted.

remainder is the sender's, check the receiver's, verdict whether a corrupted word was detected or missed, guaranteed the longest burst the generator always catches.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Bits as a polynomial. Read the message $m$ as the coefficients of a polynomial over $\mathrm{GF}(2)$ , highest power first, so the twelve bits $110101101011$ are

m(x) = x^{11} + x^{10} + x^8 + x^6 + x^5 + x^3 + x + 1 .

In $\mathrm{GF}(2)$ the only digits are $0$ and $1$ and $1 + 1 = 0$ : adding two polynomials is XOR of their coefficient strings, and subtracting is the same thing. There are no carries, which is why the long division on the stage is nothing but shifts and XORs.

The division. A generator $g(x)$ of degree $d$ is chosen in advance; the stage's CRC-4 uses $g(x) = x^4 + x + 1$ , the bits $10011$ . The sender forms $m(x)\,x^d$ , which appends $d$ zeros, and divides it by $g$ :

m(x)\,x^d = q(x)\,g(x) + r(x), \qquad \deg r < d .

Each step of the long division looks at one position: if its bit is $1$ , the divisor is XORed in beneath it, clearing that bit; if $0$ , the window just slides on. After one step per message bit, the last $d$ places hold the remainder $r$ . The transmitted word is

t(x) = m(x)\,x^d + r(x) = q(x)\,g(x),

a multiple of $g$ by construction (adding $r$ is subtracting it).

The check. The receiver gets $t(x) + e(x)$ , where $e$ is the error polynomial, a $1$ at every flipped position. It divides by $g$ ; since $t$ divides exactly, the remainder is the remainder of $e$ alone. The check passes if and only if $g$ divides $e$ . Nothing about $m$ matters, which is why the receiver's remainder can be read without knowing what was sent.

Why bursts are caught. A burst of length $L$ starting at position $s$ from the right is

e(x) = x^{s}\,b(x), \qquad \deg b = L - 1,\ b(0) = 1 .

Every useful generator has a constant term, $g(0) = 1$ , so $g$ does not divide $x^s$ , and $g$ divides $e$ only if $g$ divides $b$ . A polynomial of degree $L - 1 < d$ cannot be a multiple of a degree $d$ polynomial. So every burst of $L \le d$ bits is caught, whatever its shape and wherever it lands: the guaranteed readout.

Longer bursts. For $L = d + 1$ , $b$ has degree $d$ and is a multiple of $g$ only if $b = g$ : one shape, the multiple of g chip, out of the $2^{d-1}$ bursts of that length that start and end with a flip. For $L > d + 1$ the fraction is $2^{-d}$ . A random pattern of many flips is missed with probability $2^{-d}$ too, since the remainders of the $2^d$ residues are equally likely. CRC-32 misses about one corrupted frame in four billion, and catches every burst up to 32 bits outright.

What a CRC is not. The check is linear: $\mathrm{crc}(a + b) = \mathrm{crc}(a) + \mathrm{crc}(b)$ over $\mathrm{GF}(2)$ . Anyone can therefore choose flips whose remainder is zero, so a CRC guards against noise and never against an adversary; that is the hash functions lesson's job. And it detects without locating: the next step, Reed-Solomon, builds the same polynomial arithmetic into a code that can put the flipped symbols back.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

One divide for both ends. The sender and the receiver run the same method, told apart by a phase in the event; a second copy of the loop would give the trace tag two homes and the stage could highlight only one.
The generator is stored truncated, as the standard tables list it (0x3 for $x^4 + x + 1$ ), and the constructor rebuilds the full divisor by putting the leading $x^d$ back. It refuses an even generator: without a constant term the burst guarantee fails at the end of the word.
register is the window minus its lead bit: exactly what a hardware shift register holds after the step, so the trace shows the circuit's state without a second implementation.
A burst is a pattern XORed in, not bits set to 1, so a flip of a bit that was already $1$ clears it; the pattern must start and end with a flip so that length means what it says.
missed is corrupted && ok, computed from the words, not from the burst length, so the stage's verdict comes from what the receiver actually saw.

A parity bit notices one flip and misses two; a checksum that adds bytes misses a pair of flips that cancel. Wesley Peterson, working on magnetic storage, asked in 1961 what a check should look like when errors come in runs, as they do when a scratch crosses a track. His answer: treat the bits as a polynomial and keep the remainder after dividing by a chosen generator, since a run of flips is a polynomial too, and no run shorter than the generator can divide by it. It cost a shift register and a few XOR gates, and every disk, frame, and archive has carried one since.

1961W. Wesley Peterson and D. T. Brown - Publish 'Cyclic Codes for Error Detection' in the Proceedings of the IRE: polynomial division as a check, the burst guarantee, and the shift-register circuit that computes it.source
1975Hammond, Brown, and Liu - In a NASA-funded study choose the degree-32 generator that becomes CRC-32, after searching for the polynomial with the best error coverage at that length.source
1983IEEE 802.3 - Ethernet's frame check sequence is standardised as CRC-32: every frame on every local network ends in that remainder.source
2002Philip Koopman - Exhaustive searches over generators map, for each length, exactly how many flips every candidate CRC detects, replacing folklore polynomials with measured ones.source

Used today

Network frames - Ethernet, Wi-Fi, USB, Bluetooth, and CAN each end a frame with a CRC; a frame with a nonzero remainder is dropped and the higher layer retries.
Archives and images - Every zip and gzip entry carries a CRC-32 of its contents, and so does every chunk of a PNG, so a damaged byte is noticed before it is decoded.
Storage - Disk sectors, flash pages, and filesystem metadata are each checked with a CRC; the stronger correcting codes run beside it, not instead of it.
Hardware - The division is a shift register with a few XOR gates in the feedback path, which is why it was chosen for links long before software was fast enough.

code

burst atbit 3

burst length4 bits

pattern

remainder: 0100
check: 1100
verdict: detected
guaranteed: 4 bits

cyclic-redundancy-check.ts

import type { Tracer } from "../trace";/** A generator: its degree and the truncated polynomial (the leading x^degree left off), as the standard tables list them. */export interface CrcPreset {  degree: number;  generator: number;}/** CRC-4-ITU: x^4 + x + 1, divisor bits 10011. */export const CRC4_ITU: CrcPreset = { degree: 4, generator: 0x3 };/** CRC-8 (ATM header, I2C): x^8 + x^2 + x + 1, divisor bits 100000111. */export const CRC8: CrcPreset = { degree: 8, generator: 0x07 };export const MAX_CRC_DEGREE = 8;export const MAX_CRC_MESSAGE = 32;/** Which end is dividing: the sender computing the remainder, or the receiver checking it. */export type CrcPhase = "sender" | "receiver";/** A run of flipped bits: `length` bits from `start`, all ones unless a pattern (first and last bit 1) says otherwise. */export interface Burst {  start: number;  length: number;  pattern?: readonly number[];}export interface CrcResult {  degree: number;  /** The divisor bits, highest degree first: degree + 1 of them. */  divisor: number[];  message: number[];  /** The remainder of message times x^degree divided by the generator: degree bits. */  remainder: number[];  /** The message with the remainder appended. */  transmitted: number[];  burst: { start: number; length: number; pattern: number[] } | null;  received: number[];  /** The receiver's remainder over the whole received word: zero when nothing was seen. */  check: number[];  ok: boolean;  /** The received word differs from the transmitted one. */  corrupted: boolean;  /** Corrupted and the check caught it. */  detected: boolean;  /** Corrupted and the check passed anyway: the burst was a multiple of the generator. */  missed: boolean;  /** Every burst of at most this many bits is caught: the generator's degree. */  guaranteed: number;}/** * A cyclic redundancy check treats the message bits as a polynomial * over GF(2), where adding is XOR and there are no carries. The * sender multiplies by x^degree (appends that many zeros), divides by * the generator by long division, which is a shift and a conditional * XOR per message bit, and sends the remainder after the message. The * receiver divides the whole word the same way and expects zero. A * burst of flips is a polynomial e(x) = x^s * b(x) with b of degree * under the burst length; the generator has a constant term, so it * cannot divide x^s, and a burst no longer than the degree is never a * multiple of it: every such burst is caught. Longer bursts slip * through only when b(x) is itself a multiple of the generator, one * pattern in 2^(degree - 1). * * Time: O(n * degree) for an n-bit message. Space: O(n). */export class CyclicRedundancyCheck {  /** The generator's bits, highest degree first. */  readonly divisor: readonly number[];  constructor(    readonly degree = CRC4_ITU.degree,    readonly generator = CRC4_ITU.generator,    private readonly tracer?: Tracer,  ) {    if (!Number.isInteger(degree) || degree < 1 || degree > MAX_CRC_DEGREE) throw new RangeError(`degree must be 1 to ${MAX_CRC_DEGREE}, got ${degree}`);    if (!Number.isInteger(generator) || generator < 0 || generator >= 1 << degree) throw new RangeError(`generator must fit in ${degree} bits, got ${generator}`);    if ((generator & 1) === 0) throw new RangeError("generator needs a constant term, or a burst at the end of the word could slip through");    const full = (1 << degree) | generator;    this.divisor = Array.from({ length: degree + 1 }, (_, i) => (full >> (degree - i)) & 1);  }  /** The longest burst the generator always catches: its degree. */  guaranteedBurst(): number {    return this.degree;  }  /**   * Long division over GF(2): for each position in turn, when the bit   * there is 1 the divisor is XORed in beneath it, which clears it;   * what is left in the last `degree` positions is the remainder.   */  divide(word: readonly number[], phase: CrcPhase = "sender"): number[] {    if (word.length <= this.degree) throw new RangeError(`a word of ${word.length} bits is too short to divide by a degree ${this.degree} generator`);    const work = word.map((bit) => bit & 1);    const workingWord = word.map((bit) => bit & 1);    const steps = word.length - this.degree;    for (let index = 0; index < steps; index++) {      const lead = work[index]!;      const leadingBit = workingWord[index]!;      const xor = lead === 1;      const xor = leadingBit === 1;      if (xor) for (let j = 0; j <= this.degree; j++) work[index + j] = work[index + j]! ^ this.divisor[j]!;      if (xor) for (let j = 0; j <= this.degree; j++) workingWord[index + j] = workingWord[index + j]! ^ this.divisor[j]!;      const window = work.slice(index, index + this.degree + 1);      const window = workingWord.slice(index, index + this.degree + 1);      const register = work.slice(index + 1, index + this.degree + 1);      const register = workingWord.slice(index + 1, index + this.degree + 1);      // ▸ one position: when its bit is 1, XOR the divisor in beneath it      this.tracer?.emit("divide", { phase, index, lead, xor, window, register, work: [...work] });      this.tracer?.emit("divide", { phase, index, leadingBit, xor, window, register, workingWord: [...workingWord] });    }    return work.slice(steps);    return workingWord.slice(steps);  }  /** The message times x^degree divided by the generator; the remainder rides behind the message. */  encode(message: readonly number[]): { remainder: number[]; transmitted: number[] } {    const bits = CyclicRedundancyCheck.bits(message);    const remainder = this.divide([...bits, ...new Array<number>(this.degree).fill(0)], "sender");    const transmitted = [...bits, ...remainder];    // ▸ the last degree bits are the remainder; they ride behind the message    this.tracer?.emit("append", { message: bits, remainder: [...remainder], transmitted: [...transmitted] });    return { remainder, transmitted };  }  /** The noise: XORs a pattern of flips, all ones by default, over `length` bits from `start`; a length of 0 is no burst at all. */  burst(word: readonly number[], burst: Burst): { received: number[]; pattern: number[] } {    const { start, length } = burst;    if (!Number.isInteger(start) || !Number.isInteger(length) || length < 0 || start < 0) throw new RangeError(`burst start ${start} and length ${length} must be non-negative integers`);    if (length > 0 && start + length > word.length) throw new RangeError(`a burst of ${length} from ${start} runs past a ${word.length}-bit word`);    const pattern = length === 0 ? [] : burst.pattern ? burst.pattern.map((bit) => bit & 1) : new Array<number>(length).fill(1);    if (pattern.length !== length) throw new RangeError(`a pattern of ${pattern.length} bits does not fit a burst of ${length}`);    if (length > 0 && (pattern[0] !== 1 || pattern[length - 1] !== 1)) throw new RangeError("a burst pattern starts and ends with a flip");    const received = word.map((bit, i) => (i >= start && i < start + length ? bit ^ pattern[i - start]! : bit));    // ▸ the noise flips a run of bits in transit    this.tracer?.emit("burst", { start, length, pattern: [...pattern], received: [...received] });    return { received, pattern };  }  /** The receiver's division: a zero remainder passes the word. */  verify(received: readonly number[]): { check: number[]; ok: boolean } {    const check = this.divide(received, "receiver");    const ok = check.every((bit) => bit === 0);    // ▸ the receiver divides the whole word: zero means nothing seen    this.tracer?.emit("verify", { ok, remainder: [...check] });    return { check, ok };  }  /** Encode, hit the word with a burst (length 0 for none), and check it at the far end. */  run(message: readonly number[], burst: Burst = { start: 0, length: 0 }): CrcResult {    const bits = CyclicRedundancyCheck.bits(message);    const { remainder, transmitted } = this.encode(bits);    const hit = this.burst(transmitted, burst);    const { check, ok } = this.verify(hit.received);    const corrupted = hit.received.some((bit, i) => bit !== transmitted[i]);    return {      degree: this.degree,      divisor: [...this.divisor],      message: bits,      remainder,      transmitted,      burst: burst.length > 0 ? { start: burst.start, length: burst.length, pattern: hit.pattern } : null,      received: hit.received,      check,      ok,      corrupted,      detected: corrupted && !ok,      missed: corrupted && ok,      guaranteed: this.guaranteedBurst(),    };  }  private static bits(message: readonly number[]): number[] {    if (message.length < 1 || message.length > MAX_CRC_MESSAGE) throw new RangeError(`message must be 1 to ${MAX_CRC_MESSAGE} bits, got ${message.length}`);    return message.map((bit) => bit & 1);  }}

corrupted =: yes
verdict =: detected
guaranteed =: 4

The burst changed the word and the remainder said so: detected. A burst of at most 4 bits can never be a multiple of the generator, so it is always caught.

import type { Tracer } from "../trace";/** A generator: its degree and the truncated polynomial (the leading x^degree left off), as the standard tables list them. */export interface CrcPreset { degree: number; generator: number;}/** CRC-4-ITU: x^4 + x + 1, divisor bits 10011. */export const CRC4_ITU: CrcPreset = { degree: 4, generator: 0x3 };/** CRC-8 (ATM header, I2C): x^8 + x^2 + x + 1, divisor bits 100000111. */export const CRC8: CrcPreset = { degree: 8, generator: 0x07 };export const MAX_CRC_DEGREE = 8;export const MAX_CRC_MESSAGE = 32;/** Which end is dividing: the sender computing the remainder, or the receiver checking it. */export type CrcPhase = "sender" | "receiver";/** A run of flipped bits: `length` bits from `start`, all ones unless a pattern (first and last bit 1) says otherwise. */export interface Burst { start: number; length: number; pattern?: readonly number[];}export interface CrcResult { degree: number; /** The divisor bits, highest degree first: degree + 1 of them. */ divisor: number[]; message: number[]; /** The remainder of message times x^degree divided by the generator: degree bits. */ remainder: number[]; /** The message with the remainder appended. */ transmitted: number[]; burst: { start: number; length: number; pattern: number[] } | null; received: number[]; /** The receiver's remainder over the whole received word: zero when nothing was seen. */ check: number[]; ok: boolean; /** The received word differs from the transmitted one. */ corrupted: boolean; /** Corrupted and the check caught it. */ detected: boolean; /** Corrupted and the check passed anyway: the burst was a multiple of the generator. */ missed: boolean; /** Every burst of at most this many bits is caught: the generator's degree. */ guaranteed: number;}/** * A cyclic redundancy check treats the message bits as a polynomial * over GF(2), where adding is XOR and there are no carries. The * sender multiplies by x^degree (appends that many zeros), divides by * the generator by long division, which is a shift and a conditional * XOR per message bit, and sends the remainder after the message. The * receiver divides the whole word the same way and expects zero. A * burst of flips is a polynomial e(x) = x^s * b(x) with b of degree * under the burst length; the generator has a constant term, so it * cannot divide x^s, and a burst no longer than the degree is never a * multiple of it: every such burst is caught. Longer bursts slip * through only when b(x) is itself a multiple of the generator, one * pattern in 2^(degree - 1). * * Time: O(n * degree) for an n-bit message. Space: O(n). */export class CyclicRedundancyCheck { /** The generator's bits, highest degree first. */ readonly divisor: readonly number[]; constructor( readonly degree = CRC4_ITU.degree, readonly generator = CRC4_ITU.generator, private readonly tracer?: Tracer, ) { if (!Number.isInteger(degree) || degree < 1 || degree > MAX_CRC_DEGREE) throw new RangeError(`degree must be 1 to ${MAX_CRC_DEGREE}, got ${degree}`); if (!Number.isInteger(generator) || generator < 0 || generator >= 1 << degree) throw new RangeError(`generator must fit in ${degree} bits, got ${generator}`); if ((generator & 1) === 0) throw new RangeError("generator needs a constant term, or a burst at the end of the word could slip through"); const full = (1 << degree) | generator; this.divisor = Array.from({ length: degree + 1 }, (_, i) => (full >> (degree - i)) & 1); } /** The longest burst the generator always catches: its degree. */ guaranteedBurst(): number { return this.degree; } /** * Long division over GF(2): for each position in turn, when the bit * there is 1 the divisor is XORed in beneath it, which clears it; * what is left in the last `degree` positions is the remainder. */ divide(word: readonly number[], phase: CrcPhase = "sender"): number[] { if (word.length <= this.degree) throw new RangeError(`a word of ${word.length} bits is too short to divide by a degree ${this.degree} generator`); const work = word.map((bit) => bit & 1); const workingWord = word.map((bit) => bit & 1); const steps = word.length - this.degree; for (let index = 0; index < steps; index++) { const lead = work[index]!; const leadingBit = workingWord[index]!; const xor = lead === 1; const xor = leadingBit === 1; if (xor) for (let j = 0; j <= this.degree; j++) work[index + j] = work[index + j]! ^ this.divisor[j]!; if (xor) for (let j = 0; j <= this.degree; j++) workingWord[index + j] = workingWord[index + j]! ^ this.divisor[j]!; const window = work.slice(index, index + this.degree + 1); const window = workingWord.slice(index, index + this.degree + 1); const register = work.slice(index + 1, index + this.degree + 1); const register = workingWord.slice(index + 1, index + this.degree + 1); // ▸ one position: when its bit is 1, XOR the divisor in beneath it this.tracer?.emit("divide", { phase, index, lead, xor, window, register, work: [...work] }); this.tracer?.emit("divide", { phase, index, leadingBit, xor, window, register, workingWord: [...workingWord] }); } return work.slice(steps); return workingWord.slice(steps); } /** The message times x^degree divided by the generator; the remainder rides behind the message. */ encode(message: readonly number[]): { remainder: number[]; transmitted: number[] } { const bits = CyclicRedundancyCheck.bits(message); const remainder = this.divide([...bits, ...new Array<number>(this.degree).fill(0)], "sender"); const transmitted = [...bits, ...remainder]; // ▸ the last degree bits are the remainder; they ride behind the message this.tracer?.emit("append", { message: bits, remainder: [...remainder], transmitted: [...transmitted] }); return { remainder, transmitted }; } /** The noise: XORs a pattern of flips, all ones by default, over `length` bits from `start`; a length of 0 is no burst at all. */ burst(word: readonly number[], burst: Burst): { received: number[]; pattern: number[] } { const { start, length } = burst; if (!Number.isInteger(start) || !Number.isInteger(length) || length < 0 || start < 0) throw new RangeError(`burst start ${start} and length ${length} must be non-negative integers`); if (length > 0 && start + length > word.length) throw new RangeError(`a burst of ${length} from ${start} runs past a ${word.length}-bit word`); const pattern = length === 0 ? [] : burst.pattern ? burst.pattern.map((bit) => bit & 1) : new Array<number>(length).fill(1); if (pattern.length !== length) throw new RangeError(`a pattern of ${pattern.length} bits does not fit a burst of ${length}`); if (length > 0 && (pattern[0] !== 1 || pattern[length - 1] !== 1)) throw new RangeError("a burst pattern starts and ends with a flip"); const received = word.map((bit, i) => (i >= start && i < start + length ? bit ^ pattern[i - start]! : bit)); // ▸ the noise flips a run of bits in transit this.tracer?.emit("burst", { start, length, pattern: [...pattern], received: [...received] }); return { received, pattern }; } /** The receiver's division: a zero remainder passes the word. */ verify(received: readonly number[]): { check: number[]; ok: boolean } { const check = this.divide(received, "receiver"); const ok = check.every((bit) => bit === 0); // ▸ the receiver divides the whole word: zero means nothing seen this.tracer?.emit("verify", { ok, remainder: [...check] }); return { check, ok }; } /** Encode, hit the word with a burst (length 0 for none), and check it at the far end. */ run(message: readonly number[], burst: Burst = { start: 0, length: 0 }): CrcResult { const bits = CyclicRedundancyCheck.bits(message); const { remainder, transmitted } = this.encode(bits); const hit = this.burst(transmitted, burst); const { check, ok } = this.verify(hit.received); const corrupted = hit.received.some((bit, i) => bit !== transmitted[i]); return { degree: this.degree, divisor: [...this.divisor], message: bits, remainder, transmitted, burst: burst.length > 0 ? { start: burst.start, length: burst.length, pattern: hit.pattern } : null, received: hit.received, check, ok, corrupted, detected: corrupted && !ok, missed: corrupted && ok, guaranteed: this.guaranteedBurst(), }; } private static bits(message: readonly number[]): number[] { if (message.length < 1 || message.length > MAX_CRC_MESSAGE) throw new RangeError(`message must be 1 to ${MAX_CRC_MESSAGE} bits, got ${message.length}`); return message.map((bit) => bit & 1); }}