| |
|
The error-correcting ability of any Reed-Solomon code is determined by n-k, the number of parity symbols per block. If the locations of the errored symbols are not known in advance, then a Reed-Solomon code can correct up to (n-k)/2 errored symbols, i.e., it can correct half as many errors are there are parity symbols. Sometimes, error locations are known in advance, e.g., from "side information" in demodulator signal-to-noise ratios; these are called erasures. A Reed-Solomon code is twice as powerful at erasure correction than at error correction, and any combination of errors and erasures can be corrected as long as the equation 2E + S <= (n-k) is satisfied, where E is the number of errors and S is the number of erasures in the block.
Note that Reed-Solomon codes operate on multi-bit symbols. It does not matter to the code how many bits in a symbol are in error; an entire symbol is in error if any of its bits are. This makes Reed-Solomon codes especially suited to burst error correction on binary channels, since a multi-bit burst may corrupt only one or two Reed-Solomon symbols. Conversely, Reed-Solomon codes are a poor choice for random bit errors since each bit error is likely to result in a distinct symbol error.
The code was invented in 1960 by Irving S. Reed and Gustave Solomon, who were then members of MIT Lincoln Laboratory. Their seminal article was "Polynomial Codes over Certain Finite Fields." When it was written, digital technology was not advanced enough to implement the concept. The key to application of Reed-Solomon codes was the invention of an efficient decoding algorithm by Elwyn Berlekamp, a professor of electrical engineering at the University of California, Berkeley. Today they are used in disk drives, CDs, telecommunication and digital broadcast protocols.
One significant application of Reed-Solomon coding was to encode the digital pictures sent back by the Voyager space probe at Uranus. Voyager introduced Reed-Solomon coding in conjunction with Viterbi-decoded convolutional codes, a practice that has since become very widespread in deep space and satellite (e.g., direct digital broadcasting) communications. Viterbi decoders tend to produce errors in bursts that are well suited to correction by a Reed-Solomon code. Modern versions of concatenated Reed-Solomon/Viterbi-decoded convolutional coding were and are used on the Mars Pathfinder, Galileo, Mars Exploration Rover and Cassini missions, where they perform within about 1-1.5 dB of the ultimate limit imposed by the Shannon-Hartley law. These codes, as strong as they are, are now beginning to give way to the even more powerful turbo codes.