Forums

Reed Solomon Numerical Example Question

Started by lindasel November 10, 2008
Will someone please check out these numbers?
(Suze Orman always says "Show Me the Money." so I am asking someone to
"Show Me the Numbers."
I would like someone to work the same example I am working to find the
error magnitudes and to demonstrate how the error magnitudes in the
textbook can be obtained via the direct solution of the matrix equation.
I am referring to an example in the following textbook:
L.H. Charles Lee
Error Control Block Codes for Communication Systems
Example 6.3.
GF16, (15,9), t=3, field generator polynomial x**4 + x + 1
Information message: all zeros
Errors introduced:  
  location 12: alpha**4
  location 6: alpha**3
  location 5: alpha**7
My program replicated all of these calculations (as well as examples in
other textbooks).  My program was able to detect and correct the errors for
a test of 10,000 random information messages and error patterns, as long as
the first root of the generator polynomial is alpha**1.
I would like someone to check these numbers on the error magnitudes
calculation.
Now I am testing the case where the first root of the generator polynomial
is alpha**2.
I am using the direct solution of the error magnitudes matrix equation:
S = AE
S is a vector of dimensions 3x1 and contains the first three syndromes: 
   [0xf, 0x1, 0x9]
A is a 3x3 matrix
E is a 3x1 vector of the error magnitudes we are solving for.
Let j1, j2 and j3 be the three error locations.
A is constructed as:
Row 1:
[ (alpha**j1)**2,  (alpha**j2)**2,  (alpha**j3)**2]
Row 2:
[ (alpha**j1)**3,  (alpha**j2)**3,  (alpha**j3)**3]
Row 3:
[ (alpha**j1)**4,  (alpha**j2)**4,  (alpha**j3)**4]
For the output I am using E = Ainv S
I took the inverse of A and checked that the product of the matrix and the
inverse is the identity matrix.
You will se below that I am not getting the second errpr magnitude.  I am
getting the inverse of it.
I would be most appreciative if someone could "show me the numbers" and
let me know whether I am computing something incorrectly in this equation
or whether there is more to it than just this equation.  I also did this
calculation of the error magnitudes by hand.  It takes only a few monutes
to compute it by hand with the power and polynomial tables handy.
 synd[0] = f = alpha^ c
 synd[1] = 1 = alpha^ 0
 synd[2] = 9 = alpha^ e
 synd[3] = 7 = alpha^ a
 synd[4] = 0
 synd[5] = f = alpha^ c
 synd[0] = f
 synd[1] = 1
 synd[2] = 9
 synd[3] = 7
 synd[4] = 0
 synd[5] = f
Length of Syndrome 6
 Error Locator polynomial
  LL0 = 1
      = alpha^ 0
  LL1 = b
      = alpha^ 7
  LL2 = 3
      = alpha^ 4
  LL3 = c
      = alpha^ 6
        ALPHA^ 3 IS A ROOT
        ALPHA^ 9 IS A ROOT
        ALPHA^ c IS A ROOT
nroots = 3
 power representation of root = 3 in hex
inverse root val = c
 power representation of root = 9 in hex
inverse root val = 6
 power representation of root = c in hex
inverse root val = 3
 error found at location c
 error found at location 6
 error found at location 3
root = 3
root = 9
root = c
 rootsofsigma 3 9 c 
 locations c 6 3 
syndrome vector for matrix equation = f 1 9
 Printing 3x3 matrix
 row1:  [ a f c ]
 row2:  [ c 8 a ]
 row3:  [ 8 a f ]
 Matrix in power representation 
    element (1,1):  alpha^ 9
    element (1,2):  alpha^ c
    element (1,3):  alpha^ 6
    element (2,1):  alpha^ 6
    element (2,2):  alpha^ 3
    element (2,3):  alpha^ 9
    element (3,1):  alpha^ 3
    element (3,2):  alpha^ 9
    element (3,3):  alpha^ c
 Computing ca11
   XOR of
 Matrix inverse in power representation 
    element (1,1):  alpha^ 1
    element (1,2):  alpha^ 9
    element (1,3):  alpha^ 7
    element (2,1):  alpha^ c
    element (2,2):  alpha^ 7
    element (2,3):  alpha^ c
    element (3,1):  alpha^ 0
    element (3,2):  alpha^ 1
    element (3,3):  alpha^ c
 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
 Computing E = Ainv S
First row
  "Dot product": first row of Ainv by the syndrome vector
      XOR these terms
        alpha^ d
        alpha^ 9
        alpha^ 6
   Error magnitude = b
 Second row
      XOR these terms
        alpha^ 9
        alpha^ 7
        alpha^ b
   Error magnitude = f
Third row
   XOR these terms: f 2 e
        alpha^ c
        alpha^ 1
        alpha^ b
   Error magnitude = 3
errmags = 3 = alpha^4
errmags = f = alpha^c
errmags = b = alpha^7






lindasel <lseltzer@alumni.caltech.edu> wrote:

>GF16, (15,9), t=3, field generator polynomial x**4 + x + 1 >Information message: all zeros >Errors introduced: > location 12: alpha**4 > location 6: alpha**3 > location 5: alpha**7
Please define what "location 12" means. Is it the location corresponding to alpha**12 , using the convention where the first message location corresponds to alpha**14 and the final check location corresponds to alpha**0 ? Thanks, Steve
Steve, Thank you for looking into this.
____________________________________________________________________
First the roots of the error locator polynomial are computed.
root = 3
root = 9
root = c
 error found at location c
 error found at location 6
 error found at location 3
 rootsofsigma 3 9 c 
 locations c 6 3 
These roots are given here in polynomial representation.
The locations are the inverses of the roots.
The locations here are given in polynomial representation and are the
positions of the error locations in the codeword.  See Eqns. 6.15 to 6.17
in Lee's book.
>
I've been away from error correction for a while, but I was able to get it
to work at that time.  Here's a sample result.
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
>>>