CRC Checksums

Every time you download a file, stream a song, or save a photo, the bits travel through wires, radio and storage that occasionally flip a 0 into a 1. A cosmic ray, a scratched disk, a noisy cable — and your data is silently wrong. How does the machine on the other end know?

The answer is almost always a cyclic redundancy check (CRC): a short number — often just 32 bits — appended to your message. The receiver recomputes it and compares. If they differ, the data is corrupt and gets re-sent. It costs only a handful of cheap bit operations, yet it catches virtually every realistic error.

The trick is a beautiful piece of algebra: treat the entire message as one enormous polynomial, divide it by a fixed generator polynomial, and keep the remainder. That remainder is the CRC. Change a single bit anywhere, and the remainder changes too.

Below is a live CRC calculator. Type any text and watch its checksum appear. Then click any bit in the binary view to flip it — exactly the kind of single-bit error a noisy channel produces — and watch the CRC change completely.

<p class="hint">{{hint}}</p>
<label class="lbl">{{label_message}}</label>
<input id="msg" type="text" value="HELLO" maxlength="12" />
<label class="lbl">{{label_bits}}</label>
<div id="bits" class="bits"></div>
<div class="crc">
  <span>{{crc_label}}</span>
  <b id="crc">--</b>
  <span id="state" class="state"></span>
</div>
<div class="btns">
  <button id="reset" type="button" class="ghost">{{btn_restore}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.lbl { display: block; font-size: .78rem; font-weight: 700; text-transform: uppercase;
       letter-spacing: .04em; color: #5a7088; margin: .6rem 0 .25rem; }
#msg { font: 600 16px ui-monospace, monospace; padding: .45rem .6rem; width: 100%;
       border: 1px solid #cdd9e3; border-radius: 8px; }
.bits { display: flex; flex-wrap: wrap; gap: 4px; margin: .2rem 0 .4rem; }
.bit { width: 26px; height: 30px; display: flex; align-items: center; justify-content: center;
       font: 700 14px ui-monospace, monospace; border-radius: 6px; cursor: pointer;
       background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; transition: all .1s; user-select: none; }
.bit:hover { background: #d6e2ec; }
.bit.one { background: #1d3557; color: #fff; border-color: #16283f; }
.bit.flipped { outline: 2px solid #e63946; outline-offset: 1px; }
.crc { margin: .6rem 0; font-size: 1.05rem; }
.crc b { font: 800 1.2rem ui-monospace, monospace; color: #1d3557; }
.state { margin-left: .6rem; font-weight: 700; font-size: .9rem; }
.state.changed { color: #c92f3c; }
.state.match { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice two things. First, flipping any single bit always changes the CRC, so the error is caught. Second, the whole computation is just shifting and XOR-ing — no multiplication, no division in the usual sense, just the bitwise arithmetic of polynomials over the field with two elements.

CRC is not a hard problem — it is a solved one, and that is exactly why it is everywhere. W. Wesley Peterson introduced it in 1961, and the math is clean.

• Time cost is linear. Computing a CRC scans the message once, doing a constant amount of work (shift and XOR, or a table lookup) per byte. That is $O(n)$ for an n-bit message — about as cheap as an algorithm can be.
• The math is polynomial division over GF(2). Each bit is a coefficient; the message is one big polynomial; you divide by the fixed generator polynomial and keep the remainder. Addition and subtraction both become XOR, so there are no carries.
• Its guarantees are provable, not statistical. A well-chosen generator detects all single-bit errors, all double-bit errors, all errors that flip an odd number of bits, and every burst of errors shorter than the CRC width. Longer or adversarial errors slip through with tiny, computable probability (≈ 1 in $2^{32}$ for CRC-32).
• It is detection, not correction. A CRC tells you that something broke, not what — fixing it needs error-correcting codes, a separate and harder story than the always-easy pattern matching of a quick scan.

The contrast with the genuinely hard problems is the point: CRC sits firmly in P, far from the intractable world of P vs NP. Its brilliance is not difficulty but the perfect match between cheap arithmetic and strong guarantees.

CRC is one of the most quietly ubiquitous algorithms ever written. If bits have to survive a trip, a CRC is probably watching over them:

• Networking: Ethernet frames, Wi-Fi, and many other link layers append a CRC-32 to every packet; a bad checksum means the frame is dropped and re-sent.
• Storage: hard drives, SSDs and RAID controllers store CRCs alongside sectors to flag silent corruption before it spreads.
• File formats: ZIP archives and PNG images embed a CRC-32 per entry, which is why a corrupt download fails loudly instead of showing garbage.
• Buses and firmware: USB, SATA, CAN bus in cars, and countless microcontrollers lean on small CRCs because they cost almost nothing in hardware.

The same idea — squeeze a long message into a tiny verifiable fingerprint — also underlies the integrity checks built into data compression formats, so a decompressor can refuse to trust a damaged stream.

The cyclic redundancy check is a small marvel: read your data as a polynomial, take a remainder, and you have a fingerprint that screams the instant a single bit flips. It runs in linear time, fits in a few gates of silicon, and comes with provable guarantees rather than hopeful statistics.

Most of the limits explored on this site are about problems we can't solve cheaply. CRC is the happy opposite — a place where the right algebra makes a hard-sounding job (is this data intact?) almost free. The next time a download finishes without a hitch, thank a polynomial remainder you never saw.