US 5,331,645 AGranted

Expandable digital error detection and correction device

AssigneeIntegrated Device Technology, Inc.

InventorsMichael J. Miller, Andy P. Chan, Robert W. Stodieck, John R. Mick

Life of this patent

Estimating the term…

Loading patent…

Abstract

A pair of similar, 32-bit, error detection and correction devices, including a "lower 32-bit" device (210) and an "upper 32-bit" device (212) are configured as a 64-bit, error detection and correction system. When a (64-bit) word of data is being stored in memory, the lower 32-bit device (210) develops, on an inter-device bus (226), signals representing generation partial check bits. The upper 32-bit device (212) receives the partial check bits (226), and develops signals representing final check bits (236) for storage with the corresponding data word in memory (220 and 234). When a (64-bit) word of data is being retrieved from memory, from signals representing check bits retrieved from memory (222), the lower 32-bit device (210) generates on an inter-device bus (224), signals representing correction partial syndromes. From the correction partial syndromes (224), the upper 32-bit device (212) develops, on another inter-device bus (228), signals representing correction partial check bits; generates full syndromes; and corrects errors in the upper 32-bits of the corresponding retrieved data word (240). From the correction partial check bits (228) the lower 32-bit device (210) (also) generates full syndromes; and corrects errors in the corresponding lower 32-bits of the retrieved data word (230).

Claims10

Dependent claims

An error detection and correction device (300) comprising in combination:

a first device bus (310);
a second device bus (312);
a third device bus (318);
a fourth device bus (314);
a fifth device bus (316);
a sixth device bus (320);
a first, data, latch means (340) connected to said first device bus (310);
a correction check bit generator (342) connected to said first latch means (340);
a second, check bit, latch means (346) coupled to said second device bus (312);
a first multiplexer means (348) connected to said second device bus (312) and to said second latch means (346);
a first gate means (350) connected to said correction check bit generator (342) and to said first multiplexer means (348);
a second multiplexer means (352) connected to said correction check bit generator (342), to said first gate means (350), and to said third device bus (318);
a first tri-state buffer means (380) connected to said first device bus (310);
a second tri-state buffer means (382) connected to said fifth device bus (316);
a generation check bit generator (400) connected to said first tri-state buffer means (380);
a third multiplexer means (402) connected to said correction check bit generator (342) and to said fourth device bus (314);
a second gate means (404) connected to said third multiplexer means (402) and to said generation check bit generator (400);
a fourth multiplexer means (406) connected to said second gate means (404), to said generation check bit generator (400), and to said second tri-state buffer means (382);
a third gate means (408) connected to said fourth device bus (314) and to said first gate means (350);
a fifth multiplexer means (410) connected to said third gate means (408) and to said first gate means (350);
a combination of an error decoder, error corrector, and pipe-line latch means (520), the combination coupled to said fifth multiplexer means (410);
a third tri-state buffer means (522) connected between said error decoder, error corrector, and pipe-line latch means combination (520) and said sixth device bus (320);
a third, data, latch means (560) connected to said sixth device bus (320);
and
a sixth multiplexer means (562) connected to said error decoder, error corrector, and pipe-line latch means combination (520), to said third latch means (560), and to said first tri-state buffer means (380).

22 more elements

An error detection and correction system comprising in combination:

