Iterative reed-solomon error-correction decoding

• US 7,689,893 B1
• Filed: 12/14/2007
• Issued: 03/30/2010
• Est. Priority Date: 04/13/2004
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Burd, Gregory
• Primary Examiner(s): Baker; Stephen M
• Application Number:
  US11/956,861
• Time in Patent Office: 837 Days
• Field of Search: 714/784
• US Class Current: 714/784
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey algorithm
• CPC Class Codes: H03M 13/1545 Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial
• CPC Class Codes: H03M 13/35 Unequal or adaptive error protection, e.g. by providing a different level of protection according to significance of source information or by adapting the coding according to the change of transmission channel characteristics
• CPC Class Codes: H03M 13/3746 with iterative decoding

Abstract

Systems and methods are provided to correct errors occurring in a decision-codeword that is generated by a detector. A decoder determines whether errors in the decision-codeword are of a degree that exceeds the correction capability of a Reed-Solomon error-correction code. If they are, the decoder iteratively modifies the decision-codeword to reduce the number of errors therein. In each iteration, the decoder generates an error indicator using one or more error indicators from a previous iteration and uses the error indicator to perform error detection and correction operations.

Claims

1. A method of correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n,k) having a correction capability t=(n−

k)/2, the method comprising;

determining whether errors in the decision-codeword are of a degree that exceeds a Reed Solomon error-correction code'"'"'s correction capability, by using an error indicator for the decision-codeword;

modifying the decision-codeword to produce a modified decision-codeword if the degree of the errors exceeds the correction capability; and

generating an error indicator for the modified decision-codeword using the error indicator for the decision-codeword.

2. The method of claim 1, wherein said modifying the decision-codeword to produce a modified decision-codeword comprises correcting one symbol in the decision-codeword.

3. The method of claim 1, further comprising correcting errors in the decision-codeword if the degree of the errors does not exceed the correction capability.

4. The method of claim 1, further comprising:

modifying the decision-codeword to produce a second modified decision-codeword, if the degree of the errors exceeds the correction capability; and

generating an error indicator for the second modified decision-codeword using the error indicator for the decision-codeword.

5. The method of claim 1, wherein said modifying the decision-codeword to produce a modified decision-codeword comprises:

referring to an incidence vector to select an error event;

referring to a list of error events to identify a symbol of the decision-codeword that corresponds to the error event; and

correcting the symbol by replacing a value of the symbol with a next-most-likely value.

6. The method of claim 4, wherein said correcting the symbol comprises:

referring to the list of error events to obtain a difference value associated with the symbol; and

computing the next-most-likely value for the symbol by subtracting the difference value from the value of the symbol.

7. A method of correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n,k) having a correction capability t=(n−

k)/2 and generating an error indicator for a modified decision-codeword using an error indicator for the decision-codeword, the method comprising;

computing quotient polynomials Q_Λ

, Q_xΛ

, Q_B, Q_xB, Q_x2B;

computing remainder polynomials r_Λ

, r_xΛ

, r_B, r_xB, r_x2B;

computing quantities d₁, d₂, and d₃, where

$\begin{array}{c}{d}_1=<br><br>\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_l\right)}<br><br>\left(Q_{\mathrm{\Lambda <br><br>}}\right)}_i\right],\\ d_2=<br><br>\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_l\right)}<br><br>\left(Q_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}\right)}_i\right],<br><br>\mathrm{and}\\ d_3=<br><br>\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_l\right)}<br><br>\left(Q_{x<br><br><br><br>B}\right)}_i\right];<br><br><br><br>\end{array}$

computing a quantity D=determinant

$\left[\begin{array}{cc}{r}_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}& r_{\mathrm{xB}}\\ d_2& d_3\end{array}\right];<br><br>$

and

computing quantities a, b, and c, where

$\begin{array}{c}a=<br><br>\left(r_{\mathrm{\Lambda <br><br>}}<br><br>d_3+r_{\mathrm{xB}}<br><br>d_1\right)<br><br>D^{-1},\\ b=<br><br>\{\begin{array}{c}\left(d_1+{\mathrm{ad}}_2\right)<br><br>d_3^{-1}<br><br><br><br>\mathrm{if}<br><br><br><br>d_3\ne <br><br>0\\ \left(r_{\mathrm{\Lambda <br><br>}}+{\mathrm{ar}}_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}\right)<br><br>r_{\mathrm{xB}}^{-1}<br><br><br><br>\mathrm{otherwise}\end{array};<br><br><br><br>\mathrm{and}\\ c=<br><br>r_{\mathrm{\Lambda <br><br>}}<br><br>r_B^{-1}.\end{array}$

8. The method of claim 7, wherein said generating the error indicator for the modified decision-codeword further comprises:

