Editing Reed–Solomon error correction (section)

== Reed Solomon original view decoders ==

The decoders described in this section use the Reed Solomon original view of a codeword as a sequence of polynomial values where the polynomial is based on the message to be encoded. The same set of fixed values are used by the encoder and decoder, and the decoder recovers the encoding polynomial (and optionally an error locating polynomial) from the received message.

=== Theoretical decoder ===

Reed and Solomon described a theoretical decoder that corrected errors by finding the most popular message polynomial.<ref name="ReedSolomon"/> The decoder only knows the set of values <math>a_1</math> to <math>a_n</math> and which encoding method was used to generate the codeword's sequence of values. The original message, the polynomial, and any errors are unknown. A decoding procedure could use a method like Lagrange interpolation on various subsets of n codeword values taken k at a time to repeatedly produce potential polynomials, until a sufficient number of matching polynomials are produced to reasonably eliminate any errors in the received codeword. Once a polynomial is determined, then any errors in the codeword can be corrected, by recalculating the corresponding codeword values. Unfortunately, in all but the simplest of cases, there are too many subsets, so the algorithm is impractical. The number of subsets is the [[binomial coefficient]], <math display="inline"> \binom{n}{k} = {n! \over (n-k)! k!}</math>, and the number of subsets is infeasible for even modest codes. For a {{math|(255,249)}} code that can correct 3 errors, the naïve theoretical decoder would examine 359 billion subsets.{{citation needed|date=March 2025}} <!-- = 255 * 254 * 253 * 252 * 251 * 250 / 720 rounded down; could say 360B -->

=== Berlekamp Welch decoder ===

In 1986, a decoder known as the [[Berlekamp–Welch algorithm]] was developed as a decoder that is able to recover the original message polynomial as well as an error "locator" polynomial that produces zeroes for the input values that correspond to errors, with time complexity {{math|''O''(''n''{{sup|3}})}}, where {{mvar|n}} is the number of values in a message. The recovered polynomial is then used to recover (recalculate as needed) the original message.

==== Example ====
Using RS(7,3), GF(929), and the set of evaluation points {{math|''a{{sub|i}}'' {{=}} ''i'' − 1}}

:{{math| ''a'' {{=}} {{mset|0, 1, 2, 3, 4, 5, 6}} }}

If the message polynomial is
:{{math| ''p''(''x'') {{=}} 003''x''{{sup|2}} + 002''x'' + 001}}

The codeword is
:{{math| ''c'' {{=}} {001, 006, 017, 034, 057, 086, 121} }}

Errors in transmission might cause this to be received instead.
:{{math| ''b'' {{=}} ''c'' + ''e'' {{=}} {{mset|001, 006, 123, 456, 057, 086, 121}} }}

The key equation is:

:{{math|''b{{sub|i}}E''(''a{{sub|i}}'') - ''Q''(''a{{sub|i}}'') {{=}} 0}}
Assume maximum number of errors: {{math|''e'' {{=}} 2}}. The key equation becomes:

:{{math|''b{{sub|i}}''(''e''{{sub|0}} + ''e''{{sub|1}}''a{{sub|i}}'') - (''q''{{sub|0}} + ''q''{{sub|1}}''a{{sub|i}}'' + ''q''{{sub|2}} ''a''{{su|b=''i''|p=2}} + ''q''{{sub|3}}''a''{{su|b=''i''|p=3}} + ''q''{{sub|4}}''a''{{su|b=''i''|p=4}}) {{=}} - ''b{{sub|i}}a''{{su|b=''i''|p=2}}}}

<math display="block">\begin{bmatrix}
001 & 000 & 928 & 000 & 000 & 000 & 000 \\
006 & 006 & 928 & 928 & 928 & 928 & 928 \\
123 & 246 & 928 & 927 & 925 & 921 & 913 \\
456 & 439 & 928 & 926 & 920 & 902 & 848 \\
057 & 228 & 928 & 925 & 913 & 865 & 673 \\
086 & 430 & 928 & 924 & 904 & 804 & 304 \\
121 & 726 & 928 & 923 & 893 & 713 & 562
\end{bmatrix}
\begin{bmatrix}
e_0 \\
e_1 \\
q_0 \\
q_1 \\
q_2 \\
q_3 \\
q_4
\end{bmatrix}
=
\begin{bmatrix}
000 \\
923 \\
437 \\
541 \\
017 \\
637 \\
289
\end{bmatrix}
</math>

Using [[Gaussian elimination]]:

