Error-correction code for digital data on video disc

A process for generating a two-dimensional array comprising the steps of:

• placing serially multi-bit words to said two-dimensional array to less than all of the available data areas of said array;
• computing over the entire field of said two-dimensional array at least one auxiliary check byte;
• and
• computing and placing in remaining portions two-dimensional array column checking rows and row checking columns whereby said two-dimensional array contains two-dimensional error correction for the regeneration of data.

A memory for storing digital data, said memory being encoded with a three-dimensional data array for receiving an error-correction protocol, said memory for receiving said data array including:

• a memory for receiving multi-bit binary words, said words being written in rows and columns to form successive two-dimensional data arrays, said memory at said two-dimensional data arrays being addressable sequentially to form the three-dimensional data array;
• said memory at said two-dimensional data arrays including column-correcting rows and row-correction columns whereby each two-dimensional data array can be addressed for error correction along vectors in two dimensions;
• said successive two-dimensional data arrays of said three-dimensional array in said memory including at least one two-dimensional redundant array in said memory;
• and
• said two-dimensional redundant array of said memory being disposed for individual error correction of discrete errors in the two-dimensional arrays of the three-dimensional array along correction vectors different than those provided by said row-correcting columns and said column-correcting rows of said two-dimensional data arrays.

A process of generating a three-dimensional data array containing redundancy information comprising:

• generating at least one two-dimensional data array having rows and columns by serially placing multi-bit binary words until said array contains data;
• generating sequentially after said first two-dimensional data array a plurality of correspondent data arrays whereby successive two-dimensional data arrays are serially generated to form said three-dimensional data array;
• generating for each two-dimensional data array a plurality of column-correcting rows and row-correcting columns whereby error in each of said two-dimensional data arrays is individually addressable along two error-correcting vectors within said two-dimensional data arrays to redundantly correct any single error;
• and
• generating across the two-dimensional arrays at least one two-dimensional redundant array, whereby redundancy data from said two-dimensional redundant arrays are individually addressable to error along dimensions across said two-dimensional data arrays.

A process of writing a two-dimensional data array comprising the steps of:

• filling serially in said two-dimensional array data to an area of said array;
• generating and filling row correcting columns for locating and correcting error in rows of said two-dimensional data array;
• generating and filling column correcting rows for locating and correcting error in columns of said two-dimensional data array;
• whereby said two-dimensional array contains two-dimensional correction directions along said array;
• and
• serially writing to a memory media said rows and columns of said data array including said row correcting columns and said column correcting rows, said writing occurring from a sequence along directions differing from said error-correction whereby sequential errors on read back from said memory are individually addressable by differing data, including errors in said column-correcting rows and said row-correcting columns.

A process of generating a three-dimensional data array containing redundancy information comprising in combination:

• generating a plurality of two-dimensional data arrays having rows and columns by serially placing multi-bit binary words to said data array;
• generating for each two-dimensional data array a plurality of column correcting rows and row-correcting columns whereby error in each two-dimensional array is individually addressable along two error-correcting directions of first and second differing direction to redundantly correct any single error;
• generating across the two-dimensional arrays of said three-dimensional array along a third dimension a plurality of two-dimensional redundant arrays, the third dimension of generation being different in direction from the two error-correcting directions of said two-dimensional data arrays whereby redundancy data from said two-dimensional data arrays are individually addressable to any single error across the third dimension to any of said two-dimensional arrays;
• and
• writing to a memory media from said three-dimensional array along a fourth direction of said three-dimensional array, said write causing sequential error on read back from said memory media to be addressable by differing error-correction code combinations from said column correcting rows, said row correcting columns and said two-dimensional redundant arrays.

A process of reading from a memory media a two-dimensional array, said two-dimensional array having error-correction code therein, said two-dimensional data array comprising:

• multi-bit binary words, said words being in rows and columns of sequential words filling less than all the data spaces of said array, said data array including at least one data interval therein for at least one auxiliary check byte computed across said data array and placed in said data interval;
• said two-dimensional array including first and second row-correcting columns and first and second column-correcting rows for locating and correcting error across said respective rows and columns;
• and
• the process of reading said two-dimensional data array comprising the steps of:
• computing across rows of said two-dimensional array to generate at least two columns of row syndromes, said syndromes having values to flag the presence of errors,
• computing across said columns to form at least two rows of column syndromes having values to flag the presence of error;
• and
• computing across said data array including said auxiliary check bytes syndromes to flag the presence of error.

