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. An memory controller, comprising:
an Error Correction Code (ECC) unit configured to:
receive data from a memory, wherein the data is encoded with an ECC, and includes at least one code word;
calculate a syndrome for the at least one code word;
calculate an Error Locator Polynomial (ELP) dependent upon the calculated syndrome; and
modify a frequency of a clock signal dependent upon an actual number of errors in the at least one code word; and
a processing unit coupled to the ECC unit, wherein the processing unit is configured to:
receive the clock signal; and
determine roots of the ELP.
2. The memory controller of claim 1 , wherein to calculate the syndrome for the at least one code word, the ECC unit is further configured to multiply the at least one code word by a parity matrix.
3. The memory controller of claim 1 , wherein to modify the frequency of the clock signal, the ECC unit is further configured to decrease the frequency of the clock signal responsive to a determination that the actual number of errors in the at least one code word is greater than a predetermined threshold value.
4. The memory controller of claim 1 , wherein to modify the frequency of the clock signal, the ECC unit is further configured to increase the frequency of the clock signal responsive to a determination that the actual number of errors in the at least one code word is less than a predetermined threshold value.
5. The memory controller of claim 1 , wherein to modify the frequency of the clock signal, the ECC unit is further configured to compare the actual number of errors in the at least one code word to a maximum number of correctable errors.
6. The memory controller of claim 1 , wherein to calculate the syndrome, the ECC unit is further configured to apply vector operations in a vector space to data bits included in the at least one code word.
7. The memory controller of claim 6 , wherein syndrome is defined over a field, and wherein the field includes a primitive element.
8. A method for operating a memory controller, the method comprising:
receiving data from a memory, wherein the data is encoded with an Error Correction Code (ECC), and wherein the received data includes at least one code word;
calculating a syndrome for the at least one code word;
calculating an Error Locator Polynomial (ELP) dependent upon the calculating syndrome;
modifying a clock rate of a processing unit dependent upon an actual number of errors in the at least one code word; and
determining, by the processing unit, roots of the ELP dependent upon the clock signal.
9. The method of claim 8 , wherein calculating the syndrome for the at least one code word comprising multiplying the code word by a parity matrix.
10. The method of claim 8 , wherein modifying the clock rate of the processing unit comprised decreasing the clock rate of the processing unit responsive to a determination that the actual number of errors in the at least one code word is greater than a predetermined threshold value.
11. The method of claim 8 , wherein modifying the clock rate of the processing unit comprised increasing the clock rate of the processing unit responsive to a determination that the actual number of errors in the at least one code word is less than a predetermined threshold value.
12. The method of claim 8 , wherein modifying the clock rate of the processing unit comprises comparing the actual number of errors in the at least one code word to a maximum number of correctable errors.
13. The method of claim 8 , wherein calculating the syndrome comprises applying vector operations in a vector space to data bits included in the at least one code word.
14. The method of claim 13 , wherein the syndrome is defined over a field, and wherein the field includes a primitive element.
15. A data storage apparatus, comprising:
a memory unit; and
a controller coupled to the memory unit, wherein the controller is configured to:
receive data from the memory, wherein the data is encoded with an ECC, and includes at least one code word;
calculate a syndrome for the at least one code word;
calculate an Error Locator Polynomial (ELP) dependent upon the calculated syndrome; and
modify a frequency of a clock signal dependent upon an actual number of errors in the at least one code word; and
a processor configured to:
receive the clock signal; and
determine roots of the ELP.
16. The data storage apparatus of claim 15 , wherein to calculate the syndrome for the at least one code word, the controller is further configured to multiply the at least one code word by a parity matrix.
17. The data storage apparatus of claim 15 , wherein to modify the frequency of the clock signal, the controller is further configured to decrease the frequency of the clock signal responsive to a determination that the actual number of errors in the at least one code word is greater than a predetermined threshold value.
18. The data storage apparatus of claim 15 , wherein to modify the frequency of the clock signal, the controller is further configured to increase the frequency of the clock signal responsive to a determination that the actual number of errors in the at least one code word is less than a predetermined threshold value.
19. The data storage apparatus of claim 15 , wherein to modify the frequency of the clock signal, the controller is further configured to compare the actual number of errors in the at least one code word to a maximum number of correctable errors.
20. The data storage apparatus of claim 15 , wherein to calculate the syndrome, the controller is further configured to apply vector operations in a vector space to data bits included in the at least one code word.