Editing Reed–Solomon error correction (section)

=== Reed & Solomon's original view: The codeword as a sequence of values ===

There are different encoding procedures for the Reed–Solomon code, and thus, there are different ways to describe the set of all codewords.
In the original view of Reed and Solomon, every codeword of the Reed–Solomon code is a sequence of function values of a polynomial of degree less than <math>k</math>.<ref name="ReedSolomon"/> In order to obtain a codeword of the Reed–Solomon code, the message symbols (each within the q-sized alphabet) are treated as the coefficients of a polynomial <math>p</math> of degree less than <math>k</math>, over the finite field <math>F</math> with <math>q</math> elements.
In turn, the polynomial <math>p</math> is evaluated at <math>n \leq q</math> distinct points <math>a_1, \dots, a_n</math> of the field <math>F</math>, and the sequence of values is the corresponding codeword. Common choices for a set of evaluation points include <math>\{ 0, 1, 2, \dots, n - 1 \}</math>, <math>\{0, 1, \alpha, \alpha^2, \dots, \alpha^{n-2} \}</math>, or for <math>n < q</math>, <math>\{1, \alpha, \alpha^2, \dots, \alpha^{n-1} \}</math>, ... , where <math>\alpha</math> is a [[primitive element (finite field)|primitive element]] of <math>F</math>.

Formally, the set <math>\mathbf{C}</math> of codewords of the Reed–Solomon code is defined as follows:
<math display="block">
\mathbf{C}
 = \Bigl\{\;
     \bigl( p(a_1), p(a_2), \dots, p(a_n) \bigr)
     \;\Big|\;
     p \text{ is a polynomial over } F \text{ of degree } <k
   \;\Bigr\}\,.
