Correcting data using redundancy blocks
View Patent ↗Errors in data retrieved from a storage medium are corrected by retrieving a plurality of data blocks and a plurality of redundancy blocks associated with the plurality of data blocks from the storage medium. One or more data blocks retrieved from the storage medium having errors are identified and removed. When the number of data blocks identified as having errors is less than the number of retrieved redundancy blocks, one or more excess redundancy blocks are removed, and one or more retained redundancy blocks are kept from the retrieved redundancy blocks. One or more new redundancy blocks are generated based on the retrieved data blocks. One or more residual blocks are generated based on the one or more new redundancy blocks and the one or more retained redundancy blocks. One or more data blocks identified as having errors are corrected using the generated one or more residual blocks.
1. A method of correcting errors in data retrieved from a storage medium, comprising:
retrieving a plurality of data blocks from the storage medium;
retrieving a plurality of redundancy blocks associated with the plurality of data blocks from the storage medium;
identifying one or more data blocks retrieved from the storage medium having errors;
removing the one or more data blocks identified as having errors;
when the number of data blocks identified as having errors is less than the number of retrieved redundancy blocks, removing one or more excess redundancy blocks and keeping one or more retained redundancy blocks from the retrieved redundancy blocks;
generating one or more new redundancy blocks based on the retrieved data blocks;
generating one or more residual blocks based on the one or more new redundancy blocks and the one or more retained redundancy blocks; and
correcting the one or more data blocks identified as having errors using the generated one or more residual blocks.
2. The method of claim 1 , wherein identifying one or more data blocks retrieved from the storage medium having errors comprises:
retrieving a check sum associated with a retrieved data block from the storage medium;
generating a new check sum based on the retrieved data block; and
comparing the retrieved check sum with the new check to determine if the retrieved data block has errors.
3. The method of claim 2 , wherein the check sum is a cyclic redundancy code.
4. The method of claim 1 , wherein removing the one or more blocks identified as having errors comprises:
flagging the one or more data blocks identified as having errors as erasures.
5. The method of claim 1 , wherein the number of retained redundancy blocks is equal to the number of data blocks identified as having errors.
6. The method of claim 1 , wherein the one or more new redundancy blocks are generated based on the retrieved data blocks with the one or more data blocks identified as having errors removed.
7. The method of claim 1 , wherein the number of new redundancy blocks is equal to the number of data blocks identified as having errors.
8. The method of claim 1 , wherein generating one or more residual blocks comprises:
performing an exclusive-OR operation between a new redundancy block and a retrieved redundancy block.
9. The method of claim 1 , wherein the residual blocks are syndromes.
10. The method of claim 1 , wherein a residual block is a remainder after dividing a retrieved code word by a generator polynomial.
11. The method of claim 1 , wherein correcting the one or more data blocks identified as having errors comprises:
performing a Galois Field matrix multiplication operation between the one or more generated residual blocks and a correction matrix.
12. The method of claim 11 , wherein the correction matrix relates one or more data blocks to be corrected to the one or more residual blocks.
13. The method of claim 11 further comprising:
remove one or more rows from the correction matrix corresponding to the one or more excess redundancy block to generate a reduced correction matrix, wherein the Galois Field matrix multiplication operation is performed between the one or more generated residual blocks and the reduced correction matrix rather than the correction matrix.
14. The method of claim 13 , wherein the number of rows of the reduced correction matrix is equal to the number of data blocks identified as having errors
15. The method of claim 1 , wherein the plurality of redundancy blocks are Bose-Chaudhuri-Hocquenghem (BCH) codes.
16. The method of claim 15 , wherein BCH codes are Reed-Solomon codes.
17. A system of correcting errors in data retrieved from a storage medium, comprising:
a data buffer including:
a plurality of data blocks retrieved from the storage medium,
a plurality of redundancy blocks retrieved from the storage medium; and
a processor configured to:
identify one or more data blocks retrieved from the storage medium having errors,
remove the one or more data blocks identified as having errors,
when the number of data blocks identified as having errors is less than the number of retrieved redundancy blocks, remove one or more excess redundancy blocks and keep one or more retained redundancy blocks from the retrieved redundancy blocks,
generate one or more new redundancy blocks based on the retrieved data blocks,
generate one or more residual blocks based on the one or more new redundancy blocks and the one or more retained redundancy blocks, and
correct the one or more data blocks identified as having errors using the generated one or more residual blocks.
18. The system of claim 17 , wherein the number of retained redundancy blocks is equal to the number of data blocks identified as having errors.
19. The system of claim 17 , wherein the one or more new redundancy blocks are generated based on the retrieved data blocks with the one or more data blocks identified as having errors removed.
20. The system of claim 17 , wherein the number of new redundancy blocks is equal to the number of data blocks identified as having errors.
21. The system of claim 17 , wherein the one or more residual blocks are generated by:
performing an exclusive-OR operation between a new redundancy block and a retrieved redundancy block.
22. The system of claim 17 , wherein the one or more data blocks identified as having errors is corrected by:
performing a Galois Field matrix multiplication operation between the one or more generated residual blocks and a correction matrix.
23. The system of claim 22 , wherein the processor is further configured to:
remove one or more rows from the correction matrix corresponding to the one or more excess redundancy block to generate a reduced correction matrix, wherein the Galois Field matrix multiplication operation is performed between the one or more generated residual blocks and the reduced correction matrix rather than the correction matrix.
24. The system of claim 23 , wherein the number of rows of the reduced correction matrix is equal to the number of data blocks identified as having errors
25. A computer-readable storage medium containing computer executable instructions for causing a computer to correct errors in data retrieved from a storage medium, comprising instructions for:
retrieving a plurality of data blocks from the storage medium;
retrieving a plurality of redundancy blocks associated with the plurality of data blocks from the storage medium;
identifying one or more data blocks retrieved from the storage medium having errors;
removing the one or more data blocks identified as having errors;
when the number of data blocks identified as having errors is less than the number of retrieved redundancy blocks, removing one or more excess redundancy blocks and keeping one or more retained redundancy blocks from the retrieved redundancy blocks;
generating one or more new redundancy blocks based on the retrieved data blocks;
generating one or more residual blocks based on the one or more new redundancy blocks and the one or more retained redundancy blocks; and
correcting the one or more data blocks identified as having errors using the generated one or more residual blocks.
26. The computer-readable storage medium of claim 25 , wherein identifying one or more data blocks retrieved from the storage medium having errors comprises:
retrieving a check sum associated with a retrieved data block from the storage medium;
generating a new check sum based on the retrieved data block; and
comparing the retrieved check sum with the new check to determine if the retrieved data block has errors.
27. The computer-readable storage medium of claim 26 , wherein the check sum is a cyclic redundancy code.
28. The computer-readable storage medium of claim 25 , wherein removing the one or more blocks identified as having errors comprises:
flagging the one or more data blocks identified as having errors as erasures.
29. The computer-readable storage medium of claim 25 , wherein the number of retained redundancy blocks is equal to the number of data blocks identified as having errors.
30. The computer-readable storage medium of claim 25 , wherein the one or more new redundancy blocks are generated based on the retrieved data blocks with the one or more data blocks identified as having errors removed.
31. The computer-readable storage medium of claim 25 , wherein the number of new redundancy blocks is equal to the number of data blocks identified as having errors.
32. The computer-readable storage medium of claim 25 , wherein generating one or more residual blocks comprises:
performing an exclusive-OR operation between a new redundancy block and a retrieved redundancy block.
33. The computer-readable storage medium of claim 25 , wherein the residual blocks are syndromes.
34. The computer-readable storage medium of claim 25 , wherein a residual block is a remainder after dividing a retrieved code word by a generator polynomial.
35. The computer-readable storage medium of claim 25 , wherein correcting the one or more data blocks identified as having errors comprises:
performing a Galois Field matrix multiplication operation between the one or more generated residual blocks and a correction matrix.
36. The computer-readable storage medium of claim 35 , wherein the correction matrix relates one or more data blocks to be corrected to the one or more residual blocks.
37. The computer-readable storage medium of claim 35 further comprising:
remove one or more rows from the correction matrix corresponding to the one or more excess redundancy block to generate a reduced correction matrix, wherein the Galois Field matrix multiplication operation is performed between the one or more generated residual blocks and the reduced correction matrix rather than the correction matrix.
38. The computer-readable storage medium of claim 37 , wherein the number of rows of the reduced correction matrix is equal to the number of data blocks identified as having errors
39. The computer-readable storage medium of claim 25 , wherein the plurality of redundancy blocks are Bose-Chaudhuri-Hocquenghem (BCH) codes.
40. The computer-readable storage medium of claim 39 , wherein BCH codes are Reed-Solomon codes.