Extended error correction codes

• US 20040181734A1
• Filed: 03/14/2003
• Published: 09/16/2004
• Est. Priority Date: 03/14/2003
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Saliba, George A.
• Granted Patent: US 7,162,678 B2
• Time in Patent Office: Days
• US Class Current: 714/758
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: G11B 2020/1836 using a Reed Solomon [RS] code
• CPC Class Codes: G11B 2020/1843 using a cyclic redundancy check [CRC]
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence

Abstract

Errors in data retrieved from a storage medium are verified by retrieving a plurality of data blocks from the storage medium. A data set having data from multiple data blocks is selected, where the data set includes a plurality of rows corresponding to the data bocks and a row has data from a data block corresponding to the row. One or more error correction codes (ECCs) are retrieved from the storage medium, where the one or more ECCs correspond to the data set. A plurality of check sums are retrieved from the storage medium, where a check sum corresponds to a data block. Data blocks retrieved from the storage medium having errors are identified using the check sums corresponding to the data blocks. When the number of data blocks identified as having errors is greater than the number of ECCs for the data set, a first set of rows in the data set corresponding to the data blocks identified as having errors is selected, where the number of rows in the first set of rows is equal to the number of ECCs for the data set and less than the number of data blocks identified as having errors. Data for the first set of rows are generated using the ECCs for the data set, and the rows corresponding to the data blocks identified as having errors are verified based on the generated data for the first set of rows.

Claims

1. A method of verifying errors in data retrieved from a storage medium, comprising:

retrieving a plurality of data blocks from the storage medium;

selecting a data set having data from multiple data blocks,

wherein the data set includes a plurality of rows corresponding to the data blocks, and

wherein a row has data from a data block corresponding to the row;

retrieving one or more error correction codes (ECCs) from the storage medium,

wherein the one or more ECCs correspond to the data set;

retrieving a plurality of check sums from the storage medium,

wherein a check sum corresponds to a data block;

identifying data blocks retrieved from the storage medium having errors using the check sums corresponding to the data blocks; and

when the number of data blocks identified as having errors is greater than the number of ECCs for the data set;

selecting a first set of rows in the data set corresponding to the data blocks identified as having errors,

wherein the number of rows in the first set of rows is equal to the number of ECCs for the data set and less than the number of data blocks identified as having errors,

generating data for the first set of rows using the ECCs for the data set, and

verifying the rows corresponding to the data blocks identified as having errors based on the generated data for the first set of rows.

2. The method of claim 1, wherein verifying comprises:

comparing the generated data for the first set of rows to the data originally in the first set of rows; and

when all of the generated data and data originally in the first set of rows match, processing another data set having data from multiple data blocks.

3. The method of claim 1, wherein verifying comprises:

comparing the generated data for the first set of rows to the data originally in the first set of rows; and

when none of the generated data and data originally in the first set of rows match;

selecting a second set of rows in the data set corresponding to the data blocks identified as having errors, wherein at least one row in the second set differs from the rows in the first set,

generating data for the second set of rows using the ECCs, and

verifying the rows corresponding to the data blocks identified as having errors based on the generated data for the second set of rows.

4. The method of claim 1, wherein verifying comprises:

comparing the generated data for the first set of rows to the data originally in the first set of rows; and

when the generated data and data originally in one or more rows of the first set of rows match (matching rows) and the generated data and data originally in one or more rows of the first set of rows do not match (non-matching rows),

replacing the data originally in the non-matching rows with the generated data.

5. The method of claim 4, further comprising:

generating check sums for the data blocks corresponding to the non-matching rows; and

determining the number of data blocks identified as having errors using the generated check sums.

6. The method of claim 5, further comprising:

when the determined number of data blocks identified as having errors is greater than the number of ECCs for the data set, processing another data set having data from multiple data blocks.

7. The method of claim 5, further comprising:

when the determined number of data blocks identified as having errors is not greater than the number of ECCs for the data set, correcting the data blocks using the ECCs.

8. The method of claim 1, wherein the plurality of data blocks retrieved from the storage medium form a first logical data array having rows and columns, wherein a data block corresponds to a row in the first logical data array and the selected data set corresponds to a column in the first logical data array.

9. The method of claim 8 further comprising:

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 identified as having errors, and wherein the selected data set corresponds to a column in the second logical data array.

10. The method of claim 1, wherein the check sums are cyclic redundancy codes and the ECCs are Reed-Solomon codes.

11. The method of claim 1, wherein the selected data set corresponds to a byte-sized portion of multiple data blocks.

12. A system of verifying errors in data retrieved from a storage medium, comprising:

a data buffer including;

a plurality of data blocks retrieved from the storage medium,

one or more error correction codes (ECCs) retrieved from the storage medium, and

a plurality of check sums retrieved from the storage medium,

wherein a check sum corresponds to a data block; and

a processor configured to;

select a data set having data from multiple data blocks in the data buffer,

wherein the data set includes a plurality of rows corresponding to the data blocks, and

wherein the one or more ECCs correspond to the data set,

