Reed-Solomon decoder

• US 6,487,692 B1
• Filed: 12/21/1999
• Issued: 11/26/2002
• Est. Priority Date: 12/21/1999
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Morelos-Zaragoza, Robert
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US09/468,577
• Time in Patent Office: 1,071 Days
• Field of Search: 714/784
• US Class Current: 714/784
• CPC Class Codes: H03M 13/1525 Determination and particular use of error location polynomials
• CPC Class Codes: H03M 13/25 Error detection or forward error correction by signal space coding, i.e. adding redundancy in the signal constellation, e.g. Trellis Coded Modulation [TCM] modulation codes H03M13/31
• CPC Class Codes: H03M 13/41 using the Viterbi algorithm or Viterbi processors

Abstract

A Reed-Solomon decoder capable of correcting two symbol errors in a codeword of a Reed-Solomon RS(128,122,7) code over a Galois field GF(128) is provided. In an exemplary embodiment, the Reed-Solomon decoder is suitable for use in cable modems with little or no loss in error performance over Reed-Solomon decoder correcting three errors in a codeword.

Claims

1. A method of correcting symbol errors in a codeword of an extended Reed-Solomon RS (128,122,7) code over a Galois field GF(128), comprising:

calculating syndromes for the codeword;

determining the number of symbol errors in the codeword wherein up to two symbol errors in the codeword can be corrected;

if the number of symbol errors is greater than zero, finding the coefficients of an error locator polynomial;

if the number of symbol errors is greater than zero, locating the positions of the errors in the codeword; and

if the number of symbol errors is greater than zero, finding the values of the symbol errors.

2. The method as claimed in claim 1, wherein the number of syndromes calculated is four.

3. The method as claimed in claim 2, wherein locating the positions of the errors in the codeword comprises performing a Chien search.

4. The method as claimed in claim 2, wherein finding the values of the symbol errors comprises solving the equation $\left[\begin{array}{cc}{X}_1& X_2\\ X_1^2& X_2^2\end{array}\right]$

[Y1Y2]=[S1S2].

5. The decoder according to claim 2, wherein the means for locating the positions of the errors in the codeword comprises a Chien search module.

6. The decoder according to claim 2, wherein the means for finding the values of the symbol errors solves the equation $\left[\begin{array}{cc}{X}_1& X_2\\ X_1^2& X_2^2\end{array}\right]$

[Y1Y2]=[S1S2]

to find the values of the symbol errors.

7. The method as claimed in claim 2, wherein the error locator polynomial has the form $\sigma$



(x)=∑

i=0e

σ

i

xi.

8. The method as claimed in claim 7, wherein determining the number of symbol errors in the codeword further comprises testing the rank of the equation $\left[\begin{array}{cc}{S}_1& S_2\\ S_2& S_3\end{array}\right]$

[σ

2σ

1]=[S3S4].

9. The method as claimed in claim 7, wherein finding the coefficients of the error locator polynomial by solving the equation $\left[\begin{array}{cc}{S}_1& S_2\\ S_2& S_3\end{array}\right]$

[σ

2σ

1]=[S3S4].

10. A machine readable medium carrying a program of instructions for causing a machine to execute a method for correcting symbol errors in a codeword of an extended Reed-Solomon RS (128,122,7) code over a Galois field GF(128), the method comprising:

calculating syndromes for the codeword;

determining the number of symbol errors in the codeword wherein up to two symbol errors in the codeword can be corrected;

if the number of symbol errors is greater than zero, finding the coefficients of an error locator polynomial;

if the number of symbol errors is greater than zero, locating the positions of the errors in the codeword; and

if the number of symbol errors is greater than zero, finding the values of the symbol errors.

11. The machine readable medium carrying a program of instructions as claimed in claim 10, wherein the number of syndromes calculated is four.

12. The machine readable program of instructions as claimed in claim 11, wherein locating the positions of the errors in the codeword comprises performing a Chien search.

13. The machine readable program of instructions as claimed in claim 11, wherein finding the values of the symbol errors comprises solving the equation $\left[\begin{array}{cc}{X}_1& X_2\\ X_1^2& X_2^2\end{array}\right]$

[Y1Y2]=[S1S2].

14. The machine readable program of instructions as claimed in claim 11, wherein the error locator polynomial has the form $\sigma$



(x)=∑

i=0e

σ

i

xi.

15. The machine readable program of instructions as claimed in claim 14, wherein determining the number of symbol errors in the codeword further comprises testing the rank of the equation $\left[\begin{array}{cc}{S}_1& S_2\\ S_2& S_3\end{array}\right]$

[σ

2σ

1]=[S3S4].

16. The machine readable program of instructions as claimed in claim 14, wherein finding the coefficients of the error locator polynomial by solving the equation $\left[\begin{array}{cc}{S}_1& S_2\\ S_2& S_3\end{array}\right]$

[σ

2σ

1]=[S3S4].

17. A decoder capable of correcting symbol errors in a codeword of an extended Reed-Solomon RS (128,122,7) code over a Galois field GF(128), comprising:

means for calculating syndromes for the codeword;

means for determining the number of symbol errors in the codeword wherein up to two symbol errors in the codeword can be corrected;

means for finding the coefficients of an error locator polynomial if the number of symbol errors is greater than zero;

means for locating the positions of the symbol errors in the codeword if the number of symbol errors is greater than zero; and

means for finding the values of the symbol errors if the number of symbol errors is greater than zero.

18. The decoder according to claim 17, wherein the number of syndromes calculated by the syndrome calculating means is four.

19. The decoder according to claim 18, wherein the error locator polynomial has the form $\sigma$



(x)=∑

i=0e

σ

i

xi.

20. The decoder according to claim 19, wherein the means for determining the number of symbol errors in the codeword tests the rank of the equation $\left[\begin{array}{cc}{S}_1& S_2\\ S_2& S_3\end{array}\right]$

[σ

2σ

1]=[S3S4]

to determine the number of symbol errors in the codeword.

21. The decoder according to claim 19, wherein the means for finding the coefficients of an error locator polynomial solves the equation $\left[\begin{array}{cc}{S}_1& S_2\\ S_2& S_3\end{array}\right]$

[σ

2σ

1]=[S3S4]

to find the coefficients of the error locator polynomial.