High-performance ECC decoder

A method for decoding an Error Correction Code (ECC), comprising:

• accepting coefficients of an Error Locator Polynomial (ELP), which is defined over a field and whose roots are indicative of locations of respective errors in a set of bits, which represent data that has been encoded with the ECC;
• evaluating the ELP on a given element of the field by operating on the coefficients using respective hardware-implemented serial multipliers, such that each serial multiplier performs a sequence of multiplication cycles and produces an interim result in each cycle;
• responsively to detecting, during the sequence of the multiplication cycles, at least one interim result indicating that the given element is not one of the roots of the ELP, terminating the multiplication cycles before completion of the sequence;
• and
• when the interim results indicate that the given element is a root of the ELP, correcting at least one error indicated by the given element.

A method for decoding an Error Correction Code (ECC), comprising:

• in an ECC decoder that includes multiple logic components that are clocked by a clock signal, accepting an Error Locator Polynomial (ELP), which has a given rank and is defined over a field, and whose roots are indicative of locations of respective errors in a set of bits, which represent data that has been encoded with the ECC;
• based on the rank of the ELP, selectively disabling the clock signal to some of the logic components that are used for computing the roots of the ELP;
• identifying the roots of the ELP using the logic components for which the clock signal has not been disabled;
• and
• correcting the errors indicated by the identified roots.

An Error Correction Code (ECC) decoder, comprising:

• a syndrome calculation unit, which is coupled to produce from a set of bits, which represent data that has been encoded with the ECC, multiple syndromes by applying to the bits vector operations in a vector space, wherein each syndrome is produced by applying the vector operations to the set of bits using a respective, different basis of the vector space;
• an Error Locator Polynomial (ELP) computation unit, which is configured to generate, based on the multiple syndromes, an ELP whose roots are indicative of locations of respective errors in the set of bits;
• and
• a root search unit, which is coupled to identify at least some of the roots of the ELP so as to correct the errors indicated by the identified roots;
• wherein the syndrome calculation unit is further coupled to select each basis such that the vector operations used for producing the respective syndrome comprise a multiplication of a sparse matrix;
• wherein the syndromes are defined over a field having a primitive element, and wherein the syndrome calculation unit is coupled to define a set of basis elements as respective multiples of a given vector by different powers of the primitive element of the field.