Method of detecting and correcting errors in digital data storage systems

• US 4,277,844 A
• Filed: 07/26/1979
• Issued: 07/07/1981
• Est. Priority Date: 07/26/1979
• Status: Expired due to Term

• Current Assignee: Storage Technology Corp (Oracle Corporation)
• Original Assignee: Storage Technology Corp (Oracle Corporation)
• Inventors: Burns, William A., Hall, James B., Hancock, Robert J.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US06/061,025
• Time in Patent Office: 712 Days
• Field of Search: 371/38
• US Class Current: 714/755
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

An error detection and correction method for digital data storage is described which comprises horizontal and vertical generation of parity check bits. These may be used to correct errors in up to two bits per word and to indicate whether all errors in a given record have been corrected during a read operation or not. Hamming codes are used to generate check bits in a vertical direction, while cyclic redundancy codes are used in the horizontal direction. The invention is described as embodied in a solid-state memory unit utilizing charge-coupled devices for data storage.

Claims

1. Method of detecting errors in digital data, said data being stored as an array of bits, said array having orthogonal extension in at least two dimensions, wherein the improvement comprises generating first parity-dependent check bits in each of said dimensions during the writing of said data into said array;

regenerating comparable second check bits in each of said dimensions during the reading of said data from said array;

comparing said first and second check bits in at least one of said dimensions to generate an error syndrome;

inverting bits identified as in error by said syndrome; and

comparing said first and second check bits in the remaining of said dimensions, thus determining whether said inverting eliminated errors from said array.

2. The method of claim 1, wherein said check bits are generated in at least one of said dimensions according to a Hamming code.

3. The method of claim 1 wherein said check bits are generated in at least one of said dimensions according to a cyclic redundancy code.

4. The method of claim 1 comprising the additional step of storing the location of an inverted bit in a first word for identifying a bit in error in a second word.

5. The method of claim 1 further including the step of providing an indication of the accuracy of the reading of said data.

6. Method for detecting and correcting errors in stored digital data, said data being organized into records each comprising at least one word, each word consisting of information bits and stored check bits, comprising the steps of:

generating check bits corresponding to each word;

comparing said generated check bits with said stored check bits;

if a single-bit error is indicated by said comparison, inverting a bit indicated as in error and storing the location of said bit in a data register;

if a double-bit error is indicated by said comparison, inverting the bit stored at the location defined by the contents of said data register, and inverting a second bit indicated as in error;

performing a cyclic redundancy check; and

providing an indication of reading accuracy based on the results of said check.

7. The method according to claim 6 wherein said check bits are generated according to a Hamming code.

8. The method according to claim 6 wherein the step of comparing said generated and stored check bits is performed on each word of data.

9. The method according to claim 8 wherein said step of comparing is an exclusive-OR logical process.

10. The method according to claim 6 wherein the steps of indicating bits as in error are performed by accessing a read-only memory, having stored therein addresses of the bits of each word.

11. The method according to claim 6 wherein the steps of indicating bits as in error comprise completing a preset sequence of logical instructions.

12. Method of storage of digital data, said data being organized into at least one record comprising at least one word, comprising a read stage and a write stage, the write stage including the following steps:

generating a first plurality of check bits uniquely corresponding to each word of data; and

storing said first plurality of check bits in conjunction with said word;

said read stage including the following steps;

generating a second plurality of check bits uniquely corresponding to each word of data;

comparing said first and second pluralities of check bits to generate an error syndrome;

if said syndrome is zero, proceeding with said read operation;

if said syndrome is odd, using it to identify a single bit of said word which is in error, inverting said bit, and proceeding with said read operation;

if said syndrome is even, comparing it with the contents of a mask register to generate a second error syndrome, using said syndromes to identify two bits in error and inverting said bits; and

, when the last word of said record has been read, providing a representation of whether or not said read operation has been performed without errors.

13. The method according to claim 12, wherein said check bits are generated according to a Hamming code.

14. The method according to claim 12, wherein the identification of bits to be inverted is performed according to a predetermined series of logical steps.

15. The method according to claim 12 wherein the step of identifying bits to be inverted comprises accessing a read-only memory having the addresses of said bits stored therein.

16. The method of claim 12 further comprising the step of storing each bit of a given word in a different solid-state memory device.

17. The method of claim 16 wherein said devices are charge-coupled devices.

18. The method of claim 16 wherein said devices are random-access memory devices.

19. The method of claim 16 wherein the bits of a given word are each stored at the same location of the devices within which the individual bits are stored.

20. The method of claim 16, wherein the contents of said mask register is used to identify a defective one of said devices.

21. The method of claim 12 wherein said step of providing a representation of whether the read operation has been performed without errors comprises a cyclic redundancy check method.

22. The method of claim 21 wherein said cyclic redundancy check method comprises generating a plurality of parity-dependent bytes of data, said step being partially performed after the writing of each word, and storing said parity-dependent bytes as part of said record.

23. The method of claim 22 wherein said representation of whether the read operation has been performed without errors is provided by an operation performed on said record, including said parity-dependent bytes, during said read stage, said operation comprising the performance of a mathematical complement of said step of generating parity-dependent bytes.

24. The method of claim 12, further comprising the step of inverting certain of said check bits prior to storing said bits, and reinverting said certain bits prior to said comparing step, whereby at least some of the bits of each word are non-zero.