Method and apparatus for computing Reed-Solomon error magnitudes
First Claim
Patent Images
1. A method of determining error magnitudes in Reed-Solomon decoding, wherein a vector of v syndromes Ei and v error locations lj are determined from a received codeword, and error magnitudes elj at the v error locations can be determined from the equation
-
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 ailj to generate elements of a matrix V;
generating a syndrome vector W of syndromes Ei, 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 elj 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.
1 Assignment
0 Petitions
Accused Products
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).
-
Citations
18 Claims
-
1. A method of determining error magnitudes in Reed-Solomon decoding, wherein a vector of v syndromes Ei and v error locations lj are determined from a received codeword, and error magnitudes el
j at the v error locations can be determined from the equation-
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 ailj to generate elements of a matrix V;
generating a syndrome vector W of syndromes Ei, 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 el 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. - View Dependent Claims (2, 3, 4, 5, 6)
where A(n) is equal to al 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) . . . E1} andcomputing 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 Ei from a received codeword;
generating v error locations lj from the received codeword, determining error magnitudes el j at the v error locations from the equationwhere a is a primitive of the codeword by; triangularizing a v×
v Vandermonde matrix of the elements ailj to generate elements of a matrix V;
generating a syndrome vector W of syndromes Ei, 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 el 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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
13. A Reed-Solomon decoder comprising:
-
circuitry for generating a vector of v syndromes Ei from a received codeword;
circuitry for generating v error locations lj from the received codeword, circuitry for determining error magnitudes el j at the v error locations from the equationwhere a is a primitive of the codeword by the operations of; triangularizing a v×
v Vandermonde matrix of the elements ailj to generate elements of a matrix V;
generating a syndrome vector W of syndromes Ei, 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 el 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. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification