High-performance ECC decoder

Patent metadata

Field	Value
Publication number	US-9535788-B2
Application number	US-201514821124-A
Country	US
Kind code	B2
Filing date	Aug 7, 2015
Priority date	Apr 10, 2008
Publication date	Jan 3, 2017
Grant date	Jan 3, 2017

Abstract

Methods for Error Correction Code (ECC) decoding include producing syndromes from a set of bits, which represent data that has been encoded with the ECC. An Error Locator Polynomial (ELP) is generated based on the syndromes. At least some of the ELP roots are identified, and the errors indicated by these roots are corrected. Each syndrome may be produced by applying to the bits vector operations in a vector space. Each syndrome is produced by applying vector operations using a different basis of the vector space. The ELP may be evaluated on a given field element by operating on ELP coefficients using serial multipliers, wherein each serial multiplier performs a sequence of multiplication cycles and produces an interim result in each cycle. Responsively to detecting at least one interim result indicating that the given element is not an ELP root, the multiplication cycles are terminated before completion of the sequence.

First claim

The invention claimed is:

1. A memory controller, comprising:
circuitry configured to:
receive data from a memory, wherein the data is encoded with an Error Correction Code (ECC), wherein the data includes at least one code word;
wherein the ECC is defined over a field, wherein the field includes a plurality of field elements;
calculate a syndrome for the at least one code word; and
calculate an Error Locator Polynomial (ELP) dependent upon the syndrome;

a plurality of registers, wherein each register of the plurality of registers is configured to a given one of a plurality of coefficients of the ELP;
a first plurality of multipliers, wherein a first multiplier of the first plurality of multipliers is configured to multiply a first one of the plurality of the coefficients of the ELP by a first corresponding power of a first field element of the plurality of field elements to generate a first bit of an interim product during a first cycle; and
a second plurality of multipliers, wherein each multiplier of the second plurality of multipliers is configured to calculate, in parallel, a next power of a second field element of the plurality of field elements in response to a determination that the interim product is non-zero.

2. The memory controller of claim 1 , wherein a second multiplier of the first plurality of multipliers is configured to multiply a second one of the plurality of coefficients of the ELP by a second corresponding power of a second field element of the plurality of field elements to generate a second bit of the interim product during a second cycle in response to a determination that the interim product is zero, wherein the second cycle occurs subsequent to the first cycle.

3. The memory controller of claim 1 , wherein the field includes a Galois field.

4. The memory controller of claim 1 , wherein the ECC includes a Reed-Solomon (RS) code.

5. The memory controller of claim 1 , wherein the circuitry is further configured to determine roots of the ELP dependent upon the interim product, wherein the roots of the ELP are indicative of locations of errors within the at least one code word.

6. The memory controller of claim 5 , wherein the circuitry is further configured modify a frequency of a clock signal dependent upon a number of errors in the at least one code word.

7. A method, comprising:
receiving data from a memory, wherein the data is encoded with an Error Correction Code (ECC), wherein the data includes at least one code word;
wherein the ECC is defined over a field, wherein the field includes a plurality of field elements;
calculating a syndrome for the at least one code word;
calculating an Error Locator Polynomial (ELP) dependent upon the syndrome;
storing a given one of a plurality of coefficients of the ELP in a respective one of a plurality of registers;
multiplying, by a first multiplier of a first plurality of multipliers, a first one of the plurality of coefficients of the ELP by a first corresponding power of a first field element of the plurality of field elements to generate a first bit of an interim product during a first cycle; and
calculating, by each multiplier of a second plurality of multipliers, in parallel, a next power of a second field element of the plurality of field elements in response to determining that the interim product is non-zero.

8. The method of claim 7 , wherein the field includes a Galois field.

9. The method of claim 7 , wherein the ECC includes a Reed-Solomon (RS) code.

10. The method of claim 7 , wherein the ECC includes a Bose-Chaudhuri-Hocquenghem (BCH) code.

11. The method of claim 7 , further comprising determining roots of the ELP dependent upon the interim product, wherein the roots of the ELP are indicative of locations of errors within the at least one code word.

12. The method of claim 11 , further comprising modifying a frequency of a clock signal dependent upon a number of errors in the at least one code word.

13. The method of claim 12 , wherein modifying the frequency of the clock signal includes decreasing the frequency of the clock signal in response to determining that the number of errors in the at least one code word is greater than a predetermined value.

14. A data storage apparatus, comprising:
a memory; and
a controller coupled to the memory, wherein the controller is configured to:
receive data from a memory, wherein the data is encoded with an Error Correction Code (ECC), wherein the data includes at least one code word;
wherein the ECC is defined over a field, wherein the field includes a plurality of field elements;
calculate a syndrome for the at least one code word; and
calculate an Error Locator Polynomial (ELP) dependent upon the syndrome;
store a given one of a plurality of coefficients of the ELP in a respective one of a plurality of registers;
multiply, by a first multiplier of a first plurality of multipliers, a first one of the plurality of coefficients of the ELP by a first corresponding power of a first field element of the plurality of field elements to generate a first bit of an interim product during a first cycle; and
calculate, by each multiplier of a second plurality of multipliers, in parallel, a next power of a second field element of the plurality of field elements in response to a determination that the interim product is non-zero.

15. The data storage apparatus of claim 14 , wherein the controller is further configured to multiply, by a second multiplier of the first plurality of multipliers, a second one of the plurality of coefficients of the ELP by a second corresponding power of a second field element of the plurality of field elements to generate a second bit of the interim product during a second cycle in response to a determination that the interim product is zero, wherein the second cycle occurs subsequent to the first cycle.

16. The data storage apparatus of claim 14 , wherein the field includes a Galois field.

17. The data storage apparatus of claim 14 , wherein the ECC includes a Reed-Solomon (RS) code.

18. The data storage apparatus of claim 14 , wherein the controller is further configured to determine roots of the ELP dependent upon the interim product, wherein the roots of the ELP are indicative of locations of errors within the at least one code word.

19. The data storage apparatus of claim 18 , wherein the controller is further configured modify a frequency of a clock signal dependent upon a number of errors in the at least one code word.

20. The data storage apparatus of claim 19 , wherein to modify the frequency of the clock signal, the controller is further configured to decrease the frequency of the clock signal in response to a determination that the number of errors in the at least one code word is greater than a predetermined value.

Assignees

• Apple Inc

Inventors

• Anholt Micha
• Sommer Naftali
• Semo Gil
• Inbar Tal

Classifications

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H03M13/03

  Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words · CPC title

• H03M13/1525 Primary

  Determination and particular use of error location polynomials · CPC title

• H03M13/45

  Soft decoding, i.e. using symbol reliability information (H03M13/41 takes precedence) · CPC title

• H03M13/617

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