Error-correcting codes
Adding structured extra bits lets errors be found and fixed after transmission or storage.
Mathematics and information · Information theory · No. 127
- Electronic age
- Science
Reed-Solomon codes were published in 1960 but were not widely used until compact discs were commercialised in October 1982.
Chart: Illustration: Error-correcting codes
Where it comes from
Chart: Map of where it comes from
Richard Hamming worked on computers at Bell Labs in 1947, when a failed weekend run left him with no results. In the April 1950 Bell System Technical Journal he published a method for finding and fixing errors.
Three things to know
- The (7, 4, 3) Hamming code was the first nontrivial code in the literature, mentioned in Shannon's 1948 paper.
- For the 1977 Voyager mission NASA's Jet Propulsion Laboratory used a Reed-Solomon code that could repair up to 16 errors.
- Reed-Solomon codes are found in CDs, DVDs, disk drives, phones, space communications and the networks of the internet.
The journey
- 1 ProblemNoise or wear flips bits in stored or sent data
- 2 RedundancyExtra check bits are added by a fixed rule
- 3 First codesGolay and Hamming publish the first codes, 1949 and 1950
- 4 Strong codesReed-Solomon codes, 1960; Voyager uses one, 1977
- 5 Everyday useDiscs, disk drives, phones and the internet