Error locator polynomial decoder method

• US 10,097,208 B2
• Filed: 03/13/2017
• Issued: 10/09/2018
• Est. Priority Date: 07/14/2015
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Ilani, Ishai, Alrod, Idan
• Primary Examiner(s): Chung, Phung M
• Application Number:
  US15/456,648
• Publication Number:
  US 20170187391A1
• Time in Patent Office: 575 Days
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] 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/1575 Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance
• CPC Class Codes: H03M 13/3746 with iterative decoding
• CPC Class Codes: H03M 13/617 Polynomial operations, e.g. operations related to generator polynomials or parity-check polynomials

Abstract

A decoder includes an error locator polynomial generator circuit configured to determine, during a first cycle of a clock signal, a first value of a parameter. The first value of the parameter is associated with a first iteration of a decode operation and is based on a value of an error locator polynomial associated with a prior iteration of the decode operation. The error locator polynomial generator circuit is further configured to determine, during a second cycle of the clock signal that sequentially follows the first cycle or during a third cycle of the clock signal that sequentially follows the second cycle, an adjusted value of the error locator polynomial. The adjusted value of the error locator polynomial is associated with a second iteration of the decode operation and is based on the first value of the parameter.

Claims

1. An apparatus comprising:

an interface configured to receive a representation of a codeword; and

a decoder coupled to the interface and configured to perform a decode operation to decode the representation of the codeword, the decoder comprising;

an error locator polynomial generator circuit configured to determine, during a first cycle of a clock signal, a first value of a parameter associated with a first iteration of the decode operation and based on a value of an error locator polynomial associated with a prior iteration of the decode operation,

wherein the error locator polynomial generator circuit is further configured to determine, during a second cycle of the clock signal that sequentially follows the first cycle or during a third cycle of the clock signal that sequentially follows the second cycle, an adjusted value of the error locator polynomial associated with a second iteration of the decode operation and based on the first value of the parameter.

2. The apparatus of claim 1, wherein the error locator polynomial generator circuit is further configured to determine a second value of the parameter during the second cycle and to determine the adjusted value of the error locator polynomial based on the second value of the parameter and during the third cycle.

3. The apparatus of claim 1, wherein the error locator polynomial generator circuit is further configured to determine the adjusted value of the error locator polynomial during the second cycle.

4. The apparatus of claim 3, further comprising a three-input multiplier of the error locator polynomial generator circuit, the three-input multiplier configured to determine the adjusted value of the error locator polynomial during the second cycle.

5. The apparatus of claim 1, wherein the error locator polynomial generator circuit is further configured to determine the adjusted value of the error locator polynomial in accordance with a Berlekamp-Massey (BM) technique using the first iteration and the second iteration.

6. The apparatus of claim 1, further comprising a syndrome generator circuit of the decoder, the syndrome generator circuit coupled to an input of the error locator polynomial generator circuit and configured to determine a syndrome polynomial based on the representation of the codeword.

7. The apparatus of claim 6, wherein the error locator polynomial generator circuit is further configured to determine, during the first cycle and based on the syndrome polynomial, a first auxiliary parameter and a second auxiliary parameter.

8. The apparatus of claim 7, wherein the error locator polynomial generator circuit is further configured to determine the adjusted value of the error locator polynomial based on the first auxiliary parameter and the second auxiliary parameter.

9. The apparatus of claim 1, further comprising an error corrector circuit of the decoder, the error corrector circuit coupled to an output of the error locator polynomial generator circuit and configured to identify one or more error locations of the representation of the codeword based on the adjusted value of the error locator polynomial.

10. The apparatus of claim 1, further comprising:

a controller that includes the interface and the decoder; and

a non-volatile memory coupled to the controller.

11. A method comprising:

initiating a decoding process at an error correction device to error correct data;

during a first cycle of a clock signal, determining a first value of an error locator polynomial adjustment parameter associated with a first iteration of the decoding process and based on a value of an error locator polynomial associated with a prior iteration of the decoding process; and

during a second cycle of the clock signal that sequentially follows the first cycle or during a third cycle of the clock signal that sequentially follows the second cycle, determining an adjusted value of the error locator polynomial associated with a second iteration of the decoding process and based on the first value of the error locator polynomial adjustment parameter.

12. The method of claim 11, further comprising determining a syndrome polynomial.

13. The method of claim 12, further comprising determining, during the first cycle and based on the syndrome polynomial, a first auxiliary parameter and a second auxiliary parameter.

14. The method of claim 13, wherein the adjusted value of the error locator polynomial is determined further based on the first auxiliary parameter and the second auxiliary parameter.

15. The method of claim 11, further comprising identifying one or more error locations of the data based on the adjusted value of the error locator polynomial.

16. The method of claim 15, wherein the one or more error locations are identified using a Chien search technique.

17. The method of claim 11, wherein the parameter corresponds to a particular value of an error locator polynomial adjustment parameter, and further comprising, during a particular iteration of the decoding process preceding the first iteration, determining the parameter based on the first value of the error locator polynomial.

18. An apparatus comprising:

means for receiving a representation of a codeword; and

means for determining, during a first cycle of a clock signal, a first value of a parameter associated with a first iteration of a decode operation to decode the representation of the codeword and based on a value of an error locator polynomial associated with a prior iteration of the decode operation and for determining, during a second cycle of the clock signal that sequentially follows the first cycle or during a third cycle of the clock signal that sequentially follows the second cycle, an adjusted value of the error locator polynomial associated with a second iteration of the decode operation and based on the first value of the parameter.

19. The apparatus of claim 18, further comprising means for determining a syndrome polynomial associated with the representation of the codeword, wherein the means for determining the first value is configured to determine the adjusted value of the error locator polynomial further based on the syndrome polynomial.

20. The apparatus of claim 18, further comprising means for identifying one or more error locations of the representation of the codeword based on the adjusted value of the error locator polynomial.