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
>>>
Reply by lindasel●November 11, 20082008-11-11
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.
>
Reply by Steve Pope●November 10, 20082008-11-10
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
Reply by lindasel●November 10, 20082008-11-10
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