Iterative Reed-Solomon error-correction decoding

• US 7,328,395 B1
• Filed: 12/07/2004
• Issued: 02/05/2008
• 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/006,381
• Time in Patent Office: 1,155 Days
• Field of Search: 714/784, 714/780
• US Class Current: 714/780
• 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;

iteratively;

determining whether errors in a 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;

where;

the modified decision-codeword is a decision-codeword in a next iteration.

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

3. The method of claim 1, wherein each iteration further comprises:

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,

where the second modified decision-codeword is a decision-codeword in a next iteration.

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

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

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

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

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

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

k−

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

generating an 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.

8. The method of claim 7, wherein said generating the error indicator for the modified decision-codeword further comprises the steps in EQ1, EQ2, EQ3, and EQ4.

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

solving for coefficients a, b, and c using the constraints in EQ5 and EQ12.

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

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=\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_1\right)}<br><br>\left(Q_{\mathrm{\Lambda <br><br>}}\right)}_i\right],\\ d_2=\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_1\right)}<br><br>\left(Q_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}\right)}_i\right],\mathrm{and}\\ d_3=\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_1\right)}<br><br>\left(Q_{\mathrm{xB}}\right)}_i\right];<br><br>\end{array}$

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

computing quantities a, b, and c, where

$\begin{array}{c}a=\left(r_{\mathrm{\Lambda <br><br>}}<br><br>d_3+r_{\mathrm{xB}}<br><br>d_1\right)<br><br>D^{-1},\\ b=\{\begin{array}{cc}\left(d_1+{\mathrm{ad}}_2\right)<br><br>d_3^{-1}& \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}& \mathrm{otherwise}\end{array};<br><br>\mathrm{and}\\ c=r_{\mathrm{\Lambda <br><br>}}<br><br>r_B^{-1}.\end{array}$

11. The method of claim 10, wherein the 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.

12. The method of claim 10, wherein the 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.

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

computing the error locator polynomial Λ

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

Λ

^(e1)(x)=Λ

(x)+axΛ

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

(x) is (n−

k)/2, and

Λ

^(e1)(x)=Λ

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

(x) is not (n−

k)/2.

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

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

B^(e1)(x)=Λ

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

(x) is (n−

k)/2, and

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

(x) is not (n−

k)/2.

15. A method of correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n+Δ

,k) that corresponds to a number (n−

k+Δ

) of syndromes, the method comprising;

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

k+Δ

) syndromes denoted as S₀, S₁, . . . , S<sub>n−

k+Δ

−

1</sub>, and where Δ

is positive;

determining whether errors in the decision-codeword can be completely corrected, by using at least some of the syndromes; and

correcting errors in the decision-codeword if the errors in the decision-codeword can be completely corrected.

16. The method of claim 15, wherein said determining whether errors in the decision-codeword can be completely corrected comprises:

generating an error locator polynomial Λ

(x) for the decision-codeword;

computing quantities

$\underset{j=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left(S_{2<br><br>t+i-1-j}<br><br>{\mathrm{\Lambda <br><br>}}_j\right),$

i=1, . . . , Δ

, where t=(n−

k)/2;

performing a Chien search for the error locator polynomial Λ

(x) if the quantities are equal to zero; and

determining that errors in the decision codeword can be completely corrected if the Chien search finds that a number of distinct roots of the error locator polynomial Λ

(x) is equal to a degree of the error locator polynomial Λ

(x).

17. The method of claim 16, wherein said determining whether errors in the decision-codeword can be completely corrected further comprises:

determining that errors in the decision-codeword cannot be completely corrected if the quantities are not equal to zero.

18. 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, the system comprising;

means for determining whether errors in a 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;

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

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

19. The system of claim 18, further comprising:

means for correcting errors in the decision-codeword if the degree of the errors does not exceed the correction capability.

20. The system of claim 18, further comprises:

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

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

21. The system of claim 18, wherein said means for modifying the decision-codeword to produce a modified decision-codeword comprises:

means for referring to an incidence vector to select an error event;

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

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

22. The system of claim 21, wherein said means for correcting the symbol comprises:

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

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

23. A read channel comprising the system of claim 18.

24. A disk drive comprising the read channel of claim 23.

25. The system of claim 18, wherein said means for modifying the decision-codeword to produce a modified decision-codeword comprises:

means for correcting one symbol in the decision-codeword.

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

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

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

k−

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

means for generating an 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.

27. The system of claim 26, wherein said means for generating the error indicator for the modified decision-codeword further comprises means for computing the steps in EQ1, EQ2, EQ3, and EQ4.

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

means for solving for coefficients a, b, and c using the constraints in EQ5 and EQ12.

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

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=\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_t\right)}<br><br>\left(Q_{\mathrm{\Lambda <br><br>}}\right)}_i\right],\\ d_2=\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_t\right)}<br><br>\left(Q_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}\right)}_i\right],\mathrm{and}\\ d_3=\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_t\right)}<br><br>\left(Q_{\mathrm{xB}}\right)}_i\right];<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=\left(r_{\mathrm{\Lambda <br><br>}}<br><br>d_3+r_{\mathrm{xB}}<br><br>d_1\right)<br><br>D^{-1},\\ b=\{\begin{array}{cc}\left(d_1+{\mathrm{ad}}_2\right)<br><br>d_3^{-1}& \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}& \mathrm{otherwise}\end{array};<br><br>\mathrm{and}\\ c=r_{\mathrm{\Lambda <br><br>}}<br><br>r_B^{-1}.\end{array}$

