Fault-tolerant corrector/detector chip for high-speed data processing

• US 5,291,496 A
• Filed: 10/18/1990
• Issued: 03/01/1994
• Est. Priority Date: 10/18/1990
• Status: Expired due to Term

• Current Assignee: United States Of America As Represented By The Department Of Energy
• Original Assignee: United States Department of Energy
• Inventors: Napolitano, Leonard M. Jr., Shreeve, William O., Redinbo, G. Robert, Andaleon, David D.
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US07/599,606
• Time in Patent Office: 1,230 Days
• Field of Search: 371/37.1, 371/3, 371/37.6
• US Class Current: 714/703
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 13/51 Constant weight codes; n-out-of-m codes; Berger codes

Abstract

An internally fault-tolerant data error detection and correction integrated circuit device (10) and a method of operating same. The device functions as a bidirectional data buffer between a 32-bit data processor and the remainder of a data processing system and provides a 32-bit datum is provided with a relatively short eight bits of data-protecting parity. The 32-bits of data by eight bits of parity is partitioned into eight 4-bit nibbles and two 4-bit nibbles, respectively. For data flowing towards the processor the data and parity nibbles are checked in parallel and in a single operation employing a dual orthogonal basis technique. The dual orthogonal basis increase the efficiency of the implementation. Any one of ten (eight data, two parity) nibbles are correctable if erroneous, or two different erroneous nibbles are detectable. For data flowing away from the processor the appropriate parity nibble values are calculated and transmitted to the system along with the data. The device regenerates parity values for data flowing in either direction and compares regenerated to generated parity with a totally self-checking equality checker. As such, the device is self-validating and enabled to both detect and indicate an occurrence of an internal failure. A generalization of the device to protect 64-bit data with 16-bit parity to protect against byte-wide errors is also presented.

Claims

1. Apparatus for coupling to a plurality of parallel data signal lines that convey simultaneously presented parallel digital information for detecting an occurrence of an error in the parallel digital information and for correcting the error, comprising:

means coupled to a first plurality of parallel data signal lines for generating in a single step, when active, a first group of parallel parity signals that is a function of a logical state of the first plurality of parallel data signal lines and for providing the first group of parallel parity signals and the first plurality of parallel data signal lines for combining into a second plurality of parallel signal lines;

means coupled to the second plurality of parallel signal lines for decoding, in a single step, when active, the second plurality of parallel signal lines to determine if one or more of the parallel signal lines is in error; and

means coupled to the second plurality of parallel signal lines, and responsive to the operation of the decoding means, for identifying and correcting at least one erroneous signal line on the second plurality of signal lines and for providing the corrected signal line to the first plurality of parallel signal lines;

wherein

all of the above said means performs their functions with Boolean operations, and the generating means includes means for validating the operation of the decoding means at a time when the decoding means is active and wherein the decoding means includes means for validating the operation of the generating means at a time when the generating means is active.

2. Apparatus as set forth in claim 1 wherein the first plurality of parallel data signal lines is partitioned into eight symbols of m bits and wherein for each symbol of m bits the first group of parallel parity signal lines is comprised of two symbols of m bits, and wherein m=4.

3. Apparatus as set forth in claim 1 wherein the first plurality of parallel data signal lines is partitioned into eight symbols of m bits and wherein for each symbol of m bits the first group of parallel parity signal lines is comprised of two symbols of m bits, and wherein m=8.

4. Apparatus as set forth in claim 1, wherein the means for validating the operation of the generating means, when the generating means is active, produces a second group of parallel parity signals that is a function of a logical state of the second plurality of parallel signal lines, and wherein the apparatus further comprises means for comparing the first group of parallel parity signals to the second group of parallel parity signals to determine if they are equal and, if the first and the second group of parallel parity signals are not equal, for generating an error signal.

5. Apparatus as set forth in claim 4 wherein the, means for validating the operation of the decoding means, when the decoding means is active, produces the first group of parallel parity signals that is a function of the logical of the first plurality of the parallel data signal lines as decoded by the decoding means, and wherein the apparatus further comprises means for comparing the first group of parallel parity signals to the second group of parallel parity signals to determine if they are equal and, if the first and the second groups of parallel parity signals are not equal, for generating the error signal.

6. Apparatus as set forth in claim 1 wherein the generating means includes means for generating the first group of parallel parity signals in accordance with a shortened Reed-Solomon code.

7. Apparatus as set forth in claim 6 wherein the decoding means includes means for decoding the second plurality of parallel signal lines in accordance with a dual orthogonal basis technique.

8. Apparatus for coupling in series with a parallel data bus and interposed between a data processor and circuitry accessed by the data processor, the apparatus detecting an occurrence of an error on the parallel data bus and correcting the error, comprising:

means coupled to parallel data bus signal lines for encoding in a parallel single step operation, when the data processor is sourcing simultaneously presented parallel data to the parallel data bus, a plurality of parallel parity signals in accordance with a Reed-Solomon code, the encoding means including means for simultaneously driving sourced parallel data together with the encoded parallel parity signals to the parallel data bus for transmission to circuitry accessed by the data processor;

