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

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.

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.

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.

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.

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.

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.

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.

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.