Editing Reed–Solomon error correction (section)

=== Sugiyama decoder <span class="anchor" id="Euclidean decoder"></span> ===

Another iterative method for calculating both the error locator polynomial and the error value polynomial is based on Sugiyama's adaptation of the [[extended Euclidean algorithm]].

Define ''S''(''x''), Λ(''x''), and Ω(''x'') for ''t'' syndromes and ''e'' errors:
<math display="block"> \begin{align}
S(x) &= S_{t} x^{t-1} + S_{t-1} x^{t-2} + \cdots + S_2 x + S_1 \\[1ex]
\Lambda(x) &= \Lambda_{e} x^{e} + \Lambda_{e-1} x^{e-1} + \cdots + \Lambda_{1} x + 1 \\[1ex]
\Omega(x) &= \Omega_{e} x^{e} + \Omega_{e-1} x^{e-1} + \cdots + \Omega_{1} x + \Omega_{0}
\end{align} </math>

The key equation is:
<math display="block"> \Lambda(x) S(x) = Q(x) x^{t} + \Omega(x) </math>

For ''t'' = 6 and ''e'' = 3:
<math display="block">\begin{bmatrix}
\Lambda_3 S_6 & x^8 \\
\Lambda_2 S_6 + \Lambda_3 S_5 & x^7  \\
\Lambda_1 S_6 + \Lambda_2 S_5 + \Lambda_3 S_4 & x^6 \\
          S_6 + \Lambda_1 S_5 + \Lambda_2 S_4 + \Lambda_3 S_3 & x^5 \\
          S_5 + \Lambda_1 S_4 + \Lambda_2 S_3 + \Lambda_3 S_2 & x^4 \\
          S_4 + \Lambda_1 S_3 + \Lambda_2 S_2 + \Lambda_3 S_1 & x^3 \\
          S_3 + \Lambda_1 S_2 + \Lambda_2 S_1 & x^2 \\
          S_2 + \Lambda_1 S_1 & x \\
          S_1
\end{bmatrix}
=
\begin{bmatrix}
Q_2 x^8 \\
Q_1 x^7 \\
Q_0 x^6 \\
0 \\
0 \\
0 \\
\Omega_2 x^2 \\
\Omega_1 x \\
\Omega_0
\end{bmatrix}
</math>

The middle terms are zero due to the relationship between Λ and syndromes.

The extended Euclidean algorithm can find a series of polynomials of the form

{{block indent | em = 1.5 | text = ''A''<sub>''i''</sub>(''x'') ''S''(''x'') + ''B''<sub>''i''</sub>(''x'') ''x''<sup>''t''</sup> = ''R''<sub>''i''</sub>(''x'')}}

where the degree of ''R'' decreases as ''i'' increases. Once the degree of ''R''<sub>''i''</sub>(''x'') < ''t''/2, then
{{block indent | em = 1.5 | text = ''A''<sub>''i''</sub>(''x'') = Λ(''x'')}}
{{block indent | em = 1.5 | text = ''B''<sub>''i''</sub>(''x'') = −Q(''x'')}}
{{block indent | em = 1.5 | text = ''R''<sub>''i''</sub>(''x'') = Ω(''x'').}}

''B''(''x'') and ''Q''(''x'') don't need to be saved, so the algorithm becomes:

 ''R''<sub>−1</sub> := ''x''<sup>''t''</sup>
 ''R''<sub>0</sub>  := ''S''(''x'')
 ''A''<sub>−1</sub> := 0
 ''A''<sub>0</sub>  := 1
 ''i'' := 0
 '''while''' degree of ''R''<sub>''i''</sub> ≥ ''t''/2
   ''i'' := ''i'' + 1
   ''Q'' := ''R''<sub>''i''-2</sub> / ''R''<sub>''i''-1</sub>
   ''R''<sub>''i''</sub> := ''R''<sub>''i''-2</sub> - ''Q'' ''R''<sub>''i''-1</sub>
   ''A''<sub>''i''</sub> := ''A''<sub>''i''-2</sub> - ''Q'' ''A''<sub>''i''-1</sub>
to set low order term of Λ(''x'') to 1, divide Λ(''x'') and Ω(''x'') by ''A''<sub>''i''</sub>(0):
{{block indent | em = 1.5 | text = Λ(''x'') = ''A''<sub>''i''</sub> / ''A''<sub>''i''</sub>(0)}}
{{block indent | em = 1.5 | text = Ω(''x'') = ''R''<sub>''i''</sub> / ''A''<sub>''i''</sub>(0)}}
''A''<sub>''i''</sub>(0) is the constant (low order) term of A<sub>i</sub>.

==== Example ====

Using the same data as the Peterson–Gorenstein–Zierler example above:

{| class="wikitable"
|-
! ''i''
! R<sub>''i''</sub>
! A<sub>''i''</sub>
|-
| −1
| 001 ''x''<sup>4</sup> + 000 ''x''<sup>3</sup> + 000 ''x''<sup>2</sup> + 000 ''x'' + 000
| 000
|-
| 0
| 925 ''x''<sup>3</sup> + 762 ''x''<sup>2</sup> + 637 ''x'' + 732
| 001
|-
| 1
| 683 ''x''<sup>2</sup> + 676 ''x'' + 024
| 697 ''x'' + 396
|-
| 2
| 673 ''x'' + 596
| 608 ''x''<sup>2</sup> + 704 ''x'' + 544
|}

{{block indent | em = 1.5 | text = Λ(''x'') = ''A''<sub>2</sub> / 544 = 329 ''x''<sup>2</sup> + 821 ''x'' + 001 }}
{{block indent | em = 1.5 | text = Ω(''x'') = ''R''<sub>2</sub> / 544 = 546 ''x'' + 732}}