A process of reading from a memory media a three-dimensional data array for error-correction protocol incorporated therein, said data array including multi-bit binary words, said words being filled in rows and columns to form successive two-dimensional data arrays, said two-dimensional data arrays being addressable sequentially to form said three-dimensional data arrays;

• each said two-dimensional data array including at least paired column correcting rows and at least paired row-correcting columns whereby each two-dimensional data array can be addressed for discrete error correction in two-dimensions, said successive two-dimensional arrays of said three-dimensional array including at least first and second two-dimensional redundant arrays, said two-dimensional redundant arrays being disposed for individual error correction of discrete errors across the two-dimensional arrays of said three-dimensional array along directions differing from those provided by said row correcting columns and said column correcting rows, said process of reading from a memory media comprising the steps of:
• generating for one two-dimensional array at least two columns of syndromes, each syndrome addressed to a row of data, said syndrome having values for indicating error;
• generating for one array at least two rows of syndromes having values for indicating the presence of error;
• and
• generating syndromes across said two-dimensional arrays including said two-dimensional redundant arrays whereby single error may be addressed parallel to first, second and third differing directions along said arrays.

A process of generating a group of three-dimensional data arrays containing redundancy information comprising in combination:

• generating a plurality of two-dimensional data arrays having rows and columns by serially filling data bits to said data array;
• generating for each two-dimensional data array a plurality of column correcting rows and row-correcting columns whereby on read back error in each two-dimensional array is individually addressable along first and second directions to redundantly correct discrete error;
• generating across the two-dimensional arrays of said three-dimensional arrays along a third direction a plurality of redundancy two-dimensional arrays, the third direction being different from the two error-correcting directions of said two-dimensional data arrays whereby on read back discrete errors from said two-dimensional data arrays are individually addressable to correct error through the dimension of said two-dimensional data arrays;
• writing to a memory media from said three-dimensional arrays along a fourth direction through said three-dimensional array, said write causing on read back sequential discrete error to be addressable by differing error-correction codes from said column correcting rows, said row correcting columns and said two-dimensional redundant data arrays;
• and
• writing said redundant three-dimensional array to said memory media.

An error-correction protocol for reading a three-dimensional data array, said data array having a plurality of two-dimensional data arrays having rows and columns serially filled with multi-bit binary data words, at least one auxiliary check byte computed across said data words and plurality of column correcting rows and row correcting columns aligned to said two-dimensional data array;

• a collection of said data arrays forming said three-dimensional data array and having a plurality of two-dimensional redundant data arrays for correcting error across said two-dimensional data arrays;
• the process comprising the steps of:
• locating a two-dimensional data array to be decoded from within said three-dimensional array;
• generating for the located data array only respective column syndromes and row syndromes from said data and said column-correcting rows and row connecting columns, said syndromes having values to indicate presence of error;
• decoding said syndromes for error in the dimension of said two-dimensional array having the most values indicating the presence of error;
• thereafter decoding said syndromes for error in the remaining dimension of said two-dimensional array and if all said values indicating the presence of error are eliminated, generating an auxiliary check byte syndrome, said auxiliary syndrome having a value to indicate error.

An apparatus for reading from a memory media a two-dimensional array, said two-dimensional array having error-correction code therein, said two-dimensional array comprising multi-bit binary words, said words being in rows and columns of sequential words filling less than all the data spaces of said array, said array including at least one data interval therein for at least one auxiliary check byte computed across said data array and placed in said data interval, said two-dimensional array including first and second row-correcting columns and first and second column-correcting rows for locating and correcting errors across said respective rows and columns, said apparatus comprising:

• means for computing across rows of said two-dimensional array to generate at least two columns of row correction syndromes, said syndromes having values to flag the presence of errors;
• means for computing across said columns to form at least two rows of column correction syndromes having values to flag the presence of errors;
• and
• means for computing across said data array including said auxiliary check bytes syndromes to flag the presence of errors.

An apparatus for reading from memory media a three-dimensional data array for error-correction protocol incorporated therein, said data array including multi-bit binary words, said words being filled in rows and columns to form successive two-dimensional data arrays, said two-dimensional data arrays being addressable sequentially to form said three-dimensional data arrays;

