Error locator polynomial decoder method

Patent metadata

Field	Value
Publication number	US-10097208-B2
Application number	US-201715456648-A
Country	US
Kind code	B2
Filing date	Mar 13, 2017
Priority date	Jul 14, 2015
Publication date	Oct 9, 2018
Grant date	Oct 9, 2018

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.

First claim

What is claimed is:

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.

Assignees

• Western Digital Tech Inc

Inventors

• Ilani Ishai
• Alrod Idan

Classifications

• H03M13/617

  Polynomial operations, e.g. operations related to generator polynomials or parity-check polynomials · CPC title

• G06F11/1068

  in sector programmable memories, e.g. flash disk (G06F11/1072 takes precedence) · CPC title

• H03M13/153 Primary

  using the Berlekamp-Massey algorithm · CPC title

• H03M13/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 title

• G11C29/52

  Protection of memory contents; Detection of errors in memory contents · CPC title