unscratchable

Below is a message stored the way a compact disc, a QR code, or a deep-space probe would store it. Take the brush and gouge it. Scribble hard. When you let go, watch what the mathematics does.

The decoder was shown nothing but the survivors. The bytes you destroyed were gone, and what remained held enough structure to name every missing byte and compute every one of their values back into existence. That golden strip at the bottom is not a backup — it is something far stranger, and by the end of this essay you will know exactly how it works. (The page does keep the original in memory — but only to catch the decoder ever lying, and to serve the reset button. It is never consulted to heal.)

One honest disclosure up front: the surface tells the decoder where it was scratched — the way a CD player knows which frames came back illegible. Damage with known addresses is called an erasure. Silent corruption, where the decoder must find the damage first, costs exactly twice as much to fix. Chapter 7 lets you feel that factor of two.

Every medium betrays you. Cosmic rays flip bits in RAM; scratches blind lasers; thermal noise whispers over every wire ever made. The physical world does not have a clean channel to offer — only noisy ones. Here is a five-letter word crossing such a channel. Each bit survives only with probability 1 − p.

Even at 2% noise — a channel far better than a scratched disc — a 40-bit message arrives intact less than half the time. Sending raw data through the world is not engineering. It is prayer.

The obvious fix is the one every human already knows: repeat yourself. Send each bit three times and let the majority speak. This genuinely works — it is the first error-correcting code, and it already contains the whole subject in miniature. It also has two ugly problems.

Problem one is the price: tripling every bit buys you a disk that is one-third useful. Problem two is subtler and worse: repetition spends its redundancy stupidly. It protects each bit in isolation, learning nothing from the other bits, so two unlucky hits on the same triple still get through. Three-quarters of a century of coding theory is, at heart, one question: can redundancy be spent on the message as a whole, instead of on each bit alone?

To spend redundancy wisely, you first need to see what it buys. Picture every possible 3-bit string as a corner of a cube, where crossing one edge flips one bit. Now choose your codewords — the strings you actually allow yourself to send — to be 000 and 111: the repetition code again, seen with new eyes.

The two codewords sit at Hamming distance 3 — you must flip three bits to turn one into the other. That gap is the entire secret. One flip leaves you still nearer the truth than the lie, so the nearest codeword is the right one. And notice something almost too neat: the two decoding spheres tile the cube exactly, every corner claimed by exactly one codeword, no gaps, no overlaps. Codes this efficient are called perfect, and they are vanishingly rare. You are about to meet the most famous one.

In 1950, Richard Hamming — tired of weekends lost to a computer that halted at every parity error — found a way to make redundancy overlap. Take four data bits. Add three parity bits, each one watching a different, deliberately overlapping crew of four positions. Seven bits total, drawn here as three circles.

Flip any single bit and the three parity checks do not merely complain — they testify. Read the broken checks as a binary number and it spells out the position of the flipped bit: the error is made to confess its own address. Note what happened to the price, too: repetition needed 200% overhead to fix one error; Hamming does it for 75%. And this is another perfect code — sixteen codewords whose radius-1 spheres tile all 128 corners of the 7-cube exactly.

The syndrome trick is not a coincidence of small numbers. Hamming placed the parity bits at positions 1, 2, 4 — the powers of two — so that “which checks broke” and “binary address of the error” become the same thing. It is one of the most elegant address buses ever built, and it is made of nothing.

Hamming armors you against a random, lonely bit-flip. But look at the damage the real world actually deals: a scratch, a scuff, a burst of interference. Real damage arrives in runs — and a run of damage lands on one codeword like a fist, blowing straight through any per-word budget. The fix costs nothing but cleverness: don’t store codewords side by side. Shuffle them.

Interleaving is why a CD shrugs off a 2.5-millimeter gouge: its data is braided so that neighboring bytes on the disc belong to distant codewords. The scratch is not prevented. It is diluted — converted from the error pattern codes fear most into the one they handle best. The hero at the top of this page is braided the same way, which is why your wildest scribble was spread thin across many blocks.

One idea remains, and it is the crown jewel. Hamming protects bits; scratches destroy whole bytes. For that we jump from bits to curves. Here is the fact everyone meets in school, wearing its true face at last: three points determine a parabola — any three.

That is the entire idea of Reed–Solomon codes, published by Irving Reed and Gustave Solomon in 1960 on five quiet pages. Treat your k message bytes as the coefficients of a polynomial. Evaluate it at n > k points and send those. Any k survivors pin the polynomial back down; the other n − k are pure, interchangeable spares. There is one catch — drawing curves through bytes requires an arithmetic where bytes divide cleanly, no rounding, no infinities. Such an arithmetic exists: the finite field GF(256), where addition is XOR and every one of the 255 nonzero bytes has an exact reciprocal. The line under the figure is not an analogy — those are real bytes, computed by the same encoder that armors the hero. (In practice, this page included, the code is built in its equivalent systematic form — parity from a generator polynomial, message riding untouched in front — but the any-k-survivors guarantee is the same theorem wearing work clothes.)

Now you own every part of the machine from the first scribble: bytes become polynomial evaluations over GF(256) (chapter 6), blocks are braided against bursts (5), damage with a known address costs one spare to fix while silent corruption costs two (0 and 4 — finding an error is half the work). Here is the machine with the hood open. Write your own message. Tune the armor. Try to kill it.

And that is the whole secret you scratched at in chapter 0: not a backup, not a copy — a message deliberately over-determined, braided against bursts, wearing spare evaluations of itself as armor.

R. W. Hamming, Error Detecting and Error Correcting Codes (1950) · I. S. Reed & G. Solomon, Polynomial Codes over Certain Finite Fields (1960) · E. R. Berlekamp, Algebraic Coding Theory (1968) · J. L. Massey, Shift-Register Synthesis and BCH Decoding (1969). The decoder in this page implements syndromes → Forney syndromes → Berlekamp–Massey → Chien search → Forney’s algorithm, in about three hundred readable lines — read the source; it is tested by thousands of random corruptions on every commit. For video, 3Blue1Brown’s Hamming pair is superb. For going deeper, the Wikiversity “Reed–Solomon codes for coders” guide is the classic on-ramp.