means coupled to the parallel data bus signal lines for decoding in a parallel single step operation, when the data processor is sinking data from the parallel data bus, the parallel data bus in conjunction with associated previously encoded parallel parity signals to determine if an error exists thereon, the decoding means including means for simultaneously decoding the parallel data bus together with the parallel parity signals in accordance with a dual orthogonal basis technique;

means coupled to the parallel data bus signal lines, and in response to the operation of the decoding means, for simultaneously detecting, identifying and correcting one or more erroneous parallel data bus signal lines for supplying corrected data to the data processor;

wherein said encoding, said decoding, and said detecting, identifying and correcting means all perform their functions with Boolean operations, and the encoding means includes means for validating the operation of the decoding means at a time when the decoding means is active and wherein the decoding means includes means for validating the operation of the encoding means at a time when the generating means is active.

9. Apparatus as set forth in claim 8 wherein the encoding means includes means for validating the operation of the decoding means at a time when the data processor is sinking data, and wherein the decoding means includes means for validating the operation of the encoding means at a time when the data processor is sourcing data.

10. Apparatus as set forth in claim 8 wherein the parallel data bus is partitioned into eight parallel symbols of m bits and wherein for each group parallel symbol of m bits an associated parity signal is comprised of two symbols of m bits, and wherein m=8.

11. Apparatus as set forth in claim 8 wherien the parallel data bus is partitioned into eight parallel symbols of m bits and wherein for each group parallel symbol of m bits an associated parity signal is comprised of two symbols of m bits, and wherein m=8.

12. Apparatus as set forth in claim 8 wherein the decoding means includes means for calculating a value of a first parallel syndrome and a second parallel syndrome in a parallel single step operation as a function of the parallel data bus and the associated previous encoded parallel parity signals, and wherein the identifying and correcting means includes means for comparing the first parallel syndrome and second parallel syndrome to zero to determine if the parallel data bus is in error, the identifying and correcting means further including means responsive to a second parallel single operation of the detecting means for decoding the first parallel syndrome and the second parallel syndrome for selecting one of a plurality of parallel data bus parallel symbols having an error.

13. Apparatus as set forth in claim 12 wherein each of the parallel data bus is comprised of four bits.

14. Apparatus as set forth in claim 12 wherein for each of the parallel symbols the identifying and correcting means comprises a parallel plurality of single bit corrector means, each of the corrector means being coupled to a single bit of the parallel data bus and to a corresponding bit of the first parallel syndrome, and responsive to the operation of the selecting means, providing a corrected data bit at an output thereof.

15. A method for detecting an occurrence of an error in digital information and for correcting the error, comprising the steps of:

generating, in response to a multi-bit datum output by a data processing means, a parity signal having a value that is a function of a logical state of the bits of the datum;

associating the parity signal with the datum;

decoding, in response to a multi-bit datum to be input to the data processing means, the datum and the associated parity signal to determine if one or more of the bits is in error;

identifying bits, if any, that are in error;

correcting the erroneous bits; and

providing the correct datum to the data processing means while also providing a correct parity signal associated therewith;

wherein the step of generating includes a step of validating the correctness of the generated parity signal which further comprises the steps of regenerating the parity signal and comparing the generated parity signal to the regenerated parity signal to determine if they are logically equal one to another; and

wherein

the step of providing includes a step of validating the correctness of the provided parity signal which further comprises the steps of regenerating the provided parity signal and comparing the provided parity signal to the regenerated parity signal to determine if they are logically equal one to another.

16. A method as set forth in claim 16 wherein the steps of comparing each include a step of asserting an error signal line to indicate when the result of the comparison indicates that the compared values are not logically equal.

17. A method for detecting an occurrence of an error in parallel digital information and for correcting the error, comprising the steps of:

generating, in response to a parallel multi-bit data output by a data processing means, a parallel parity signal having a value that is determined in accordance with a shortened Reed-Solomon code and as a function of a logical state of the parallel bits of the data;

associating the parallel parity signal in parallel with the data;

decoding in accordance with a dual orthogonal basis, in response to a parallel multi-bit data to be input to the parallel processing means, the parallel data and the associated parallel parity signal to determine if one or more of the bits is in error;

identifying bits, if any, that are in error;

correcting the erroneous bits; and

providing the correct parallel data to the data processing means while also providing a correct parallel parity signal

wherein all steps of said method are performed using Boolean operations.

18. A method set forth in claim 17 wherein the step of generating includes a step of validating the correctness of the generated parallel parity signal which further comprises the steps of regenerating the parallel parity signal and comparing the generated parallel parity signal to the regenerated parallel parity signal to determine if they are logically equal one to another;

and wherein the step of providing t he correct parallel data includes a step of validating the correctness of the provided parallel parity signal which further comprises the steps of regenerating the provided parallel parity signal and comparing the provided parallel parity signal to the regenerated parallel parity signal to determine if they are logically equal one to another.

19. A method as set forth in claim 17 wherein the step of decoding includes the steps of:

calculating a value of a first parallel syndrome and a second parallel syndrome in a parallel single step operation on the logical state of the parallel data and the parallel parity signal;