identify data blocks retrieved from the storage medium having errors using the check sums corresponding to the data blocks, and

when the number of data blocks identified as having errors is greater than the number of ECCs for the data set;

select a first set of rows in the data set corresponding to the data blocks identified as having errors,

wherein the number of rows in the first set of rows is equal to the number of ECCs for the data set and less than the number of data blocks identified as having errors,

generate data for the first set of rows using the ECCs for the data set, and

verify the rows corresponding to the data blocks identified as having errors based on the generated data for the first set of rows.

13. The system of claim 12, wherein the rows corresponding to the data blocks identified as having errors are verified by:

comparing the generated data for the first set of rows to the data originally in the first set of rows; and

when all of the generated data and data originally in the first set of rows match, processing another data set having data from multiple data blocks.

14. The system of claim 12, the rows corresponding to the data blocks identified as having errors are verified by:

comparing the generated data for the first set of rows to the data originally in the first set of rows; and

when none of the generated data and data originally in the first set of rows match;

selecting a second set of rows in the data set corresponding to the data blocks identified as having errors, wherein at least one row in the second set differs from the rows in the first set,

generating data for the second set of rows using the ECCs, and

verifying the rows corresponding to the data blocks identified as having errors based on the generated data for the second set of rows.

15. The system of claim 12, the rows corresponding to the data blocks identified as having errors are verified by:

comparing the generated data for the first set of rows to the data originally in the first set of rows; and

when the generated data and data originally in one or more rows of the first set of rows match (matching rows) and the generated data and data originally in one or more rows of the first set of rows do not match (non-matching rows), replacing the data originally in the non-matching rows with the generated data.

16. The system of claim 15, further comprising:

generating check sums for the data blocks corresponding to the non-matching rows; and

determining the number of data blocks identified as having errors using the generated check sums.

17. The system of claim 16, further comprising:

when the determined number of data blocks identified as having errors is greater than the number of ECCs for the data set, processing another data set having data from multiple data blocks.

18. The system of claim 16, further comprising:

when the determined number of data blocks identified as having errors is not greater than the number of ECCs for the data set, correcting the data blocks using the ECCs.

19. The system of claim 12, wherein the data blocks in the data buffer form a logical data array having rows and columns, wherein a data block corresponds to a row in the logical data array and the selected data set corresponds to a column in the logical data array.

20. The system of claim 19, wherein the selected data set corresponds to a byte-sized portion of multiple data blocks.

21. A computer-readable storage medium containing computer executable instructions for causing a computer to verify errors in data retrieved from a storage medium comprising instructions for:

retrieving a plurality of data blocks from the storage medium;

selecting a data set having data from multiple data blocks,

wherein the data set includes a plurality of rows corresponding to the data blocks, and

wherein a row has data from a data block corresponding to the row;

retrieving one or more error correction codes (ECCs) from the storage medium,

wherein the one or more ECCs correspond to the data set;

retrieving a plurality of check sums from the storage medium,

wherein a check sum corresponds to a data block;

identifying data blocks retrieved from the storage medium having errors using the check sums corresponding to the data blocks; and

when the number of data blocks identified as having errors is greater than the number of ECCs for the data set;

selecting a first set of rows in the data set corresponding to the data blocks identified as having errors,

wherein the number of rows in the first set of rows is equal to the number of ECCs for the data set and less than the number of data blocks identified as having errors,

generating data for the first set of rows using the ECCs for the data set, and

verifying the rows corresponding to the data blocks identified as having errors based on the generated data for the first set of rows.

22. The computer-readable medium of claim 21, wherein verifying comprises:

comparing the generated data for the first set of rows to the data originally in the first set of rows; and

when all of the generated data and data originally in the first set of rows match, processing another data set having data from multiple data blocks.

23. The computer-readable medium of claim 21, wherein verifying comprises:

comparing the generated data for the first set of rows to the data originally in the first set of rows; and

when none of the generated data and data originally in the first set of rows match;

selecting a second set of rows in the data set corresponding to the data blocks identified as having errors, wherein at least one row in the second set differs from the rows in the first set,

generating data for the second set of rows using the ECCs, and

verifying the rows corresponding to the data blocks identified as having errors based on the generated data for the second set of rows.

24. The computer-readable medium of claim 21, wherein verifying comprises:

comparing the generated data for the first set of rows to the data originally in the first set of rows; and

when the generated data and data originally in one or more rows of the first set of rows match (matching rows) and the generated data and data originally in one or more rows of the first set of rows do not match (non-matching rows), replacing the data originally in the non-matching rows with the generated data.

25. The computer-readable medium of claim 24, further comprising:

generating check sums for the data blocks corresponding to the non-matching rows; and

determining the number of data blocks identified as having errors using the generated check sums.

26. The computer-readable medium of claim 25, further comprising:

when the determined number of data blocks identified as having errors is greater than the number of ECCs for the data set, processing another data set having data from multiple data blocks.

27. The computer-readable medium of claim 25, further comprising:

when the determined number of data blocks identified as having errors is not greater than the number of ECCs for the data set, correcting the data blocks using the ECCs.