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
Famous quotes containing the words error and/or correction:
“Theoretically, I grant you, there is no possibility of error in necessary reasoning. But to speak thus “theoretically,” is to use language in a Pickwickian sense. In practice, and in fact, mathematics is not exempt from that liability to error that affects everything that man does.”
—Charles Sanders Peirce (1839–1914)
“Shakespeare, with an improved education and in a more enlightened age, might easily have attained the purity and correction of Racine; but nothing leads one to suppose that Racine in a barbarous age would have attained the grandeur, force and nature of Shakespeare.”
—Horace Walpole (1717–1797)