Polynomial Codes over Certain Finite Fields
Send extra samples of a polynomial, and the whole message survives even when some arrive wrong.
Scratch a CD, tear part of a QR code, lose a packet from a probe four billion kilometres away — and the message still comes through intact. That near-magic is Reed–Solomon.
The idea, unpacked
The trick is to send your message as a curve rather than as a list. Take your data and treat it as the recipe for a smooth mathematical curve, then send not the recipe but a string of points read off that curve — more points than you strictly need to draw it.
Now suppose some of those points get smudged in transit. Because the curve is gentle and you sent extra points, the receiver can see that most of the points still line up on one curve, with a few outliers poking off it. There is only one smooth curve that fits the majority — so the outliers are spotted, snapped back into place, and the original message is rebuilt. The more spare points you send, the more damage you can shrug off.
Two engineers, ahead of the machines
In 1960, Irving Reed and Gustave Solomon, working at MIT's Lincoln Laboratory, published a four-page paper describing this scheme. It was elegant and provably optimal — but there was a catch: nobody yet knew how to actually find and fix the errors quickly in a long message. For a few years it was a beautiful idea waiting for a method. Then the decoders arrived — Peterson, then Berlekamp and Massey in 1967 — and the floodgates opened. By the time the compact disc launched in the 1980s and Voyager sailed past the planets, Reed–Solomon was quietly doing the work, and it has never stopped.
Why it mattered
Shannon had proved in 1948 that you could communicate almost perfectly over a noisy channel — but his proof did not say how. Reed–Solomon was one of the first codes strong enough and cheap enough to actually deliver on that promise at scale, and uniquely good at the kind of damage that comes in clumps: a scratch, a dust speck, a fading radio signal. It is the reason your scratched disc still plays and your half-obscured QR code still scans. Without it, digital storage and communication as we know them would be far more fragile.
Two points make a line
Remember that two points determine a straight line, and three points a parabola. If someone hands you five points that are supposed to lie on a line and one of them is clearly off, you don't need to be told which — the four that agree define the line, and the stray one stands out and can be corrected. Reed–Solomon is exactly this, scaled up: send many points of a curve, and a few wrong ones can never disguise themselves, because they cannot all fall back onto one low, smooth curve.
Before and after
Claude Shannon (1948) proved reliable communication over noise was possible; Richard Hamming (1950) built the first practical code that corrected single bit errors. Reed–Solomon took the next step, correcting whole symbols and clustered bursts, and became the most widely used error-correcting code in history. The decoding algorithms (Berlekamp–Massey, 1967) and the later list-decoding results extended it further. In this Library it sits between Shannon's promise and the storage and networks that now rely on keeping data perfect.