Compact chien-search based decoding apparatus and method
View Patent ↗A method and an apparatus that has Chien search capabilities, the apparatus includes a first hardware circuit and a second hardware circuit. The first hardware circuit evaluates an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined to provide a first set of intermediate results and a first Chien search result and provides the first set of intermediate results to the second hardware circuit; the second hardware circuit evaluates the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results. The first hardware circuit may be substantially bigger than the second hardware circuit and the first element may differ from the second element.
1. An apparatus that has Chien search capabilities, the apparatus comprising: a first hardware circuit to evaluate an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined, and to provide a first set of intermediate results and a first Chien search result; and a second hardware circuit, wherein the first hardware circuit is to provide the first set of intermediate results to the second hardware circuit, and wherein the second hardware circuit is to evaluate the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results; wherein the first hardware circuit comprises a mask and add unit to sum unmasked bits representative of preliminary results obtained during an evaluation of the error locator polynomial to provide the first set of intermediate results.
2. An apparatus that has Chien search capabilities, the apparatus comprising: a first hardware circuit to evaluate an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined, and to provide a first set of intermediate results and a first Chien search result; and a second hardware circuit, wherein the first hardware circuit is to provide the first set of intermediate results to the second hardware circuit, and wherein the second hardware circuit is to evaluate the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results; wherein the first hardware circuit comprises a shift and add unit to shift the first set of intermediate results by different shift factors to provide shifted results and adds the shifted results to provide a first shifted sum.
3. The apparatus according to claim 2 , wherein the first hardware circuit comprises a modulo circuit to perform a modulo operation on the first shifter sum to provide the first Chien search result.
4. The apparatus according to claim 2 , wherein the first hardware circuit further comprises a mask and add unit to sum unmasked bits representative of preliminary results obtained during an evaluation of the error locator polynomial to provide the first set of intermediate results.
5. An apparatus that has Chien search capabilities, the apparatus comprising: a first hardware circuit to evaluate an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined, and to provide a first set of intermediate results and a first Chien search result; and a second hardware circuit, wherein the first hardware circuit is to provide the first set of intermediate results to the second hardware circuit, and wherein the second hardware circuit is to evaluate the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results; wherein the second hardware circuit comprises a squaring circuit to square the first set of intermediate results to provide a second set of intermediate results.
6. The apparatus according to claim 5 , wherein the second hardware circuit comprises a shift and add unit to shift the second set of intermediate results by different shift factors to provide shifted results and adds the shifted results to provide a second shifted sum.
7. The apparatus according to claim 6 , wherein the second hardware circuit comprises a modulo circuit to perform a modulo operation on the second shifted sum to provide the second Chien search result.
8. An apparatus that has Chien search capabilities, the apparatus comprising: a first hardware circuit to evaluate an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined, and to provide a first set of intermediate results and a first Chien search result; and a second hardware circuit, wherein the first hardware circuit is to provide the first set of intermediate results to the second hardware circuit, and wherein the second hardware circuit is to evaluate the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results; comprising a third hardware circuit to evaluate the error locator polynomial for a third element of the finite field to provide a third Chien search result in response to a second set of intermediate results generated by the second hardware circuit.
9. An apparatus that has Chien search capabilities, the apparatus comprising multiple hardware circuits, the multiple hardware circuits comprise: a first hardware circuit to evaluate an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined, and to provide a first set of intermediate results and a first Chien search result; and a second hardware circuit, wherein the first hardware circuit is to provide the first set of intermediate results to the second hardware circuit, and wherein the second hardware circuit is to evaluate the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results; wherein each hardware circuit of the multiple hardware circuits evaluates the error locator polynomial for a different element of the finite field, wherein each of the multiple hardware circuits is to perform a modulo operation only at a modulo circuit that provides a Chien search result.
10. The apparatus according to claim 9 , wherein each hardware circuit comprises a mask and add unit to sum unmasked bits representative of preliminary results obtained during an evaluation of the error location polynomial.
11. A method for providing Chien search results comprising: evaluating, by a first hardware circuit, an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined to provide a first set of intermediate results and a first Chien search result; providing the first set of intermediate results to a second hardware circuit; evaluating, by the second hardware circuit, the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results; masking bits representative of preliminary results obtained during an evaluation of the error location polynomial; and summing unmasked bits representative of the preliminary results to provide the first set of intermediate results.
12. A method for providing Chien search results comprising: evaluating, by a first hardware circuit, an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined to provide a first set of intermediate results and a first Chien search result; providing the first set of intermediate results to a second hardware circuit; evaluating, by the second hardware circuit, the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results; shifting the first set of intermediate results by different shift factors to provide shifted results; and adding the shifted results to provide a first shifted sum.
13. The method according to claim 12 , comprising performing a modulo operation on the first shifted sum to provide the first Chien search result.
14. The method according to claim 12 , comprising: masking bits representative of preliminary results obtained during an evaluation of the error location polynomial; and summing unmasked bits representative of the preliminary results to provide the first set of intermediate results.
15. A method for providing Chien search results comprising: evaluating, by a first hardware circuit an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined to provide a first set of intermediate results and a first Chien search result; providing the first set of intermediate results to a second hardware circuit; evaluating, by the second hardware circuit, the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results; and squaring the first set of intermediate results to provide a second set of intermediate results.
16. The method according to claim 15 , comprising: shifting the second set of intermediate results by different shift factors to provide shifted results; and adding the shifted results to provide a second shifted sum.
17. The method according to claim 16 , comprising performing a modulo operation on the second shifted sum to provide the second Chien search result.
18. A method for providing Chien search results comprising: evaluating, by a first hardware circuit, an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined to provide a first set of intermediate results and a first Chien search result; providing the first set of intermediate results to a second hardware circuit; evaluating, by the second hardware circuit, the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results; and evaluating, by a third hardware circuit, the error locator polynomial for a third element of the finite field to provide a third Chien search result in response to a second set of intermediate results generated by the second hardware circuit.
19. A method for providing Chien search results comprising: evaluating, by a first hardware circuit, an error locator polynomial for a first element of a finite field over which the error locator polynomial is defined to provide a first set of intermediate results and a first Chien search result; providing the first set of intermediate results to a second hardware circuit; evaluating, by the second hardware circuit, the error locator polynomial for a second element of the finite field to provide a second Chien search result in response to the first set of intermediate results; and evaluating the error locator polynomial for different elements of the finite field, wherein each evaluation comprises applying modulo operation only at a last stage of the evaluating.
20. The method according to claim 19 , comprising: masking bits representative of preliminary results obtained during an evaluation of the error location polynomial; and summing unmasked bits representative of the preliminary results to provide the first set of intermediate results.