computing syndromes for the modified decision-codeword, where there are (n−

k) syndromes denoted as S₀^(el), S₁^(el), . . . , S<sub>(n−

k−

1</sub>^(el); and

generating the error indicator for the modified decision-codeword using at least some of the syndromes and at least one of;

an error locator polynomial Λ

(x) for the decision-codeword and a scratch polynomial B(x) for the decision-codeword.

9. The method of claim 7, further comprising correcting one symbol in the decision-codeword to produce the modified decision-codeword and wherein the one symbol in the modified decision-codeword that was corrected is located at a position i_l in the modified decision-codeword, and wherein the quotient polynomials are quotients resulting from dividing Λ

(x), xΛ

(x), B(x), xB(x), and x²B(x) by xα

^il+1.

10. The method of claim 7, further comprising correcting one symbol in the decision-codeword to produce the modified decision-codeword and wherein the one symbol in the modified decision-codeword that was corrected is located at a position i_l in the modified decision-codeword, and wherein the remainder polynomials are remainders resulting from dividing Λ

(x), xΛ

(x), B(x), xB(x), and x²B(x) by xα

^il+1.

11. The method of claim 7, wherein said generating the error indicator for the modified decision-codeword further comprises:

computing an error locator polynomial Λ

^(el)(x) for the modified decision-codeword, where

Λ

^(el)(x)=Λ

(x)+α

xΛ

(x)+bxB(x) if a degree of Λ

(x) is (n−

k)/2, and

Λ

^(el)(x)=Λ

(x)+axB(x)+bx²B(x) if the degree of Λ

(x) is not (n−

k)/2.

12. The method of claim 7, wherein said generating the error indicator for the modified decision-codeword further comprises:

computing a scratch polynomial B^(el)(x) for the modified decision-codeword, where

B^(el)(x)=Λ

(x)+cB(x) if a degree of Λ

(x) is (n−

k)/2, and

B^(el)(x)=xB(x)+cB(x) if the degree of Λ

(x) is not (n−

k)/2.

13. A system for correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n,k) having a correction capability t=(n−

k)/2 and having means for generating an error indicator for a modified decision-codeword using an error indicator for the decision-codeword, the method comprising;

means for computing quotient polynomials Q_Λ

, Q_xΛ

, Q_B, Q_xB, Q_x2B;

means for computing remainder polynomials r_Λ

, r_xΛ

, r_B, r_xB, r_x2B;

means for computing quantities d₁, d₂, and d₃, where

$\begin{array}{c}{d}_1=<br><br>\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_l\right)}<br><br>\left(Q_{\mathrm{\Lambda <br><br>}}\right)}_i\right],\\ d_2=<br><br>\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_l\right)}<br><br>\left(Q_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}\right)}_i\right],<br><br>\mathrm{and}\\ d_3=<br><br>\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_l\right)}<br><br>\left(Q_{x<br><br><br><br>B}\right)}_i\right];<br><br><br><br>\end{array}$

means for computing a quantity

$D=\mathrm{determinant}<br><br>\left[\begin{array}{cc}{r}_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}& r_{\mathrm{xB}}\\ d_2& d_3\end{array}\right];<br><br>$

and

means for computing quantities a, b, and c, where

$\begin{array}{c}a=<br><br>\left(r_{\mathrm{\Lambda <br><br>}}<br><br>d_3+r_{\mathrm{xB}}<br><br>d_1\right)<br><br>D^{-1},\\ b=<br><br>\{\begin{array}{c}\left(d_1+{\mathrm{ad}}_2\right)<br><br>d_3^{-1}<br><br><br><br>\mathrm{if}<br><br><br><br>d_3\ne <br><br>0\\ \left(r_{\mathrm{\Lambda <br><br>}}+{\mathrm{ar}}_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}\right)<br><br>r_{\mathrm{xB}}^{-1}<br><br><br><br>\mathrm{otherwise}\end{array};<br><br><br><br>\mathrm{and}\\ c=<br><br>r_{\mathrm{\Lambda <br><br>}}<br><br>r_B^{-1}.\end{array}$

14. The system of claim 13, wherein said means for generating the error indicator for the modified decision-codeword further comprises:

means for computing syndromes for the modified decision-codeword, where there are (n−

k) syndromes denoted as S₀^(el), S₁^(el), . . . , S<sub>(n−

k−

1)</sub>^(el); and

means for generating the error indicator for the modified decision-codeword using at least some of the syndromes and at least one of;

an error locator polynomial Λ

(x) for the decision-codeword and a scratch polynomial B(x) for the decision-codeword.

15. The system of claim 13, further comprising means for correcting one symbol in the decision-codeword to produce the modified decision-codeword and wherein the one symbol in the modified decision-codeword that was corrected is located at a position i_l in the modified decision-codeword, and wherein the quotient polynomials are quotients resulting from dividing Λ

(x), xΛ

(x), B(x), xB(x), and x²B(x) by xα

^il+1.

16. The system of claim 13, further comprising means for correcting one symbol in the decision-codeword to produce the modified decision-codeword and wherein the one symbol in the modified decision-codeword that was corrected is located at a position i_l in the modified decision-codeword, and wherein the remainder polynomials are remainders resulting from dividing Λ

(x), xΛ

(x), B(x), xB(x), and x²B(x) by xα

^il+1.

17. The system of claim 13, wherein said means for generating the error indicator for the modified decision-codeword further comprises:

means for computing a error locator polynomial Λ

