How can a scratched CD or a distant spacecraft fix errors nobody ever saw?
A CD can lose a 2.5 mm stripe of data to a scratch and still play perfectly, thanks to a trick with polynomials from 1960.
▶ Start the storyThey send extra data computed so cleverly that the missing or wrong parts can be rebuilt. Every error-correcting scheme adds redundancy. The simplest, a parity bit, can tell that something went wrong but not where, so the data has to be sent again. Reed–Solomon codes, invented by Irving Reed and Gustave Solomon in 1960, can find and repair the damage on the spot, without asking the sender for anything.
The trick is to turn the message into a curve. Picture a message of two numbers as a straight line: two numbers are enough to pin down a line. Instead of sending just those two numbers, you send four points on that line. If any two points are lost, the other two still pin down the same line. If one point arrives wrong, it sticks out: the other three still line up, and the odd one can be fixed. Real Reed–Solomon codes do the same with polynomials, curvier cousins of lines, over many points.
The rule of thumb is precise. Add t extra check symbols and the code can repair up to t symbols if it knows where the damage is, or t/2 if it has to find the damage too. That is why a QR code reader treats an unreadable patch as a known gap: known gaps are twice as cheap to fix.
Step 1: Message as a line
Two numbers are enough to define a straight line.
Step 2: Send extra points
Send four points on the line instead of two.
Step 3: Lose two? Fine
Any two surviving points still define the same line.
Step 4: One wrong? Spot it
Three points still line up; the odd one is the error.
A CD layers two such codes and shuffles the data so that a scratch is spread thinly over many blocks. The result can fully correct bursts of up to 4,000 bits, about 2.5 mm of disc. The same idea protected the pictures sent home by the Voyager probes from 1977.
Quiz me
0/3
Recap
Add t check symbols: fix t gaps you can see, or t/2 errors you have to find.
Surprising fact · Error correction was born from Richard Hamming's frustration at a computer that gave up on his jobs every weekend.
Sources (5)
No source, no claim. Every fact in this lesson (29 claims) cites at least one of these.