Editing Reed–Solomon error correction (section)

==== Example ====

Consider the Reed–Solomon code defined in {{math|''GF''(929)}} with {{math|''α'' {{=}} 3}} and {{math|''t'' {{=}} 4}} (this is used in [[PDF417]] barcodes) for a RS(7,3) code. The generator polynomial is
<math display="block">
 g(x) = (x - 3)(x - 3^2)(x - 3^3)(x - 3^4) = x^4 + 809 x^3 + 723 x^2 + 568 x + 522.
</math>
If the message polynomial is {{math|''p''(''x'') {{=}} 3 ''x''<sup>2</sup> + 2 ''x'' + 1}}, then a systematic codeword is encoded as follows:
<math display="block">
 s_r(x) = p(x) \, x^t \bmod g(x) = 547 x^3 + 738 x^2 + 442 x + 455,
</math>
<math display="block">
 s(x) = p(x) \, x^t - s_r(x) = 3 x^6 + 2 x^5 + 1 x^4 + 382 x^3 + 191 x^2 + 487 x + 474.
</math>
Errors in transmission might cause this to be received instead:
<math display="block">
 r(x) = s(x) + e(x) = 3 x^6 + 2 x^5 + 123 x^4 + 456 x^3 + 191 x^2 + 487 x + 474.
</math>
The syndromes are calculated by evaluating ''r'' at powers of ''α'':
<math display="block">
 S_1 = r(3^1) = 3 \cdot 3^6 + 2 \cdot 3^5 + 123 \cdot 3^4 + 456 \cdot 3^3 + 191 \cdot 3^2 + 487 \cdot 3 + 474 = 732,
</math>
<math display="block">
 S_2 = r(3^2) = 637,\quad S_3 = r(3^3) = 762,\quad S_4 = r(3^4) = 925,
</math>
yielding the system
<math display="block">
 \begin{bmatrix}
  732 & 637 \\
  637 & 762
 \end{bmatrix}
 \begin{bmatrix}
  \Lambda_2 \\ \Lambda_1
 \end{bmatrix}
 =
 \begin{bmatrix}
  -762 \\ -925
 \end{bmatrix}
 =
 \begin{bmatrix}
  167 \\ 004
 \end{bmatrix}.
</math>

Using [[Gaussian elimination]],
<math display="block">
 \begin{bmatrix}
  001 & 000 \\
  000 & 001
 \end{bmatrix}
 \begin{bmatrix}
  \Lambda_2 \\ \Lambda_1
 \end{bmatrix}
 =
 \begin{bmatrix}
  329 \\ 821
 \end{bmatrix},
</math>
so
<math display="block">
 \Lambda(x) = 329 x^2 + 821 x + 001,
</math>
with roots ''x''<sub>1</sub> = 757 = 3<sup>−3</sup> and ''x''<sub>2</sub> = 562 = 3<sup>−4</sup>.
The coefficients can be reversed:
<math display="block">
 R(x) = 001 x^2 + 821 x + 329,
</math>
to produce roots 27 = 3<sup>3</sup> and 81 = 3<sup>4</sup> with positive exponents, but typically this isn't used. The logarithm of the inverted roots corresponds to the error locations (right to left, location 0 is the last term in the codeword).

To calculate the error values, apply the [[Forney algorithm]]:
<math display="block">
 \Omega(x) = S(x) \Lambda(x) \bmod x^4 = 546 x + 732,
</math>
<math display="block">
 \Lambda'(x) = 658 x + 821,
</math>
<math display="block">
 e_1 = -\Omega(x_1)/\Lambda'(x_1) = 074,
</math>
<math display="block">
 e_2 = -\Omega(x_2)/\Lambda'(x_2) = 122.
</math>

Subtracting <math>e_1 x^3 + e_2 x^4 = 74x^3 + 122x^4</math> from the received polynomial ''r''(''x'') reproduces the original codeword ''s''.