High-performance ECC decoder

摘要

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.

主权项

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; andcalculate 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.