Introduction

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.

Compute a CRC

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">Type a message. Its bits become a polynomial, divided by a fixed generator; the <b>remainder</b> is the CRC. Click any bit below to <b>flip</b> it (a single-bit error) and watch the CRC change — that is how corruption is caught.</p>
<label class="lbl">Message</label>
<input id="msg" type="text" value="HELLO" maxlength="12" />
<label class="lbl">Bits (click one to flip it)</label>
<div id="bits" class="bits"></div>
<div class="crc">
  <span>CRC-8 =</span>
  <b id="crc">--</b>
  <span id="state" class="state"></span>
</div>
<div class="btns">
  <button id="reset" type="button" class="ghost">Restore message</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; }

// CRC-8 (polynomial 0x07, the CRC-8/SMBus standard). We treat the message bits
// as a polynomial over GF(2) and take the remainder modulo the generator. The
// math is pure shift + XOR: addition in GF(2) is XOR, so there are no carries.
const POLY = 0x07;            // x^8 + x^2 + x + 1 (the low 8 bits of the divisor)
function crc8(bytes){
  let crc = 0;
  for (const b of bytes){
    crc ^= b;                            // bring in the next byte
    for (let i = 0; i < 8; i++){
      // if the top bit is set, shift and XOR with the generator; else just shift
      crc = (crc & 0x80) ? ((crc << 1) ^ POLY) & 0xff : (crc << 1) & 0xff;
    }
  }
  return crc;
}
const hex2 = n => '0x' + n.toString(16).toUpperCase().padStart(2,'0');

let bytes = [];        // current (possibly bit-flipped) bytes
let original = [];     // bytes straight from the text box
let baseline = 0;      // CRC of the untouched message

function fromText(t){
  const arr = [];
  for (let i = 0; i < t.length; i++) arr.push(t.charCodeAt(i) & 0xff);
  return arr.length ? arr : [0];
}
function renderBits(){
  const box = document.getElementById('bits'); box.innerHTML = '';
  bytes.forEach((byte, bi) => {
    for (let bit = 7; bit >= 0; bit--){
      const on = (byte >> bit) & 1;
      const flipped = ((original[bi] ?? 0) >> bit & 1) !== on;
      const d = document.createElement('div');
      d.className = 'bit' + (on ? ' one' : '') + (flipped ? ' flipped' : '');
      d.textContent = on;
      d.addEventListener('click', () => { bytes[bi] ^= (1 << bit); update(); });
      box.appendChild(d);
    }
  });
}
function update(){
  renderBits();
  const c = crc8(bytes);
  document.getElementById('crc').textContent = hex2(c);
  const st = document.getElementById('state');
  const changed = bytes.some((b,i) => b !== original[i]) || bytes.length !== original.length;
  if (!changed){ st.textContent = '(matches the original message)'; st.className = 'state match'; }
  else { st.textContent = (c === baseline ? '(undetected!)' : 'error detected — CRC differs'); st.className = 'state changed'; }
}
function load(){
  original = fromText(document.getElementById('msg').value);
  bytes = original.slice();
  baseline = crc8(original);
  update();
}
document.getElementById('msg').addEventListener('input', load);
document.getElementById('reset').addEventListener('click', () => {
  bytes = original.slice(); update();
});
load();
Result
Console

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.

The Real Complexity

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)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 2322^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/crc-checksums/Content licensed under CC BY-NC 4.0.