Reed-Solomon syndrome equation solution question

Good afternoon:

I have implemented an RS encoder and decoder in GF16 and GF256.  It works
for the case when the first root of the generator polynomial is alpha^1,
the usual case shown in textbooks.  I have been able to reproduce the
textbook examples and it worked for a test of 10,000 random messages with
random error locations and error values (t=3).  However, when I try to
use
alpha^2 as the first root, I am able to obtain the error locations, but
the error values.  
When I computed the syndromes I used
S[0+i] = R[alpha^(m0+i)]
where R is the received message polynomial and m0 is the location of the
first root of the generator polynomial. I obtained the syndromes, then the
Berlekamp-Massey algorithm worked and the error locations were correct. 
The problem is in finding the error values.

Right now I am looking at the syndrome equations in terms of the error
locations. This is a matrix equation 
S = AE
where the error values E[i] are unknown.
I implemented the matrix inverse solution for the case of three errors.
This works for the situation when the first root of the gen poly is
alpha^1, but as soon as I run the algorithm for the first root being
alpha^2, the syndrome equation doesn't work.
This suggests to me that the syndrome equation has to be different for
the
case when the first gen poly root is not at location 1, but I don't know
why or how.  In other words, I don't think the problem is in an
implementation of the Forney algorithm, I think the problem is in writing
the syndrome equation S=AE that one is starting with.

Thank you for any information, as my work is usually on speech, audio or
medical imaging DSP, and this is not my expertise area.

Linda Seltzer

On Oct 22, 2:58 pm, "lindasel" <lselt...@alumni.caltech.edu> wrote:
> Good afternoon:
>
> I have implemented an RS encoder and decoder in GF16 and GF256.  It works
> for the case when the first root of the generator polynomial is alpha^1,
> the usual case shown in textbooks.  I have been able to reproduce the
> textbook examples and it worked for a test of 10,000 random messages with
> random error locations and error values (t=3).  However, when I try to
> use
> alpha^2 as the first root, I am able to obtain the error locations, but
> the error values.
> When I computed the syndromes I used
> S[0+i] = R[alpha^(m0+i)]
> where R is the received message polynomial and m0 is the location of the
> first root of the generator polynomial. I obtained the syndromes, then the
> Berlekamp-Massey algorithm worked and the error locations were correct.
> The problem is in finding the error values.
>
> Right now I am looking at the syndrome equations in terms of the error
> locations. This is a matrix equation
> S = AE
> where the error values E[i] are unknown.
> I implemented the matrix inverse solution for the case of three errors.
> This works for the situation when the first root of the gen poly is
> alpha^1, but as soon as I run the algorithm for the first root being
> alpha^2, the syndrome equation doesn't work.
> This suggests to me that the syndrome equation has to be different for
> the
> case when the first gen poly root is not at location 1, but I don't know
> why or how.  In other words, I don't think the problem is in an
> implementation of the Forney algorithm, I think the problem is in writing
> the syndrome equation S=AE that one is starting with.
>
> Thank you for any information, as my work is usually on speech, audio or
> medical imaging DSP, and this is not my expertise area.
>
> Linda Seltzer

Hi Linda,

You can find the correct error values by using m0 in the Forney
algorithm as follows:

