# 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 Template:Mvar check symbols to the data, an RS code can detect any combination of up to Template:Mvar erroneous symbols, or correct up to t/2⌋ symbols. As an erasure code, it can correct up to Template:Mvar 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 Template:Mvar. The choice of Template:Mvar is up to the designer of the code, and may be selected within wide limits.

#### Error locators and error values

For convenience, define the error locators Xk and error values Yk as:

${\displaystyle X_{k}=\alpha ^{i_{k}},\ Y_{k}=e_{i_{k}}}$

Then the syndromes can be written in terms of the error locators and error values as

${\displaystyle S_{j}=\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}}$

The syndromes give a system of n − k ≥ 2ν equations in 2ν unknowns, but that system of equations is nonlinear in the Xk and does not have an obvious solution. However, if the Xk were known (see below), then the syndrome equations provide a linear system of equations that can easily be solved for the Yk error values.

${\displaystyle {\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&\cdots &X_{\nu }^{1}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{\nu }^{2}\\\vdots &\vdots &&\vdots \\X_{1}^{n-k}&X_{2}^{n-k}&\cdots &X_{\nu }^{n-k}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\\vdots \\Y_{\nu }\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\\vdots \\S_{n-k}\end{bmatrix}}}$

Consequently, the problem is finding the Xk, because then the leftmost matrix would be known, and both sides of the equation could be multiplied by its inverse, yielding Yk

#### Error locator polynomial

Peterson found a linear recurrence relation that gave rise to a system of linear equations. Template:Harv Solving those equations identifies the error locations.

Define the error locator polynomial Λ(x) as

${\displaystyle \Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }}$

The zeros of Λ(x) are the reciprocals ${\displaystyle X_{k}^{-1}}$:

${\displaystyle \Lambda (X_{k}^{-1})=0}$
${\displaystyle \Lambda (X_{k}^{-1})=1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu }=0}$

Multiply both sides by ${\displaystyle Y_{k}X_{k}^{j+\nu }}$ and it will still be zero. j is any number such that 1≤j≤v.

{\displaystyle {\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0.\\{\text{Hence }}&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0,\\{\text{and so }}&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0\\\end{aligned}}}

Sum for k = 1 to ν

{\displaystyle {\begin{aligned}&\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j})=0\\&\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu })+\Lambda _{1}\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu -1})+\Lambda _{2}\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu -2})+\cdots +\Lambda _{\nu }\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j})=0\end{aligned}}}

This reduces to

${\displaystyle S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu }S_{j}=0\,}$
${\displaystyle S_{j}\Lambda _{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu }\ }$

This yields a system of linear equations that can be solved for the coefficients Λi of the error location polynomial:

${\displaystyle {\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &&\vdots \\S_{\nu }&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}}$

The above assumes the decoder knows the number of errors ν, but that number has not been determined yet. The PGZ decoder does not determine ν directly but rather searches for it by trying successive values. The decoder first assumes the largest value for a trial ν and sets up the linear system for that value. If the equations can be solved (i.e., the matrix determinant is nonzero), then that trial value is the number of errors. If the linear system cannot be solved, then the trial ν is reduced by one and the next smaller system is examined. Template:Harv

#### Obtain the error locators from the error locator polynomial

Use the coefficients Λi found in the last step to build the error location polynomial. The roots of the error location polynomial can be found by exhaustive search. The error locators are the reciprocals of those roots. Chien search is an efficient implementation of this step.

#### Calculate the error locations

Calculate ik by taking the log base a of Xk. This is generally done using a precomputed lookup table.

#### Calculate the error values

Once the error locators are known, the error values can be determined. This can be done by direct solution for Yk in the error equations given above, or using the Forney algorithm.

#### Fix the errors

Finally, e(x) is generated from ik and eik and then is subtracted from r(x) to get the sent message s(x).

### Berlekamp–Massey decoder

The Berlekamp–Massey algorithm is an alternate iterative procedure for finding the error locator polynomial. During each iteration, it calculates a discrepancy based on a current instance of Λ(x) with an assumed number of errors e:

${\displaystyle \Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}}$