a first system bus (220);
a second system bus (222);
a third system bus (224);
a fourth system bus (226);
a fifth system bus (228);
a sixth system bus (230);
a seventh system bus (234);
an eighth system bus (236);
a ninth system bus (240);
and
a pair of similar, error detection and correction devices, including a first device (210) connected to said first (220), said second (222), said third (224), said fourth (226), said fifth (228) and said sixth (230) system busses and a second device (212) connected to said third (224), said fourth (226), said fifth (228), said seventh (234), said eighth (236), and said ninth (240) system busses,
said first device (210) including means for receiving on said sixth system bus (230) a set of externally developed signals representing a first predetermined portion of a first word of data, for developing on said first system bus (220) a set of signals representing said first data word first predetermined portion, for generating a set of partial check bits from said first data word first predetermined portion, for developing on said fourth system bus (226) a set of signals representing said first data word first predetermined portion partial check bits, for receiving on said first system bus (220) a set of externally developed signals representing said first predetermined portion of a second word of data, for receiving on said second system bus (222) a set of externally developed signals representing a set of second data word final check bits, for generating a set of partial check bits from said second data word first predetermined portion, for generating a set of first device (210) partial syndromes bits from said second data word final check bits and said second data word first predetermined portion partial check bits, for developing on said third system bus (224) a set of signals representing said first device (210) partial syndrome bits, for receiving on said fifth system bus (228) a set of signals representing second device (212) partial check bits, for generating a set of first device (210) full syndrome bits from said second data word first predetermined portion partial check bits and said second device (212) partial check bits, for correcting errors in said second data word first predetermined portion, and for developing on said sixth system bus (230) a set of signals representing said corrected second data word first predetermined portion, and
said second device (212) including means for receiving on said ninth system bus (240) a set of externally developed signals representing a second predetermined portion of said first data word, for developing on said seventh system bus (234) a set of signals representing said first data word second predetermined portion, for receiving on said fourth system bus (226) the signals representing said first data word first predetermined portion partial check bits, for generating a set of first data word final check bits from said first data word second predetermined portion and said first data word first predetermined portion partial check bits, for developing on said eighth system bus (236) a set of signals representing said first data word final check bits, for receiving on said seventh system bus (234) a set of externally developed signals representing said second predetermined portion of said second word of data, for generating a set of said second device (212) partial check bits from said second data word second predetermined portion, for developing on said fifth system bus (228) second device partial check bits signals, for receiving on said third system bus (224) the signals representing said first device (210) partial syndrome bits, for generating a set of second device (212) full syndrome bits from said second device (212) partial check bits and said first device (210) partial syndrome bits, for correcting errors in said second data word second predetermined portion, and for developing on said ninth system bus (240) a set of signals representing said corrected second data word second predetermined portion;
and
wherein at least one of said pair of error detection and correction devices includes,
a first device bus (310);
a second device bus (312);
a third device bus (318);
a first, data, latch means (340) connected to said first device bus (310);
a correction check bit generator (342) connected to said first latch means (340);
a second, check bit, latch means (346) coupled to said second device bus (312);
a first multiplexer means (348) connected to said second device bus (312) and to said second latch means (346);
a first gate means (350) connected to said correction check bit generator (342) and to said first multiplexer means (348);
a second multiplexer means (352) connected to said correction check bit generator (342), to said first gate means (350), and to said third device bus (318);
a fourth device bus (314);
a fifth device bus (316);
a first tri-state buffer means (380) connected to said first device bus (310);
a second tri-state buffer means (382) connected to said fifth device bus (316);
a generation check bit generator (400) connected to said first tri-state buffer means (380) a third multiplexer means (402) connected to said correction check bit generator (342) and to said fourth device bus (314);
a second gate means (404) connected to said third multiplexer means (402) and to said generation check bit generator (400);
and
a fourth multiplexer means (406) connected to said second gate means (404), to said generation check bit generator (430), and to said second tri-state buffer means (382).

29 more elements

An error detection and correction system comprising in combination:

a first system bus (220);
a second system bus (222);
a third system bus (224);
a fourth system bus (226);
a fifth system bus (228);
a sixth system bus (230);
a seventh system bus (234);
an eighth system bus (236);
a ninth system bus (240);
and
a pair of similar, error detection and correction devices, including a first device (210) connected to said first (220), said second (222), said third (224), said fourth (226), said fifth (228) and said sixth (230) system busses and a second device (212) connected to said third (224), said fourth (226), said fifth (228), said seventh (234), said eighth (236), and said ninth (240) system busses,
said first device (210) including means for receiving on said sixth system bus (230) a set of externally developed signals representing a first predetermined portion of a first word of data, for developing on said first system bus (220) a set of signals representing said first data word first predetermined portion, for generating a set of partial check bits from said first data word first predetermined portion, for developing on said fourth system bus (226) a set of signals representing said first data word first predetermined portion partial check bits, for receiving on said first system bus (220) a set of externally developed signals representing said first predetermined portion of a second word of data, for receiving on said second system bus (222) a set of externally developed signals representing a set of second data word final check bits, for generating a set of partial check bits from said second data word first predetermined portion, for generating a set of first device (210) partial syndromes bits from said second data word final check bits and said second data word first predetermined portion partial check bits, for developing on said third system bus (224) a set of signals representing said first device (210) partial syndrome bits, for receiving on said fifth system bus (228) a set of signals representing second device (212) partial check bits, for generating a set of first device (210) full syndrome bits from said second data word first predetermined portion partial check bits and said second device (212) partial check bits, for correcting errors in said second data word first predetermined portion, and for developing on said sixth system bus (230) a set of signals representing said corrected second data word first predetermined portion, and
said second device (212) including means for receiving on said ninth system bus (240) a set of externally developed signals representing a second predetermined portion of said first data word, for developing on said seventh system bus (234) a set of signals representing said first data word second predetermined portion, for receiving on said fourth system bus (226) the signals representing said first data word first predetermined portion partial check bits, for generating a set of first data word final check bits from said first data word second predetermined portion and said first data word first predetermined portion partial check bits, for developing on said eighth system bus (236) a set of signals representing said first data word final check bits, for receiving on said seventh system bus (234) a set of externally developed signals representing said second predetermined portion of said second word of data, for generating a set of said second device (212) partial check bits from said second data word second predetermined portion, for developing on said fifth system bus (228) second device partial check bits signals, for receiving on said third system bus (224) the signals representing said first device (210) partial syndrome bits, for generating a set 70 of second device (212) full syndrome bits from said second device (212) partial check bits and said first device (210) partial syndrome bits, for correcting errors in said second data word second predetermined portion, and for developing on said ninth system bus (240) a set of signals representing said corrected second data word second predetermined portion;
wherein said first device (210) includes,
a first device bus (310) connected to said first system bus (220);
second device bus (312) connected to said second system bus (222);
a third device bus (318) connected to said third system bus (224);
a fourth device bus (314) connected to said fifth system bus (228);
a fifth device bus (316) connected to said fourth system bus (226);
a sixth device bus (320) connected to said sixth system bus (230);
a first, data, latch means (340) connected to said first device bus (310);
a correction check bit generator (342) connected to said first latch means (340);
a second, check bit, latch means (346) coupled to said second device bus (312);
a first multiplexer means (348) connected to said second device bus (312) and to said second latch means (346);
a first gate means (350) connected to said correction check bit generator (342) and to said first multiplexer means (348);
a second multiplexer means (352) connected to said correction check bit generator (342), to said first gate means (350), and to said third device bus (318);
a first tri-state buffer means (380) connected to said first device bus (310);
a second tri-state buffer means (382) connected to said fifth device bus (316);
a generation check bit generator (400) connected to said first tri-state buffer means (380);
a third multiplexer means (402) connected to said correction check bit generator (342) and to said fourth device bus (314);
a second gate means (404) connected to said third multiplexer means (402) and to said generation check bit generator (400);
a fourth multiplexer means (406) connected to said second gate means (404), to said generation check bits generator (400), and to said second tri-state buffer means (382);
a third gate means (408) connected to said fourth device bus (314) and to said first gate means (350)
a fifth multiplexer means (410) connected to said third gate means (408) and to said first gate means (350);
a combination of an error decoder, error corrector, and pipeline latch means (520), the combination coupled to said fifth multiplexer means (410);
a third tri-state buffer means (522) connected between said error decoder, error corrector, and pipeline latch means combination (520) and said sixth device bus (320);
a third, data, latch means (560) connected to said sixth device bus (320);
and
a sixth multiplexer means (562) connected to said error decoder, error corrector, and pipeline latch means combination (520), to said third latch means (560), and to said first tri-state buffer means (380).

36 more elements

An error detection and correction system comprising in combination:

