Error correction algorithm using interleaved parity check and Reed-Solomon code
View Patent ↗Methods and apparatuses for correcting errors in a data stream are described herein. In one aspect, the error correction process is operable to correct errors in at least two separate types of data streams, each of which utilizes a distinct error correction scheme. The error correction process utilizes Reed-Solomon code and Error Detection Code (EDC) in combination for error correction. The process comprises using a Reed-Solomon code to identify errors in a plurality of data blocks and attempting to correct the errors. An EDC map is then generated, wherein the EDC map identifies the location of the errors within the corresponding data blocks which includes errors that are not corrected by the Reed-Solomon code.
1. An error correction device operable to receive a stream of encoded data, which includes a plurality of error detection codes (EDCs), the error correction device comprising:
a decoder operable to use the plurality of EDCs to detect errors in a first dimension of a two dimensional data array derived from the stream of encoded data, and use a Reed-Solomon code to correct codewords in a second dimension of the two dimensional data array, wherein the decoder is further operable to map codewords from the Reed-Solomon code to corresponding bits within at least one of the EDCs, wherein the decoder is operable to generate an EDC map to correlate the codewords from the Reed-Solomon code to EDC residuals, wherein the EDC map consists of binary ones for the bits within the EDC residual that are affected by a changing symbol within the Reed-Solomon codeword, and binary zeros in all the other bits.
2. The error correction device according to claim 1 , wherein a symbol size of the Reed-Solomon code is smaller than that of at least one of the EDCs.
3. The error correction device according to claim 2 , wherein the data storage medium is selected from a group consisting of optical disk, magnetic disk, optical tape, and magnetic tape.
4. The error correction device according to claim 1 , wherein the error correction device is configured as a part of a controller, and the controller is coupled to a transducer for detecting data recorded on a data storage medium.
5. The error correction device according to claim 4 , wherein the transducer comprises a magnetic tape drive head, and the data storage medium comprises a magnetic tape.
6. The error correction device according to claim 1 , wherein at least one of the EDCs is described by a primitive polynomial having a form g(x)=x n +1, where n is the number of bits within an EDC symbol.
7. The error correction device according to claim 6 , wherein a generator polynomial of the EDC has a form G(X)=X+α s wherein α is a root of the primitive polynomial and s is any integer between 0 and n−1.
8. The error correction device according to claim 1 , wherein the EDC map is normalized by performing a cyclic bit-rotation or other mapping operation, such that the bits within a bit-mask directly map to corresponding bits within the EDC residual.
9. The error correction device according to claim 8 , wherein two or more EDC maps are generated and a bit-wise logical OR of all the EDC maps is used for determining the bits of the EDC residual affected by all the notable Reed-Solomon codewords.
10. The error correction device according to claim 8 , wherein two or more EDC maps are generated and bit-wise logical AND and OR operations are used within the EDC maps to determine whether two or more Reed-Solomon codewords could affect the same bits within the EDC residual.
11. The error correction device according to claim 1 , wherein the decoder is operable to use an EDC map, and is further operable to determine an error pattern for a notable Reed-Solomon codeword deemed either non-correctable or unreliably corrected.
12. The error correction device according to claim 1 , wherein a second EDC from the plurality of EDCs is used exclusively for error detection and can determine whether corrections from a first EDC from the plurality of EDCs are reliable.
13. The error correction device according to claim 12 , wherein the second EDC comprises a cyclic redundancy check (CRC).
14. The error correction device according to claim 12 , wherein the second EDC comprises a Reed-Solomon code.
15. A method of data error correction comprising:
using a Reed-Solomon code to identify errors in a plurality of data blocks and attempt to correct the errors;
using cyclic redundancy check to determine whether there are errors in any of the data blocks; and
using an error detection code (EDC) in each data block to correct errors in the data block which are not corrected by the Reed-Solomon code, wherein using an EDC in each data block to correct errors further comprises generating an EDC map, wherein the EDC map identifies the location of the errors within the corresponding data blocks which includes errors that are not corrected by the Reed-Solomon code, wherein generating an EDC map comprises:
creating a set of EDC Maps for each notable Reed-Solomon codeword, the EDC map consisting of binary ones for the bits within the EDC residual that might be are affected by a changing symbol within the Reed-Solomon codeword, and binary zeros in all the other bits; and
normalizing the EDC Maps by performing a mapping operation, such that the bits within the bit-mask directly map to corresponding bits within the EDC residual.
16. The method according to claim 15 , wherein the mapping operation comprises a cyclic bit-rotation.
17. The method according to claim 15 , wherein at least one of the EDC is described by a primitive polynomial having a form g(x)=x n +1, where n is the number of bits within an EDC symbol.
18. The method according to claim 17 , wherein a generator polynomial of the EDC has a form G(X)=X+α s where α is a root of the primitive polynomial and s is any integer between 0 and n−1.
19. A tape drive operable to perform the method according to claim 15 .
20. A magnetic tape drive comprising:
a controller operable to use a Reed-Solomon code to identify errors in a plurality of data blocks and attempt to correct the errors, use cyclic redundancy check to determine whether there are errors in any of the data blocks, and use EDC in each data block to correct errors in the data block which are not corrected by the Reed-Solomon code,
wherein the controller is further operable to generate an EDC map that maps codewords from the Reed-Solomon code to corresponding bits within at least one EDC, wherein the controller is operable to use the EDC map to identify the location of the at least one error within the corresponding data block,
wherein the at least one error is not corrected by the Reed-Solomon code, and the controller is further operable to use the EDC map to correct the at least one error.
21. An error correction device operable to receive a stream of encoded data, which includes a plurality of error detection codes (EDCs), the error correction device comprising:
a decoder operable to use the plurality of EDCs to detect errors in a first dimension of a two dimensional data array derived from the stream of encoded data, and use a Reed-Solomon code to correct codewords in a second dimension of the two dimensional data array, wherein the decoder is further operable to map codewords from the Reed-Solomon code to corresponding bits within at least one of the EDCs,
wherein at least one of the EDCs is described by a primitive polynomial having a form g(x)=x n +1, where n is the number of bits within an EDC symbol.
22. The error correction device according to claim 21 , wherein a generator polynomial of the EDC has a form G(X)=X+α s wherein α is a root of the primitive polynomial and s is any integer between 0 and n−1.
23. An error correction device operable to receive a stream of encoded data, which includes a plurality of error detection codes (EDCs), the error correction device comprising:
a decoder operable to use the plurality of EDCs to detect errors in a first dimension of a two dimensional data array derived from the stream of encoded data, and use a Reed-Solomon code to correct codewords in a second dimension of the two dimensional data array, wherein the decoder is further operable to map codewords from the Reed-Solomon code to corresponding bits within at least one of the EDCs,
wherein the decoder is operable to generate an EDC map to correlate the codewords from the Reed-Solomon code to EDC residuals, wherein the EDC map consists of binary ones for the bits within the EDC residual that are affected by a changing symbol within the Reed-Solomon codeword, and binary zeros in all the other bits.
24. The error correction device according to claim 23 , wherein the EDC map is normalized by performing a cyclic bit-rotation or other mapping operation, such that the bits within a bit-mask directly map to corresponding bits within the EDC residual.
25. The error correction device according to claim 24 , wherein two or more EDC maps are generated and a bit-wise logical OR of all the EDC maps is used for determining the bits of the EDC residual affected by all the notable Reed-Solomon codewords.
26. The error correction device according to claim 24 , wherein two or more EDC maps are generated and bit-wise logical AND and OR operations are used within the EDC maps to determine whether two or more Reed-Solomon codewords could affect the same bits within the EDC residual.
27. A method of data error correction comprising:
using a Reed-Solomon code to identify errors in a plurality of data blocks and attempt to correct the errors;
using cyclic redundancy check to determining whether there are errors in any of the data blocks; and
using an error detection code (EDC) in each data block to correct errors in the data block which are not corrected by the Reed-Solomon code,
wherein using EDC in each data block to correct errors further comprises generating an EDC map, wherein the EDC map identifies the location of the errors within the corresponding data blocks which includes errors that are not corrected by the Reed-Solomon code, and
wherein generating an EDC map comprises:
creating a set of EDC Maps for each notable Reed-Solomon codeword, the EDC map consisting of binary ones for the bits within the EDC residual that are affected by a changing symbol within the Reed-Solomon codeword, and binary zeros in all the other bits; and
normalizing the EDC Maps by performing a mapping operation, such that the bits within the bit-mask directly map to corresponding bits within the EDC residual.
28. The method according to claim 27 , wherein the mapping operation comprises a cyclic bit-rotation.
29. The method according to claim 28 , wherein at least one of the EDC is described by a primitive polynomial having a form g(x)=x n +1, where n is the number of bits within an EDC symbol.
30. The method according to claim 29 , wherein a generator polynomial of the EDC has a form G(X)=X+α s where α is a root of the primitive polynomial and s is any integer between 0 and n−1.