Reduced processing in high-speed Reed-Solomon decoding
Processing polynomials is disclosed. At least a portion of processing associated with an error evaluator polynomial and at least a portion of processing associated with an error locator polynomial are performed simultaneously. The error evaluator polynomial and the error locator polynomial are associated with Berlekamp-Massey processing. Data associated with the error evaluator polynomial is removed, including by shifting data in an array so that at least one element in the array is emptied in a shift.
1. A method of processing polynomials; including:
using a processor to simultaneously perform at least a portion of processing associated with an error evaluator polynomial and at least a portion of processing associated with an error locator polynomial, wherein the error evaluator polynomial and the error locator polynomial are associated with Berlekamp-Massey processing; and
removing data associated with the error evaluator polynomial, including by shifting data in an array so that at least one element in the array is emptied in a shift.
2. The method of claim 1 , wherein shifting includes left-shifting an array of registers.
3. The method as recited in claim 1 , wherein simultaneously performing processing includes an iterative process.
4. The method as recited in claim 1 , wherein:
simultaneously performing processing includes an iterative process; and
removing data includes removing a piece of data associated with the error evaluator polynomial at each iteration.
5. The method as recited in claim 1 , wherein removing data includes eliminating the error evaluator polynomial by an end of the simultaneously performed processing.
6. The method as recited in claim 1 , wherein the error evaluator polynomial and the error locator polynomial are associated with Reed-Solomon data.
7. The method as recited in claim 1 , wherein the error evaluator polynomial and the error locator polynomial are associated with data obtained from a storage device.
8. The method as recited in claim 1 , further including obtaining a syndrome polynomial.
9. The method as recited in claim 1 , wherein a location of an error is obtained using the error locator polynomial.
10. The method as recited in claim 1 , wherein a location of an error is obtained by obtaining at least one root of the error locator polynomial.
11. The method as recited in claim 1 , wherein a location of an error is obtained using a Chien search.
12. The method as recited in claim 1 further including obtaining a degree limited scratch polynomial using the error locator polynomial.
13. The method as recited in claim 1 , further including performing at least part of a discrepancy computation and at least part of an error locator update simultaneously.
14. The method as recited in claim 1 , further including performing a Chien search, wherein at least part of the Chien search and at least part of determining a magnitude of an error are performed simultaneously.
15. A system for processing polynomials, including:
a processor configured to:
simultaneously performing at least a portion of processing associated with an error evaluator polynomial and at least a portion of processing associated with an error locator polynomial, wherein the error evaluator polynomial and the error locator polynomial are associated with Berlekamp-Massey processing; and
remove data associated with the error evaluator polynomial, including by shifting data in an array so that at least one element in the array is emptied in a shift; and
a memory configured to be accessible to the processor.
16. The system as recited in claim 15 , wherein the system is smaller than a second system that does not remove data associated with the error evaluator polynomial.
17. The system as recited in claim 15 , wherein the processor includes a plurality of devices and each of the plurality of devices is configured to generate a coefficient of the error locator polynomial.
18. The system as recited in claim 15 , wherein the processor includes a plurality of devices and each of the plurality of device is configured to generate a coefficient of a scratch polynomial.
19. The system as recited in claim 15 , wherein the processor includes a plurality of devices and each of the plurality of devices has the same structure.
20. The system as recited in claim 15 , wherein the processor includes a plurality of devices and the number of the plurality of devices varies in accordance with an error correction capability.
21. A computer program product for processing polynomials, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:
simultaneously performing at least a portion of processing associated with an error evaluator polynomial and at least a portion of processing associated with an error locator polynomial, wherein the error evaluator polynomial and the error locator polynomial are associated with Berlekamp-Massey processing; and
removing data associated with the error evaluator polynomial, including by shifting data in an array so that at least one element in the array is emptied in a shift.