Reed-Solomon error correction

The Reed-Solomon error correction is an error-correcting code which encodes blocks of n-bit symbols. The total number of n-bit symbols in the encoded block is 2ⁿ-1. Thus a block encoding 8-bit bytes has 255 bytes. The number of data symbols is variable. A commonly used code encodes 233 data bytes in the 255-byte block.

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 Reed-Solomon code can bridge a series of errors in a block of data to recover the coeeficients of the polynomial that drew the original curve.

Reed-Solomon codes are unusual in that they correct bursts of errors with very little additional data. Also they permit a designer to trade-off 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 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. Their first significant application was to encode the digital pictures sent back by the Voyager space probe.