Editing Reed–Solomon error correction (section)

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