US4993028A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error detection and correction coding
Assignee: Thinking Machines Corp
•
Filing: 1988-09-07
•
Granted: 1991-02-12
•
Expires: 2008-09-07
Abstract
Abstract A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of the original data word (e.g., a 32-bit data word) being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip. In the method, the unique combinations of data word bits used for deriving a first set of check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on a first set of syndrome bits formed by comparing each original check bit of the first set with a corresponding new check bit.
Inventors
- 👤 W. Daniel Hillis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 03:29
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F11/1008; G06F11/1012; G06F11/1028
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
231 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, each data bit of a given nibble of the data word being used in forming each bit of a unique combination of exactly three of the check bits of the first set, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, the unique combinations of data word bits used for deriving the check bits being chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits.
Claim 2
Independent Claim
231 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, each data bit of a given nibble of the data word being used in forming each bit of a unique combination of exactly three of the check bits of the first set, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, the unique combinations of data word bits used for deriving the check bits being chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits.
Claim 3
Dependent Claim
27 words
The method of claim 1 in which each of the check bits of the first set is formed based on the same three bits of all nibbles.
Claim 4
Dependent Claim
172 words
The method of claim 1 in which a second set of four original check bits are derived from bits of the original data word, each check bit of the second set being based on a unique combination of data word bits, a second set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the second set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a second set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the second set of check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the first and second sets of syndrome bits.
Claim 5
Dependent Claim
56 words
The method of claim 1 in which the unique combinations of data word bits are chosen so that any single bit error in the possibly corrupted version of the data word will result in different numbers of syndrome bits of the first set being set, than will any two bit errors in the possibly corrupted version.
Claim 6
Dependent Claim
15 words
The method of claim 1 in which there are 32 bits in the data word.
Claim 7
Independent Claim
253 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, the four bits of each successive nibble of the data word being stored in order in the corresponding memory chip, and the first bits of all nibbles being used in forming the same three check bits, the second bits of all nibbles being used in forming the same three check bits, and so on, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, the unique combinations of data word bits used for deriving the check bits being chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits.
Claim 8
Independent Claim
253 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, the four bits of each successive nibble of the data word being stored in order in the corresponding memory chip, and the first bits of all nibbles being used in forming the same three check bits, the second bits of all nibbles being used in forming the same three check bits, and so on, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, the unique combinations of data word bits used for deriving the check bits being chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits.
Claim 9
Independent Claim
226 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits, any four bit errors in the same nibble causing exactly four of the syndrome bits corresponding to the first set of check bits to be set.
Claim 10
Independent Claim
226 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits, any four bit errors in the same nibble causing exactly four of the syndrome bits corresponding to the first set of check bits to be set.
Claim 11
Dependent Claim
39 words
The method of claim 1, 6, or 7 in which the unique combinations of data word bits used for deriving the check bits of the first set are defined by the left-hand side of the matrix of FIG. 1.
Claim 12
Independent Claim
226 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits, any three bit errors in the same nibble causing exactly one of the syndrome bits corresponding to the first set of check bits to be set.
Claim 13
Independent Claim
226 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits, any three bit errors in the same nibble causing exactly one of the syndrome bits corresponding to the first set of check bits to be set.
Claim 14
Independent Claim
296 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits, the unique combinations of data word bits being chosen so that any single bit error in the possibly corrupted version of the data word will result in different numbers of syndrome bits of the first set being set, than will any two bit errors in the possibly corrupted version, any single bit error in the possibly corrupted version resulting in an odd number of syndrome bits of the first set being set, and any two bit errors in the possibly corrupted version resulting in an even number of syndrome bits of the first set being set.
Claim 15
Independent Claim
296 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits, the unique combinations of data word bits being chosen so that any single bit error in the possibly corrupted version of the data word will result in different numbers of syndrome bits of the first set being set, than will any two bit errors in the possibly corrupted version, any single bit error in the possibly corrupted version resulting in an odd number of syndrome bits of the first set being set, and any two bit errors in the possibly corrupted version resulting in an even number of syndrome bits of the first set being set.
Claim 16
Independent Claim
292 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits, the unique combinations of data word bits being chosen so that any single bit error in the possibly corrupted version of the data word will result in different numbers of syndrome bits of the first set being set, than will any two bit errors in the possibly corrupted version, any single bit error in the possibly corrupted version resulting in three syndrome bits of the first set being set, and any two bit errors in the possibly corrupted version resulting in zero or two syndrome bits of the first set being set.
Claim 17
Independent Claim
292 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits, the unique combinations of data word bits being chosen so that any single bit error in the possibly corrupted version of the data word will result in different numbers of syndrome bits of the first set being set, than will any two bit errors in the possibly corrupted version, any single bit error in the possibly corrupted version resulting in three syndrome bits of the first set being set, and any two bit errors in the possibly corrupted version resulting in zero or two syndrome bits of the first set being set.
Claim 18
Dependent Claim
52 words
The method of claim 1, 10, and 11 in which the unique combinations of data word bits used for deriving the two sets of check bits are chosen so that the identity of any single bit error in the data word can be determined based on the two sets of syndrome bits.
Claim 19
Independent Claim
388 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits, a second set of four original check bits being derived from bits of the original data word, each check bit of the second set being based on a unique combination of data word bits, a second set of four new check bits being derived from bits of the possibly corrupted version of the original data word, each new check bit of the second set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a second set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, the unique combinations of data word bits used for deriving the second set of check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the first and second sets of syndrome bits, and in which some of the check bits are formed by exclusive ORing and others of the check bits are formed by exclusive NORing.
Claim 20
Independent Claim
388 words
A method of detecting bit errors in a possibly corrupted version of an original data word, the bits of said original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, in which a first set of four original check bits are derived from bits of the original data word, each check bit of the first set being based on a unique combination of data word bits, a first set of four new check bits are derived from bits of the possibly corrupted version of the original data word, each new check bit of the first set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a first set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, and the unique combinations of data word bits used for deriving the check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits, a second set of four original check bits being derived from bits of the original data word, each check bit of the second set being based on a unique combination of data word bits, a second set of four new check bits being derived from bits of the possibly corrupted version of the original data word, each new check bit of the second set corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, a second set of syndrome bits are formed by comparing each original check bit with the corresponding new check bit, the unique combinations of data word bits used for deriving the second set of check bits are chosen so that the existence of any three bit errors or four bit errors within a single nibble of the possibly corrupted version will be detectable based on the first and second sets of syndrome bits, and in which some of the check bits are formed by exclusive ORing and others of the check bits are formed by exclusive NORing.
Claim 21
Dependent Claim
34 words
The method of claim 13 in which it is the first set of check bits that are formed by exclusive ORing and the second set of check bits that are formed by exclusive NORing.
Claim 22
Dependent Claim
28 words
The method of claim 13 or 14 in which each data bit participates in the formation of an odd number of the check bits in the second set.
Claim 23
Dependent Claim
29 words
The method of claim 13 or 14 in which all data bits of a given nibble participate in the formation of the same check bits in the second set.
Claim 24
Dependent Claim
36 words
The method of claim 13 or 14 in which the data bits participate in the formation of the check bits in the second set in accordance with the right-hand side of the matrix of FIG. 1.
Claim 25
Dependent Claim
42 words
The method of claim 13 or 14 in which the unique combinations of data word bits used for deriving the two sets of check bits are chosen so that bit errors in possibly corrupted versions of the check bits can be detected.
Claim 26
Dependent Claim
236 words
Apparatus for detecting bit errors in a possibly corrupted version of an original data word, the bits of the original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, comprising a check bit generator for deriving a first set of four original check bits from bits of the original data word, each check bit being based on a unique combination of data word bits, each data bit of a given nibble of the data word being used in forming each bit of a unique combination of exactly three of the check bits of the first set, said check bit generator also being connected to derive a first set of four new check bits from bits of the possibly corrupted version of the original data word, each new check bit corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, and a bit comparator for forming a first set of syndrome bits by comparing each original check bit with the corresponding new check bit, the unique combinations of data word bits used for deriving the check bits being chosen so that the existence of any three bit errors of four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits.
Claim 27
Dependent Claim
236 words
Apparatus for detecting bit errors in a possibly corrupted version of an original data word, the bits of the original data word being organized in nibbles of four bits each, each nibble being stored in a single four-bit memory chip, comprising a check bit generator for deriving a first set of four original check bits from bits of the original data word, each check bit being based on a unique combination of data word bits, each data bit of a given nibble of the data word being used in forming each bit of a unique combination of exactly three of the check bits of the first set, said check bit generator also being connected to derive a first set of four new check bits from bits of the possibly corrupted version of the original data word, each new check bit corresponding to one of the original check bits, each new check bit being based on the same unique combination of bits as its corresponding original check bit, and a bit comparator for forming a first set of syndrome bits by comparing each original check bit with the corresponding new check bit, the unique combinations of data word bits used for deriving the check bits being chosen so that the existence of any three bit errors of four bit errors within a single nibble of the possibly corrupted version will be detectable based on the syndrome bits.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-02-11 | 1994-08-13 | 1995-02-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-02-11 | 1998-08-13 | 1999-02-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-02-11 | 2002-08-13 | 2003-02-12 | $7700.00 | Window Closed / Lapsed |