comparing the first parallel syndrome and second parallel syndrome to zero to determine if the parallel data is correct;

if the parallel data is found to be in error, decoding the first and second parallel syndrome values for identifying an erroneous portion of the parallel data; and

combining the erroneous portion of the parallel data with an associated portion of one of the parallel syndromes to correct the erroneous portion of the parallel data.

20. Apparatus for coupling to a plurality of signal lines that convey digital information for detecting an occurrence of an error in the digital information and for correcting the error, comprising:

means coupled to a first plurality of the signal lines wherein the first plurality of signal lines are partitioned into eight groups of m bits, where m =4, for generating, when active, a first signal comprised of two m bits for each group that is a function of a logical state of the first plurality of the signal lines and for providing the first signal to a second plurality of the signal lines;

means coupled to the second plurality of signal lines for decoding, when active, the first and the second plurality of signal lines to determine if one or more of the signal lines is in error; and

means coupled to the second plurality of signal lines, and responsive to the operation of the decoding means, for identifying and correcting an erroneous signal line of the second plurality of signal lines;

wherein

the generating means includes means for validating the operation of the decoding means at a time when the decoding means is active and wherein the decoding means includes means for validating the operation of the generating means at a time when the generating means is active.

21. Apparatus for coupling to a plurality of signal lines that convey digital information for detecting an occurrence of an error in the digital information and for correcting the error, comprising:

means coupled to a first plurality of the signal lines wherein the first plurality of signal lines are partitioned into eight groups of m bits, where m =8, for generating, when active, a first signal comprised of two m bits for each group that is a function of a logical state of the first plurality of the signal lines and for providing the first signal to a second plurality of the signal lines;

means coupled to the second plurality of signal lines for decoding, when active, the first and the second plurality of signal lines to determine if one or more of the signal lines is in error; and

means coupled to the second plurality of signal lines, and responsive to the operation of the decoding means, for identifying and correcting an erroneous signal line of the second plurality of signal lines;

wherein

the generating means includes means for validating the operation of the decoding means at a time when the decoding means is active and wherein the decoding means includes means for validating the operation of the generating means at a time when the generating means is active.

22. A method for detecting an occurrence of an error in digital information and for correcting the error, comprising the steps of:

generating, in response to a multi-bit datum output by a data processing means, a parity signal having a value that is determined in accordance with a shortened Reed-Solomon code and as function of a logical state of the bits of the datum, and validating the correctness of the generated parity signal which further comprises the steps of regenerating the parity signal and comparing the generated parity signal to the regenerated parity signal to determine if they are logically equal one to another;

associating the parity signal with the datum;

decoding in accordance with a dual orthogonal basis, in response to a multi-bit datum to be input to the processing means, the datum and the associated parity signal to determine if one or more of the bits is in error;

identifying bits, if any, that are in error;

correcting the erroneous bits; and

providing the correct datum to the data processing means while also providing a correct parity signal and while further validating the correctness of the provided parity signal which further comprises the steps of regenerating the provided parity signal and comparing the provided parity signal to the regenerated parity signal to determine if they are locally equal one to another.

23. Apparatus for coupling in series with a data bus and interposed between a data processor and circuitry accessed by the data processor, the apparatus detecting an occurrence of an error on the data bus and correcting the error, comprising

means coupled to data bus signal lines for encoding, when the data processor is sourcing data to the data bus, a plurality of parity signals in accordance with a Reed-Solomon code, the encoding means including means for driving sourced data and the encoded parity signals to the data bus for transmission to circuitry accessed by the data processor, and wherein the data bus is partitioned into eight groups of m bits and wherein for each group of m bits an associated parity signal is comprised of two m bits, where m=4;

means coupled to the data bus signal lines for decoding, when the data processor is sinking data from the data bus, the data bus in conjunction with associated previously encoded parity signals to determine if an error exists thereon, the decoding means including means for decoding the data bus and the parity signals in accordance with a dual orthogonal basis technique; and

means coupled to the second plurality of signal lines, and responsive to the operation of the decoding means, for detecting, identifying and correcting one or more erroneous data bus signal lines for supplying corrected data to the data processor.

24. Apparatus for coupling in series with a data bus and interposed between a data processor and circuitry accessed by the data processor, the apparatus detecting an occurrence of an error on the data bus and correcting the error, comprising

means coupled to data bus signal lines for encoding, when the data processor is sourcing data to the data bus, a plurality of parity signals in accordance with a Reed-Solomon code, the encoding means including means for driving sourced data and the encoded parity signals to the data bus for transmission to circuitry accessed by the data processor, and wherein the data bus is partitioned into eight groups of m bits and wherein for each group of m bits an associated parity signal is comprised of two m bits, where m=8;

means coupled to the data bus signal lines for decoding, when the data processor is sinking data from the data bus, the data bus in conjunction with associated previously encoded parity signals to determine if an error exists thereon, the decoding means including means for decoding the data bus and the parity signals in accordance with a dual orthogonal basis technique; and

means coupled to the second plurality of signal lines, and responsive to the operation of the decoding means, for detecting, identifying and correcting one or more erroneous data bus signal lines for supplying corrected data to the data processor.