^(el)(x) for the modified decision-codeword, where

Λ

^(el)(x)=Λ

(x)+axΛ

(x)+bxB(x) if a degree of Λ

(x) is (n−

k)/2, and

Λ

^(el)(x)=Λ

(x)+axB(x)+bx²B(x) if the degree of Λ

(x) is not (n−

k)/2.

18. The system of claim 13, wherein said means for generating the error indicator for the modified decision-codeword further comprises:

means for computing a scratch polynomial B^(el)(x) for the modified decision-codeword, where

B^(el)(x)=Λ

(x)+cB(x) if a degree of Λ

(x) is (n−

k)/2, and

B^(el)(x)=xB(x)+cB(x) if the degree of Λ

(x) is not (n−

k)/2.

19. A system for correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n,k) having a correction capability t=(n−

k)/2, in which an error indicator generation circuit that generates an error indicator for a modified decision-codeword using an error indicator for the decision-codeword, the error indicator generation circuit comprising;

a quotient computation circuit that computes quotient polynomials Q_Λ

, Q_xΛ

, Q_B, Q_xB, Q_x2B;

a remainder computation circuit that computes remainder polynomials r_Λ

, r_xΛ

, r_B, r_xB, r_x2B;

a circuit that computes quantities d₁, d₂, and d₃, where

$\begin{array}{c}{d}_1=<br><br>\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_l\right)}<br><br>\left(Q_{\mathrm{\Lambda <br><br>}}\right)}_i\right],\\ d_2=<br><br>\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_l\right)}<br><br>\left(Q_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}\right)}_i\right],<br><br>\mathrm{and}\\ d_3=<br><br>\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_l\right)}<br><br>\left(Q_{x<br><br><br><br>B}\right)}_i\right];<br><br><br><br>\end{array}$

a determinant computation circuit that computes a quantity

$D=\mathrm{determinant}<br><br>\left[\begin{array}{cc}{r}_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}& r_{\mathrm{xB}}\\ d_2& d_3\end{array}\right];<br><br>$

and

a circuit that computes quantities a, b, and c, where

$\begin{array}{c}a=<br><br>\left(r_{\mathrm{\Lambda <br><br>}}<br><br>d_3+r_{\mathrm{xB}}<br><br>d_1\right)<br><br>D^{-1},\\ b=<br><br>\{\begin{array}{c}\left(d_1+{\mathrm{ad}}_2\right)<br><br>d_3^{-1}<br><br><br><br>\mathrm{if}<br><br><br><br>d_3\ne <br><br>0\\ \left(r_{\mathrm{\Lambda <br><br>}}+{\mathrm{ar}}_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}\right)<br><br>r_{\mathrm{xB}}^{-1}<br><br><br><br>\mathrm{otherwise}\end{array};<br><br><br><br>\mathrm{and}\\ c=<br><br>r_{\mathrm{\Lambda <br><br>}}<br><br>r_B^{-1}.\end{array}$

20. The system of claim 19, wherein said error indicator generation circuit further comprises:

a syndrome computation circuit that computes syndromes for the modified decision-codeword, where there are (n−

k) syndromes denoted as S₀^(el), S₁^(el), . . . , S<sub>(n−

k−

1)</sub>^(el), where

said error indicator generation circuit generates the error indicator for the modified decision-codeword using at least some of the syndromes and at least one of;

an error locator polynomial Λ

(x) for the decision-codeword and a scratch polynomial B(x) for the decision-codeword.

21. The system of claim 19, further comprising a symbol correction circuit that corrects one symbol in the decision-codeword and wherein the one symbol in the modified decision-codeword that was corrected is located at a position i_l in the modified decision-codeword, and wherein the quotient polynomials are quotients resulting from dividing Λ

(x), xΛ

(x), B(x), xB(x), and x²B(x) by xα

^il+1.

22. The system of claim 19, further comprising a symbol correction circuit that corrects one symbol in the decision-codeword and wherein the one symbol in the modified decision-codeword that was corrected is located at a position i_l in the modified decision-codeword, and wherein the remainder polynomials are remainders resulting from dividing Λ

(x), xΛ

(x), B(x), xB(x), and x²B(x) by xα

^il+1.

23. The system of claim 19, wherein said error indicator generation circuit further comprises:

an error locator polynomial computation circuit that computes a error locator polynomial Λ

^(el)(x) for the modified decision-codeword, where

Λ

^(el)(x)=Λ

(x)+axΛ

(x)+bxB(x) if a degree of Λ

(x) is (n−

k)/2, and

Λ

^(el)(x)=Λ

(x)+axB(x)+bx²B(x) if the degree of Λ

(x) is not (n−

k)/2.

24. The system of claim 19, wherein said error indicator generation circuit further comprises:

an error locator polynomial computation circuit that computes a scratch polynomial B^(el)(x) for the modified decision-codeword, where

B^(el)(x)=Λ

(x)+cB(x) if a degree of Λ

(x) is (n−

k)/2, and

B^(el)(x)=xB(x)+cB(x) if the degree of Λ

(x) is not (n−

k)/2.