e(i) = [Xi^(2-m0) * Omega(1/Xi)] / [Lambda'(1/Xi)]

Darol Klawetter

On Oct 22, 2:58&#4294967295;pm, "lindasel" <lselt...@alumni.caltech.edu> wrote:
> Good afternoon:
>
> I have implemented an RS encoder and decoder in GF16 and GF256. &#4294967295;It works
> for the case when the first root of the generator polynomial is alpha^1,
> the usual case shown in textbooks. &#4294967295;I have been able to reproduce the
> textbook examples and it worked for a test of 10,000 random messages with
> random error locations and error values (t=3). &#4294967295;However, when I try to
> use
> alpha^2 as the first root, I am able to obtain the error locations, but
> the error values. &#4294967295;
> When I computed the syndromes I used
> S[0+i] = R[alpha^(m0+i)]
> where R is the received message polynomial and m0 is the location of the
> first root of the generator polynomial. I obtained the syndromes, then the
> Berlekamp-Massey algorithm worked and the error locations were correct.
> The problem is in finding the error values.
>
> Right now I am looking at the syndrome equations in terms of the error
> locations. This is a matrix equation
> S = AE
> where the error values E[i] are unknown.
> I implemented the matrix inverse solution for the case of three errors.
> This works for the situation when the first root of the gen poly is
> alpha^1, but as soon as I run the algorithm for the first root being
> alpha^2, the syndrome equation doesn't work.
> This suggests to me that the syndrome equation has to be different for
> the
> case when the first gen poly root is not at location 1, but I don't know
> why or how. &#4294967295;In other words, I don't think the problem is in an
> implementation of the Forney algorithm, I think the problem is in writing
> the syndrome equation S=AE that one is starting with.
>
> Thank you for any information, as my work is usually on speech, audio or
> medical imaging DSP, and this is not my expertise area.
>
> Linda Seltzer

S = AE where S is a vector of syndromes and E the vector of error
values
and A is (in essence) a Vandermonde matrix can be solved by computing
the inverse of A and finding E as SA^{-1}.  The inverse of a
Vandermonde
matrix is known explicitly, that is, there is a formula for each entry
in the
inverse matrix, which is often ill-conditioned when floating-point
computations
are in use.  No such problem arises in finite fields.  Forney's
formula is a
clever way of combining the inverse computation and the SA^{-1}
calculation
to give the error values directly.  It also does not require one to
know ALL
the error locations X_i (needed to find A and hence A^{-1}) before
beginning
the computation of error values.  Each error value Y_i can be found
immediately after finding the corresponding error location X_i.

For the case of three errors and a generator polynomial
g(z) = (z-alpha^2)(z-alpha^3)....(z-alpha^{2t+1}) where t is 3 or
more,
the equations to be solved are

S_0 = (X_1)^2(Y_1) + (X_2)^2(Y_2) + (X_3)^2(Y_3)
S_1 = (X_1)^3(Y_1) + (X_2)^3(Y_2) + (X_3)^3(Y_3)
S_2 = (X_1)^4(Y_1) + (X_2)^4(Y_2) + (X_3)^4(Y_3)

where S_0 = R(alpha^2), S_1 = R(alpha^3), S_2= R(alpha^4)
and X_1, X_2, X_3 are the error locations.  A standard Vandermonde
matrix is usually defined as (read in monospaced font, please)

   1         1         1
  X_1       X_2       X_3
(X_1)^2   (X_2)^2   (X_3)^2

The matrix manipulations needed to transform this to the one
needed (and the corresponding transformations of the inverse)
should be worked out by interested parties.

Hope this helps

--Dilip Sarwate

I formed this matrix and was able to take the inverse.  I tested product of
the matrix and the inverse and got the identity matrix.
However, when I computed the error magnitudes for the set of equations
Y = [Ainv] S,
there were still some errors:
(1) the error values dont come out in a consistent order for the error
locations for different test cases.  
(2) it doesn't get the correct error value for the second equation.
There seems to be more to it than just getting the inverse and multiplying
it by the syndrome vector.
Thank you for any suggestions.
>For the case of three errors and a generator polynomial
>g(z) =3D (z-alpha^2)(z-alpha^3)....(z-alpha^{2t+1}) where t is 3 or
>more,
>the equations to be solved are
>
>S_0 =3D (X_1)^2(Y_1) + (X_2)^2(Y_2) + (X_3)^2(Y_3)
>S_1 =3D (X_1)^3(Y_1) + (X_2)^3(Y_2) + (X_3)^3(Y_3)
>S_2 =3D (X_1)^4(Y_1) + (X_2)^4(Y_2) + (X_3)^4(Y_3)
>
>where S_0 =3D R(alpha^2), S_1 =3D R(alpha^3), S_2=3D R(alpha^4)
>and X_1, X_2, X_3 are the error locations. 

I've been away from error correction for a while, but I was able to get it
to work back then.  Here is a sample result.  Thank you for answering my
questions.
-Linda Seltzer
_______________________________________________________________
transmitted message [0] =  f
 transmitted message [1] =  0
 transmitted message [2] =  5
 transmitted message [3] =  5
 transmitted message [4] =  4
 transmitted message [5] =  7
 transmitted message [6] =  0
 transmitted message [7] =  f
 transmitted message [8] =  0
 transmitted message [9] =  a
 transmitted message [a] =  7
 transmitted message [b] =  6
 transmitted message [c] =  4
 transmitted message [d] =  8
 transmitted message [e] =  0
----------------------------------------
 ******ERROR CORRECTION TEST - Arbitrary example
Before errors inserted: recd_msg[0] = f
Before errors inserted: recd_msg[1] = 0
Before errors inserted: recd_msg[2] = 5
Before errors inserted: recd_msg[3] = 5
Before errors inserted: recd_msg[4] = 4
Before errors inserted: recd_msg[5] = 7
Before errors inserted: recd_msg[6] = 0
Before errors inserted: recd_msg[7] = f
Before errors inserted: recd_msg[8] = 0
Before errors inserted: recd_msg[9] = a
Before errors inserted: recd_msg[a] = 7
Before errors inserted: recd_msg[b] = 6
Before errors inserted: recd_msg[c] = 4
Before errors inserted: recd_msg[d] = 8
Before errors inserted: recd_msg[e] = 0
inserted error at location 8, value b
inserted error at location 9, value 2
inserted error at location e, value 2
After errors inserted: recd_msg[0] = f
After errors inserted: recd_msg[1] = 0
After errors inserted: recd_msg[2] = 5
After errors inserted: recd_msg[3] = 5
After errors inserted: recd_msg[4] = 4
After errors inserted: recd_msg[5] = 7
After errors inserted: recd_msg[6] = 0
After errors inserted: recd_msg[7] = f
After errors inserted: recd_msg[8] = b
After errors inserted: recd_msg[9] = 2
After errors inserted: recd_msg[a] = 7
After errors inserted: recd_msg[b] = 6
After errors inserted: recd_msg[c] = 4
After errors inserted: recd_msg[d] = 8
After errors inserted: recd_msg[e] = 2
 synd[0] = 0
 synd[1] = e
 synd[2] = f
 synd[3] = 2
 synd[4] = f
 synd[5] = e

 synd[0] = 0
 synd[1] = e
 synd[2] = f
 synd[3] = 2
 synd[4] = f
 synd[5] = e
Length of Syndrome 6
 Error Locator polynomial
  LL0 = 1
  LL1 = 6
  LL2 = a
  LL3 = 2
nroots = 3
 power representation of root = 1 in hex
inverse root val = e
 power representation of root = 6 in hex
inverse root val = 9
 power representation of root = 7 in hex
inverse root val = 8
 error found at location e
 error found at location 9
 error found at location 8
root = 1
root = 6
root = 7
 rootsofsigma 1 6 7 
syndrome vector for matrix equation = 0 e f
 Printing 3x3 matrix
 row1 before squaring: [5  a  9]
    element (1,1):  alpha^ 8
    element (1,2):  alpha^ 9
    element (1,3):  alpha^ e
 row1:  [ 2 8 d ]
 row2:  [ a f f ]
 row3:  [ 4 c e ]
 Matrix in power representation 
    element (1,1):  alpha^ 1
    element (1,2):  alpha^ 3
    element (1,3):  alpha^ d
    element (2,1):  alpha^ 9
    element (2,2):  alpha^ c
    element (2,3):  alpha^ c
    element (3,1):  alpha^ 2
    element (3,2):  alpha^ 6
    element (3,3):  alpha^ b
 Transpose Matrix in power representation 
    element (1,1):  alpha^ 1
    element (1,2):  alpha^ 9
    element (1,3):  alpha^ 2
    element (2,1):  alpha^ 3
    element (2,2):  alpha^ c
    element (2,3):  alpha^ 6
    element (3,1):  alpha^ d
    element (3,2):  alpha^ c
    element (3,3):  alpha^ b
 Computing ca11
   XOR of
    element (3,2):  alpha^ 8
    element (3,3):  alpha^ 3
  Cofactors
    element (1,1):  alpha^ d
    element (1,2):  alpha^ 9
    element (1,3):  alpha^ 5
    element (2,1):  alpha^ c
    element (2,2):  alpha^ b
    element (2,3):  alpha^ 5
    element (3,1):  alpha^ 3
    element (3,2):  alpha^ d
    element (3,3):  alpha^ 1
Determinant = a = alpha ** 9
 Matrix inverse in power representation 
    element (1,1):  alpha^ 4
    element (1,2):  alpha^ 0
    element (1,3):  alpha^ b
    element (2,1):  alpha^ 3
    element (2,2):  alpha^ 2
    element (2,3):  alpha^ b
    element (3,1):  alpha^ 9
    element (3,2):  alpha^ 4
    element (3,3):  alpha^ 7
 Product of matrix and inverse 
    element (1,1):  alpha^ 0
    element (1,2) = 0
    element (1,3) = 0
    element (2,1) = 0
    element (2,2):  alpha^ 0
    element (2,3) = 0
    element (3,1) = 0
    element (3,3) = 0
    element (3,3):  alpha^ 0
errmags at 8 = b = alpha^7
errmags at 9 = 8 = alpha^3
errmags at e = 2 = alpha^1
Error at location 8 is b
Error at location 8 is b
Error at location 9 is 8
Error at location 9 is 8
Error at location e is 2
Error at location e is 2
Error vector [0] = 0
Error vector [1] = 0
Error vector [2] = 0
Error vector [3] = 0
Error vector [4] = 0
Error vector [5] = 0
Error vector [6] = 0
Error vector [7] = 0
Error vector [8] = b
Error vector [9] = 8
Error vector [a] = 0
Error vector [b] = 0
Error vector [c] = 0
Error vector [d] = 0
Error vector [e] = 2
Add to recd_msg[0] = f
Add to recd_msg[1] = 0
Add to recd_msg[2] = 5
Add to recd_msg[3] = 5
Add to recd_msg[4] = 4
Add to recd_msg[5] = 7
Add to recd_msg[6] = 0
Add to recd_msg[7] = f
Add to recd_msg[8] = b
Add to recd_msg[9] = 2
Add to recd_msg[a] = 7
Add to recd_msg[b] = 6
Add to recd_msg[c] = 4
Add to recd_msg[d] = 8
Add to recd_msg[e] = 2
************Doing error correction 
correctedmsg [0] = f
correctedmsg [1] = 0
correctedmsg [2] = 5
correctedmsg [3] = 5
correctedmsg [4] = 4
correctedmsg [5] = 7
correctedmsg [6] = 0
correctedmsg [7] = f
correctedmsg [8] = 0
correctedmsg [9] = a
correctedmsg [a] = 7
correctedmsg [b] = 6
correctedmsg [c] = 4
correctedmsg [d] = 8
correctedmsg [e] = 0
>>>