US 5,491,702 A · Apparatus for detecting any single bit error, detecting any two bit error, and detecting any three or four bit error in a group of four bits for a 25- or 64-bit data word

Abstract

An error detection system wherein 64 bits of data word are protected by 8 check bits which yield 8-bit syndromes. Single-bit errors are indicated by syndromes that contain exactly three "1"s or by syndromes that contain exactly five "1"s in which bits 0-3 or 4-7 of the syndrome are all "1." Single-bit errors that occur from faulty check bits are indicated by syndromes that contain exactly one "1." All two-bit errors, and four-bit errors within a nibble, are indicated by syndromes that contain an even number of "1"s (i.e., an even number of "1"s). Three-bit errors within a nibble are indicated by syndromes that contain five "1"s in which bits 0-3 of the syndrome and bits 4-7 of the syndrome are not all "1." Four-bit errors within a nibble are indicated by syndromes that contain four "1"s. In another embodiment of the invention, 25 bits of data word are protected by 7 check bits yielding 7-bit syndromes. Single-bit errors are indicated by syndromes that contain exactly three "1" s except single-bit errors that occur from faulty check bits are indicated by syndromes that contain exactly one "1". Two-bit errors are indicated by syndromes that contain an even number of "1"s, and three-bit errors within a nibble are indicated by syndromes that contain five "1"s or seven "1"s. Four-bit errors within a nibble are indicated by syndromes that contain four "1"s or six "1"s.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims117

Dependent claims

An apparatus for detecting data errors in a block of data comprising:

syndrome calculating means for calculating a multiple-bit syndrome from the block of data;
and
three-bit-error indicating means, coupled to the syndrome calculating means, for indicating every occurrence of a three-bit error within a four-bit group of data bits within the block of data and distinguishing all three-bit errors from one-bit errors, wherein the three-bit-error indicating means comprises:
more-than-three-ones detecting means, coupled to the syndrome calculating means, for detecting the occurrence of more than three ones in the syndrome;
and
error signalling means, coupled to the more-than-three-ones detecting means, for providing an error signal when the syndrome contains more than three ones.

3 more elements

An apparatus for detecting data errors in a sixty-four bit block of data comprising:

syndrome calculating means for calculating an eight bit syndrome from the block of data, the syndrome including a first four-bit portion and a second four-bit portion;
a first three-ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of exactly three ones in the first four-bit portion of the syndrome;
a second three-ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of exactly three ones in the second four-bit portion of the syndrome;
a first ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of one or more ones in the first four bit portion of the syndrome;
a second ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of one or more ones in the second four-bit portion of the syndrome;
even ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of an even number of ones in the syndrome;
odd ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of an odd number of ones in the syndrome;
one-bit-error indicating means, coupled to the first three ones detecting means, to the second three ones detecting means, to the first ones detecting means, to the second ones detecting means, and to the odd ones detecting means, for providing a one-bit-error signal indicating an occurrence of one-bit errors within the block of data;
and
uncorrectable error indicating means, coupled to the first three-ones detecting means, to the second three-ones detecting means, to the first ones detecting means, to the second ones detecting means, and to the even ones detecting means, for providing an uncorrectable-error signal indicating every occurrence of two-bit errors and three-bit and four-bit errors within a four-bit group of data bits within the block of data and distinguishing all three-bit errors from one-bit errors.

7 more elements

An apparatus for detecting data errors in a twenty-five bit block of data comprising:

syndrome calculating means for calculating a seven-bit syndrome from the block of data, the syndrome including a four-bit portion and a three-bit portion;
three-ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of three ones in the three-bit portion of the syndrome;
first ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of at least one one in the four-bit portion of the syndrome;
three-or-more-ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of three or more ones in the four-bit portion of the syndrome;
second ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of at least one one in the three-bit portion of the syndrome;
even ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of an even number of ones in the syndrome;
odd ones detecting means, coupled to the syndrome calculating means, for detecting an occurrence of an odd number of ones in the syndrome;
one-bit-error indicating means, coupled to the three ones detecting means, to the first ones detecting means, to the three-or-more-ones detecting means, to the second ones detecting means, and to the odd ones detecting means, for providing a one-bit-error signal indicating an occurrence of one-bit errors within the block of data;
and
uncorrectable error indicating means, coupled to the three-ones detecting means, to the first ones detecting means, to the three-or-more-ones detecting means, to the second ones detecting means, and to the even ones detecting means, for providing an uncorrectable-error signal indicating every occurrence of two-bit errors and three-bit and four-bit errors within a four-bit group of data bits within the block of data and distinguishing all three bit errors from one-bit errors.

7 more elements

An apparatus for detecting data errors in a block of data having a plurality of check bits interspersed throughout the block of data comprising:

