Matrix error correction for digital data

• US 5,170,400 A
• Filed: 12/26/1989
• Issued: 12/08/1992
• Est. Priority Date: 12/26/1989
• Status: Expired due to Fees

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Dotson, Ronald S.
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US07/456,170
• Time in Patent Office: 1,078 Days
• Field of Search: 371/37.4
• US Class Current: 714/755
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: H03M 13/096 Checksums
• CPC Class Codes: H03M 13/17 Burst error correction, e.g. error trapping, Fire codes

Abstract

A technique for digital data error detection and correction is disclosed which adds alignment and checksum bytes to three sides of a matrix (24) of digital data to be protected. This technique is particularly used for the recording and storage (16,18) of digital data on video tape medium (14). The digital data is treated as a matrix block (24). Checksum and alignment bytes are added (20) to the digital data before tape storage and stripped (22) therefrom after successful alignment checks and data validation. In particular, the first column may be used to provide alignment bytes of a predetermined value for each row. The last column provides row checksum bytes for the data in each row. The last row provides column check sum bytes for each column, excluding the column of alignment bytes. The data location at the intersection of the row of column checksum bytes and the column of row checksum bytes may be used as a checksum byte for either the row or column checksum bytes.

Claims

1. A method of error detection and correction in the storage and recovery of digital data, comprising the steps of:

encoding data to be stored in a matrix format;

adding row checksum locations to the matrix in a first column in which each row checksum location is in a particular row and the data stored therein represents a predetermined mathematical relationship with the remaining locations in that row;

adding column checksum locations to the matrix in a single row in which each column checksum location is in a particular column and the data stored therein represents a predetermined mathematical relationship with the remaining locations in that column;

adding row alignment locations to each row in the matrix in a second column in which each such location includes predetermined alignment data;

adding a row checksum checksum location;

adding a column checksum checksum location;

wherein one of the column checksum checksum or row checksum checksum is located at the intersection of the row of column checksums and the column of row checksums;

wherein the other of the column checksum checksum or row checksum checksum is located in the column of row alignment locations;

storing the encoded matrix of digital data;

removing the encoded matrix of digital data from storage;

then monitoring the alignment of the data in each row alignment location to determine alignment accuracy and attempting to realign any row in which the data in the alignment location indicates misalignment;

comparing the data in each checksum row and column location to determine if that data accurately reflects the appropriate predetermined mathematical relationship with the locations related thereto;

attempting to correct the data in locations in which comparison of the data in the checksum row and column location indicates an error may have occurred; and

decoding the matrix by stripping out all checksum row and column and row alignment locations.

2. A system for the storage and recovery of digital data with error detection and correction, comprising in combination:

means for encoding data to be stored in a matrix format by adding row checksum locations to the matrix in a first column in which each row checksum location is in a particular row and the data stored therein represents a predetermined mathematical relationship with the remaining locations in that row and by adding column checksum locations to the matrix in a single row in which each column checksum location is in a particular column and the data stored therein represents a predetermined mathematical relationship with the remaining locations in that column;

means for adding row alignment locations to each row in a second column in the matrix before the matrix is stored in which each such location includes predetermined alignment data;

means for adding a row checksum checksum location in which the data stored therein represents a predetermined mathematical relationship with the row checksums;

means for adding a column checksum checksum location in which the data stored therein represents a predetermined mathematical relationship with the column checksums;

wherein one of the column checksum checksum or row checksum checksum is located at the intersection of the row of column checksums and the column of row checksums;

wherein the other of the column checksum checksum or row checksum checksum is located in the column of row alignment locations;

means for storing the encoded matrix of digital data;

means for removing the encoded matrix of digital data from storage;

means for monitoring the alignment of the data in each row alignment location after the matrix is removed from storage to determine alignment accuracy;

means for attempting to realign any row in which monitoring of the data int he alignment location indicates that a misalignment error may have occurred;

means for comparing the data in each checksum row and column location to determine if that data accurately reflects the appropriate predetermined mathematical relationship with the locations related thereto;

means for attempting to correct the data in locations in which comparison of the data in the checksum row and column location indicates an error may have occurred; and

means for decoding the matrix by stripping out all checksum row and column locations and row alignment locations.