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 progressively removed.
1. A method of processing polynomials, including:
simultaneously performing, by a processor using an iterative process, 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
progressively removing data associated with the error evaluator polynomial, including by:
removing a piece of data associated with the error evaluator polynomial at each iteration; and
eliminating the error evaluator polynomial by an end of the simultaneously performed processing, wherein removing and eliminating include setting {circumflex over (Ω)} (r+1) (x) to γ (r) ·[ 1 {circumflex over (Ω)} (r) ](x)−{circumflex over (Ω)} 0 (r) ·{circumflex over (Θ)} (r) (x).
2. The method as recited in claim 1 , wherein the error evaluator polynomial and the error locator polynomial are associated with Reed-Solomon data.
3. 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.
4. The method as recited in claim 1 , further including obtaining a syndrome polynomial.
5. The method as recited in claim 1 , wherein a location of an error is obtained using the error locator polynomial.
6. 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.
7. The method as recited in claim 1 , wherein a location of an error is obtained using a Chien search.
8. The method as recited in claim 1 further including obtaining a degree limited scratch polynomial using the error locator polynomial.
9. 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.
10. 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.
11. The method as recited in claim 1 , wherein progressively removing data includes by left-shifting coefficients associated with the error evaluator polynomial.
12. A system for processing polynomials, including:
a processor configured to:
simultaneously perform, using an iterative process, 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
progressively remove data associated with the error evaluator polynomial, including by:
removing a piece of data associated with the error evaluator polynomial at each iteration; and
eliminating the error evaluator polynomial by an end of the simultaneously performed processing, wherein removing and eliminating include setting {circumflex over (Ω)} (r+1) (x) to γ (r) ·[ 1 {circumflex over (Ω)} (r) ](x)−{circumflex over (Ω)} 0 (r) ·{circumflex over (Θ)} (r) (x); and
a memory configured to be accessible to the processor.
13. The system as recited in claim 12 , wherein the system is smaller than a second system that does not progressively remove data associated with the error evaluator polynomial.
14. The system as recited in claim 12 , 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.
15. The system as recited in claim 12 , 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.
16. The system as recited in claim 12 , wherein the processor includes a plurality of devices and each of the plurality of devices has the same structure.
17. The system as recited in claim 12 , wherein the processor includes a plurality of devices and the number of the plurality of devices varies in accordance with an error correction capability.
18. The system as recited in claim 12 , wherein the processor is configured to progressively remove data includes by left-shifting coefficients associated with the error evaluator polynomial.
19. A computer program product for processing polynomials, the computer program product being embodied in a computer readable storage medium and comprising code that, when executed, causes a computer to perform the following:
simultaneously performing, using an iterative process, 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
progressively removing data associated with the error evaluator polynomial, including
removing a piece of data associated with the error evaluator polynomial at each iteration; and
eliminating the error evaluator polynomial by an end of the simultaneously performed processing, wherein removing and eliminating include setting {circumflex over (Ω)} (r+1) (x) to γ (r) ·[ 1 {circumflex over (Ω)} (r) ](x)−{circumflex over (Ω)} 0 (r) ·{circumflex over (Θ)} (r) (x).
20. The computer program product as recited in claim 19 , wherein the computer instructions for progressively removing data include computer instructions for left-shifting coefficients associated with the error evaluator polynomial.