Method and apparatus for computing Reed-Solomon error magnitudes

• US 6,915,478 B2
• Filed: 12/21/2001
• Issued: 07/05/2005
• Est. Priority Date: 12/21/2001
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Cox, Darrell K
• Primary Examiner(s): DILDINE JR, R STEPHEN
• Application Number:
  US10/026,342
• Publication Number:
  US 20030126542A1
• Time in Patent Office: 1,292 Days
• Field of Search: H03/M01.3/15, 714/784, 714/748
• US Class Current: 714/784
• CPC Class Codes: H03M 13/1585 Determination of error values

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).

Claims

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_lj at the v error locations can be determined from the equation $E_l=\sum _{}^{}$

j=1v⁢

 

⁢

ⅇ

lj⁢

ai⁢

 

⁢

lj,

where a is a primitive of the codeword, comprising the steps of;

triangularizing a v×

v Vandermonde matrix of the elements a^ilj 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_lj 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))<sub>v−

n+1)</sub>V(n−

1)

where A(n) is equal to a^ln 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} 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_lj at the v error locations from the equation $E_l=\underset{j=1}{\overset{v}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{e<br><br>}}_{l_j}<br><br>a^{i<br><br>\text{\hspace{1em}<br><br>}<br><br>l_j},$

where a is a primitive of the codeword by;

triangularizing a v×

v Vandermonde matrix of the elements a^ilj 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_lj 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))<sub>v−

n+1</sub>)V(n−

1)

where A(n) is equal to a^ln 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) . . . E1} 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_lj at the v error locations from the equation $E_l=\underset{j=1}{\overset{v}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{e<br><br>}}_{l_j}<br><br>a^{i<br><br>\text{\hspace{1em}<br><br>}<br><br>l_j},$

where a is a primitive of the codeword by the operations of;

triangularizing a v×

v Vandermonde matrix of the elements a^ilj 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_lj 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))<sub>v−

n+1</sub>)V(n−

1)

where A(n) is equal to a^ln 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) . . . E1} and

computing W(n) as the sum of the elements of U(n).