Low complexity chien search in chase-type decoding of reed-solomon codes

1. A method for processing data, comprising:

obtaining a length of an error locator polynomial;

determining, using a processor in a data decoder, whether the length of the error locator polynomial is greater than a first threshold;

in the event the length of the error locator polynomial is greater than the first threshold, skipping performance of a Chien search on the error locator polynomial;

in the event the length of the error locator polynomial is less than or equal to than the first threshold, performing the Chien search on the error locator polynomial to determine one or more roots of the error locator polynomial, wherein the roots correspond to one or more error locations;

prior to performing the Chien search, storing the error locator polynomial;

determining whether a number of stored error locator polynomials is greater than a second threshold; and

performing the Chien search on the error locator polynomial in the event the number of stored error locator polynomials is greater than the second threshold.

2. The method of claim 1 , wherein the first threshold is based at least in part on an error correction capability (τ).

3. The method of claim 2 , wherein the first threshold is further based at least in part on an erasure correction capability (f).

4. The method of claim 1 further comprising selecting the error locator polynomial from a plurality of candidate error locator polynomials.

5. The method of claim 4 , wherein selecting is based at least in part on one or more reliability values.

6. The method of claim 5 , wherein the one or more reliability values are output by a soft-output Viterbi decoder.

7. The method of claim 1 further comprising:

determining, after the Chien search is performed, whether the Chien search was successful; and

selecting a second error locator polynomial from a plurality of candidate error locator polynomials in the event the Chien search was not successful.

8. A method for processing data, comprising:

obtaining a length of an error locator polynomial;

determining, using a processor, whether the length of the error locator polynomial is greater than a threshold;

in the event the length of the error locator polynomial is greater than the threshold, skipping performance of a Chien search on the error locator polynomial;

in the event the length of the error locator polynomial is less than or equal to than the threshold, performing the Chien search on the error locator polynomial to determine one or more roots of the error locator polynomial, wherein the roots correspond to one or more error locations;

obtaining raw data and reliabilities corresponding to each bit in the raw data;

determining a plurality of flip patterns based at least in part on the raw data;

selecting and discarding one flip pattern from the plurality; and

redistributing one or more probabilities associated with the discarded flip pattern amongst one or more surviving flip patterns.

9. The method of claim 8 , wherein redistributing is based at least in part on which surviving flip pattern is a nearest flip pattern in a Hamming distance sense.

10. A system for processing data, comprising:

an interface configured to:

obtain a length of an error locator polynomial; and

obtain raw data and reliabilities corresponding to each bit in the raw data and a processor configured to:

determine whether the length of the error locator polynomial is greater than a threshold;

in the event the length of the error locator polynomial is greater than the threshold, skip performance of a Chien search on the error locator polynomial;

in the event the length of the error locator polynomial is less than or equal to than the threshold, perform the Chien search on the error locator polynomial to determine one or more roots of the error locator polynomial, wherein the roots correspond to one or more error locations;

determine a plurality of flip patterns based at least in part on the raw data select and discard one flip pattern from the plurality; and

redistribute one or more probabilities associated with the discarded flip pattern amongst one or more surviving flip patterns.

11. The system of claim 10 , wherein the threshold is based at least in part on an error correction capability (τ).

12. The system of claim 11 , wherein the threshold is further based at least in part on an erasure correction capability (f).

13. The system of claim 10 , wherein the processor is further configured to select the error locator polynomial from a plurality of candidate error locator polynomials.

14. The system of claim 13 , wherein the processor is configured to select based at least in part on one or more reliability values.

15. The system of claim 14 , wherein the one or more reliability values are output by a soft-output Viterbi decoder.

16. The system of claim 10 , wherein the processor is further configured to:

determine, after the Chien search is performed, whether the Chien search was successful; and

select a second error locator polynomial from a plurality of candidate error locator polynomials in the event the Chien search was not successful.

17. The system of claim 10 , wherein the processor is configured to redistribute based at least in part on which surviving flip pattern is a nearest flip pattern in a Hamming distance sense.

18. A system for processing data, comprising:

an interface configured to obtain a length of an error locator polynomial; and

a processor configured to:

determine whether the length of the error locator polynomial is greater than a threshold;

in the event the length of the error locator polynomial is greater than the threshold, skip performance of a Chien search on the error locator polynomial;

in the event the length of the error locator polynomial is less than or equal to than the threshold, perform the Chien search on the error locator polynomial to determine one or more roots of the error locator polynomial, wherein the roots correspond to one or more error locations;

prior to performing the Chien search, store the error locator polynomial;

determine whether a number of stored error locator polynomials is greater than a second threshold; and

perform the Chien search on the error locator polynomial in the event the number of stored error locator polynomials is greater than the second threshold.

19. A computer program product for processing data, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

obtaining a length of an error locator polynomial;

determining whether the length of the error locator polynomial is greater than a threshold;

in the event the length of the error locator polynomial is greater than the threshold, skipping performance of a Chien search on the error locator polynomial;

in the event the length of the error locator polynomial is less than or equal to than the threshold, performing the Chien search on the error locator polynomial to determine one or more roots of the error locator polynomial, wherein the roots correspond to one or more error locations;

prior to performing the Chien search, storing the error locator polynomial;

determining whether a number of stored error locator polynomials is greater than a second threshold; and

performing the Chien search on the error locator polynomial in the event the number of stored error locator polynomials is greater than the second threshold.

20. A computer program product for processing data, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

obtaining a length of an error locator polynomial;

determining whether the length of the error locator polynomial is greater than a threshold;

in the event the length of the error locator polynomial is greater than the threshold, skipping performance of a Chien search on the error locator polynomial;

in the event the length of the error locator polynomial is less than or equal to than the threshold, performing the Chien search on the error locator polynomial to determine one or more roots of the error locator polynomial, wherein the roots correspond to one or more error locations;

obtaining raw data and reliabilities corresponding to each bit in the raw data;

determining a plurality of flip patterns based at least in part on the raw data;

selecting and discarding one flip pattern from the plurality; and

redistributing one or more probabilities associated with the discarded flip pattern amongst one or more surviving flip patterns.