Decoding error correction codes using a modular single recursion implementation
View Patent ↗Systems and methods are provided for performing error correction decoding. The coefficients of the error locator polynomial are iteratively determined for each codeword using a modular implementation of a single recursion key-equation solver algorithm. According to this implementation, a plurality of modules are used to calculate the current and previous coefficients of the error locator polynomial. One module is used for each correctable error. The modular single recursion implementation is programmable, because the number of modules can be easily changed to correct any number of correctable errors. Galois field tower arithmetic can be used to calculate the inverse of an error term. Galois field tower arithmetic greatly reduces the size of the inversion unit. The latency time can be reduced by placing the computations of the inverse error term outside the critical path of the error locator polynomial algorithm.
1. A controller chipset for correcting errors in data, the controller chipset comprising:
a plurality of modules that compute coefficients of an error locator polynomial in each iteration of a single recursion key-equation solver algorithm, and that store current and previous values of the error locator polynomial coefficients, each of the modules corresponding to one correctable error,
wherein error locations and error values are computed using the current and previous values of the error locator polynomial coefficients stored in the modules.
2. The controller chipset defined in claim 1 wherein each of the modules has two registers for storing the error locator polynomial coefficients and only one multiplier that multiplies a syndrome by one of the current values of the error locator polynomial coefficients to generate multiplier outputs.
3. The controller chipset defined in claim 2 wherein the controller chipset updates a value of an error term by summing together the multiplier outputs to generate a first result, and adding the first result to a current value of the error term.
4. The controller chipset defined in claim 3 wherein each of the plurality of modules computes updated coefficients of the error locator polynomial in each iteration using a polynomial update equation v k =v k −(e·u k ) for each of the current values of the error locator polynomial coefficients V k , wherein e is the current value of the error term, and u k represents the previous values of the error locator polynomial coefficients.
5. The controller chipset defined in claim 4 wherein the error term is updated in each subsequent iteration prior to the computation performed in the polynomial update equation by multiplying an inverse of a previous value of the error term with the current value of the error term, and
wherein the inverse of the error term is calculated only once in two computation cycles.
6. The controller chipset defined in claim 5 wherein the inverse of the error term is computed using Galois field tower arithmetic.
7. The controller chipset defined in claim 1 wherein the controller chipset further comprises:
a plurality of syndrome registers for storing the syndromes, wherein the plurality of modules receive the syndromes from the syndrome registers.
8. The controller chipset defined in claim 3 wherein the error term is computed using only t adders that sum together the multiplier outputs, where t equals a number of correctable errors.
9. A method for correcting errors in data, the method comprising:
computing coefficients of an error locator polynomial in each iteration of a single recursion key-equation solver algorithm using a plurality of modules, each of the modules comprising registers and a multiplier, and each module corresponding to one correctable error;
storing current and previous values of the error locator polynomial coefficients in the registers; and
computing error locations and error values using the current and previous values of the error locator polynomial coefficients.
10. The method defined in claim 9 further comprising:
multiplying syndromes by the current error locator polynomial coefficients using the multipliers in the plurality of modules, wherein each of the modules has only one multiplier;
summing together outputs of the multiplier to generate an error term; and
updating the current values of the error locator polynomial coefficients using the error term.
11. The method defined in claim 9 wherein each of the modules has two registers for storing the error locator polynomial coefficients and only one multiplier that multiplies a syndrome by one of the current values of the error locator polynomial coefficients to generate multiplier outputs.
12. The method defined in claim 11 further comprising:
updating a value of an error term by summing together the multiplier outputs to generate a first result; and
adding the first result to a current value of the error term.
13. The method defined in claim 12 wherein the error term is computed using only t adders that sum together the multiplier outputs, where t equals a number of correctable errors.
14. The method defined in claim 12 wherein computing coefficients of the error locator polynomial in each iteration of the single recursion key-equation solver algorithm using the plurality of modules further comprises:
computing updated coefficients of the error locator polynomial in each iteration using a polynomial update equation V k =V k −(e·u k ) for each of the current values of the error locator polynomial coefficients v k , wherein e is the current value of the error term, and u k represents the previous values of the error locator polynomial coefficients.
15. The method defined in claim 14 wherein the error term is updated in each subsequent iteration prior to the computation performed in the polynomial update equation by multiplying an inverse of a previous value of the error term with the current value of the error term, and wherein the inverse of the error term is calculated only once in two computation cycles.
16. The method defined in claim 15 wherein the inverse of the error term is computed using Galois field tower arithmetic.