<math display="block">
\begin{bmatrix}
001 & 000 & 000 & 000 & 000 & 000 & 000 \\
000 & 001 & 000 & 000 & 000 & 000 & 000 \\
000 & 000 & 001 & 000 & 000 & 000 & 000 \\
000 & 000 & 000 & 001 & 000 & 000 & 000 \\
000 & 000 & 000 & 000 & 001 & 000 & 000 \\
000 & 000 & 000 & 000 & 000 & 001 & 000 \\
000 & 000 & 000 & 000 & 000 & 000 & 001
\end{bmatrix}
\begin{bmatrix}
e_0 \\
e_1 \\
q_0 \\
q_1 \\
q_2 \\
q_3 \\
q_4
\end{bmatrix}
=
\begin{bmatrix}
006 \\
924 \\
006 \\
007 \\
009 \\
916 \\
003
\end{bmatrix}
</math>


:{{math| ''Q''(''x'') {{=}} 003''x''{{sup|4}} + 916''x''{{sup|3}} + 009''x''{{sup|2}} + 007''x'' + 006}}
:{{math| ''E''(''x'') {{=}} 001''x''{{sup|2}} + 924''x'' + 006}}

:{{math| {{sfrac|''Q''(''x'')|''E''(''x'')}} {{=}} ''P''(''x'') {{=}} 003''x''{{sup|2}} + 002''x'' + 001}}

Recalculate {{math| ''P''(''x'') }} where {{math| ''E''(''x'') {{=}} 0 : {{mset|2, 3}} }} to correct {{mvar|b}} resulting in the corrected codeword:

:{{math| ''c'' {{=}} {{mset|001, 006, 017, 034, 057, 086, 121}} }}}}

=== Gao decoder ===

In 2002, an improved decoder was developed by Shuhong Gao, based on the extended Euclid algorithm. <ref>https://www.math.clemson.edu/~sgao/papers/RS.pdf</ref>

==== Example ====
*<math>R_{-1} = \prod_{i=1}^n (x - a_i)</math>
*<math>R_0 = </math> Lagrange interpolation of <math>(a_i, b(a_i))</math> for <math>i = 1</math> to <math>n</math>
*<math>A_{-1} = 0</math>
*<math>A_{0} = 1</math>
*generate <math>R_{i}</math> and <math>A_{i}</math> until degree of <math>R_{i} < (n+k)/2</math>, for this example <math> (n+k)/2 = (7+3)/2 = 5</math>

{| class="wikitable"
|-
! ''i''
! ''R{{sub|i}}''
! ''A{{sub|i}}''
|-
| −1
| 001''x''{{sup|7}} + 908''x''{{sup|6}} + 175''x''{{sup|5}} + 194''x''{{sup|4}} + 695''x''{{sup|3}} + 094''x''{{sup|2}} + 720''x'' + 000
| 000
|-
| 0
| 055''x''{{sup|6}} + 440''x''{{sup|5}} + 497''x''{{sup|4}} + 904''x''{{sup|3}} + 424''x''{{sup|2}} + 472''x'' + 001
| 001
|-
| 1
| 702''x''{{sup|5}} + 845''x''{{sup|4}} + 691''x''{{sup|3}} + 461''x''{{sup|2}} + 327''x'' + 237
| 152 x + 237
|-
| 2
| 266''x''{{sup|4}} + 086''x''{{sup|3}} + 798''x''{{sup|2}} + 311''x'' + 532
| 708''x''{{sup|2}} + 176''x'' + 532
|}

:{{math| ''Q''(''x'') {{=}} ''R''{{sub|2}} {{=}} 266''x''{{sup|4}} + 086''x''{{sup|3}} + 798''x''{{sup|2}} + 311''x'' + 532}}

:{{math| ''E''(''x'') {{=}} ''A''{{sub|2}} {{=}} 708''x''{{sup|2}} + 176''x'' + 532}}

To duplicate the polynomials generated by Berlekamp Welsh,
divide ''Q''(''x'') and ''E''(''x'') by most significant coefficient of ''E''(''x'') = 708.

:{{math| ''Q''(''x'') {{=}} 003''x''{{sup|4}} + 916''x''{{sup|3}} + 009''x''{{sup|2}} + 007''x'' + 006}}
:{{math| ''E''(''x'') {{=}} 001''x''{{sup|2}} + 924''x'' + 006}}

:{{math| {{sfrac|''Q''(''x'')|''E''(''x'')}} {{=}} ''P''(''x'') {{=}} 003''x''{{sup|2}} + 002''x'' + 001}}

Recalculate {{math| ''P''(''x'') }} where {{math| ''E''(''x'') {{=}} 0 : {{mset|2, 3}} }} to correct {{math|''b''}} resulting in the corrected codeword:

:{{math| ''c'' {{=}} {001, 006, 017, 034, 057, 086, 121} }}