Reed–Solomon Error Correction

Reed–Solomon Error Correction

In coding theory, Reed–Solomon (RS) codes are non-binary cyclic error-correcting codes invented by Irving S. Reed and Gustave Solomon. They described a systematic way of building codes that could detect and correct multiple random symbol errors. By adding t check symbols to the data, an RS code can detect any combination of up to t erroneous symbols, and correct up to ⌊t/2⌋ symbols. As an erasure code, it can correct up to t known erasures, or it can detect and correct combinations of errors and erasures. Furthermore, RS codes are suitable as multiple-burst bit-error correcting codes, since a sequence of b + 1 consecutive bit errors can affect at most two symbols of size b. The choice of t is up to the designer of the code, and may be selected within wide limits.

In Reed–Solomon coding, source symbols are viewed as coefficients of a polynomial p(x) over a finite field. The original idea was to create n code symbols from k source symbols by oversampling p(x) at n > k distinct points, transmit the sampled points, and use interpolation techniques at the receiver to recover the original message. That is not how RS codes are used today. Instead, RS codes are viewed as cyclic BCH codes, where encoding symbols are derived from the coefficients of a polynomial constructed by multiplying p(x) with a cyclic generator polynomial. This gives rise to efficient decoding algorithms (described below).

Reed–Solomon codes have since found important applications from deep-space communication to consumer electronics. They are prominently used in consumer electronics such as CDs, DVDs, Blu-ray Discs, in data transmission technologies such as DSL and WiMAX, in broadcast systems such as DVB and ATSC, and in computer applications such as RAID 6 systems.

Read more about Reed–Solomon Error Correction:  History, Properties

Other articles related to "errors":

Reed–Solomon Error Correction - Applications - Satellite Transmission
... One significant application of Reed–Solomon coding was to encode the digital pictures sent back by the Voyager space probe ... Voyager introduced Reed–Solomon coding concatenated with convolutional codes, a practice that has since become very widespread in deep space and satellite (e.g ... Viterbi decoders tend to produce errors in short bursts ...

Famous quotes containing the words correction and/or error:

    There are always those who are willing to surrender local self-government and turn over their affairs to some national authority in exchange for a payment of money out of the Federal Treasury. Whenever they find some abuse needs correction in their neighborhood, instead of applying the remedy themselves they seek to have a tribunal sent on from Washington to discharge their duties for them, regardless of the fact that in accepting such supervision they are bartering away their freedom.
    Calvin Coolidge (1872–1933)

    Knowledge is ancient error reflecting on its youth.
    Francis Picabia (1878–1953)