30. The system of claim 29, wherein the 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.

31. The system of claim 29, wherein the 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.

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

means for computing the error locator polynomial Λ

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

Λ

^(e1)(x)=Λ

(x)+axΛ

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

(x) is (n−

k)/2, and

Λ

^(e1)(x)=Λ

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

(x) is not (n−

k)/2.

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

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

B^(e1)(x)=Λ

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

(x) is (n−

k)/2, and

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

(x) is not (n−

k)/2.

34. A system for correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n+Δ

,k) that corresponds to a number (n−

k+Δ

) of syndromes, the system comprising;

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

k+Δ

) syndromes denoted as S₀, S₁, . . . , S<sub>n−

k+Δ

−

1</sub>, and where Δ

is positive;

means for determining whether errors in the decision-codeword can be completely corrected, by using at least some of the syndromes; and

means for correcting errors in the decision-codeword if the errors in the decision-codeword can be completely corrected.

35. The system of claim 34, wherein said means for determining whether errors in the decision-codeword can be completely corrected comprises:

means for generating an error locator polynomial Λ

(x) for the decision-codeword;

means for computing quantities

$\underset{j=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left(S_{2<br><br>t+i-1-j}<br><br>{\mathrm{\Lambda <br><br>}}_j\right),$

i=1, . . . , Δ

, where t=(n−

k)/2;

means for performing a Chien search for the error locator polynomial Λ

(x) if the quantities are equal to zero; and

means for determining that errors in the decision codeword can be completely corrected if the Chien search finds that a number of distinct roots of the error locator polynomial Λ

(x) is equal to a degree of the error locator polynomial Λ

(x).

36. The system of claim 35, wherein said means for determining whether errors in the decision-codeword can be completely corrected further comprises:

means for determining that errors in the decision-codeword cannot be completely corrected if the quantities are not equal to zero.

37. A read channel comprising the system of claim 34.

38. A disk drive comprising the read channel of claim 37.

39. 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, the system comprising;

an excessive-error detection circuit that determines whether errors in a 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;

a modification circuit that modifies the decision-codeword to produce a modified decision-codeword if the degree of the errors exceeds the correction capability; and

an error indicator generation circuit that generates an error indicator for the modified decision-codeword using the error indicator for the decision-codeword.

40. The system of claim 39, further comprising:

a correction circuit that corrects errors in the decision-codeword if the degree of the errors does not exceed the correction capability.

41. The system of claim 39, further comprises:

a second modification circuit that modifies the decision-codeword to produce a second modified decision-codeword, if the degree of the errors exceeds the correction capability; and

a second error indicator generation circuit that generates an error indicator for the second modified decision-codeword using the error indicator for the decision-codeword.

42. The system of claim 39, wherein said modification circuit comprises:

a selection circuit that refers to an incidence vector to select an error event;

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

a symbol correction circuit that corrects the symbol by replacing a value of the symbol with a next-most-likely value.

43. The system of claim 42, wherein said symbol correction circuit comprises:

a retrieval circuit that refers to the list of error events to obtain a difference value associated with the symbol; and

a subtraction circuit that computes the next-most-likely value for the symbol by subtracting the difference value from the value of the symbol.

44. A read channel comprising the system of claim 39.

45. A disk drive comprising the read channel of claim 44.

46. The system of claim 39, wherein said error indicator generation circuit comprises:

a symbol correction circuit that corrects one symbol in the decision-codeword.

47. The system of claim 42, wherein said error indicator generation circuit comprises:

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

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

k−

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

said error generation circuit generates an 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.

48. The system of claim 47, wherein said error indicator generation circuit generates the error indicator for the modified decision-codeword according to EQ1, EQ2, EQ3, and EQ4.

49. The system of claim 48, wherein said error indicator generation circuit:

a coefficient computing circuit that solves for coefficients a, b, and c using the constraints in EQ5 and EQ12.

50. The system of claim 47, wherein said error indicator generation circuit further comprises:

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=\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_t\right)}<br><br>\left(Q_{\mathrm{\Lambda <br><br>}}\right)}_i\right],\\ d_2=\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_t\right)}<br><br>\left(Q_{x<br><br><br><br>\mathrm{\Lambda <br><br>}}\right)}_i\right],\mathrm{and}\\ d_3=\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left[{S_{n-k-i}^{\left(e_t\right)}<br><br>\left(Q_{\mathrm{xB}}\right)}_i\right];<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=\left(r_{\mathrm{\Lambda <br><br>}}<br><br>d_3+r_{\mathrm{xB}}<br><br>d_1\right)<br><br>D^{-1},\\ b=\{\begin{array}{cc}\left(d_1+{\mathrm{ad}}_2\right)<br><br>d_3^{-1}& \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}& \mathrm{otherwise}\end{array};<br><br>\mathrm{and}\\ c=r_{\mathrm{\Lambda <br><br>}}<br><br>r_B^{-1}.\end{array}$

