Editing Reed–Solomon error correction (section)

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