syndrome calculating circuitry for calculating a multiple bit syndrome from the block of data;
three-bit error indicating circuitry, coupled to the syndrome calculating circuitry, for indicating every occurrence of a three-bit error within any four bit group of data bits within the block of data and distinquishing all three-bit errors from one-bit errors;
and
four-bit-error indicating circuitry, coupled to the syndrome calculating circuitry, for indicating every occurrence of a four-bit error within any four-bit group of data bits within the block of data, wherein the four-bit-error indicating circuitry comprises:
even-ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting the occurrence of an even number of ones in the syndrome;
and
error signalling circuitry, coupled to the even-ones detecting circuitry, for providing an error signal when the syndrome contains an even number of ones.

4 more elements

An apparatus for detecting data errors in a sixty-four bit block of data having a plurality of check bits interspersed throughout the block of data comprising:

syndrome calculating circuitry for calculating an eight bit syndrome from the block of data, the syndrome including a first four-bit portion and a second four-bit portion;
a first three-ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of exactly three ones in the first four-bit portion of the syndrome;
a second three-ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of exactly three ones in the second four-bit portion of the syndrome;
a first ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of one or more ones in the first four bit portion of the syndrome;
a second ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of one or more ones in the second four-bit portion of the syndrome;
even ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of an even number of ones in the syndrome;
odd ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of an odd number of ones in the syndrome;
one-bit-error indicating circuitry, coupled to the first three ones detecting circuitry, to the second three ones detecting circuitry, to the first ones detecting circuitry, to the second ones detecting circuitry, and to the odd ones detecting circuitry, for providing a one-bit-error signal indicating an occurrence of one-bit errors within the block of data;
and
uncorrectable error indicating circuitry, coupled to the first three-ones detecting circuitry, to the second three-ones detecting circuitry, to the first ones detecting circuitry, to the second ones detecting circuitry, and to the even ones detecting circuitry, for providing an uncorrectable-error signal indicating every occurrence of two-bit errors and three-bit and four-bit errors within a four-bit group of data bits within the block of data and distinguishing all three-bit errors from one-bit errors.

7 more elements

An apparatus for detecting data errors in a twenty-five bit block of data having a plurality of check bits interspersed throughout the block of data comprising:

syndrome calculating circuitry for calculating a seven-bit syndrome from the block of data, the syndrome including a four-bit portion and a three-bit portion;
three-ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of three ones in the three-bit portion of the syndrome;
first ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of at least one one in the four-bit portion of the syndrome;
three-or-more-ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of three or more ones in the four-bit portion of the syndrome;
second ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of at least one one in the three-bit portion of the syndrome;
even ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of an even number of ones in the syndrome;
odd ones detecting circuitry, coupled to the syndrome calculating circuitry, for detecting an occurrence of an odd number of ones in the syndrome;
one-bit-error indicating circuitry, coupled to the three ones detecting circuitry, to the first ones detecting circuitry, to the three-or-more-ones detecting circuitry, to the second ones detecting circuitry, and to the odd ones detecting circuitry, for providing a one-bit-error signal indicating an occurrence of one-bit errors within the block of data;
and
uncorrectable error indicating circuitry, coupled to the three-ones detecting circuitry, to the first ones detecting circuitry, to the three-or-more-ones detecting circuitry, to the second ones detecting circuitry, and to the even ones detecting circuitry, for providing an uncorrectabie-error signal indicating every occurrence of two-bit errors and three-bit and four-bit errors within a four-bit group of data bits within the block of data and distinguishing all three bit errors from one-bit errors.

7 more elements

Dependencies are inferred from the claim text.

Description4,680 words

Summary965 words

#This invention relates to fault detection in computer systems and, more particularly, to a method and apparatus for detecting memory failures using error detecting/correcting codes.

#Many techniques are known for detecting and/or correcting data errors which occur in computer systems. Such errors typically occur because of hardware failure or because of external influences such as electromagnetic radiation, subatomic particles, etc. The errors ordinarily occur as inverted data bits within the datum. That is, an error appears as a "1" which should be a "0" and vice versa. A common error detection technique includes the use of parity bits embedded within the datum. To determine the value of the parity bit, the number of "1"s in the datum (not including the parity bit) are counted, and it is determined whether the sum is even or odd. In even parity systems, the total number of "1"s in the datum (including the parity bit) must always be even. Thus, if the total number of "1"s in the datum, less the parity bit, is odd, then the parity bit is set to "1", whereas if the total number of "1"s in the datum is even, then the parity bit is set to "0". In odd parity systems, the parity bit is set to ensure that the total number of "1"s in the datum, including the parity bit, is odd. Of course, this simple parity bit scheme cannot detect an even number of errors, so a datum with 2, 4, 6, etc., errors will appear error-free. Furthermore, the location of the erroneous bit is unknown, so the error cannot be corrected.

