Can the Euclid algorithm be used to do Reed Solomon decoding for the more general case where b > 1 in WHP 031?

Question

I have been attempting to understand how to decode the following RS(7,3) code (prim Poly = 1011, prim Elem = 2, b = 2) per the Euclid algo described in WHP 031 previously linked to on the wikipedia page here: https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction without success.

• My source codeword = [3 2 1 2 3 7 7]
• Codeword w/ 2 errors = [3 2 5 2 3 7 1]
• calculated syndromes = [2 2 0 1]
• error magn, omega = [4 5]
• error loc, lambda = [2 1 1]

I have used a python implementation of the Berlekamp-Massey algo to verify that the syndrome and error magn, and error loc polys are correct and that the codeword with 2 errors can be correctly decoded with b = 2 (first consecutive root = 4), but cannot understand how I might have implemented Euclid's algo incorrectly for larger values of b other than 0 or 1 where the syndrome takes the form S(x) = Sb+2t+1 * x^2t-1 + .... + Sb+1 * x + Sb.

Is the algo capable of handling the cases for larger values of b? Does the approach in WHP 031 require modification for these cases?

Answer 1

Can the Euclid algorithm be used to do Reed Solomon decoding for the more general case where b > 1

Yes

---

I fixed the broken Wiki link to use an internet archive link. That article is not very descriptive of the algorithm. Sugiyama's extended Euclid algorithm can be used for FCR (first consecutive root) of 2^{b > 1}. In this case FCR = 2^2 = 4, which results in a self-reciprocal generator polynomial (coefficients are 1 4 6 4 1, which reversed are the same). Following the Wiki example:

algorithm:

Let t = number of generator roots. Let s(x) = polynomial with syndromes as coefficients. The key equation is

Λ(x) s(x) = q(x) x^t + Ω(x)

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

a[i](x) s(x) + b[i](x) x^t = r[i](x)

where the degree of r[i](x) decreases as i increases, and once the degree of r[i] < t/2, then Λ(x) = a[i](x), and Ω(x) = r[i](x). Both Λ(x) and Ω(x) are usually divided by the low order (constant) term of Λ(x) so that the lowest order term of Λ(x) = 1. q(x) and b[i](x) don't need to be saved, so the algorithm becomes:

r[−1] = x^t
a[-1] = 0
r[ 0] = s(x)
a[ 0] = 1
i = 0
while degree of r[i] ≥ t/2
    i = i + 1
    q = r[i-2] / r[i-1]          (quotient)
    r[  i] = r[i-2] - q r[i-1]   (remainder)
    a[  i] = a[i-2] - q a[i-1]   (euclidean polynomial)
Λ(x) = a[i] / a[i][lo]           ([lo] is low order term)
Ω(x) = r[i] / a[i][lo]           ([lo] is low order term)

example from question:

generator roots:  4 3 6 7
generator poly:   1x^4 + 6x^3 + 4x^2 + 6x + 1

encoded msg:    3 2 1 2 3 7 7
error msg:      3 2 5 2 3 7 1

syndromes: s[{4 3 6 7}] = {5 7 0 4}

r[-1]     1x^4 + 0x^3 + 0x^2 + 0x + 0
a[-1]                               0
r[ 0]            4x^3 + 0x^2 + 7x + 5
a[ 0]                               1
q                              7x + 0
r[ 1]                   3x^2 + 6x + 0
a[ 1]                          7x + 0
q                              5x + 1
r[ 2]                          1x + 5
a[ 2]                   6x^2 + 7x + 1
Λ(x)                    6x^2 + 7x + 1
Ω(x)                           1x + 5
roots of Λ(x)                   1   3
locators (1/roots)              1   6
indexes 6-log{1 6} = 6-{0 4} =  6   2
error values                    6   4

error msg:      3 2 5 2 3 7 1
error values:       4       6
corrected msg:  3 2 1 2 3 7 7