Degree limited polynomial in Reed-Solomon decoding
Processing Reed Solomon data is disclosed. A scratch polynomial having a degree is obtained using an inversionless Berlekamp-Massey process. The degree of the scratch polynomial is limited. A magnitude of an error associated with the Reed Solomon data is determined based at least in part on information associated with the degree limited scratch polynomial. In some embodiments, determining the magnitude of an error using the degree limited scratch polynomial enables a smaller device.
1. A method of processing Reed Solomon data, including:
generating, at a processor, a degree limited scratch polynomial having a degree that is limited to a defined value using an inversionless Berlekamp-Massey process, wherein generating includes shifting out at least one zero root in a polynomial being operated on in the event the degree of the polynomial being operated on exceeds the defined value, wherein the defined value is t−1 and t is an error correction capability of a code used to generate the Reed Solomon data; and
determining a magnitude of an error associated with the Reed Solomon data using the processor based at least in part on information associated with the degree limited scratch polynomial.
2. A system for processing Reed Solomon data, including a processor configured to:
obtain generate a degree limited scratch polynomial having a degree that is limited to a defined value using an inversionless Berlekamp-Massey process, wherein generating includes shifting out at least one zero root in a polynomial being operated on in the event the degree of the polynomial being operated on exceeds the defined value, wherein the defined value is t−1 and t is an error correction capability of a code used to generate the Reed Solomon data; and
determine a magnitude of an error associated with the Reed Solomon data based at least in part on information associated with the degree limited scratch polynomial; and a memory configured to be accessible to the processor.
3. The system as recited in claim 2 , wherein the processor includes a plurality of devices and each of the plurality of devices is configured to generate (1) a coefficient of the scratch polynomial and (2) a coefficient of an error locator polynomial.
4. The system as recited in claim 2 , wherein the processor includes a plurality of devices and each of the plurality of devices has the same structure.
5. The system as recited in claim 2 , wherein the processor includes a plurality of devices and the number of the plurality of devices varies in accordance with an error correction capability.
6. The system as recited in claim 2 , wherein limiting the degree of the scratch polynomial allows at least one configuration with fewer components compared to a system in which the degree of the scratch polynomial is not limited.
7. The system as recited in claim 2 , wherein the processor is further configured to perform a Chien search.
8. The system as recited in claim 2 , wherein at least one zero root is not removed from the scratch polynomial.
9. The system as recited in claim 2 , wherein the processor is further configured to obtain a syndrome polynomial.
10. The system as recited in claim 2 , wherein the processor is further configured to determine a location of the error.
11. The system as recited in claim 2 , wherein the processor is further configured to obtain roots of an error locator polynomial.
12. The system as recited in claim 2 , wherein the processor is further configured to determine a location of the error, including using a Chien search.
13. The system as recited in claim 2 wherein information associated with an error evaluator polynomial is not used in determining the magnitude.
14. The system as recited in claim 2 , wherein the processor is further configured to obtain an error locator polynomial.
15. The system as recited in claim 2 , wherein the processor is further configured to obtain an error locator polynomial, including by suing an iterative process.
16. The system as recited in claim 2 , wherein the processor is further configured to obtain an error locator polynomial, including by using an iterative process such that the iterative process is stopped in the event a criterion associated with an error correction capability is satisfied.
17. The system as recited in claim 2 , wherein the inversionless Berlekamp-Massey process includes simultaneously performing at least a portion of processing associated with discrepancy computation and at least a portion of processing associated with error locator update.
18. The system as recited in claim 2 , wherein the processor is further configured to perform a Chien search, wherein at least part of the Chien search and at least part of determining the magnitude of the error are performed simultaneously.
19. The system as recited in claim 2 , wherein the Reed Solomon data is obtained from a storage device.
20. A computer program product for processing Reed Solomon data, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:
generating a degree limited scratch polynomial having a degree that is limited to a defined value using an inversionless Berlekamp-Massey process, wherein generating includes shifting out at least one zero root in a polynomial being operated on in the event the degree of the polynomial being operated on exceeds the defined value, wherein the defined value is t−1 and t is an error correction capability of a code used to generate the Reed Solomon data; and
determining a magnitude of an error associated with the Reed Solomon data based at least in part on information associated with the degree limited scratch polynomial.