Editing Reed–Solomon error correction (section)

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