Method and apparatus for computing Reed-Solomon error magnitudes

Abstract

In a Reed-Solomon decoder, error magnitudes are determined from a root matrix and a syndrome vector. The root matrix is triangularized ( 60 ) using recursive calculations. The syndrome vector is adjusted to the triangulization ( 62 ) by recursive calculations. The error magnitudes are then determined through substitution ( 64 ).

1. A method of determining error magnitudes in Reed-Solomon decoding, wherein a vector of v syndromes E i  and v error locations l j  are determined from a received codeword, and error magnitudes e l     j    at the v error locations can be determined from the equation 
           E   l     =       ∑     j   =   1     v     ⁢           ⁢       ⅇ     l   j       ⁢     a     i   ⁢           ⁢     l   j               ,       
 
     where a is a primitive of the codeword, comprising the steps of:
 triangularizing a v×v Vandermonde matrix of the elements a il     j    to generate elements of a matrix V;  
 generating a syndrome vector W of syndromes E i , adjusted for the triangularization of matrix V;  
 generating a solution to an equation of a form Vx M=W, where M is a vector of the error magnitudes e l     j    and Vx is a vector of matrix V, having a single unknown error magnitude;  
 substituting to create other equations of the form Vx M=W having a single unknown that can be solved for a respective error magnitude.  
 
   
   
     2. The method of  claim 1  wherein said triangularizing step comprises the step of recursively generating vectors of V. 
   
   
     3. The method of  claim 2  wherein said recursively generating step comprises the steps of:
 setting a first vector V( 1 ) of matrix V; and  
 generating subsequent vectors n, 2≦n≦v, as: 
     V ( n )=( V (1)+ R ( A ( n −1)) v−n+1)   V ( n −1)  
 
 
     where A(n) is equal to a l     n    and R(A(n)) m  is a vector having A(n) replicated m times. 
   
   
     4. The method of  claim 3  wherein said step of setting the first vector comprises setting the first vector V(1) to {A(1) A(2) . . . A(v)}. 
   
   
     5. The method of  claim 1  wherein said step of generating a syndrome vector comprises the step of recursively generating elements of W. 
   
   
     6. The method of  claim 5  wherein said step of recursively generating elements of W comprises the steps of:
 for each element W(n): 
 generating a vector T(n)=R(A(n)) n *T(n−1)+T(n−1)<<1, where R(A(n)) m  is a vector having A(n) replicated m times and is T(n−1)<<1 is a previous value of T, left-shifted and right-filled with a “0”;  
 generating a vector U(n)=T(n−1)*{E(n) E(n−1) . . . E 1 } and  
 computing W(n) as the sum of the elements of U(n).  
 
 
   
   
     7. A method of Reed-Solomon decoding, comprising the steps of:
 generating a vector of v syndromes E i  from a received codeword;  
 generating v error locations l j  from the received codeword,  
 determining error magnitudes e l     j    at the v error locations from the equation 
           E   l     =       ∑     j   =   1     v     ⁢           ⁢       ⅇ     l   j       ⁢     a     i   ⁢           ⁢     l   j               ,       
 
 
     where a is a primitive of the codeword by:
 triangularizing a v×v Vandermonde matrix of the elements a il     j    to generate elements of a matrix V;  
 generating a syndrome vector W of syndromes E i , adjusted for the triangularization of matrix V;  
 generating a solution to an equation of a form Vx M=W, where M is a vector of the error magnitudes e l     j    and Vx is a vector of matrix V, having a single unknown error magnitude;  
 substituting to create other equations of the form Vx M=W having a single unknown that can be solved for a respective error magnitude.  
 
   
   
     8. The method of  claim 7  wherein said triangularizing step comprises the step of recursively generating vectors of V. 
   
   
     9. The method of  claim 8  wherein said recursively generating step comprises the steps of:
 setting a first vector V(1) of matrix V; and  
 generating subsequent vectors n, 2≦n≦v, as: 
     V ( n )=( V (1)+ R ( A ( n −1)) v−n+1 ) V ( n −1)  
 
 where A(n) is equal to a l     n    and R(A(n)) m  is a vector having A(n) replicated m times.  
 
   
   
     10. The method of  claim 9  wherein said step of setting the first vector comprises setting the first vector V(1) to {A(1) A(2) . . . A(v)}. 
   
   
     11. The method of  claim 7  wherein said step of generating a syndrome vector comprises the step of recursively generating elements of W. 
   
   
     12. The method of  claim 7  wherein said step of recursively generating elements of W comprises the steps of:
 for each element W(n): 
 generating a vector T(n)=R(A(n)) n *T(n−1)+T(n−1)<<1, where R(A(n)) m  is a vector having A(n) replicated m times and is T(n−1)<<1 is a previous value of T, left-shifted and right-filled with a “0”;  
 generating a vector U(n)=T(n−1)*{E(n) E(n−1) . . . E 1 } and  
 computing W(n) as the sum of the elements of U(n).  
 
 
   
   
     13. A Reed-Solomon decoder comprising:
 circuitry for generating a vector of v syndromes E i  from a received codeword;  
 circuitry for generating v error locations l j  from the received codeword,  
 circuitry for determining error magnitudes e l     j    at the v error locations from the equation 
           E   l     =       ∑     j   =   1     v     ⁢           ⁢       ⅇ     l   j       ⁢     a     i   ⁢           ⁢     l   j               ,       
 
 
     where a is a primitive of the codeword by the operations of:
 triangularizing a v×v Vandermonde matrix of the elements a il     j    to generate elements of a matrix V;  
 generating a syndrome vector W of syndromes E i , adjusted for the triangularization of matrix V;  
 generating a solution to an equation of a form Vx M=W, where M is a vector of the error magnitudes e l     j    and Vx is a vector of matrix V, having a single unknown error magnitude;  
 substituting to create other equations of the form Vx M=W having a single unknown that can be solved for a respective error magnitude.  
 
   
   
     14. The Reed-Solomon decoder of  claim 13  wherein said circuitry for determining error magnitudes comprises circuitry for recursively generating vectors of V. 
   
   
     15. The Reed-Solomon decoder of  claim 14  wherein said circuitry for recursively generating vectors comprises circuitry for:
 setting a first vector V(1) of matrix V; and  
 generating subsequent vectors n, 2≦n≦v, as: 
     V ( n )=( V (1)+ R ( A ( n −1)) v−n+1 ) V ( n −1)  
 
 where A(n) is equal to a l     n    and R(A(n)) m  is a vector having A(n) replicated m times.  
 
   
   
     16. The Reed-Solomon decoder of  claim 15  wherein said circuitry for determining error magnitudes sets the first vector V(1) to {A(1) A(2) . . . A(v)}. 
   
   
     17. The Reed-Solomon decoder of  claim 13  wherein said circuitry for determining error magnitudes generates a syndrome vector by recursively generating elements of W. 
   
   
     18. The Reed-Solomon decoder of  claim 13  wherein said circuitry for generating error magnitudes recursively generates elements of W by:
 for each element W(n): 
 generating a vector T(n)=R(A(n)) n *T(n−1)+T(n−1)<<1, where R(A(n)) m  is a vector having A(n) replicated m times and is T(n−1)<<1 is a previous value of T, left-shifted and right-filled with a “0”;  
 
 generating a vector U(n)=(n−1)*{E(n) E(n−1) . . . E 1 } and  
 computing W(n) as the sum of the elements of U(n).