US 5,920,578 A · Method and apparatus for efficiently processing a multi-dimensional code

Abstract

An error detection and correction system is disclosed for efficiently processing a product code typically employed in an optical storage device. In particular, the present invention decreases the processing time associated with iteratively processing the rows and columns of the product code by processing only those code words that were "flagged" during a previous iteration. If, for example, while processing the column code words a byte in a column code word is corrected, then the corresponding intersecting row code word is flagged for processing during the "row pass." Only the row code words that have been flagged are processed during the "row pass", which significantly reduces buffer access latency and increases the overall throughput of the storage system. To assist in error detection and correction, an array of erasure pointers is employed where each erasure pointer corresponds to a byte in a code word. If there are no initial pointers set for a code word and the code word is uncorrectable or the possibility of a miscorrection is high, then all of the pointers for that code word are set and all of the intersecting code words are flagged for processing during the next pass. If a code word is error-free or correctable, then its pointers are cleared and the intersecting code words corresponding to the cleared erasure pointers are flagged for processing during the next pass. Eventually, enough pointers in a previously uncorrectable code word may be cleared such that the code word becomes correctable.

Claims24

Dependent claims

An apparatus for processing a multi-dimensional code received from an optical storage device, wherein the multi-dimensional code comprises a first set of code words that intersect with a second set of code words, a read flag is associated with at least one code word, and an erasure pointer is associated with at least one symbol of one code word, the apparatus comprising:

(a) a buffer for storing the symbols of the code words;
and
(b) an error detection and correction (EDAC) system for detecting and correcting errors in the code words, wherein:
(i) the EDAC system checks the read flag of a first code word and, if the read flag is set, reads the first code word from the buffer;
(ii) the EDAC system clears at least one erasure pointer of the first code word if the first code word is error free;
and
(iii) the EDAC system sets the read flag of a second code word that intersects with the first code word at the cleared erasure pointer.

4 more elements

A method for processing a multi-dimensional code received from an optical storage device, wherein the multi-dimensional code comprises a first set of code words that intersect with a second set of code words, a read flag is associated with at least one code word, and an erasure pointer is associated with at least one symbol of one code word, the method comprising the steps of:

(a) storing the symbols of the code words in a buffer;
(b) checking the read flag of a first set code word and, if the read flag is set, reading the first set code word from the buffer and clearing the read flag of the first set code word;
(c) if the first set code word comprises a symbol in error:
correcting the symbol in error;
and
setting the read flag of the second set code word that intersects with the first set code word at the corrected symbol;
if the first set code word is error free:
clearing at least one erasure pointer of the first set code word;
and
setting the read flag of the second set code word that intersects with the first set code word at the cleared erasure pointer;
(d) repeating steps (b) and (c) until all of the read flags associated with the code words in the first set have been checked;
(e) checking the read flag of a second set code word and, if the read flag is set, reading the second set code word from the buffer and clearing the read flag of the second set code word;
(f) if the second set code word comprises a symbol in error:
correcting the symbol in error;
and
setting the read flag of the first set code word that intersects with the second set code word at the corrected symbol;
if the second set code word is error free:
clearing at least one erasure pointer of the second set code word;
and
setting the read flag of the first set code word that intersects with the second set code word at the cleared erasure pointer;
(g) repeating steps (e) and (f) until all of the read flags associated with the code words in the second set have been checked;
and
(h) iterating steps (b) through (g) until all of the code words are error free or until the number of iterations reaches a predetermined count.

20 more elements

Dependencies are inferred from the claim text.

Method and apparatus for efficiently processing a multi-dimensional code

Life of this patent

Method and apparatus for efficiently processing a multi-dimensional code

Life of this patent

Abstract

Claims24