Algebraic decoder and method for correcting an arbitrary mixture of burst and random errors
View Patent ↗An error correction algebraic decoder and an associated method correct a combination of a B-byte burst of errors and t-byte random errors in a failed sector, by iteratively adding and removing an erasure (N−B) times until the entire failed sector has been scanned, provided the following inequality is satisfied: (B+2t)≦(R−1), where N denotes the number of bytes, B denotes the length of the burst of errors, t denotes the total number of random errors, and R denotes the number of check bytes in the failed sector. This results in a corrected sector at a decoding latency that is a generally linear function of the number of the check bytes R, as follows: Decoding Latency=5R(N−B).
1. An error correction algebraic decoding method for correcting a combination of a burst of errors and random errors in a failed sector, comprising:
iteratively adding and removing an erasure (N−B) times until the entire failed sector has been scanned, where N denotes the number of bytes in the failed sector, and B denotes the length of the burst of errors in the failed sector; and
wherein (B+2t) is less than, or equal to (R−1), where R denotes the number of check bytes in the failed sector, where t denotes the total number of random errors in the failed sector,
resulting in a corrected sector at a decoding latency that is a generally linear function of the number of the check bytes R, and wherein the decoding latency is expressed as follows:
decoding latency=5R ( N−B ).
2. The method of claim 1 , further comprising applying an initialization stage for receiving a plurality of syndromes and for generating a modified syndrome polynomial from the plurality of syndromes.
3. The method of claim 2 , further comprising iteratively removing (R−B) erasures, using the modified syndrome polynomial.
4. The method of claim 3 , further comprising calculating an error locator polynomial, assuming the initial existence of R erasures at a beginning of the failed sector.
5. The method of claim 4 , further comprising determining if the error locator polynomial is valid.
6. The method of claim 5 , wherein if the error locator polynomial is valid, adding the error locator polynomial to a solution list.
7. The method of claim 1 , further comprising performing a cyclic redundancy check; and
selecting a valid burst and error locator and corresponding error values, to correct the failed sector.
8. The method of claim 3 , wherein the initialization stage comprises calculating a syndrome polynomial S(x), as follows:
S
(
x
)
:
=
∑
i
=
0
R
-
1
s
i
x
R
-
1
-
i
,
where “i” denotes an index that goes from 0 to (R−1); and Si denotes an i th syndrome.
9. The method of claim 8 , further comprising calculating an erasure polynomial E(x), as follows:
E
(
x
)
:
=
∏
i
=
0
R
-
1
(
x
-
α
i
)
,
where α i refers to a Galois Field representation of symbol values and locations.
10. The method of claim 9 , further comprising calculating a modified syndrome polynomial S(x) E , as follows:
S ( x ) E :=[E ( x )* S ( x )] mod x R ,
resulting in the modified syndrome polynomial.
11. The method of claim 10 , wherein iteratively removing (R−B) erasures comprises calculating initial polynomial basis values [l 1 , l 2 ] for solutions [B, t], as follows:
1 1 :=[1, S ( x ) E ], and
1 2 :=[0, x R ],
where each of [l 1 ] and [l 2 ] is a vector of two polynomials.
12. The method of claim 11 , further comprising iteratively calculating the initial polynomial basis values [l 1, l 2 ] for all solutions [B, t], and removing corresponding erasures, as follows:
for i=B, . . . , R−1,
[l 1 , l 2 ]:=Remove Erasure ([l 1 , l 2 ], α i ); and
wherein [l 1 ] is comprised of vectors [v, q], and [l 2 ] is comprised of vectors [u, p], as follows:
[l 1 ]=[v, q], and
[l 2 ]=[u, p],
where v represents an error locator polynomial, q represents an error evaluation polynomial, u represents a previous error locator polynomial, and p represents a previous error evaluation polynomial.
13. The method of claim 4 , wherein iteratively adding and removing the erasure (N−B) times comprises sequentially removing an erasure and adding an erasure for shifting a byte erasure.
14. The method of claim 13 , wherein shifting the byte erasure comprises removing the byte erasure from an initial position along the failed sector.
15. The method of claim 14 , wherein shifting the byte erasure further comprises adding a byte erasure at a distance R from the initial position.
16. The method of claim 15 , wherein removing the byte erasure further comprises evaluating polynomials q 0 and p 0 , as expressed below:
q 0 :=q (β),
p 0 :=p (β), and
β=α i ,
wherein β refers to an erasure location that is set equal to α i .
17. The method of claim 16 , wherein removing the byte erasure further comprises inquiring if the following erasure removal condition is satisfied:
q 0 =0, or (p 0 ≠0 and δ( vE )>δ( p )),
where the function δ(.) denotes a polynomial degree.
18. The method of claim 17 , wherein if the erasure removal condition is satisfied, creating a combination of vectors l 1 and l 2 , to selectively eliminate candidate erasure location β positions within the failed sector from valid solutions of an error evaluator polynomial, as follows:
c=q 0 /p 0 ,
l 1 =[v−cu , ( q−cp )/( x−β )], and
l 2 =[( x−β ) u, p],
where q 0 denotes a value of the error evaluation polynomial q at β=α i , and p 0 denotes a value of a previous error evaluation polynomial p at β=α i .
19. The method of claim 17 , wherein if the erasure removal condition is not satisfied, setting a value c and vectors [l 1 ] and [l 2 ], as follows:
c=p 0 /q 0 ,
l 1 =[( x−β ) v, q ], and
l 2 =[u−cv , ( p−cq )/( x−β )].
20. The method of claim 17 , wherein adding the byte erasure comprises using vectors.
21. The method of claim 20 , wherein adding the byte erasure comprises setting polynomials v 0 and u 0 , as expressed below:
v 0 :=v (β),
u 0 :=u (β), and
β=α i .
22. The method of claim 21 , wherein adding the byte erasure further comprises determining if the following erasure addition condition is satisfied:
v 0 =0, or ( u 0 ≠0 and δ( vE )>δ( p )).
23. The method of claim 22 , wherein if the erasure addition condition is satisfied, creating a combination of vectors l 1 and l 2 , to selectively eliminate candidate erasure location β positions within the failed sector from valid solutions of the error locator polynomial, as follows:
c=v 0 /u 0 ,
1 1 =[( v−cu )/( x−β ), q−cp ], and
1 2 =[u , ( x−β ) p].
where v 0 is a value of the error evaluation polynomial v at β=α i , and u 0 is a value of a previous error evaluation polynomial u at β=α i .
24. The method of claim 22 , wherein if the erasure addition condition is not satisfied, setting a value c and vectors [l 1 ] and [l 2 ], as follows:
c=v 0 /u 0 ,
1 1 =[v , ( x−β ) q ], and
1 2 =[( v−cu )/( x−β ), p−cq].
25. An error correction algebraic decoder for correcting a combination of a burst of errors and random errors in a failed sector, comprising:
a first set of instruction codes for iteratively adding and removing an erasure (N−B) times until the entire failed sector has been scanned, where N denotes the number of bytes in the failed sector, and B denotes the length of the burst of errors in the failed sector; and
wherein (B+2t) is less than, or equal to (R−1), where R denotes the number of check bytes in the failed sector, where t denotes the total number of random errors in the failed sector,
resulting in a corrected sector at a decoding latency that is a generally linear function of the number of the check bytes R, and wherein the decoding latency is expressed as follows:
decoding latency=5R ( N−B ).
26. The decoder of claim 25 , further comprising a second set of instruction codes for applying an initialization stage, to receive a plurality of syndromes and to generate a modified syndrome polynomial from the plurality of syndromes.
27. The decoder of claim 26 , further comprising a third set of instruction codes for iteratively removing (R−B) erasures, using the modified syndrome polynomial.
28. The decoder of claim 27 , further comprising a fourth set of instruction codes for calculating an error locator polynomial, presuming the initial existence of R erasures at a beginning of the failed sector.
29. The decoder of claim 28 , wherein if the error locator polynomial is valid, the error locator polynomial is added to a solution list.
30. The decoder of claim 25 , further comprising a fifth set of instruction codes for performing a cyclic redundancy check, and for selecting a valid burst and error locator and corresponding error values, to generate the corrected sector.
31. An error correction decoder for correcting a combination of a burst of errors and random errors in a failed sector, comprising:
means for iteratively adding and removing an erasure (N−B) times until the entire failed sector has been scanned, where N denotes the number of bytes in the failed sector, and B denotes the length of the burst of errors in the failed sector; and
wherein (B+2t) is less than, or equal to (R−1), where R denotes the number of check bytes in the failed sector, where t denotes the total number of random errors in the failed sector,
resulting in a corrected sector at a decoding latency that is a generally linear function of the number of the check bytes R, and wherein the decoding latency is expressed as follows:
decoding latency=5R ( N−B ).
32. The decoder of claim 31 , further comprising means for applying an initialization stage, to receive a plurality of syndromes and to generate a modified syndrome polynomial from the plurality of syndromes.
33. The decoder of claim 32 , further comprising means for removing (R−B) erasures, using the modified syndrome polynomial.
34. The decoder of claim 33 , further comprising means for calculating an error locator polynomial, presuming the initial existence of R erasures at a beginning of the failed sector.
35. The decoder of claim 34 , wherein if the error locator polynomial is valid, adding the error locator polynomial is added to a solution list.
36. The decoder of claim 31 , further comprising means for performing a cyclic redundancy check, and for selecting a valid burst and error locator and corresponding error values, to generate the corrected sector.
37. An error correction algebraic decoding method for correcting a combination of a burst of errors and random errors in a failed sector, comprising:
iteratively adding and removing an erasure (N−B) times until the entire failed sector has been scanned, where N denotes the number of bytes in the failed sector, and B denotes the length of the burst of errors in the failed sector; and
wherein (B+2t) is less than, or equal to (R−1), where R denotes the number of check bytes in the failed sector, where t denotes the total number of random errors in the failed sector, resulting in a corrected sector, and wherein the decoding latency is expressed as fallows:
decoding latency=5( N−B ).