Error correction codes
View Patent ↗Data stored on a storage medium is corrected by retrieving a plurality of data blocks and a plurality of error correction codes (ECCs) from the storage medium. An ECC corresponds to a data set having data from multiple data blocks, and the ECCs are generated prior to storing the data blocks and the ECCs in the storage medium. After retrieving the data blocks and ECCs from the storage medium, a data set is identified as having an error based on the data in the data set and the ECC corresponding to the data set, where an error indicates that the data in the data set retrieved from the storage medium is different from the data in the data set when the data was originally stored in the storage medium. Data in the data set identified as having an error is corrected using the ECC corresponding to the data set.
1. A method of correcting data stored on a storage medium, comprising:
retrieving a plurality of data blocks from the storage medium, wherein the plurality of data blocks retrieved from the storage medium form a first logical data array having rows and columns, wherein a row corresponds to a data block and a column corresponds to a data set;
retrieving a plurality of error correction codes (ECCs) from the storage medium,
wherein an ECC corresponds to a data set having data from multiple data blocks,
wherein the ECCs were generated prior to storing the data blocks and the ECCs in the storage medium;
identifying a data set in the first logical data array as having an error based on the data in the data set and the ECC corresponding to the data set,
wherein an error indicates that the data in the data set retrieved from the storage medium is different from the data in the data set at the time the data was originally stored in the storage medium;
forming a second logical data array from the first logical data array, wherein the second logical data array only includes columns from the first logical data array corresponding to data sets identified as having an error; and
correcting data in the data set in the second logical data array using the ECC corresponding to the data set.
2. The method of claim 1 further comprising:
retrieving a plurality of check sums from the storage medium,
wherein a check sum corresponds to a data block;
identifying a data block retrieved from the storage medium as having an error using the check sum corresponding to the data block; and
wherein the data corrected in the data set is from the data block identified as having an error.
3. The method of claim 1 , wherein identifying a data set comprises:
performing an exclusive-OR (XOR) operation of the data in the data set and the ECC corresponding to the data set; and
identifying the data set as having an error if the XOR operation produces a non-zero result.
4. The method of claim 1 , wherein identifying a data set comprises:
generating a new ECC for the data set, wherein the data in the data set used to generate the new ECC was retrieved from the storage medium;
comparing the new ECC with an ECC retrieved from the storage medium corresponding to the data set; and
identifying data set as having an error if the new ECC and the retrieved ECC are different.
5. The method of claim 1 , wherein the second logical data array includes a column of check sums, wherein a check sum corresponds to a data block, and wherein the data corrected in the data set is from a data block identified by the check sum corresponding to the data block as having an error.
6. The method of claim 1 , wherein the ECCs are Reed-Solomon codes.
7. The method of claim 1 , wherein a data set corresponds to a byte-sized portion of multiple data blocks.
8. A system of correcting data stored on a storage medium, comprising:
a data buffer including:
a plurality of data blocks retrieved from the storage medium,
wherein the plurality of data blocks retrieved from the storage medium form a first logical data array having rows and columns, and wherein a row corresponds to a data block and a column corresponds to a data set, and
a plurality of error correction codes (ECCs) retrieved from the storage medium,
wherein an ECC corresponds to a data set having data from multiple data blocks, and
wherein the ECCs were generated prior to storing the data blocks and the ECCs in the storage medium; and
a processor configured to:
identify a data set in the first logical data array as having an error based on the data in the data set and the ECC corresponding to the data set,
wherein an error indicates that the data in the data set retrieved from the storage medium is different from the data in the data set at the time the data was originally stored in the storage medium,
form a second logical data array from the first logical data array, wherein the second logical data array only includes columns from the first logical data array corresponding to data sets identified as having an error, and
correct data in the data set in the second logical data array using the ECC corresponding to the data set.
9. The system of claim 8 , wherein the data buffer further includes a plurality of check sums retrieved from the storage medium, wherein a check sum corresponds to a data block, and wherein the processor is further configured to identify a data block retrieved from the storage medium as having an error using the check sum corresponding to the data block, wherein the data corrected in the data set is from the data block identified as having an error.
10. The system of claim 8 , wherein a data set is identified by:
performing an exclusive-OR (XOR) operation of the data in the data set and the ECC corresponding to the data set; and
identifying the data set as having an error if the XOR operation produces a non-zero result.
11. The system of claim 8 , wherein a data set is identified by:
generating a new ECC for the data set, wherein the data in the data set used to generate the new ECC was retrieved from the storage medium;
comparing the new ECC with an ECC retrieved from the storage medium corresponding to the data set; and
identifying the data set as having an error if the new ECC and the retrieved ECC are different.
12. The system of claim 8 , wherein the second logical data array includes a column of check sums, wherein a check sum corresponds to a data block, and wherein the data corrected in the data set is from a data block identified by the check sum corresponding to the data block as having an error.
13. The system of claim 8 , wherein the ECCs are Reed-Solomon codes.
14. The system of claim 8 , wherein a data set corresponds to a byte-sized portion of multiple data blocks.
15. A computer-readable storage medium containing computer executable instructions for causing a computer to correct data stored on a storage medium, comprising instructions for:
retrieving a plurality of data blocks from the storage medium, wherein the plurality of data blocks retrieved from the storage medium form a first logical data array having rows and columns, wherein a row corresponds to a data block and a column corresponds to a data set;
retrieving a plurality of error correction codes (ECCs) from the storage medium,
wherein an ECC corresponds to a data set having data from multiple data blocks,
wherein the ECCs were generated prior to storing the data blocks and the ECCs in the storage medium;
identifying a data set in the first logical data array as having an error based on the data in the data set and the ECC corresponding to the data set,
wherein an error indicates that the data in the data set retrieved from the storage medium is different from the data in the data set the data was originally stored in the storage medium;
forming a second logical data array from the first logical data array, wherein the second logical data array only includes columns from the first logical data array corresponding to data sets identified as having an error; and
correcting data in the data set in the second logical data array using the ECC corresponding to the data set.
16. The computer readable medium of claim 15 further comprising instructions for:
retrieving a plurality of check sums from the storage medium,
wherein a check sum corresponds to a data block;
identifying a data block retrieved from the storage medium as having an error using the check sum corresponding to the data block; and
wherein the data corrected in the data set is from the data block identified as having an error.
17. The computer readable medium of claim 15 , wherein identifying a data set comprises:
performing an exclusive-OR (XOR) operation of the data in the data set and the ECC corresponding to the data set; and
identifying the data set as having an error if the XOR operation produces a non-zero result.
18. The computer readable medium of claim 15 , wherein identifying a data set comprises:
generating anew ECC for the data set, wherein the data in the data set used to generate the new ECC was retrieved from the storage medium;
comparing the new ECC with an ECC retrieved from the storage medium corresponding to the data set; and
identifying the data set as having an error if the new ECC and the retrieved ECC are different.
19. The computer readable medium of claim 15 , wherein the second logical data array includes a column of check sums, wherein a check sum corresponds to a data block, and wherein the data corrected in the data set is from a data block identified by the check sum corresponding to the data block as having an error.
20. The computer readable medium of claim 15 , wherein the ECCs are Reed-Solomon codes.
21. The computer readable medium of claim 15 , wherein a data set corresponds to a byte-sized portion of multiple data blocks.