Editing Reed–Solomon error correction (section)

== Constructions (encoding) ==

The Reed–Solomon code is actually a family of codes, where every code is characterised by three parameters: an [[Block code#The alphabet .CE.A3|alphabet]] size {{mvar|q}}, a [[Block code#The block length n|block length]] {{mvar|n}}, and a [[Block code#The message length k|message length]] {{mvar|k}}'','' with <math>k < n \leq q</math>. The set of alphabet symbols is interpreted as the [[finite field]] <math>F</math> of order <math>q</math>, and thus, <math>q</math> must be a [[prime power]]. In the most useful parameterizations of the Reed–Solomon code, the block length is usually some constant multiple of the message length, that is, the [[Block code#The rate R|rate]] <math>R = \frac{k}{n}</math> is some constant, and furthermore, the block length is either equal to the alphabet size or one less than it, i.e., <math>n=q</math> or <math>n=q-1</math>.{{citation needed|date=March 2017}}

=== 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]].

=== The BCH view: The codeword as a sequence of coefficients ===
In this view, the message is interpreted as the coefficients of a polynomial <math>p(x)</math>. The sender computes a related polynomial <math>s(x)</math> of degree <math>n-1</math> where <math>n \le q-1</math> and sends the polynomial <math>s(x)</math>. The polynomial <math>s(x)</math> is constructed by multiplying the message polynomial <math>p(x)</math>, which has degree <math>k-1</math>, with a [[generator polynomial]] <math>g(x)</math> of degree <math>n-k</math> that is known to both the sender and the receiver. {{^|comment - as mentioned in remarks below, methods like puncturing may omit transmission of some of the coefficients}} The generator polynomial <math>g(x)</math> is defined as the polynomial whose roots are sequential powers of the Galois field primitive <math>\alpha</math>
<math display="block">g(x) = \left(x-\alpha^{i}\right) \left(x-\alpha^{i+1}\right) \cdots \left(x-\alpha^{i+n-k-1}\right) = g_0 + g_1x + \cdots + g_{n-k-1}x^{n-k-1} + x^{n-k}</math>

For a "narrow sense code", <math>i = 1</math>.

<math display="block">\mathbf{C} =
\left\{
  \left ( s_1, s_2,\dots, s_{n} \right)
  \;\Big|\;
  s(a)=\sum_{i=1}^n s_i a^{i}
  \text{ is a polynomial that has at least the roots } \alpha^1,\alpha^2, \dots, \alpha^{n-k}
\right\} .</math>

==== Systematic encoding procedure ====
The encoding procedure for the BCH view of Reed–Solomon codes can be modified to yield a [[systematic code|systematic encoding procedure]], in which each codeword contains the message as a prefix, and simply appends error correcting symbols as a suffix. Here, instead of sending <math>s(x) = p(x) g(x)</math>, the encoder constructs the transmitted polynomial <math>s(x)</math> such that the coefficients of the <math>k</math> largest monomials are equal to the corresponding coefficients of <math>p(x)</math>, and the lower-order coefficients of <math>s(x)</math> are chosen exactly in such a way that <math>s(x)</math> becomes divisible by <math>g(x)</math>. Then the coefficients of <math>p(x)</math> are a subsequence of the coefficients of <math>s(x)</math>. To get a code that is overall systematic, we construct the message polynomial <math>p(x)</math> by interpreting the message as the sequence of its coefficients.

Formally, the construction is done by multiplying <math>p(x)</math> by <math>x^t</math> to make room for the <math>t=n-k</math> check symbols, dividing that product by <math>g(x)</math> to find the remainder, and then compensating for that remainder by subtracting it. The <math>t</math> check symbols are created by computing the remainder <math>s_r(x)</math>:
<math display="block">s_r(x) = p(x)\cdot x^t \ \bmod \  g(x).</math>

The remainder has degree at most <math>t-1</math>, whereas the coefficients of <math>x^{t-1},x^{t-2},\dots,x^1,x^0</math> in the polynomial <math>p(x)\cdot x^t</math> are zero. Therefore, the following definition of the codeword <math>s(x)</math> has the property that the first <math>k</math> coefficients are identical to the coefficients of <math>p(x)</math>:
<math display="block">s(x) = p(x)\cdot x^t - s_r(x)\,.</math>

As a result, the codewords <math>s(x)</math> are indeed elements of <math>\mathbf{C}</math>, that is, they are divisible by the generator polynomial <math>g(x)</math>:<ref>{{cite book |last1=Lin |first1=Shu |last2=Costello |first2=Daniel J. |title=Error control coding: fundamentals and applications |date=1983 |publisher=Prentice-Hall |location=Englewood Cliffs, NJ |isbn=978-0-13-283796-5 |page=171 |edition=Nachdr.}}</ref>
<math display="block">s(x) \equiv p(x) \cdot x^t - s_r(x) \equiv s_r(x) - s_r(x) \equiv 0 \mod g(x)\,.</math>

This function <math>s</math> is a linear mapping. To generate the corresponding systematic encoding matrix G, set G's left square submatrix to the identity matrix and then encode each row:

<math display="block">G =
\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>
Ignoring leading zeroes, the last row = <math>g(x)</math>.

<math>C(m) = mG</math> for the following <math>n \times k</math>-matrix <math>G</math> with elements from <math>F</math>:
<math display="block">C(m) = mG = \begin{bmatrix} m_0 & m_1 & \ldots & m_{k-1}\end{bmatrix}
\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>