Low power Reed-Solomon decoder

• US 8,949,697 B1
• Filed: 10/09/2012
• Issued: 02/03/2015
• Est. Priority Date: 10/11/2011
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Chang, Yuan-Mao
• Primary Examiner(s): Lamarre, Guy
• Application Number:
  US13/647,723
• Time in Patent Office: 847 Days
• Field of Search: 714/784, 714/785, 714/782, 714/E11.032, 714/757, 714/E11.033, 714/704, 714/746, 714/774, 714/776, 708/492
• US Class Current: 714/781
• 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/6502 Reduction of hardware complexity or efficient processing

Abstract

Systems, methods, apparatus, and techniques are provided for decoding a codeword. A plurality of syndrome values is received corresponding to a received codeword and a value of an error locator polynomial corresponding to the received codeword is initialized. The value of the error locator polynomial is iteratively updated by processing the plurality of syndrome values, where each iterative update includes determining a current degree of the error locator polynomial and terminating the iterative updating in response to a determination that the current degree of the error locator polynomial exceeds a threshold value.

Claims

1. A decoder for decoding a received codeword, the decoder comprising:

an error locator polynomial determination module configured to;

receive a plurality of syndrome values corresponding to the received codeword, and

iteratively update a value of an error locator polynomial initialized to the received codeword by processing the plurality of syndrome values, wherein each iterative update comprises;

determining a current degree of the error locator polynomial,

updating a number of errors, and

terminating the iterative updating in response to a determination that the current degree of the error locator polynomial exceeds a maximum number of correctable errors of the received codeword.

2. The decoder of claim 1, wherein the error locator polynomial determination module is further configured to:

determine a discrepancy parameter;

compare the discrepancy parameter to a threshold value in response to a determination that a performed number of iterations of the iterative updating is equal to a number of parity bits in the received codeword; and

selectively initiate a Chien search based on the comparison.

3. The decoder of claim 1, wherein the error locator polynomial determination module is further configured to:

initialize a degree counter parameter; and

increment a value of the degree counter parameter during each iteration of the iterative updating in which the error locator polynomial is not modified.

4. The decoder of claim 1, wherein the iterative updating of the value of the error locator polynomial is performed based on a Berlekamp-Massey algorithm.

5. The decoder of claim 1, further comprising a roots and error value determination module configured to:

receive the error locator polynomial from the error locator polynomial determination module; and

analyze the value of the error locator polynomial at a plurality of points in a domain of the error locator polynomial, wherein the evaluation at a given point comprises;

determining a value of error locator polynomial at the point; and

determining a value of a derivative of the error locator polynomial at the point.

6. The decoder of claim 5, wherein the analyzing the value of the error locator polynomial at a plurality of points is performed based on a modified Chien search.

7. The decoder of claim 1, wherein the roots and error value determination module is further configured to:

determine whether a double root condition is present in the error locator polynomial; and

declare a decoding failure in response to determining that the double root condition is present.

8. The decoder of claim 1, wherein the error locator polynomial determination module is further configured to terminate a scheduled modified Chien search in response to a determination that a current degree of the error locator polynomial exceeds a threshold value.

9. The decoder of claim 1, wherein the error locator polynomial determination module is further configured to determine:

a plurality of locations in the received codeword that include a symbol error; and

an error value associated with each of the determined plurality of locations.

10. The decoder of claim 1, wherein each iterative update further comprises:

computing a discrepancy parameter based on the error locator polynomial and the plurality of syndrome values.

11. A method for decoding a codeword, the method comprising:

receiving a plurality of syndrome values corresponding to the received codeword;

initializing a value of an error locator polynomial corresponding to the received codeword; and

iteratively updating the value of the error locator polynomial by processing the plurality of syndrome values, wherein each iterative update comprises;

determining a current degree of the error locator polynomial,

updating a number of errors, and

terminating the iterative updating in response to a determination that the current degree of the error locator polynomial exceeds a maximum number of correctable errors of the received codeword.

12. The method of claim 11, further comprising:

determining a discrepancy parameter;

comparing the discrepancy parameter to a threshold value in response to a determination that a performed number of iterations of the iterative updating is equal to a number of parity bits in the received codeword; and

selectively initiating a Chien search based on the comparison.

13. The method of claim 11, further comprising:

initializing a degree counter parameter; and

incrementing a value of the degree counter parameter during each iteration of the iterative updating in which the error locator polynomial is not modified.

14. The method of claim 11, wherein the iterative updating of the value of the error locator polynomial is performed based on a Berlekamp-Massey algorithm.

15. The method of claim 11, further comprising:

receiving the error locator polynomial from the error locator polynomial determination module; and

analyzing the value of the error locator polynomial at a plurality of points in a domain of the error locator polynomial, wherein the evaluation at a given point comprises;

determining a value of the error locator polynomial at the point; and

determining a value of a derivative of the error locator polynomial at the point.

16. The method of claim 15, wherein the analyzing the value of the error locator polynomial at a plurality of points is performed based on a modified Chien search.

17. The method of claim 11, further comprising:

determining whether a double root condition is present in the error locator polynomial; and

declaring a decoding failure in response to determining that the double root condition is present.

18. The method of claim 11, further comprising terminating a scheduled modified Chien search in response to a determination that a current degree of the error locator polynomial exceeds a threshold value.

19. The method of claim 11, further comprising determining:

a plurality of locations in the received codeword that include a symbol error; and

an error value associated with each of the determined plurality of locations.

20. The method of claim 11, further comprising computing a discrepancy parameter based on the error locator polynomial and the plurality of syndrome values.