• each said two-dimensional data array including at least paired column-correcting rows and at least paired row-correcting columns whereby each two-dimensional data array can be addressed for discrete error correction in two dimensions, said successive two-dimensional arrays of said three-dimensional array including at least first and second two-dimensional redundant arrays, said two-dimensional redundant arrays being disposed for individual error correction of discrete errors across the two-dimensional arrays of said three-dimensional array along directions differing from those provided by said row-correcting columns and said column-correcting rows, said apparatus comprising:
• means for generating for one two-dimensional array at least two columns of syndromes, each syndrome addressed to a row of data, said syndrome having values for indicating error;
• means for generating for one array at least two rows of syndromes having values for indicating the presence of error;
• and
• means for generating syndromes across said two-dimensional arrays including said two-dimensional redundant arrays whereby single error may be addressed parallel to first, second and third differing directions along said arrays.

A processor for decoding a data array comprising:

• temporary memory means for storing said data array;
• an arithmetic logic unit;
• a plurality of latches for storing memory addresses;
• and
• permanent memory means for storing a program adapted to control said temporary memory means, arithmetic logic unit and latches to decode a two-dimensional data array having error-correction code therein, said data array comprising data intervals of multi-bit binary words, said words being written in rows and columns of sequential multi-bit binary words filling less than all of the data intervals of said array;
• said data array including at least one data interval therein for at least one auxiliary check byte computed across the data array;
• said two-dimensional data array including at least first and second row-correcting columns having means for correcting errors across rows of data;
• said two-dimensional data array including at least first and second column-correcting rows having means for correcting errors across columns of data;
• each row-correcting column and each column-correcting row including coded information for the location and correction of at least one error in a column and/or one error in a row whereby upon data regeneration by said columns and rows, said regenerated data can be used in the calculation of auxiliary check syndromes to indicate whether data has been acurately regenerated.

A processor for decoding a data array comprising:

• temporary memory means for storing said data array;
• an arithmetic logic unit;
• a plurality of latches for storing memory addresses;
• and
• permanent memory means for storing a program adapted to control said temporary memory means, arithmetic logic unit and latches to decode a three-dimensional data array with an error-correction protocol, said data array including multi-bit binary words, said words being written in rows and columns to form successive two-dimensional data arrays, said two-dimensional data arrays being addressable sequentially to form the three-dimensional data array;
• said two-dimensional data arrays including column-correcting rows and row-correcting columns whereby each two-dimensional data array can be addressed for error correction along vectors in two dimensions;
• said successive two-dimensional data arrays of said three-dimensional array including at least one two-dimensional redundant array;
• and
• said two-dimensional redundant array being disposed for individual error correction of discrete errors in the two-dimensional arrays of the three-dimensional array along correction vectors different than those provided by said row-correcting columns and said column-correcting rows of said two-dimensional data arrays.

An apparatus for writing a two-dimensional data array to a memory comprising:

• means for serially placing multi-bit binary words in said two-dimensional array data;
• means for generating and filling row correcting columns for locating and correcting error in rows of said two-dimensional data array;
• means for generating and filling column correcting rows for locating and correcting error in columns of said two-dimensional data array;
• whereby said two-dimensional array contains two-dimensional correction directions along said array;
• and
• means for serially writing to a memory media said rows and columns of said data array including said row-correcting columns and said column-correcting rows, said writing occurring from a sequence along directions differing from said error-correction whereby sequential errors on read back from said memory are individually addressable by differing data, including errors in said column-correcting rows and said row-correcting columns.

An apparatus for writing a three-dimensional array containing redundancy information to a memory media comprising in combination:

• means for generating a plurality of two-dimensional data arrays having rows and columns by serially placing multi-bit binary words to said data array;
• means for generating for each two-dimensional data array a plurality of column-correcting rows and row-correcting columns whereby error in each two-dimensional array is individually addressable along two error-correcting directions of first and second differing directions to redundantly correct any single error;
• means for generating across the two-dimensional arrays of said three-dimensional array along a third dimension of plurality of two-dimensional redundant arrays, the third dimension of generation being different in direction from the two error-correcting directions of said two-dimensional data arrays whereby redundancy data from said two-dimensional data arrays are individually addressable to any single error across the third dimension to any of said two-dimensional arrays;
• and
• means for writing to a memory media from said three-dimensional array along a fourth direction of said three-dimensional array, said write causing sequential error on read back from said memory media to be addressable by differing error-correction code combinations from said column-correcting rows, said row-correcting columns and said two-dimensional redundant arrays.