Error detection and correction for data stored across multiple byte-wide memory devices

• US 5,909,541 A
• Filed: 06/26/1996
• Issued: 06/01/1999
• Est. Priority Date: 07/14/1993
• Status: Expired due to Fees

• Current Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Original Assignee: Honeywell Incorporated (Honeywell International Inc.)
• Inventors: Walker, Gary, Gray, Scott L., Sampson, Neil L.
• Primary Examiner(s): Beausoliel, Robert W.
• Assistant Examiner(s): Baderman, Scott T.
• Application Number:
  US08/668,309
• Time in Patent Office: 1,070 Days
• Field of Search: 395/182.04, 395/182.11, 371/67.1, 371/68.1, 371/40.11, 371/40.2, 371/40.3, 371/40.4, 711/115, 711/153, 711/173
• US Class Current: 714/6.2
• CPC Class Codes: G06F 11/1044 with specific ECC/EDC distribution
• CPC Class Codes: G06F 11/1633 using mutual exchange of the output between the redundant processing components

Abstract

A digital computing system includes a first and second processor clocked for locked step operation. A shared memory stores a linear block codeword across a plurality of byte-wide memory devices. The codeword includes a first dataword and a second dataword. Each of the first and second datawords includes an equal plurality of databits and each includes an equal plurality of checkbits associated therewith. First error detection and correction logic connected to the first processor receives the first dataword and checkbits associated therewith of the codeword addressed by the first processor and a second dataword and checkbits associated therewith of the codeword addressed by the second processor. First error detection and correction logic detects and/or corrects errors in the codeword. Second error detection and correction logic connected to the second processor receives the second dataword and checkbits associated therewith of the codeword addressed by the second processor and the first dataword and checkbits associated therewith of the codeword addressed by the first processor. The second error detection and correction logic detects and/or corrects errors in the codeword.

Claims

1. A fault-tolerant, fail passive digital computing system, said system comprising:

a processor;

a memory for storing at least one linear block codeword across a plurality of byte-wide memory devices, said codeword including a dataword and a plurality of checkbits associated therewith;

a databus comprising a plurality of byte-wide partitions, the databus coupling the processor to the memory; and

,

an error detection and correction means connected to said processor and said memory on said databus for receiving said at least one linear block codeword from said memory or said processor, said error detection and correction means including a syndrome generator having an H matrix for detecting and correcting any single bit error in said linear block codeword transported on said databus such that any byte-wide errors in said linear block codeword are confined to one of said plurality of byte-wide partitions.

2. The system according to claim 1, wherein said error detection and correction means includes

means for receiving a write dataword from said processor for communication to said memory, and,

means for generating a plurality of checkbits based on said write dataword, wherein said means for generating uses an n,k linear block code where n is 80 and k is 64.

3. The system according to claim 1, wherein said H matrix is defined as:

row 1=1100 0100 1100 0100 1100 0100 1100 0100 1100 0100 1100 0100 1100 0100 1100 0100 0000 0000 0000 0001

row 2=1110 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 0000 0000 0000 0010

row 3=1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 1010 0000 0000 0000 0100

row 4=0000 1101 0000 1101 0000 1101 0000 1101 0000 1101 0000 1101 0000 1101 0000 1101 0000 0000 0000 1000

row 5=1100 1000 0110 0100 1011 0010 0101 1001 1010 1100 1101 0110 1110 1011 1111 0101 0000 0000 0001 0000

row 6=0101 1001 1010 1100 1101 0110 1110 1011 1111 0101 0111 1010 0011 1101 0001 1110 0000 0000 0010 0000

row 7=1011 0010 0101 1001 1010 1100 1101 0110 1110 1011 1111 0101 0111 1010 0011 1101 0000 0000 0100 0000

row 8=0110 0100 1011 0010 0101 1001 1010 1100 1101 0110 1110 1011 1111 0101 0111 1010 0000 0000 1000 0000

row 9=1011 1100 1010 1100 1010 1100 1010 1100 1010 1100 1010 1100 1010 1100 1010 1100 0000 0001 0000 0000

row 10=0101 0110 0101 0110 0101 0110 0101 0110 0101 0110 0101 0110 0101 0110 0101 0110 0000 0010 0000 0000

row 11=0011 0011 0010 0011 0010 0011 0010 0011 0010 0011 0010 0011 0010 0011 0010 0011 0000 0100 0000 0000

row 12=1001 0001 1001 0001 1001 0001 1001 0001 1001 0001 1001 0001 1001 0001 1001 0001 0000 1000 0000 0000