and then adjusts Λ(x) and e so that a recalculated Δ would be zero. The article Berlekamp–Massey algorithm has a detailed description of the procedure. In the following example, C(x) is used to represent Λ(x).

#### Example

Consider the Reed–Solomon code defined in GF(929) with α = 3 and t = 4 (this is used in PDF417 barcodes). The generator polynomial is

${\displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522}$

If the message polynomial is p(x) = 3 x2 + 2 x + 1, then the codeword is calculated as follows.

${\displaystyle s_{r}(x)=p(x)\,x^{t}\mod g(x)=547x^{3}+738x^{2}+442x+455}$
${\displaystyle s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474}$

${\displaystyle r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474}$

The syndromes are calculated by evaluating r at powers of α.

${\displaystyle S_{1}=r(3^{1})=3\cdot 3^{6}+2\cdot 3^{5}+123\cdot 3^{4}+456\cdot 3^{3}+191\cdot 3^{2}+487\cdot 3+474=732}$
${\displaystyle S_{2}=r(3^{2})=637,\;S_{3}=r(3^{3})=762,\;S_{4}=r(3^{4})=925}$

To correct the errors, first use the Berlekamp–Massey algorithm to calculate the error locator polynomial.

n Sn+1 d C B b m
0 732 732 197 x + 1 1 732 1
1 637 846 173 x + 1 1 732 2
2 762 412 634 x2 + 173 x + 1 173 x + 1 412 1
3 925 576 329 x2 + 821 x + 1 173 x + 1 412 2

The final value of C is the error locator polynomial, Λ(x). The zeros can be found by trial substitution. They are x1 = 757 = 3−3 and x2 = 562 = 3−4, corresponding to the error locations. To calculate the error values, apply the Forney algorithm.