a first system bus (220);
a second system bus (222);
a third system bus (224);
a fourth system bus (226);
a fifth system bus (228);
a sixth system bus (230);
a seventh system bus (234);
an eighth system bus (236);
a ninth system bus (240);
and
a pair of similar, error detection and correction devices, including a first device (210) connected to said first (220), said second (222), said third (224), said fourth (226), said fifth (228) and said sixth (230) system busses and a second device (212) connected to said third (224), said fourth (226), said fifth (228), said seventh (234), said eighth (236), and said ninth (240) system busses,
said first device (210) including means for receiving on said sixth system bus (230) a set of externally developed signals representing a first predetermined portion of a first word of data, for developing on said first system bus (220) a set of signals representing said first data word first predetermined portion, for generating a set of partial check bits from said first data word first predetermined portion, for developing on said fourth system bus (226) a set of signals representing said first data word first predetermined portion partial check bits, for receiving on said first system bus (220) a set of externally developed signals representing said first predetermined portion of a second word of data, for receiving on said second system bus (222) a set of externally developed signals representing a set of second data word final check bits, for generating a set of partial check bits from said second data word first predetermined portion, for generating a set of first device (210) partial syndromes bits from said second data word final check bits and said second data word first predetermined portion partial check bits, for developing on said third system bus (224) a set of signals representing said first device (210) partial syndrome bits, for receiving on said fifth system bus (228) a set of signals representing second device (212) partial check bits, for generating a set of first device (210) full syndrome bits from said second data word first predetermined portion partial check bits and said second device (212) partial check bits, for correcting errors in said second data word first predetermined portion, and for developing on said sixth system bus (230) a set of signals representing said corrected second data word first predetermined portion, and
said second device (212) including means for receiving on said ninth system bus (240) a set of externally developed signals representing a second predetermined portion of said first data word, for developing on said seventh system bus (234) a set of signals representing said first data word second predetermined portion, for receiving on said fourth system bus (226) the signals representing said first data word first predetermined portion partial check bits, for generating a set of first data word final check bits from said first data word second predetermined portion and said first data word first predetermined portion partial check bits, for developing on said eighth system bus (236) a set of signals representing said first data word final check bits, for receiving on said seventh system bus (234) a set of externally developed signals representing said second predetermined portion of said second word of data, for generating a set of said second device (212) partial check bits from said second data word second predetermined portion, for developing on said fifth system bus (228) second device partial check bits signals, for receiving on said third system bus (224) the signals representing said first device (210) partial syndrome bits, for generating a set of second device (212) full syndrome bits from said second device (212) partial check bits and said first device (210) partial syndrome bits, for correcting errors in said second data word second predetermined portion, and for developing on said ninth system bus (240) a set of signals representing said corrected second data word second predetermined portion;
wherein said second device (212) includes,
a first device bus (310) connected to said seventh system bus (234);
a second device bus (312) connected to said third system bus (224);
a third device bus (318) connected to said fifth system bus (228);
a fourth device bus (314) connected to said fourth system bus (226);
a fifth device bus (316) connected to said eighth system bus (236);
a sixth device bus (320) connected to said ninth system bus (240);
a first, data, latch means (340) connected to said first device bus (310);
a correction check bit generator (342) connected to said first latch means (340);
a second, check bit, latch means (346) coupled to said second device bus (312);
a first multiplexer means (348) connected to said second device bus (312) and to said second latch means (346);
a first gate means (350) connected to said correction check bit generator (342) and to said first multiplexer means (348);
a second multiplexer means (352) connected to said correction check bit generator (342), to said first gate means (350), and to said third device bus (318);
a first tri-state buffer means (380) connected to said first device bus (310);
a second tri-state buffer means (382) connected to said fifth device bus (316);
a generation check bit generator (400) connected to said first tri-state buffer means (380);
a third multiplexer means (402) connected to said correction check bit generator (342) and to said fourth device bus (314);
a second gate means (404) connected to said third multiplexer means (402) and to said generation check bit generator (400);
a fourth multiplexer means (406) connected to said second gate means (404), to said generation check bit generator (400), and to said second tri-state buffer means (382);
a third gate means (408) connected to said fourth device bus (314) and to said first gate means (350);
a fifth multiplexer means (410) connected to said third gate means (408) and to said first gate means (350);
a combination of an error decoder, error corrector, and pipeline latch means (520), the combination coupled to said fifth multiplexer means (410);
a third tri-state buffer means (522) connected between said error decoder, error corrector, and pipeline latch means combination (520) and said sixth device bus (320);
a third, data, latch means (560) connected to said sixth device bus (320);
and
a sixth multiplexer means (562) connected to said error decoder, error corrector, and pipeline latch means combination (520), to said third latch means (560), and to said first tri-state buffer means (380).

