Audiopedia

The standard error correction method used in digital audio to correct errors while reading from the optical disc media. 

Advances in error correction, similar to Exact Audio Copy (EAC), as well as PS Audio’s proprietary Multiple Read Error Correction techniques found in the PerfectWave Transport have been met with growing acceptance in the high end audio community.

Reed–Solomon error correction is an error-correcting code that works by oversampling a polynomial constructed from the data. The polynomial is evaluated at several points, and these values are sent or recorded. Sampling the polynomial more often than is necessary makes the polynomial over-determined. As long as it receives “many” of the points correctly, the receiver can recover the original polynomial even in the presence of a “few” bad points.

Reed–Solomon codes are used in a wide variety of commercial applications, most prominently in CDs, DVDs and 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.

Reed–Solomon codes are block codes. This means that a fixed block of input data is processed into a fixed block of output data. In the case of the most commonly used R–S code (255, 223) – 223 Reed–Solomon input symbols (each eight bits long) are encoded into 255 output symbols.

  * Most R–S error-correcting code schemes are systematic. This means that some portion of the output codeword contains the input data in its original form.
  * A Reed–Solomon symbol size of eight bits forces the longest codeword length to be 255 symbols.
  * The standard (255, 223) Reed–Solomon code is capable of correcting up to 16 Reed–Solomon symbol errors in each codeword. Since each symbol is actually eight bits, this means that the code can correct up to 16 short bursts of error.

The Reed–Solomon code, like the convolutional code, is a transparent code. This means that if the channel symbols have been inverted somewhere along the line, the decoders will still operate. The result will be the complement of the original data. However, the Reed–Solomon code loses its transparency when the code is shortened (see below). The “missing” bits in a shortened code need to be filled by either zeros or ones, depending on whether the data is complemented or not. (To put it another way, if the symbols are inverted, then the zero fill needs to be inverted to a ones fill.) For this reason it is mandatory that the sense of the data (i.e., true or complemented) be resolved before Reed–Solomon decoding.

Overview

The key idea behind a Reed–Solomon code is that the data encoded is first visualized as a polynomial. The code relies on a theorem from algebra that states that any k distinct points uniquely determine a polynomial of degree, at most, k − 1.

The sender determines a degree k − 1 polynomial, over a finite field, that represents the k data points. The polynomial is then “encoded” by its evaluation at various points, and these values are what is actually sent. During transmission, some of these values may become corrupted. Therefore, more than k points are actually sent. As long as sufficient values are received correctly, the receiver can deduce what the original polynomial was, and hence decode the original data.

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 coefficients of the polynomial that drew the original curve.

Properties of Reed–Solomon codes

The error-correcting ability of any Reed–Solomon code is determined by n − k, the measure of redundancy in the block. If the locations of the errored symbols are not known in advance, then a Reed–Solomon code can correct up to (n − k) / 2 erroneous symbols, i.e., it can correct half as many errors as there are redundant symbols added to the block. Sometimes error locations are known in advance (e.g., “side information” in demodulator signal-to-noise ratios)—these are called erasures. A Reed–Solomon code (like any perfect code) is able to correct twice as many erasures as errors, and any combination of errors and erasures can be corrected as long as the relation 2E + S \le n - k is satisfied, where E is the number of errors and S is the number of erasures in the block.

The properties of Reed–Solomon codes make them especially well-suited to applications where errors occur in bursts. This is because it does not matter to the code how many bits in a symbol are in error—if multiple bits in a symbol are corrupted it only counts as a single error. Conversely, if a data stream is not characterized by error bursts or drop-outs but by random single bit errors, a Reed–Solomon code is usually a poor choice.

Designers are not required to use the “natural” sizes of Reed–Solomon code blocks. A technique known as “shortening” can produce a smaller code of any desired size from a larger code. For example, the widely used (255,223) code can be converted to a (160,128) code by padding the unused portion of the block (usually the beginning) with 95 binary zeroes and not transmitting them. At the decoder, the same portion of the block is loaded locally with binary zeroes. The compact disc is an example of an application of shortened Reed–Solomon codes.

In 1999 Madhu Sudan and Venkatesan Guruswami at MIT, published “Improved Decoding of Reed–Solomon and Algebraic-Geometry Codes” introducing an algorithm that allowed for the correction of errors beyond half the minimum distance of the code. It applies to Reed–Solomon codes and more generally to algebraic geometry codes. This algorithm produces a list of codewords (it is a list-decoding algorithm) and is based on interpolation and factorization of polynomials over GF(2m) and its extensions.

History

The code was invented in 1960 by Irving S. Reed and Gustave Solomon, who were then members of MIT Lincoln Laboratory. Their seminal article was entitled “Polynomial Codes over Certain Finite Fields.” When it was written, digital technology was not advanced enough to implement the concept. The first application, in 1982, of RS codes in mass-produced products was the compact disc, where two interleaved RS codes are used. An efficient decoding algorithm for large-distance RS codes was developed by Elwyn Berlekamp and James Massey in 1969. Today RS codes are used in hard disk drive, DVD, telecommunication, and digital broadcast protocols.