51. The system of claim 50, wherein the 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.

52. The system of claim 50, wherein the 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.

53. The system of claim 50, wherein said error indicator generation circuit further comprises:

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

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

Λ

^(e1)(x)=Λ

(x)+axΛ

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

(x) is (n−

k)/2, and

Λ

^(e1)(x)=Λ

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

(x) is not (n−

k)/2.

54. The system of claim 50, wherein said error indicator generation circuit further comprises:

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

B^(e1)(x)=Λ

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

(x) is (n−

k)/2, and

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

(x) is not (n−

k)/2.

55. A system for correcting errors in a decision-codeword by employing a Reed Solomon error-correction code RS(n+Δ

,k) that corresponds to a number (n−

k+Δ

) of syndromes, the system comprising;

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

k+Δ

) syndromes denoted as S₀, S₁, . . . , S<sub>n−

k+Δ

−

1</sub>, and where Δ

is positive;

an excessive-error detection circuit that determines whether errors in the decision-codeword can be completely corrected, by using at least some of the syndromes; and

a correction circuit that corrects errors in the decision-codeword if the errors in the decision-codeword can be completely corrected.

56. The system of claim 55, wherein said an excessive-error detection circuit comprises:

an error location polynomial computation circuit that generates an error locator polynomial Λ

(x) for the decision-codeword;

a circuit that computes quantities

