Reed–Solomon error correction

related topics
{math, number, function}
{system, computer, user}
{math, energy, light}
{disease, patient, cell}
{area, part, region}
{style, bgcolor, rowspan}

In coding theory, Reed–Solomon (RS) codes are non-binary[1] 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.[2] 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 an efficient decoding algorithm, which was discovered by Elwyn Berlekamp and James Massey, and is known as the Berlekamp-Massey decoding algorithm.

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 & WiMAX, in broadcast systems such as DVB and ATSC, and in computer applications such as RAID 6 systems.


Full article ▸

related documents
Artificial neural network
Hash table
Finite field
Cantor set
Word problem for groups
Inverse function
Naive set theory
Inner product space
Limit superior and limit inferior
Peano axioms
Matrix multiplication
Zermelo–Fraenkel set theory
Computational complexity theory
Markov chain
Topological space
Collatz conjecture
Pythagorean theorem
Mathematical induction
Bra-ket notation
Cauchy sequence
Ruby (programming language)
Recurrence relation