Apparatus for detecting and correcting errors in an encoded memory word
First Claim
1. Apparatus for detecting faults in a memory storing a data word consisting of information bits and check bits encoded in an error correcting code, for detecting errors caused by said faults, and for correcting certain of said errors and preventing the miscorrections of others, comprising;
- a first and a second correction channel, each of which is operative to receive said data word from memory and to attempt to correct it utilizing different sequences of error-correction operations in each channel;
means including registers and a comparator for receiving the attempted-to-be-corrected word from each of said channels and comparing said words as received, to produce an equal or unequal signal; and
means responsive to an equal signal for gating out one of said attemtped-to-be-corrected words from one of said registers for utilization as a valid code word.
0 Assignments
0 Petitions
Accused Products
Abstract
Apparatus for a digital memory system which performs single and double error detection and correction, as well as the detection of faults in the memory storage elements which do not produce errors in the data word stored therein. The data word is encoded in a specialized Hamming SEC/DED code and the apparatus generates syndromes and byte parity bits which are analyzed to detect both the presence and nature of the errors and faults. A parallel correction procedure is followed and the results thereof compared to prevent the erroneous correction of errors.
-
Citations
17 Claims
-
1. Apparatus for detecting faults in a memory storing a data word consisting of information bits and check bits encoded in an error correcting code, for detecting errors caused by said faults, and for correcting certain of said errors and preventing the miscorrections of others, comprising;
-
a first and a second correction channel, each of which is operative to receive said data word from memory and to attempt to correct it utilizing different sequences of error-correction operations in each channel; means including registers and a comparator for receiving the attempted-to-be-corrected word from each of said channels and comparing said words as received, to produce an equal or unequal signal; and means responsive to an equal signal for gating out one of said attemtped-to-be-corrected words from one of said registers for utilization as a valid code word. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. In a fault detecting and error correcting apparatus for detecting faults in a memory storing a data word therein, for detecting errors in said data word, for correcting certain of said errors, and preventing the miscorrection of other errors, the said word consisting of N bits of which K bits are check bits encoded in a Hamming SEC/DED code in which the parity check matrix has N columns and K rows and there are an odd number of ones in each column and each row has the same number of ones modulo two, including one for each check bit, apparatus for testing an N-bit word and producing signals manifestive of the nature of the errors therein, comprising;
-
means for generating K syndrome bits, each of which is the modulo two sum of a different predetermined combination of bits from a data word to be tested, certain of said syndromes being generated from the combinations of A and B where A is a predetermined byte of information bits different for each syndrome and B is the remaining element of the bit combination specific to the given syndrome; means for generating a plurality, less than K, of byte parity check bits each of which is equal to the modulo two sum of the B combination of bits of a corresponding syndrome having a B component therein; means for obtaining the modulo two sum of each of said byte parity check bits and its corresponding A byte bits and producing a zero or one parity test signal manifestive of an even or odd parity check of each of the combinations; means for producing an R signal if any one of said byte parity test signals is non-zero and a R signal if all parity test signals are zero; means for obtaining the modulo two sum of said syndrome bits and producing a G signal if said sum is zero and a G signal if said sum is one; means for producing an E signal if any one of said syndrome bits is non-zero and a E signal if all syndrome bits are zero; and means for combining said error signals in the following combinations;
space="preserve" listing-type="tabular">ER EG EG ER EG E EGmeans responsive to the combinations ER;
EG;
EG;
EG for discontinuing any error correction and signalling an error; andmeans responsive to an E or EG signal for initiating error correction operations; and means responsive to ER signal for reading out the word under test for further use as a valid code word. - View Dependent Claims (14, 15)
-
-
16. Apparatus for performing single error corrections upon a word encoded in a Hamming SEC/DED code having a parity check matrix in which there are the same number of ones in each column, comprising;
-
means for generating a plurality of syndrome bits, each of which is the modulo two sum of a different combination of bits of said word, the combinations being compatible with the parity check matrix; a plurality of AND gates one for each bit position of said word; means for coupling a different combination of said syndrome bits to each of said AND gates whereby one of said AND gates will yield an output for a single error in the corresponding bit position; a plurality of exclusive OR gates, one for each bit position; and means for combining in each of said exclusive OR gates one of the bits of the word to be corrected and the output of a corresponding AND gate whereby a single bit in error is complemented.
-
-
17. Apparatus for performing double error correction upon a word stored in a memory having faults in only those error bit positions, the said word being encoded in a Hamming SEC/DED error correcting code characterized by a parity checked matrix having the same number of ones modulo two in each row and an odd number of ones in each column, comprising;
-
first register means for receiving the data word as recorded in said memory; second register means for recording the data word as recorded in said memory; means under control of said first register for attempting to enter the complement of the contents of said register into memory; means for re-entering the actual word as sought-to-be-complemented in said memory into said first register; means for comparing each bit in said first register with each corresponding bit in said second register and producing therefrom a fault location word having ones in the faulty bit positions and zeros in the sound bit positions; and means for exclusively ORing each bit of said data word in said second register with a corresponding bit of said fault location word to thus complement and correct the two erroneous bits.
-
Specification