</math>
Since any two ''distinct'' polynomials of degree less than <math>k</math> agree in at most <math>k-1</math> points, this means that any two codewords of the Reed–Solomon code disagree in at least <math>n - (k-1) = n-k+1</math> positions. Furthermore, there are two polynomials that do agree in <math>k-1</math> points but are not equal, and thus, the [[Block code#The distance d|distance]] of the Reed–Solomon code is exactly <math>d=n-k+1</math>. Then the relative distance is <math>\delta = d/n = 1-k/n + 1/n = 1-R+1/n\sim 1-R</math>, where <math>R=k/n</math> is the rate. This trade-off between the relative distance and the rate is asymptotically optimal since, by the [[Singleton bound]], ''every'' code satisfies <math>\delta+R\leq 1+1/n</math>.
Being a code that achieves this optimal trade-off, the Reed–Solomon code belongs to the class of [[maximum distance separable code]]s.

While the number of different polynomials of degree less than ''k'' and the number of different messages are both equal to <math>q^k</math>, and thus every message can be uniquely mapped to such a polynomial, there are different ways of doing this encoding. The original construction of Reed & Solomon interprets the message ''x'' as the ''coefficients'' of the polynomial ''p'', whereas subsequent constructions interpret the message as the ''values'' of the polynomial at the first ''k'' points <math>a_1,\dots,a_k</math> and obtain the polynomial ''p'' by interpolating these values with a polynomial of degree less than ''k''. The latter encoding procedure, while being slightly less efficient, has the advantage that it gives rise to a [[systematic code]], that is, the original message is always contained as a subsequence of the codeword.<ref name="ReedSolomon"/>

==== Simple encoding procedure: The message as a sequence of coefficients ====
In the original construction of Reed and Solomon, the message <math>m=(m_0,\dots,m_{k-1}) \in F^k
</math> is mapped to the polynomial <math>p_m</math> with
<math display="block">p_m(a) = \sum_{i=0}^{k-1} m_i a^{i} \,.</math>
The codeword of <math>m</math> is obtained by evaluating <math>p_m</math> at <math>n</math> different points <math>a_0, \dots, a_{n-1}</math> of the field <math>F</math>.<ref name="ReedSolomon"/> Thus the classical encoding function <math>C:F^k \to F^n</math> for the Reed–Solomon code is defined as follows:
<math display="block">C(m) = \begin{bmatrix}
p_m(a_0) \\
p_m(a_1) \\
\cdots \\
p_m(a_{n-1})
\end{bmatrix}</math>
This function <math>C</math> is a [[linear mapping]], that is, it satisfies <math>C(m) = Am
</math> for the following <math>n \times k</math>-matrix <math>A</math> with elements from <math>F</math>:
<math display="block">C(m) = Am = \begin{bmatrix}
1 & a_0 & a_0^2 & \dots & a_0^{k-1} \\
1 & a_1 & a_1^2 & \dots & a_1^{k-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & a_{n-1} & a_{n-1}^2 & \dots  & a_{n-1}^{k-1}
\end{bmatrix}
\begin{bmatrix}
m_0 \\
m_1 \\
\vdots \\
m_{k-1}
\end{bmatrix}
</math>

This matrix is a [[Vandermonde matrix]] over <math>F</math>. In other words, the Reed–Solomon code is a [[linear code]], and in the classical encoding procedure, its [[Linear code#Properties|generator matrix]] is <math>A</math>.

==== Systematic encoding procedure: The message as an initial sequence of values ====

There are alternative encoding procedures that produce a [[systematic code|systematic]] Reed–Solomon code. One method uses [[Lagrange interpolation]] to compute polynomial <math>p_m</math> such that <math display="block">p_m(a_i) = m_i \text{ for all } i\in\{0,\dots,k - 1\}.
</math> Then <math>p_m</math> is evaluated at the other points <math>a_k, \dots, a_{n - 1}</math>.

<math display="block">C(m) = \begin{bmatrix}
p_m(a_0) \\
p_m(a_1) \\
\cdots \\
p_m(a_{n-1})
\end{bmatrix}</math>

This function <math>C</math> is a linear mapping. To generate the corresponding systematic encoding matrix G, multiply the Vandermonde matrix A by the inverse of A's left square submatrix.

<math display="block">G =
(A\text{'s left square submatrix})^{-1} \cdot A
=
\begin{bmatrix}
1         & 0      & 0         & \dots  & 0      & g_{1,k+1} & \dots  & g_{1,n} \\
0         & 1      & 0         & \dots  & 0      & g_{2,k+1} & \dots  & g_{2,n} \\
0         & 0      & 1         & \dots  & 0      & g_{3,k+1} & \dots  & g_{3,n} \\
\vdots    & \vdots & \vdots    &        & \vdots & \vdots    &        & \vdots  \\
0         & \dots  & 0         & \dots  & 1      & g_{k,k+1} & \dots  & g_{k,n}
\end{bmatrix}</math>

<math>C(m) = Gm</math> for the following <math>n \times k</math>-matrix <math>G</math> with elements from <math>F</math>:
<math display="block">C(m) = Gm =
\begin{bmatrix}
1         & 0      & 0         & \dots  & 0      & g_{1,k+1} & \dots  & g_{1,n} \\
0         & 1      & 0         & \dots  & 0      & g_{2,k+1} & \dots  & g_{2,n} \\
0         & 0      & 1         & \dots  & 0      & g_{3,k+1} & \dots  & g_{3,n} \\
\vdots    & \vdots & \vdots    &        & \vdots & \vdots    &        & \vdots  \\
0         & \dots  & 0         & \dots  & 1      & g_{k,k+1} & \dots  & g_{k,n}
\end{bmatrix}\begin{bmatrix}
m_0 \\
m_1 \\
\vdots \\
m_{k-1}
\end{bmatrix}
</math>

==== Discrete Fourier transform and its inverse ====

A [[discrete Fourier transform (general)|discrete Fourier transform]] is essentially the same as the encoding procedure; it uses the generator polynomial <math>p_m</math> to map a set of evaluation points into the message values as shown above:
<math display="block">C(m) = \begin{bmatrix}
p_m(a_0) \\
p_m(a_1) \\
\cdots \\
p_m(a_{n-1})
\end{bmatrix}</math>

The inverse Fourier transform could be used to convert an error free set of ''n'' < ''q'' message values back into the encoding polynomial of ''k'' coefficients, with the constraint that in order for this to work, the set of evaluation points used to encode the message must be a set of increasing powers of ''α'':
<math display="block">a_i = \alpha^i</math>
<math display="block">a_0, \dots, a_{n-1} = \{ 1, \alpha, \alpha^2, \dots, \alpha^{n-1} \}</math>

However, Lagrange interpolation performs the same conversion without the constraint on the set of evaluation points or the requirement of an error free set of message values and is used for systematic encoding, and in one of the steps of the [[#Gao decoder|Gao decoder]].