36 more elements

An error detection and correction device comprising in combination:

a first device bus (310);
a second device bus (312);
a third device bus (318);
a first, data, latch means (340) connected to said first device bus (310);
a correction check bit generator (342) connected to said first latch means (340);
a second, check bit, latch means (346) coupled to said second device bus (312);
a first multiplexer means (348) connected to said second device bus (312) and to said second latch means (346);
a first gate means (350) connected to said correction check bit generator (342) and to said first multiplexer means (348);
a second multiplexer means (352) connected to said correction check bit generator (342), to said first gate means (350), and to said third device bus (318);
a fourth device bus (314);
a fifth device bus (316);
a first tri-state buffer means (380) connected to said first device bus (310);
a second tri-state buffer means (382) connected to said fifth device bus (316);
a generation check bit generator (400) connected to said first tri-state buffer means (380);
a third multiplexer means (402) connected to said correction check bit generator (342) and to said fourth device bus (314);
a second gate means (404) connected to said third multiplexer means (402) and to said generation check bit generator (400);
and
a fourth multiplexer means (406) connected to said second gate means (404), to said generation check bit generator (400), and to said second tri-state buffer means (382).

15 more elements

An error detection and correction (EDC) device (300) for inclusion in a memory system that includes an identical pair of first and second EDC devices, each EDC device comprising:

a data input latch (340) for receiving half of a parallel set of bits from a memory system;
a data output latch (560) for transmitting said half of parallel set of bits to said memory system;
a check bit input latch (346) for receiving a plurality of check bits or partial syndrome bits from an external source;
a check bit generator (342) having an input (364) for receiving a plurality of latched input bits from the data input latch (340);
a preliminary syndrome generator (350) having a first input from the check bit generator (342) and a second input from the check bit latch (346);
a first multiplexer (352) for selecting for output a set of correction partial check bits (378) from a first input coupled to the check bit generator (342) or a set of partial syndrome bits on pins (314) from the preliminary syndrome generator;
a final syndrome generator (408) having a first input for receiving a set of partial check bits from an external source and a second input coupled to the preliminary syndrome generator (350);
a second multiplexor (410) for selecting for output a first input from the final syndrome generator (408) or a second input from the preliminary syndrome generator (350);
a bit error decoder (520) having an input from the second multiplexer (410);
a correction logic (520) having a first input from the bit error decoder, a second input from a multiplexer (468) coupled to data latch (340), and a data output to a pipeline latch;
and
mode selection means (490, 502, 512) for assigning said first and second EDC devices to opposite bit processing roles that include, a least significant data (LSD) bit processing role in which the first multiplexor (352) selects its second input such that said set of partial syndrome bits (378) is output on pins (318) and the check bit input latch (346) is configured to receive a plurality of check bits from said memory system, and
a most significant data (MSD) bit processing role in which the first multiplexer (352) selects its first input (364) such that another set of correction partial check bits is output and the check bit input latch (346) is configured to receive said set of partial syndrome bits from the EDC device in said LSD bit processing role, and said preliminary syndrome generator (350) receives input from said check bit latch (346) containing partial syndrome information and second input from check bit generator (342), and said multiplexer (410) selects a final syndrome from said final syndrome generator (408) and the final syndrome generator (408) is configured to receive said set of partial check bits on pins (314) on said first input and partial syndrome bits (378) on said second input.

10 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/054,346Filed 26 Apr 1993 · continuation
Priority: 17 Jan 1990
Granted: 19 Jul 1994
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 11/1048
In individual solid state devices: using arrangements adapted for a specific error detection or correction feature
H03M 13/19
Linear codes: single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming…
G06F
Computing and data processing
H03M
Coding