${\displaystyle \Omega (x)=S(x)\Lambda (x)\mod x^{4}=546x+732\,}$
${\displaystyle \Lambda '(x)=658x+821\,}$
${\displaystyle e_{1}=-\Omega (x_{1})/\Lambda '(x_{1})=-649/54=280\times 843=74\,}$
${\displaystyle e_{2}=-\Omega (x_{2})/\Lambda '(x_{2})=122\,}$

Subtracting e1x3 and e2x4 from the received polynomial r reproduces the original codeword s.

### Euclidean decoder

Another iterative method for calculating the error locator polynomial is based on the Euclidean algorithm

t = number of parities
R0 = xt
S0 = syndrome polynomial
A0 = 1
B0 = 0
i = 0
while degree of Si ≥ (t/2)
Q = Ri / Si
Si+1 = Ri – Q Si = Ri modulo Si
Ai+1 = Q Ai + Bi
Ri+1 = Si
Bi+1 = Ai
i = i + 1
Λ(x) = Ai / Ai(0)
Ω(x) = (–1)deg Ai Si / Ai(0)

Ai(0) is the constant (least significant) term of Ai.

Here is an example of the Euclidean method, using the same data as the Berlekamp Massey example above. In the table below, R and S are forward, A and B are reversed.

i Ri Ai Si Bi
0 001 x4 + 000 x3 + 000 x2 + 000 x + 000 001 925 x3 + 762 x2 + 637 x + 732 000
1 925 x3 + 762 x2 + 637 x + 732 533 + 232 x 683x2 + 676 x + 024 001
2 683 x2 + 676 x + 024 544 + 704 x + 608 x2 673 x + 596 533 + 232 x
Λ(x) = A2 / 544 = 001 + 821 x + 329 x2
Ω(x) = (–1)2 S2 / 544 = 546 x + 732

### Decoding in frequency domain (sketch)

The above algorithms are presented in the time domain. Decoding in the frequency domain, using Fourier transform techniques, can offer computational and implementation advantages. Template:Harv

The following is a sketch of the main idea behind this error correction technique.

By definition, a code word of a Reed–Solomon code is given by the sequence of values of a low-degree polynomial over a finite field. A key fact for the error correction algorithm is that the values and the coefficients of a polynomial are related by the discrete Fourier transform.

The purpose of a Fourier transform is to convert a signal from a time domain to a frequency domain or vice versa. In case of the Fourier transform over a finite field, the frequency domain signal corresponds to the coefficients of a polynomial, and the time domain signal correspond to the values of the same polynomial.

As shown in Figures 1 and 2, an isolated value in the frequency domain corresponds to a smooth wave in the time domain. The wavelength depends on the location of the isolated value.

Conversely, as shown in Figures 3 and 4, an isolated value in the time domain corresponds to a smooth wave in the frequency domain.

{{#invoke: Gallery | gallery}}

In a Reed–Solomon code, the frequency domain is divided into two regions as shown in Figure 5: a left (low-frequency) region of length ${\displaystyle k}$, and a right (high-frequency) region of length ${\displaystyle n-k}$. A data word is then embedded into the left region (corresponding to the ${\displaystyle k}$ coefficients of a polynomial of degree at most ${\displaystyle k-1}$), while the right region is filled with zeros. The result is Fourier transformed into the time domain, yielding a code word that is composed only of low frequencies. In the absence of errors, a code word can be decoded by reverse Fourier transforming it back into the frequency domain.

Now consider a code word containing a single error, as shown in red in Figure 6. The effect of this error in the frequency domain is a smooth, single-frequency wave in the right region, called the syndrome of the error. The error location can be determined by determining the frequency of the syndrome signal.

Similarly, if two or more errors are introduced in the code word, the syndrome will be a signal composed of two or more frequencies, as shown in Figure 7. As long as it is possible to determine the frequencies of which the syndrome is composed, it is possible to determine the error locations. Notice that the error locations depend only on the frequencies of these waves, whereas the error magnitudes depend on their amplitudes and phase.

The problem of determining the error locations has therefore been reduced to the problem of finding, given a sequence of ${\displaystyle n-k}$ values, the smallest set of elementary waves into which these values can be decomposed. It is known from digital signal processing that this problem is equivalent to finding the roots of the minimal polynomial of the sequence, or equivalently, of finding the shortest linear feedback shift register (LFSR) for the sequence. The latter problem can either be solved inefficiently by solving a system of linear equations, or more efficiently by the Berlekamp–Massey algorithm.

{{#invoke: Gallery | gallery}}

### Decoding beyond the error-correction bound

The Singleton bound states that the minimum distance d of a linear block code of size (n,k) is upper-bounded by n − k + 1. The distance d was usually understood to limit the error-correction capability to ⌊d/2⌋. The Reed–Solomon code achieves this bound with equality, and can thus correct up to ⌊(n − k + 1)/2⌋ errors. However, this error-correction bound is not exact.

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.[6] It applies to Reed–Solomon codes and more generally to algebraic geometric codes. This algorithm produces a list of codewords (it is a list-decoding algorithm) and is based on interpolation and factorization of polynomials over ${\displaystyle GF(2^{m})}$ and its extensions.

### Soft-decoding

The algebraic decoding methods described above are hard-decision methods, which means that for every symbol a hard decision is made about its value. For example, a decoder could associate with each symbol an additional value corresponding to the channel demodulator's confidence in the correctness of the symbol. The advent of LDPC and turbo codes, which employ iterated soft-decision belief propagation decoding methods to achieve error-correction performance close to the theoretical limit, has spurred interest in applying soft-decision decoding to conventional algebraic codes. In 2003, Ralf Koetter and Alexander Vardy presented a polynomial-time soft-decision algebraic list-decoding algorithm for RS codes, which was based upon the work by Sudan and Guruswami.[7]

## Notes

1. {{#invoke:citation/CS1|citation |CitationClass=citation }}
2. Not quite true. See remarks below.
3. {{#invoke:citation/CS1|citation |CitationClass=book }}
4. See Template:Harvtxt, for example.
5. {{#invoke:citation/CS1|citation |CitationClass=citation }}. Explains the Delsarte-Goethals-Seidel theorem as used in the context of the error correcting code for compact disc.
6. {{#invoke:citation/CS1|citation |CitationClass=citation }}
7. {{#invoke:Citation/CS1|citation |CitationClass=journal }}

## References

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}

• {{#invoke:citation/CS1|citation

|CitationClass=citation }}