Probabilistic transition rule for two-level decoding of reed-solomon codes
Decoding data is disclosed, including computing a syndrome polynomial for Reed-Solomon encoded data, applying the Berlekamp-Massey method to solve key equations associated with the syndrome polynomial, comparing a linear feedback shift register (LSFR) length L Λ associated with an error locator polynomial Λ(x) with an error correction capability t, and based on the comparison, determining whether to perform soft decision decoding or a Chien search.
1. A method of decoding data, comprising:
receiving Reed-Solomon encoded data at an input;
computing a syndrome polynomial for the Reed-Solomon encoded data, wherein computing is performed by a processor;
applying the Berlekamp-Massey method to solve key equations associated with the syndrome polynomial;
comparing a linear feedback shift register (LFSR) length L Λ with an error correction capability t, wherein the LFSR is associated with an error locator polynomial Λ(x); and
based on the comparison, determining whether to perform soft decision decoding or a Chien search;
in the event that the LFSR length L Λ is greater than a metric, performing soft decision decoding on the Reed-Solomon encoded data to produce decoded data; and
providing the decoded data as output.
2. A method as recited in claim 1 , wherein the metric is a difference between the error correction capability t and a tolerance δ.
3. A method as recited in claim 2 , further including in the event that the LFSR length L Λ is less than the metric, performing a Chien search.
4. A method as recited in claim 1 , further including in the event that the LFSR length L Λ is less than a difference between the error correction capability t and a tolerance δ, performing a Chien search.
5. A method as recited in claim 1 , wherein comparing and determining are performed before performing a Chien search.
6. A method as recited in claim 1 , wherein in the event soft decision decoding is performed, the Chien search is not performed.
7. A method as recited in claim 1 , wherein in the event the Chien search is performed and the Chien search fails, a result is discarded.
8. A system for decoding data, comprising:
a processor configured to:
compute a syndrome polynomial for Reed-Solomon encoded data;
apply the Berlekamp-Massey method to solve key equations associated with the syndrome polynomial;
compare a linear feedback shift register (LFSR) length L Λ with an error correction capability t, wherein the LFSR is associated with an error locator polynomial Λ(x); and
based on the comparison, determine whether to perform soft decision decoding or a Chien search;
a memory coupled with the processor, wherein the memory is configured to provide the processor with instructions.
9. A system as recited in claim 8 , wherein the processor is further configured to, in the event that the LFSR length L Λ is greater than a difference between the error correction capability t and a tolerance δ, perform soft decision decoding.
10. A system as recited in claim 8 , wherein the processor is further configured to, in the event that the LFSR length L Λ is less than a difference between the error correction capability t and a tolerance δ, perform a Chien search.
11. A system as recited in claim 8 , wherein comparing and determining are performed before performing a Chien search.
12. A system as recited in claim 8 , wherein in the event soft decision decoding is performed, the Chien search is not performed.
13. A system as recited in claim 8 , wherein in the event the Chien search is performed and the Chien search fails, a result is discarded.
14. A computer program product for decoding data, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:
computing a syndrome polynomial for Reed-Solomon encoded data;
applying the Berlekamp-Massey method to solve key equations associated with the syndrome polynomial;
comparing a linear feedback shift register (LFSR) length L Λ with an error correction capability t, wherein the LFSR is associated with an error locator polynomial Λ(x); and
based on the comparison, determining whether to perform soft decision decoding or a Chien search.
15. A computer program product as recited in claim 14 , further comprising computer instructions for, in the event that the LFSR length L Λ is greater than a difference between the error correction capability t and a tolerance δ, performing soft decision decoding.
16. A computer program product as recited in claim 14 , further comprising computer instructions for, in the event that the LFSR length L Λ is less than a difference between the error correction capability t and a tolerance δ, performing a Chien search.
17. A computer program product as recited in claim 14 , wherein comparing and determining are performed before performing a Chien search.
18. A computer program product as recited in claim 14 , wherein in the event soft decision decoding is performed, the Chien search is not performed.
19. A computer program product as recited in claim 14 , wherein in the event the Chien search is performed and the Chien search fails, a result is discarded.