
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 nonbinary^{[1]} cyclic errorcorrecting 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 multipleburst biterror 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 ReedSolomon 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 BerlekampMassey decoding algorithm.
ReedSolomon codes have since found important applications from deepspace communication to consumer electronics. They are prominently used in consumer electronics such as CDs, DVDs, Bluray 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.
Contents
Full article ▸


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