#More advanced systems are available which locate the position of single bit errors and which detect the existence of multiple bit errors. See, for example, R. W. Hamming, "Error Detecting and Error Correcting Codes," Bell System Tech. J. 29, 147(1950); W. W. Peterson, Error Correcting Codes, MIT Press, Cambridge, Mass., 1961; and M.Y Hsiao, "A Class of Optimal Minimum Odd-Weight-Column SEC-DED Codes" IBM J. Res. Develop., July 1970, p. 395. In a typical system employing one of these codes, the datum is encoded to produce a first plurality of check bits (e.g., 8 bits) which are appended to the datum. The value of each check bit is determined from a unique subset of bits of the datum in the same manner described for the calculation of parity bits. When the datum is later read, the subsets are combined with their respective check bits to produce a plurality of bits termed a "syndrome." If the syndrome bits are zero, the datum is free of errors. However, if the syndrome bits are non-zero, then an error exists somewhere in the datum. The value of the syndrome bits may be used for locating and correcting single bit errors.

Brief description of the drawings10 figures

#FIG. 1 is a diagram of a particular embodiment of a parity check matrix according to the present invention which may be used for detecting and correcting errors in a group of sixty-four bits;

#FIG. 2 is a diagram of a particular embodiment of a check bit generating. circuit according to the present invention;

#FIG. 3 is a diagram of a particular embodiment of a syndrome bit generating circuit according to the present invention;

Detailed description3,447 words

#FIG. 1 is a diagram of a particular embodiment of a parity check matrix according to the present invention which may be used for detecting and correcting errors in a group of sixty-four bits (e.g., data in a cache memory). In this embodiment, the sixty-four data bits are protected by eight check bits for yielding eight-bit syndromes. The 18 sections, each of four columns, represent information stored, for example, as 18 four-bit nibbles in 18 separate DRAMs, each with a "four-by-X" organization where X depends on the density of the DRAM. Of course, in alternative embodiments of the invention other memories or memory organizations can be employed. The positions of the eight check bits are shown in the top row, while the positions of the 64 data bits are shown in the next two rows, where the top row is the first (most significant) digit of the data bit number and the second row is the second (least significant) digit of the data bit number. For example, as shown in the top row check bit C2 appears in the fourth four-bit nibble from the left in the right-most bit position, while data bit D51 appears immediately to the right of check bit C2. Unlike the check bits described in the Hsiao reference discussed above, the check bits are not grouped together and appended to the end of each 64-bit data block. Instead, the check bits are interspersed throughout the 64-bit data block, and not necessarily in numerical order.

#As shown in FIG. 1, the matrix includes eight rows, each of which is used to generate one check bit and one syndrome bit. Each "1" in a data bit position indicates that the associated data bit is included in an exclusive-OR which is used to calculate a check bit for that row. For example, FIG. 2 shows how check bit C7 is generated from row 7 of the matrix. Data bits numbered 63-58, 57-56, 53, 51, 43-36, 31, 27, 23, 19, 11, 8, 5 and 3 are input to an exclusive-OR gate 50 whose output terminal provides the value of check bit C7. As shown in FIG. 3, the corresponding syndrome bit S7 is generated by an exclusive-OR gate 52 using the same bits together with check bit C7. The eight syndrome bits, S7 through S0, together comprise the syndrome for the 64-bit code.

#The bottom row of the parity check matrix indicates the number of "1"s in each column of the matrix. The check bit columns contain only one "1" since each check bit is used to calculate only one syndrome bit. Most columns contain three "1"s, while some columns contain 5 "1"s. Each column of the parity check matrix is unique. That is, no column has the same pattern of "1"s as another column. This allows detection and correction of single bit errors. For example, if data bit 63 is in error, then the syndrome will have the value 11001000. Since no other column has that pattern, the identification of bit 63 as the bit in error is assured. The syndrome pattern then may be decoded using appropriate gating circuitry to identify and correct the erroneous bit as discussed below in conjunction with FIGS. 6A-D and 7A-B.

Facts

Application

07/918,819Filed 22 Jul 1992

Granted

13 Feb 1996

Term ended

13 Feb 2013

Estimated · how

Pre-1995 term; greater of 17 years from grant or 20 years from filing when eligible. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification5 codes

G06F 11/1028
Using codes or arrangements adapted for a specific type of error: adjacent errors, e.g. error in n-bit wide storage units, i.e. package error
H03M 13/00
Coding, decoding or code conversion, for error detection or error correction
H03M 13/51
Error detection, forward error correction or error protection, not provided for in groups H03M13/01 - H03M13/37: constant weight codes; n-out-of-m…
G06F
Computing and data processing

Apparatus for detecting any single bit error, detecting any two bit error, and detecting any three or four bit error in a group of four bits for a 25- or 64-bit data word

Life of this patent

Apparatus for detecting any single bit error, detecting any two bit error, and detecting any three or four bit error in a group of four bits for a 25- or 64-bit data word

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims117

Description4,680 words

Drawings

Classification5 codes

Life of this patent

Description4,680 words