$\underset{j=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left(S_{2<br><br>t+i-1-j}<br><br>{\mathrm{\Lambda <br><br>}}_j\right),$

i=1, . . . , Δ

, where t=(n−

k)/2;

a Chien search circuit that performs a Chien search for the error locator polynomial Λ

(x) if the quantities are equal to zero; and

an excessive-error detection circuit that determines that errors in the decision-codeword can be completely corrected if the Chien search finds that a number of distinct roots of the error locator polynomial Λ

(x) is equal to a degree of the error locator polynomial Λ

(x).

57. The system of claim 56, wherein said excessive-error detection circuit determines that errors in the decision-codeword cannot be completely corrected if the quantities are not equal to zero.

58. A read channel comprising the system of claim 55.

59. A disk drive comprising the read channel of claim 58.

60. A computer-readable storage medium containing a computer program, the computer program comprising instructions for execution on a computer to employ a Reed-Solomon error-correction code RS(n,k) having correction capability t=(n−

k)/2, and to;

iteratively;

determine whether errors in a 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;

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

generate an error indicator for the modified decision-codeword using the error indicator for the decision-codeword;

where;

the modified decision-codeword is a decision-codeword in a next iteration.

61. The computer-readable storage medium of claim 60, said computer program further comprising instructions to:

correct errors in the decision-codeword if the degree of the errors does not exceed the correction capability.

62. The computer-readable storage medium of claim 60, said computer program further comprising instructions to:

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

generate an error indicator for the second modified decision-codeword using the error indicator for the decision-codeword,

where the second modified decision-codeword is a decision-codeword in a next iteration.

63. The computer-readable storage medium of claim 60, wherein said instructions to modify the decision-codeword to produce a modified decision-codeword comprise instructions to:

refer to an incidence vector to select an error event;

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

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

64. The computer-readable storage medium of claim 63, wherein said instructions to correct the symbol comprise instructions to:

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

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

65. The computer-readable storage medium of claim 60, wherein said instructions to modify the decision-codeword to produce a modified decision-codeword comprise instructions to:

correct one symbol in the decision-codeword.

66. The computer-readable storage medium of claim 65, wherein said instructions to generate the error indicator for the modified decision-codeword comprise instructions to:

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

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

k−

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

generate an 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.

67. The computer-readable storage medium of claim 66, wherein said instructions to generate the error indicator for the modified decision-codeword further comprises the steps in EQ1, EQ2, EQ3, and EQ4.

68. The computer-readable storage medium of claim 67, wherein said instructions to generate the error indicator for the modified decision-codeword further comprises:

instructions to solve for coefficients a, b, and c using the constraints in EQ5 and EQ12.

69. The computer-readable storage medium of claim 66, wherein said instructions to generate the error indicator for the modified decision-codeword comprise instructions to:

compute quotient polynomials Q_Λ

, Q_xΛ

, Q_B, Q_xB, Q_x2B;

compute remainder polynomials r_Λ

, r_xΛ

, r_B, r_xB, r_x2B;

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

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

compute 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

compute quantities a, b, and c, where

$\begin{array}{c}a=\left(r_{\mathrm{\Lambda <br><br>}}<br><br>d_3+r_{\mathrm{xB}}<br><br>d_1\right)<br><br>D^{-1},\\ b=\{\begin{array}{cc}\left(d_1+{\mathrm{ad}}_2\right)<br><br>d_3^{-1}& \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}& \mathrm{otherwise}\end{array};<br><br>\mathrm{and}\\ c=r_{\mathrm{\Lambda <br><br>}}<br><br>r_B^{-1}.\end{array}$

70. The computer-readable storage medium of claim 69, wherein the 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.

71. The computer-readable storage medium of claim 69, wherein the 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.

72. The computer-readable storage medium of claim 69, wherein said instructions to generate the error indicator for the modified decision-codeword comprise instructions to:

compute the error locator polynomial Λ

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

Λ

^(e1)(x)=Λ

(x)+axΛ

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

(x) is (n−

k)/2, and

Λ

^(e1)(x)=Λ

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

(x) is not (n−

k)/2.

73. The computer-readable storage medium of claim 69, wherein said instructions to generate the error indicator for the modified decision-codeword comprise instructions to:

compute the scratch polynomial B^(e1)(x) for the modified decision-codeword, where

B^(e1)(x)=Λ

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

(x) is (n−

k)/2, and

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

(x) is not (n−

k)/2.

74. A computer-readable medium containing a computer program, the computer program comprising instructions for execution on a computer to employ a Reed Solomon error-correction code RS(n+Δ

,k) that corresponds to a number (n−

k+Δ

) of syndromes, and to;

compute syndromes for a decision-codeword, where there are (n−

k+Δ

) syndromes denoted as S₀, S₁, . . . , S<sub>n−

k+Δ

−

1</sub>, and where Δ

is positive;

determine whether errors in the decision-codeword can be completely corrected, by using at least some of the syndromes; and

correct errors in the decision-codeword if the errors in the decision-codeword can be completely corrected.

75. The computer-readable storage medium of claim 74, wherein said instructions to determine whether errors in the decision-codeword can be completely corrected comprise instructions to:

generate an error locator polynomial Λ

(x) for the decision-codeword;

compute quantities

$\underset{i=0}{\overset{t}{\sum <br><br>}}<br><br><br><br>\left(S_{2<br><br>t+1-i}<br><br>{\mathrm{\Lambda <br><br>}}_i\right),$

i=1, . . . , Δ

, where t=(n−

k)/2;

perform a Chien search for the error locator polynomial Λ

(x) if the quantities are equal to zero; and

determine that errors in the decision-codeword can be completely corrected if the Chien search finds that a number of distinct roots of the error locator polynomial Λ

(x) is equal to a degree of the error locator polynomial Λ

(x).

76. The computer-readable storage medium of claim 75, wherein said instructions to determine whether errors in the decision-codeword can be completely corrected comprise instructions to:

determine that errors in the decision-codeword cannot be completely corrected if the quantities are not equal to zero.