Incremental generation of polynomials for decoding reed-solomon codes
Generating a polynomial is disclosed. A prior error locator polynomial, associated with locating errors in encoded data, is obtained. A new error locator polynomial, associated with a test error pattern, is incrementally generated based at least in part on the prior error locator polynomial.
1. A method for generating a polynomial, including:
obtaining, at a processor, a first error locator polynomial, associated with locating errors in encoded data;
incrementally generating a second error locator polynomial using the processor, including by:
obtaining a test error pattern; and
flipping those bits in the first error locator polynomial that correspond to the test error pattern to obtain the second error locator polynomial; and
performing error correction decoding on encoded data using the second error locator polynomial.
2. A method as recited in claim 1 , wherein incrementally generating excludes performing a Berlekamp-Massey process.
3. A method as recited in claim 1 , further including performing a Berlekamp-Massey process to obtain an initial error locator polynomial.
4. A method as recited in claim 1 , wherein obtaining includes incrementally generating the first error locator polynomial.
5. A method as recited in claim 1 , wherein the test error pattern is associated with a tree structure.
6. A method as recited in claim 1 , wherein the encoded data is associated with storage.
7. A method as recited in claim 1 , further including incrementally generating a second scratch polynomial, associated with the test error pattern, based at least in part on a first scratch polynomial.
8. A method as recited in claim 1 , wherein incrementally generating a second error locator polynomial is further based at least in part on a first scratch polynomial.
9. A method as recited in claim 1 , further including evaluating the first error locator polynomial, wherein incrementally generating takes into consideration the evaluation of the first error locator polynomial.
10. A method as recited in claim 1 , wherein incrementally generating includes using a plurality of cases.
11. A method as recited in claim 1 , wherein incrementally generating includes using a plurality of cases and a probability associated with one or more of the plurality of cases is considered.
12. A method as recited in claim 1 , further including determining whether to overwrite a saved error locator polynomial with the second error locator polynomial.
13. A method as recited in claim 1 , further including determining at least one error location using a saved error locator polynomial.
14. A system for generating a polynomial, including:
an interface configured to obtain a first error locator polynomial, associated with locating errors in encoded data;
a processor configured to:
incrementally generate a second error locator polynomial, including by:
obtaining a test error pattern; and
flipping those bits in the first error locator polynomial that correspond to the test error pattern to obtain the second error locator polynomial; and
perform error correction decoding on encoded data using the second error locator polynomial.
15. A system as recited in claim 14 , wherein the test error pattern is associated with a tree structure.
16. A system as recited in claim 14 , wherein the processor is further configured to evaluate the first error locator polynomial, and the processor is configured to incrementally generate the second error locator polynomial by taking into consideration the evaluation of the first error locator polynomial.
17. A system as recited in claim 14 , wherein the processor is further configured to determine at least one error location using a saved error locator polynomial.
18. A computer program product for generating a polynomial, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:
obtaining a first error locator polynomial, associated with locating errors in encoded data;
incrementally generating a second error locator polynomial, including by:
obtaining a test error pattern; and
flipping those bits in the first error locator polynomial that correspond to the test error pattern to obtain the second error locator polynomial; and
performing error correction decoding on encoded data using the second error locator polynomial.
19. A computer program product as recited in claim 18 , wherein the test error pattern is associated with a tree structure.
20. A computer program product as recited in claim 18 , the computer program product further comprising computer instructions for evaluating the first error locator polynomial, wherein incrementally generating takes into consideration the evaluation of the first error locator polynomial.
21. A computer program product as recited in claim 18 , the computer program product further comprising computer instructions for determining at least one error location using a saved error locator polynomial.
22. A method as recited in claim 1 , wherein incrementally generating a second error locator polynomial (Λ(x)) further includes using one or more of the following cases:
Case
1
:
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
;
Case
2
:
B
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
2
x
2
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
2
;
Case
3
:
L
Λ
>
L
B
⋀
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
2
x
2
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
2
;
Case
4
:
L
Λ
>
L
B
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
+
axB
(
σ
i
)
(
x
)
+
bx
2
B
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
;
Case
5
:
L
Λ
<
L
B
⋀
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
x
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
1
;
Case
6
:
L
Λ
>
L
B
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
+
axB
(
σ
i
)
(
x
)
+
bx
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
1
;
Case
7
:
L
Λ
=
L
B
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
≠
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
+
axB
(
σ
i
)
(
x
)
+
bx
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
1
;
or
Case
8
:
L
Λ
=
L
B
⋀
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
=
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
2
x
2
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
2
.
23. A system as recited in claim 14 , wherein the processor is configured to incrementally generate a second error locator polynomial (Λ(x)) by further using one or more of the following cases:
Case
1
:
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
;
Case
2
:
B
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
2
x
2
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
2
;
Case
3
:
L
Λ
>
L
B
⋀
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
2
x
2
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
2
;
Case
4
:
L
Λ
>
L
B
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
+
axB
(
σ
i
)
(
x
)
+
bx
2
B
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
;
Case
5
:
L
Λ
<
L
B
⋀
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
x
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
1
;
Case
6
:
L
Λ
>
L
B
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
+
axB
(
σ
i
)
(
x
)
+
bx
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
1
;
Case
7
:
L
Λ
=
L
B
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
≠
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
+
axB
(
σ
i
)
(
x
)
+
bx
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
1
;
or
Case
8
:
L
Λ
=
L
B
⋀
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
=
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
2
x
2
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
2
.
24. A computer program product as recited in claim 18 , wherein the computer instructions for incrementally generating a second error locator polynomial (Λ(x)) further include computer instructions for using one or more of the following cases:
Case
1
:
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
;
Case
2
:
B
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
2
x
2
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
2
;
Case
3
:
L
Λ
>
L
B
⋀
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
2
x
2
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
2
;
Case
4
:
L
Λ
>
L
B
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
+
axB
(
σ
i
)
(
x
)
+
bx
2
B
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
;
Case
5
:
L
Λ
<
L
B
⋀
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
x
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
1
;
Case
6
:
L
Λ
>
L
B
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
=
0
⋀
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
+
axB
(
σ
i
)
(
x
)
+
bx
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
1
;
Case
7
:
L
Λ
=
L
B
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
≠
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
{
Λ
(
σ
i
+
1
)
(
x
)
←
Λ
(
σ
i
)
(
x
)
+
axB
(
σ
i
)
(
x
)
+
bx
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
1
;
or
Case
8
:
L
Λ
=
L
B
⋀
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
≠
0
⋀
B
(
σ
i
)
(
X
i
+
1
-
1
)
Ω
_
(
σ
i
)
(
X
i
+
1
-
1
)
=
Λ
(
σ
i
)
(
X
i
+
1
-
1
)
Θ
_
(
σ
i
)
(
X
i
+
1
-
1
)
{
Λ
(
σ
i
+
1
)
(
x
)
←
(
1
-
X
i
+
1
2
x
2
)
Λ
(
σ
i
)
(
x
)
L
Λ
←
L
Λ
+
2
.