Error correction and concurrent verification of a product code
DCFirst Claim
1. A correction validator for validating corrections to an error correction code (ECC) made by an ECC decoder, wherein the ECC code is a multi-dimensional code comprised of a first set of code words that intersect with a second set of code words, the ECC decoder process the first and second set of code words in iterative passes, and the ECC decoder skips a code word if a predetermined condition is satisfied, the correction validator comprises:
- (a) at least one register for storing a validation value computed in response to data in the multi-dimensional code and computed proximate in time to when the ECC decoder processes the data in the multi-dimensional code;
(b) an offset controller for adjusting the validation value according to an offset value when the ECC decoder skips a code word in the multi-dimensional code; and
(c) a comparator for comparing a final validation value to a predetermined value when the ECC decoder finishes processing the multi-dimensional code, wherein a result of the comparison indicates whether corrections made by the ECC decoder are valid.
3 Assignments
Litigations
0 Petitions
Accused Products
Abstract
A multi-layered error detection and correction (EDAC) system is disclosed for processing an error correction code (ECC) typically employed in optical disk storage devices. A first layer of the EDAC system includes a primary ECC, such as a multiple burst Reed-Solomon code, and a second layer incudes a secondary ECC, such as a CRC code, for use in verifying the validity of the corrections made using the primary ECC. The primary ECC is multi-dimensional and, in the embodiment disclosed herein, it is a two-dimensional P/Q product code typically employed in a CD-ROM storage device. The secondary ECC operates in unison with the primary ECC. As the EDAC system processes and corrects the data using the primary ECC, the EDAC system also simultaneously updates the secondary ECC. In this manner, when the EDAC system is finished processing the data using the primary ECC, the validation syndrome generated by the secondary ECC is available immediately for checking the validity of the corrections. Consequently, the additional pass otherwise required when no uncorrectable errors are encountered after completing a P or Q pass is obviated. To significantly increase the processing of the EDAC system, error-free code words are skipped during the iterative passes of the multi-dimensional primary ECC. When a code word is skipped, the validation syndrome generated using the secondary ECC is adjusted to account for the skipped data bytes.
91 Citations
33 Claims
-
1. A correction validator for validating corrections to an error correction code (ECC) made by an ECC decoder, wherein the ECC code is a multi-dimensional code comprised of a first set of code words that intersect with a second set of code words, the ECC decoder process the first and second set of code words in iterative passes, and the ECC decoder skips a code word if a predetermined condition is satisfied, the correction validator comprises:
-
(a) at least one register for storing a validation value computed in response to data in the multi-dimensional code and computed proximate in time to when the ECC decoder processes the data in the multi-dimensional code; (b) an offset controller for adjusting the validation value according to an offset value when the ECC decoder skips a code word in the multi-dimensional code; and (c) a comparator for comparing a final validation value to a predetermined value when the ECC decoder finishes processing the multi-dimensional code, wherein a result of the comparison indicates whether corrections made by the ECC decoder are valid. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
5. The correction validator as recited in claim 2, wherein:
-
(a) the multi-dimensional code is a product code comprising a plurality of column code words and a plurality of row code words; and (b) the offset value corresponding to one skipped column code word is one symbol of a row code word.
-
-
6. The correction validator as recited in claim 2, wherein:
-
(a) the multi-dimensional code is a product code comprising a plurality of column code words and a plurality of row code words; and (b) the offset value corresponding to one skipped row code word is computed relative to the number of symbols in a row code word and the number of row code words.
-
-
7. The correction validator as recited in claim 1, wherein the validation value comprises a first and second validation value and the at least one register comprises:
-
(a) a data register for storing the first validation value in response to symbols of the multi-dimensional code; and (b) an error register for storing the second validation value in response to correction values generated by the ECC decoder.
-
-
8. The correction validator as recited in claim 7, wherein:
-
(a) the first validation value is computed during a first pass by the ECC decoder over the first set of codewords; and (b) the second validation value is computed proximate in time with the ECC decoder correcting data in the multi-dimensional code.
-
-
9. The correction validator as recited in claim 7, further comprising a means for combining the first validation value and the second validation value to generate the final validation value.
-
10. The correction validator as recited in claim 1, further comprising a mod-2 adder for adding a correction value generated by the ECC decoder to the validation value adjusted by the offset value, wherein a result of the addition replaces the validation value stored in the register.
-
-
11. A method for validating corrections to an error correction code (ECC) made by an ECC decoder, wherein the ECC code is a multi-dimensional code comprised of a first set of code words that intersect with a second set of code words, the ECC decoder process the first and second set of code words in iterative passes, and the ECC decoder skips a code word if a predetermined condition is satisfied, the method comprising the steps of:
-
(a) computing a validation value in response to data in the multi-dimensional code and proximate in time to when the ECC decoder processes the data in the multi-dimensional code; (b) adjusting the validation value according to an offset value when the ECC decoder skips a code word in the multi-dimensional code; and (c) comparing a final validation value to a predetermined value when the ECC decoder finishes processing the multi-dimensional code, wherein a result of the comparison indicates whether corrections made by the ECC decoder are valid. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
15. The method as recited in claim 12, wherein:
-
(a) the multi-dimensional code is a product code comprising a plurality of column code words and a plurality of row code words; and (b) the offset value corresponding to one skipped column code word is one symbol of a row code word.
-
-
16. The method as recited in claim 12, wherein:
-
(a) the multi-dimensional code is a product code comprising a plurality of column code words and a plurality of row code words; and (b) the offset value corresponding to one skipped row code word is computed relative to the number of symbols in a row code word and the number of row code words.
-
-
17. The method as recited in claim 11, wherein the validation value comprises a first and second validation value, further comprising the steps of:
-
(a) computing the first validation value in response to symbols of the multi-dimensional code; and (b) computing the second validation value in response to correction values generated by the ECC decoder.
-
-
18. The method as recited in claim 17, wherein:
-
(a) the first validation value is computed during a first pass by the ECC decoder over the first set of code words; and (b) the second validation value is computed proximate in time with the ECC decoder correcting data in the multi-dimensional code.
-
-
19. The method as recited in claim 17, further comprising the step of combining the first validation value and the second validation value to generate the final validation value.
-
20. The method as recited in claim 11, wherein the step of adjusting the validation value further comprises the steps of:
-
(a) adding modulo-2 a correction value generated by the ECC decoder to the validation value adjusted by the offset value; and (b) replacing the validation value with the result of the addition.
-
-
-
21. An error detection and correction (EDAC) system for correcting errors in a multi-dimensional error correction code (ECC) comprised of a first set of code words that intersect with a second set of code words, the EDAC system comprising:
-
(a) a data buffer for storing the first and second set of code words of the multi-dimensional code; (b) an ECC decoder for reading from the buffer the first and second set of code words in iterative passes, wherein the ECC decoder does not read a code word from the buffer if a predetermined condition is satisfied; (c) at least one register for storing a validation value computed in response to data in the multi-dimensional code and correction values generated by the ECC decoder, wherein the validation value is computed proximate in time to when the ECC decoder reads the data of the multi-dimensional code from the buffer; (d) an offset controller for adjusting the validation value according to an offset value when the ECC decoder does not read a code word in the multi-dimensional code from the buffer; and (e) a comparator for comparing a final validation value to a predetermined value when the ECC decoder finishes processing the multi-dimensional code, wherein a result of the comparison indicates whether corrections made by the ECC decoder are valid. - View Dependent Claims (22, 23, 24)
-
-
25. A correction validator for validating corrections to an error correction code (ECC) made by an ECC decoder, wherein the ECC code is a multi-dimensional code comprised of a first set of code words that intersect with a second set of code words, the ECC decoder process the first and second set of code words in iterative passes, the correction validator comprises:
-
(a) at least one register for storing a validation value computed in response to data in the multi-dimensional code and computed proximate in time to when the ECC decoder processes the data in the multi-dimensional code; and (b) a comparator for comparing a final validation value to a predetermined value after the ECC decoder finishes processing the first set of code words, wherein the comparison is made for at least two passes over the first set of code words, and a result of the comparison indicates whether corrections made by the ECC decoder are valid and complete. - View Dependent Claims (26, 27)
-
-
28. A method for validating corrections to an error correction code (ECC) made by an ECC decoder, wherein the ECC code is a multi-dimensional code comprised of a first set of code words that intersect with a second set of code words, the ECC decoder processes the first and second set of code words in iterative passes, the method comprising the steps of:
-
(a) computing a validation value in response to data in the multi-dimensional code and proximate in time to when the ECC decoder processes the data in the multi-dimensional code; and (b) after the ECC decoder finishes processing the first set of code words, comparing a final validation value to a predetermined value for at least two passes over the first set of code words, wherein a result of the comparison indicates whether corrections made by the ECC decoder are valid. - View Dependent Claims (29, 30)
-
-
31. A correction validator for validating corrections to an error correction code (ECC) made by an ECC decoder, wherein the ECC code is a multi-dimensional code comprised of a first set of code words that intersect with a second set of code words, the ECC decoder process the first and second set of code words in iterative passes, the correction validator comprises:
-
(a) a data register for storing a data validation value computed in response to data in the multi-dimensional code and computed proximate in time to when the ECC decoder processes the data in the multi-dimensional code; (b) an error register for storing an error validation value computed in response to correction values generated by the ECC decoder for correcting the data in the multi-dimensional code; (c) a means for combining the contents of the data register and the error register to generate a final validation value; and (d) a comparator for comparing the final validation value to a predetermined value, wherein a result of the comparison indicates whether corrections made by the ECC decoder are valid and complete. - View Dependent Claims (32, 33)
-
Specification