US4417339A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fault tolerant error correction circuit
Assignee: Unisys Corp
•
Filing: 1981-06-22
•
Granted: 1983-11-22
•
Expires: 2001-06-22
Abstract
Abstract A fault tolerant error correction circuit utilizing any modified Hamming code is disclosed. In addition to correcting single bit errors and detecting double bit errors, the error correction circuit disclosed can tolerate the failure of any single parity check subcircuit without corrupting the information bits of a correct input data pattern. Improved reliability results because a using system will remain UP if there is a single bit error in the input data pattern or faults in a single parity check subcircuit, but not both. If both an error and a fault do occur, the error correction circuit will either report a double bit error or a correct output will be generated with no error indication.
Inventors
- 👤 Robert G. Cantarella
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 10:45
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/19
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
277 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of m input information bits, i 0 , i 1 , . . . , i m-1 , and a set of k parity bits, p 0 , p 1 , . . . , p k-1 , where m≧k>0, said circuit capable of tolerating a failure of any one of a plurality of elements included in said circuit without corrupting the information bits of a correct inputted data pattern, said circuit comprising: k-1 parity check means, each of said k-1 parity check means receiving a different one of k-1 subsets of the set of m input information bits and one of a first subset of the set of k parity bits, each of said k-1 parity check means for producing a syndrome bit corresponding to its received parity bit; decoder means, receiving said produced syndrome bits, for decoding said produced syndrome bits into a correction vector; exclusive ORing means, receiving said correction vector and said set of m input information bits, for producing a set of m output information bits; and error status means, responsive to a second subset of said set of k parity bits, a second subset of the set of m information bits and said produced syndrome bits, for providing error status indications including an indication that the set of m output information bits is correct in response to said circuit receiving said correct inputted data pattern and the occurrence of said failure of any one of said plurality of elements.
Claim 2
Dependent Claim
277 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of m input information bits, i 0 , i 1 , . . . , i m-1 , and a set of k parity bits, p 0 , p 1 , . . . , p k-1 , where m≧k>0, said circuit capable of tolerating a failure of any one of a plurality of elements included in said circuit without corrupting the information bits of a correct inputted data pattern, said circuit comprising: k-1 parity check means, each of said k-1 parity check means receiving a different one of k-1 subsets of the set of m input information bits and one of a first subset of the set of k parity bits, each of said k-1 parity check means for producing a syndrome bit corresponding to its received parity bit; decoder means, receiving said produced syndrome bits, for decoding said produced syndrome bits into a correction vector; exclusive ORing means, receiving said correction vector and said set of m input information bits, for producing a set of m output information bits; and error status means, responsive to a second subset of said set of k parity bits, a second subset of the set of m information bits and said produced syndrome bits, for providing error status indications including an indication that the set of m output information bits is correct in response to said circuit receiving said correct inputted data pattern and the occurrence of said failure of any one of said plurality of elements.
Claim 3
Dependent Claim
18 words
The circuit in accordance with claim 1 wherein said plurality of elements includes said k-1 parity check means.
Claim 4
Dependent Claim
78 words
The correction circuit in accordance with claim 1 wherein said error status means includes: overall parity means, receiving said second subset of the set of k parity bits, said second subset of the set of m input information bits and said produced syndrome bits, said overall parity means for generating an overall parity indication; and status indication means, receiving said produced syndrome bits and said overall parity indication, said status indication means for producing said error status indications.
Claim 5
Dependent Claim
29 words
The correction circuit in accordance with claim 3 wherein said first subset of the set of k parity bits includes the non-leading parity bits p j , where 1≦j≦k-1.
Claim 6
Dependent Claim
48 words
The correction circuit in accordance with claim 3 wherein: said first subset of the set of k parity bits includes the non-leading parity bits p j , where 1≦j≦k-1; and said second subset of the set of k parity bits includes the leading parity bit P 0 .
Claim 7
Dependent Claim
61 words
The correction circuit in accordance with claim 3 wherein said status indication means includes: a logical OR gate receiving as its inputs each of said produced syndrome bits and said overall parity indication; and a logical AND gate receiving as its inputs the output of said logical OR gate and a signal corresponding to the inverse of the overall parity indication.
Claim 8
Dependent Claim
125 words
The correction circuit in accordance with claim 1 wherein each of said k-1 parity check means includes means for performing a logical exclusive OR of the parity bit p j and each of the input information bits i j .sbsb.1, i j .sbsb.2, . . . , i j .sbsb.l , where p j is the parity bit received by the respective parity check means and i j .sbsb.1, i j .sbsb.2, . . . , i j .sbsb.l is the subset of the set of m input information bits specified by said modified Hamming code as included in the generation of said parity bit p j , whereby a syndrome bit s j is produced at the output of said respective parity check means.
Claim 9
Dependent Claim
124 words
The correction circuit in accordance with claim 3 wherein each of said k-1 parity check means includes means for performing a logical exclusive OR of the parity bit p j and each of the information bits i j .sbsb.1, i j .sbsb.2, . . . , i j .sbsb.l , where p j is the parity bit received by the respective parity check means and i j .sbsb.1, i j .sbsb.2, . . . , i j .sbsb.l is the subset of the set of m input information bits specified by said modified Hamming code as included in the generation of said parity bit p j , whereby a syndrome bit s j is produced at the output of said respective parity check means.
Claim 10
Dependent Claim
66 words
The correction circuit in accordance with claim 3 wherein said overall parity means includes means for performing a logical exclusive OR of each member of the second subset of the set of k parity bits, the produced syndrome bits and the second subset of the set of m input information bits, whereby said overall parity indication is produced at the output of said overall parity means.
Claim 11
Dependent Claim
50 words
The correction circuit in accordance with claim 8 or 9 wherein: said first subset of the set of k parity bits includes the non-leading parity bits p j , where 1≦j≦k-1; and said second subset of the set of k parity bits includes the leading parity bit p 0 .
Claim 12
Dependent Claim
66 words
The correction circuit in accordance with claim 8 wherein said overall parity means includes means for performing a logical exclusive OR of each member of the second subset of the set of k parity bits, the produced syndrome bits and the second subset of the set of m input information bits, whereby said overall parity indication is produced at the output of said overall parity means.
Claim 13
Dependent Claim
65 words
The correction circuit in accordance with claim 3 or 9 wherein: said second subset of the set of k parity bits includes the leading parity bit p 0 ; and said second subset of the set of m input information bits includes each of the k-1 subsets of the set of m input information bits and further includes the set of m input information bits.
Claim 14
Dependent Claim
44 words
The correction circuit in accordance with claim 10 wherein: said second subset of the set of m input information bits includes each of the k-1 subsets of the set of m input information bits and further includes the set of m input information bits.
Claim 15
Dependent Claim
85 words
The correction circuit in accordance with claim 3 wherein: said decoder means includes means to decode said produced syndrome bits in accordance with said modified Hamming code; and said correction vector is a sequence of binary digits C 0 , C 1 , . . . , C m-1 corresponding to the sequence of m input information bits i 0 , i 1 , . . . , i m-1 , said sequence of binary digits identifying which corresponding input information bit should be complemented.
Claim 16
Dependent Claim
51 words
The correction circuit in accordance with claim 14 wherein said exclusive ORing means includes means for performing a logical exclusive OR of each digit in said correction vector with a corresponding input information bit to produce at the output of said exclusive ORing means said set of m output information bits.
Claim 17
Dependent Claim
212 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of input information bits and a set of parity bits, said circuit capable of tolerating a failure of any one of a plurality of elements included in said circuit without corrupting the information bits of a correct inputted data pattern, said circuit comprising: parity check means, responsive to said inputted data pattern, for generating a set of syndrome bits; decoder means, responsive to said set of syndrome bits, for decoding said set of syndrome bits into a correction vector; forming means, responsive to said correction vector and said set of input information bits, for producing a set of output information bits; overall parity means, responsive to said inputted data pattern and said set of syndrome bits, for generating an overall parity indication; and status indication means, responsive to said set of syndrome bits and said overall parity indication, for producing error status indications including an indication that the set of output information bits is correct in response to said circuit receiving said correct inputted data pattern and the occurrence of said failure in any one of said plurality of elements.
Claim 18
Dependent Claim
212 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of input information bits and a set of parity bits, said circuit capable of tolerating a failure of any one of a plurality of elements included in said circuit without corrupting the information bits of a correct inputted data pattern, said circuit comprising: parity check means, responsive to said inputted data pattern, for generating a set of syndrome bits; decoder means, responsive to said set of syndrome bits, for decoding said set of syndrome bits into a correction vector; forming means, responsive to said correction vector and said set of input information bits, for producing a set of output information bits; overall parity means, responsive to said inputted data pattern and said set of syndrome bits, for generating an overall parity indication; and status indication means, responsive to said set of syndrome bits and said overall parity indication, for producing error status indications including an indication that the set of output information bits is correct in response to said circuit receiving said correct inputted data pattern and the occurrence of said failure in any one of said plurality of elements.
Claim 19
Dependent Claim
61 words
The fault tolerant circuit in accordance with claim 16 wherein said parity check means includes a plurality of parity check circuits, each of said parity check circuits receiving a different subset of said set of input information bits and one of said set of parity bits, each of said parity check circuits for generating one of said set of syndrome bits.
Claim 20
Dependent Claim
64 words
The fault tolerant circuit in accordance with claim 16 wherein said overall parity means includes means for performing a logical exclusive OR of each member of a subset of the set of parity bits, the set of syndrome bits and a second subset of the set of information bits, whereby said overall parity indication is produced at the output of said overall parity means.
Claim 21
Dependent Claim
62 words
The fault tolerant correction circuit in accordance with claim 18 wherein said status indication means includes: a logical OR gate receiving as its inputs said set of syndrome bits and said overall parity indication; and a logical AND gate receiving as its inputs the output of said logical OR gate and a signal corresponding to the inverse of said overall parity indication.
Claim 22
Dependent Claim
22 words
The circuit in accordance with claim 16 wherein said plurality of elements includes said parity check means and said overall parity means.
Claim 23
Dependent Claim
200 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of input information bits and a set of parity bits, said circuit capable of tolerating a failure of any one of a plurality of elements included in said circuit without corrupting the information bits of a correct inputted data pattern, said circuit comprising: parity check means, responsive to said set of input information bits and said set of parity bits, for producing a set of syndrome bits; decoder means, responsive to said set of syndrome bits, for decoding said set of syndrome bits into a correction vector; exclusive ORing means, responsive to said correction vector and said set of input information bits, for producing a set of output information bits; and error status means, responsive to said inputted data pattern and said set of syndrome bits, said error status means including means for indicating that the set of output information bits is correct in response to said circuit receiving said correct inputted data pattern and the occurrence of said failure in any one of said plurality of elements.
Claim 24
Dependent Claim
200 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of input information bits and a set of parity bits, said circuit capable of tolerating a failure of any one of a plurality of elements included in said circuit without corrupting the information bits of a correct inputted data pattern, said circuit comprising: parity check means, responsive to said set of input information bits and said set of parity bits, for producing a set of syndrome bits; decoder means, responsive to said set of syndrome bits, for decoding said set of syndrome bits into a correction vector; exclusive ORing means, responsive to said correction vector and said set of input information bits, for producing a set of output information bits; and error status means, responsive to said inputted data pattern and said set of syndrome bits, said error status means including means for indicating that the set of output information bits is correct in response to said circuit receiving said correct inputted data pattern and the occurrence of said failure in any one of said plurality of elements.
Claim 25
Dependent Claim
62 words
The circuit in accordance with claim 21 wherein said error status means includes: overall parity means, responsive to said inputted data pattern and said set of syndrome bits, said overall parity means for generating an overall parity indication; and status indication means, responsive to said set of syndrome bits and said overall parity indication, said status means for providing error status indications.
Claim 26
Dependent Claim
59 words
The circuit in accordance with claim 22 wherein said status indication means includes: a logical OR gate receiving as its inputs said set of syndrome bits and said overall parity indication; and a logical AND gate receiving as its inputs the output of said logical OR gate and a signal corresponding to the inverse of said overall parity indication.
Claim 27
Dependent Claim
53 words
The circuit in accordance with claim 22 wherein said overall parity means includes means for performing a logical exclusive OR of each member of a subset of the set of parity bits, the set of syndrome bits and a subset of the set of information bits, whereby said overall parity indication is produced.
Claim 28
Dependent Claim
17 words
The circuit in accordance with claim 21 wherein said plurality of elements includes said parity check means.
Claim 29
Dependent Claim
171 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of m input information bits, i 0 , i 1 , . . . , i m-1 and a set of k parity bits p 0 p 1 . . . , p k-1 , where m≧k>0, said circuit comprising: k-1 parity check means, each of said k-1 parity check means receiving a different one of k-1 subsets of the set of m input information bits and one of a first subset of the set of k parity bits, each of said k-1 parity check means for producing a syndrome bit corresponding to its received parity bit; decoder means, receiving said produced syndrome bits, for decoding said produced syndrome bits into a correction vector; exclusive ORing means, receiving said correction vector and said set of m input information bits, for producing a set of m output information bits; and
Claim 30
Dependent Claim
171 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of m input information bits, i 0 , i 1 , . . . , i m-1 and a set of k parity bits p 0 p 1 . . . , p k-1 , where m≧k>0, said circuit comprising: k-1 parity check means, each of said k-1 parity check means receiving a different one of k-1 subsets of the set of m input information bits and one of a first subset of the set of k parity bits, each of said k-1 parity check means for producing a syndrome bit corresponding to its received parity bit; decoder means, receiving said produced syndrome bits, for decoding said produced syndrome bits into a correction vector; exclusive ORing means, receiving said correction vector and said set of m input information bits, for producing a set of m output information bits; and
Claim 31
Dependent Claim
124 words
error status means for providing error status indications, said error status means including overall parity means, receiving a second subset of the set of k parity bits, a second subset of the set of m input information bits and said produced syndrome bits, said second subset of the set of k parity bits including the leading parity bit p 0 , said second subset of the set of m input information bits including each of the k-1 subsets of the set of m input information bits and the set of m input information bits, said overall parity means for generating an overall parity indication, and status indication means, receiving said produced syndrome bits and said overall parity indication, for producing said error status indications.
Claim 32
Dependent Claim
124 words
error status means for providing error status indications, said error status means including overall parity means, receiving a second subset of the set of k parity bits, a second subset of the set of m input information bits and said produced syndrome bits, said second subset of the set of k parity bits including the leading parity bit p 0 , said second subset of the set of m input information bits including each of the k-1 subsets of the set of m input information bits and the set of m input information bits, said overall parity means for generating an overall parity indication, and status indication means, receiving said produced syndrome bits and said overall parity indication, for producing said error status indications.
Claim 33
Dependent Claim
173 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of input information bits and a set of parity bits, said circuit comprising: parity check means, responsive to said inputted data pattern, for generating a set of syndrome bits; decoder means, responsive to said set of syndrome bits, for decoding said set of syndrome bits into a correction vector; forming means, responsive to said correction vector and said set of input information bits, for producing a set of output information bits; overall parity means for generating an overall parity indication, said overall parity means including means for performing a logical exclusive OR of each member of a subset of the set of parity bits, the set of syndrome bits and a second subset of the set of input information bits; and status indication means, responsive to said set of syndrome bits and said overall parity indication, for producing error status indications.
Claim 34
Dependent Claim
173 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of input information bits and a set of parity bits, said circuit comprising: parity check means, responsive to said inputted data pattern, for generating a set of syndrome bits; decoder means, responsive to said set of syndrome bits, for decoding said set of syndrome bits into a correction vector; forming means, responsive to said correction vector and said set of input information bits, for producing a set of output information bits; overall parity means for generating an overall parity indication, said overall parity means including means for performing a logical exclusive OR of each member of a subset of the set of parity bits, the set of syndrome bits and a second subset of the set of input information bits; and status indication means, responsive to said set of syndrome bits and said overall parity indication, for producing error status indications.
Claim 35
Dependent Claim
193 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of input information bits and a set of parity bits, said circuit comprising: parity check means, responsive to said set of input information bits and said set of parity bits, for producing a set of syndrome bits; decoder means, responsive to said set of syndrome bits, for decoding said set of syndrome bits into a correction vector; exclusive ORing means, responsive to said correction vector and said set of input information bits, for producing a set of output information bits; overall parity means, responsive to said inputted data pattern and said set of syndrome bits, for generating an overall parity indication; and status indication means for providing error status indications, said status indication means including a logical OR gate receiving as its inputs said set of syndrome bits and said overall parity indication, and a logical AND gate receiving as its inputs the output of said logical OR gate and a signal corresponding to the inverse of said overall parity indication.
Claim 36
Dependent Claim
193 words
A fault tolerant circuit for correcting and detecting errors in an inputted data pattern, said inputted data pattern encoded in a modified Hamming type code, said inputted data pattern including a set of input information bits and a set of parity bits, said circuit comprising: parity check means, responsive to said set of input information bits and said set of parity bits, for producing a set of syndrome bits; decoder means, responsive to said set of syndrome bits, for decoding said set of syndrome bits into a correction vector; exclusive ORing means, responsive to said correction vector and said set of input information bits, for producing a set of output information bits; overall parity means, responsive to said inputted data pattern and said set of syndrome bits, for generating an overall parity indication; and status indication means for providing error status indications, said status indication means including a logical OR gate receiving as its inputs said set of syndrome bits and said overall parity indication, and a logical AND gate receiving as its inputs the output of said logical OR gate and a signal corresponding to the inverse of said overall parity indication.
References Cited (Backward Citations)
US3831144A
Cited
US3983536A
Cited
US4005405A
Cited
US4077028A
Cited
US4175692A
Cited
US4168486A
Cited
US4201337A
Cited
US4296494A
Cited
US4340964A
Cited
US4291407A
Cited
US4334309A
Cited
US4345328A
Cited
US4359772A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1986-11-21 | 1987-05-23 | 1987-11-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1990-11-21 | 1991-05-23 | 1991-11-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1994-11-21 | 1995-05-23 | 1995-11-22 | $7700.00 | Window Closed / Lapsed |