row 13=0000 0011 0010 0110 0100 1101 1001 1010 0011 0101 0110 1011 1101 0111 1010 1111 0001 0000 0000 0000

row 14=1001 1010 0011 0101 0110 1011 1101 0111 1010 1111 0101 1110 1011 1100 0111 1000 0010 0000 0000 0000

row 15=0101 1101 1001 1010 0011 0101 0110 1011 1101 0111 1010 1111 0101 1110 1011 1100 0100 0000 0000 0000

row 16=0010 0110 0100 1101 1001 1010 0011 0101 0110 1011 1101 0111 1010 1111 0101 1110 1000 0000 0000 0000.

4. The system according to claim 1 wherein said data word portion of said codeword includes 64 data bits and wherein the number of said plurality of checkbits is 16.

5. The system according to claim 1 wherein said memory comprises a plurality of single byte memory devices, each single byte memory device being associated with one of the plurality of byte-wide partitions.

6. A method of storing data in a memory comprising:

generating a first copy of the data at a first processor;

providing the first copy of the data to a first error detector having a first read-only port and a first read/write port, the first read/write port being coupled to the memory;

generating a second copy of the data at a second processor;

providing the second copy of the data to a second error detector having a second read/write port and a second read-only port, the second read/write port being coupled to the memory and to the first read-only port, and the second read-only port being coupled to the first read/write port;

generating a first set of checkbits at the first error detector based upon the first copy of the data;

generating a second set of checkbits at the second error detector based upon the second copy of the data;

providing a first output data from the first read/write port, the first output data comprising a first portion of the first copy of the data and a first portion of the first set of checkbits;

providing a second output data from the second read/write port, the second output data comprising a second portion of the second copy of the data and a second portion of the second set of checkbits;

monitoring the first output data at the second error detector;

monitoring the second output data at the first error detector; and

storing the first and second output data in the memory.

7. The method of claim 6 wherein the first portion of the data is equivalent to the second portion of the data.

8. The method of claim 6 wherein the first and second output data each comprise 40 bits.

9. The method of claim 8 wherein the first portion of the first copy of the data comprises 32 bits, the first portion of the first set of checkbits comprises 8 bits, the second portion of the second copy of the data comprises 32 bits, and the second portion of the second set of checkbits comprises 8 bits.

10. The method of claim 6 wherein the first and second sets of checkbits are generated by exclusive-OR'"'"'ing the first and second copies of the data, respectively, with a parity check matrix.

11. The method of claim 9 wherein the first and second sets of checkbits are generated by exclusive-OR'"'"'ing the first and second copies of the data, respectively, with a parity check matrix.

12. The method of claim 6 wherein the memory comprises a plurality of single-byte memory devices.

13. The method of claim 12 whereby the first and second error detectors are coupled to the memory through a first buffer and a second buffer, respectively, each buffer being capable of facilitating the writing of the first and second output data, respectively, to the memory.

14. The method of claim 13 whereby the first and second buffers write the first and second output data, respectively, to the memory through a databus comprising a plurality of byte-wide partitions, each partition being associated with one of the plurality of single-byte memory addresses.

15. A system for exchanging data having a first portion and a second portion between a first processor, a second processor and a shared memory, the system comprising:

a first error detector associated with the first processor having a first port and a second port, the second port being coupled to the memory; and

a second error detector having a third port and a fourth port, the third port being coupled to the memory and to the first port, and the fourth port being coupled to the second port;

whereby the first and second error detector each comprise a parity check matrix for generating a plurality of checkbits from the data, and whereby the first error detector provides first output data which comprises the first portion of the data via the second port, and whereby the second error detector provides second output data which comprises a second portion of the data via the third port, and

whereby the first error detector monitors the second portion of the data via the first port based upon the plurality of checkbits, and whereby the second error detector monitors the first portion of the data via the fouth port based upon the plurality of checkbits.

16. The method of claim 15 wherein the first and second output data each comprise 32 bits.

17. The method of claim 15 wherein the checkbits are generated by exclusive-OR'"'"'ing the data with the parity check matrix.

18. The method of claim 15 wherein the memory comprises a plurality of single-byte memory devices.

19. The method of claim 18 whereby the first and second error detectors are coupled to the memory through a first buffer and a second buffer, respectively, each buffer being capable of facilitating the writing of the first and second output data, respectively, to the memory.

20. The method of claim 19 whereby the first and second buffers write the first and second output data, respectively, to the memory through a databus comprising a plurality of byte-wide partitions, each partition being associated with one of the plurality of single-byte memory addresses.