Method and apparatus for computing reed-solomon error magnitudes

• US 20030126542A1
• Filed: 12/21/2001
• Published: 07/03/2003
• Est. Priority Date: 12/21/2001
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Cox, Darrell K.
• Granted Patent: US 6,915,478 B2
• Time in Patent Office: Days
• 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_l 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

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^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

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{<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^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_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^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) . . . 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{<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^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_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^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

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<br><br>\left(n\right)=T<br><br>\left(n-1\right)\star <br><br>\left\{E<br><br>\left(n\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>E<br><br>\left(n-1\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{E1}\right\}$

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