The scheme encodes the block's message as points in a polynomial plotted over a finite field (usually a small binary number). The coefficients of the polynomial are the data of the block. The plot overdetermines the coefficients, which can be recovered from quite small subsets of the plotted points. In the same sense that one can correct a curve by interpolating past a gap, a ReedSolomon code can bridge a series of errors in a block of data to recover the coeeficients of the polynomial that drew the original curve.
ReedSolomon codes are unusual in that they correct bursts of errors with very little additional data. Also they permit a designer to tradeoff computational power to get more data per block, or an ability to correct larger groups of errors.
The code was invented in 1960 by Irving S. Reed and Gustave Solomon, who were then members of MIT's 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 ReedSolomon 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. Their first significant application was to encode the digital pictures sent back by the Voyager space probe.
Search Encyclopedia

Featured Article
