Editing Reed–Solomon error correction (section)

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