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
Reed Solomon Numerical Example Question
Started by ●November 10, 2008
Reply by ●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**7Please 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 ●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 ●April 23, 20092009-04-23
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>>>