Method and apparatus for detecting and correcting errors and erasures in product ECC-coded data arrays for DVD and similar storage subsystems

A machine-implementable method for managing detection and correction of errors and erasures in product-coded data arrays in a storage subsystem, said subsystem having a cyclic, tracked medium for storing the data arrays, an accessing mechanism, a local memory, and a processor coupling the mechanism and the memory and responsive to extrinsic commands for (1) causing the mechanism to read selected array data from the medium and write into the local memory, (2) ascertain and correct the error and erasure state from syndromes derived from said array data in row and column directions orthogonally, and (3) stage the corrected data from said subsystem, comprising the steps of:

• (a) iteratively syndrome processing the array data written into the memory in t1 row major order including (1) classifying each row as containing either no errors, random errors, or erasure errors;
• (2) forming a map (table 1) of indicia and correction patterns for each row containing random errors;
• (3) forming a pointer to each row containing erasure errors;
• and (4) effectuating the row array random error corrections in the memory according to the row map;
• and
• (b) iteratively syndrome processing the array data written into the memory in column major order including (1) forming a map (table 2) of indicia and correction patterns for each pair adjacent position within a column containing erasure errors as indexed by the row pointer, (2) forming a map for each position within a column containing random errors, and (3) effectuating the column array erasure corrections and the random error corrections in the memory according to the column map.

A machine-implementable method for managing detection and correction of errors and erasures in systematic product-coded data arrays in a storage subsystem, said subsystem having a cyclic, tracked medium for storing the data arrays, an accessing mechanism, a local memory, and a processor coupling the mechanism and the memory and responsive to extrinsic commands for (1) causing the mechanism to read selected array data from the medium and write into the local memory, (2) ascertain and correct the error and erasure state from syndromes derived from said array data in row and column directions orthogonally, and (3) stage the corrected data from said subsystem, comprising the steps of:

• (a) iteratively syndrome processing the array data written into the memory in row major order including (1) classifying each row as containing either no errors, random errors, or erasure errors, three or more syndrome-detected errors within the same array row being classified as an erasure;
• (2) forming a dense map (table 1) of indicia and correction patterns for each row containing random errors;
• (3) forming a pointer to each row containing erasure errors;
• and (4) effectuating the row array random error corrections in the memory according to the row map through logically combining the correction pattern recited in the map and the data in error in the array and writing back the combined result in place in the array;
• and
• (b)iteratively syndrome processing the array data written into the memory in column major order including (1) forming a dense map (table 2) of indicia and correction patterns for each pair adjacent position within a column containing erasure errors as indexed by the row pointer, (2) forming a dense map extension for each position within a column containing random errors, the dense column map and extension includes adjacent column locations subject only to erasure recovery and adjacent column locations subject only to random error recovery, and (3) effectuating the column array erasure corrections and the random error corrections in the memory according to the column map.

In a subsystem having a cyclic, tracked medium for storing systematic product linear block or cyclic error correction-coded (ECC) data arrays, a local memory, an arrangement for accessing selected arrays from said medium and writing the accessed arrays to the memory, and a processor coupling the accessing arrangement and memory and responsive to external commands, said processor including logic for detecting and correcting errors and erasures in the data arrays written into the memory, said subsystem further comprising:

• first ECC logic coupling the processor and the memory for iteratively syndrome evaluating the array data in row major order and (1) forming a first map classifying each row containing location indicia of random errors, their correction patterns, and pointers to rows containing erasure errors;
• and (2) effectuating row array random error corrections in place in memory according to the first map;
• and
• second ECC logic also coupling the processor and memory for iteratively syndrome evaluating the array data in column major order and (1) forming a second dense map containing location indicia and correction patterns for each pair adjacent position within each column containing erasure errors as indexed by a counterpart row pointer and location indicia within each column containing random errors and their correction patterns, and (2) effectuating column array erasure corrections and random error corrections in place in memory according to the second map.

An article of manufacture comprising a machine-readable memory having stored therein indicia of a plurality of processor-executable control program steps for detecting and correcting errors and erasures by a processor in systematic product linear block or cyclic error correction-coded (ECC) data arrays written into a memory, said processor accessing said memory, comprising the steps of:

• (a) indicia of a first control program step for iteratively syndrome processing the array-data in row major order and (1) forming a first dense map classifying each row containing location indicia of random errors, their correction patterns, and pointers to rows containing erasure errors;
• and (2) effectuating row array random error corrections in place in memory according to the first map;
• and
• (b) indicia of a second control program step for iteratively syndrome processing the array data in column major order and (1) forming a second dense map containing location indicia and correction patterns for each pair adjacent position within each column containing erasure errors as indexed by a counterpart row pointer and location indicia within each column containing random errors and their correction patterns, and (2) effectuating column array erasure corrections and random error corrections in place in memory according to the second map.