The encyclopedia · Engineering & Operations · Technical decision · 1960
Reed-Solomon codes let a scratched CD still play
In 1960 Reed and Solomon encoded data as a polynomial so a few damaged values could be rebuilt exactly.
MIT Lincoln Laboratory
the move
Digital information is just 0s and 1s, and any imperfect device occasionally flips one, so a scratched CD or a weak radio link can corrupt data. The simple fix is redundancy: send everything three times and take a majority vote, but that triples the data to survive one error.
Reed and Solomon's 1960 paper instead encoded a message as the coefficients of a polynomial and evaluated it at many points, so the whole message becomes a long list of values. A degree-(k-1) polynomial is uniquely fixed by k points, so the receiver only needs some of the values to interpolate back the original message.
This means a handful of extra points can repair many errors, so byte-for-byte far less overhead than repetition. It let Voyager II send clean pictures from the outer planets and lets a scratched disc still play, because the damage is treated as missing samples to reconstruct rather than as data to read.
why it works
- A low-degree polynomial is determined by just a few points, so extra evaluated points are cheap redundancy.
- Interpolation recovers the coefficients even when some values are wrong or missing, so corruption is repairable.
- The overhead is a few extra points, far less than the tripling brute-force repetition needs.
what transfers
Spend redundancy as a few clever check values that can be solved back, not as repeat-copies, and you fix more corruption per byte while adding almost no overhead to clean data.
what came after
Reed-Solomon codes became the standard error-correction scheme inside compact discs, digital audio tape, hard drives, DSL, and the 2D barcodes such as QR codes, letting damaged media still be read correctly; the five-page 1960 paper is now among the most consequential in digital communications.
references
spotted an error? The archive wants to know.