Error detection and correction locator circuits

Claim 2

In a data processing system including a memory subsystem having a memory for storing groups of data signals, each group including a number of data bits and error detection and correction (EDAC) means including an encoder for generating a group of check code bit signals for each of said groups of data signals for storage in said memory together with the group of data signals associated therewith and a syndrome decoder for generating a group of syndrome bit signals in response to each group of data signals and group of check code bits read out from said memory, said group of syndrome signals for detecting correctable and uncorrectable error conditions within said group of data and check code bits signals, said EDAC means further including EDAC correction circuits comprising: a plurality of decoder circuit means, each having a number of input terminals and a number of output terminals including first and second groups, said number of input terminals of each decoder circuit means being connected to receive a different combination of said group of syndrome signals from said syndrome decoder; a plurality of data bit correction circuit means connected to receive each said group of data signals read out from said memory, said plurality corresponding to said number of data bits, each of said data bit correction circuit means being connected to a different one of said first group of output terminals of one of said plurality of decoder circuit means and being connected to receive a different one of said number of data bits; and, said plurality of decoder circuit means being conditioned by said group of syndrome signals to force a predetermined one of said first group of output terminals of one of said plurality of decoder circuit means to a predetermined state for enabling correction of a data bit signal by one of said pluarlity of said correction circuit means when said group of syndrome signals designate the presence of a correctable error condition and said plurality of decoder circuit means being conditioned by said group of syndrome signals to force one of said second group of output terminals of one of said plurality of decoder circuit means to said predetermined state for inhibiting correction of any of said data bit signals by said plurality of correction circuit means when said group of syndrome signals designate the presence of an uncorrectable error condition.

Claim 3

The system of claim 1 wherein said group of syndrome signals includes first and second groups of binary signals, said first group of binary signals being coded to designate which one of said plurality of decoder circuit means is to be enabled for operation and said second group of binary signals being coded to designate which one of said number of output terminals is to be forced to said predetermined state, and said number of input terminals of said plurality of decoder circuit means includes first and second groups of input terminals said first group of each decoder circuit means being connected to receive said first group of binary signals and said second group of each decoder circuit means being connected to receive said second group of binary signals.

Claim 4

The system of claim 2 wherein said first group of input terminals are enable inputs and said second group of input terminals are select inputs, said first group of input terminals of each decoder circuit means being connected to receive a different combination of said first group of syndrome signals and said second group of input terminals of said plurality of decoder circuit means being connected to receive the same combination of said second group of syndrome signals.

Claim 5

The system of claim 3 wherein said first group of said output terminals includes no greater than one-half the total number of said output terminals.

Claim 6

The system of claim 4 wherein said first group and second group of input terminals correspond to one-half the total number of said input terminals.

Claim 7

The system of claim 1 wherein said predetermined state is a binary ZERO state and wherein each of said data bit correction circuit means includes an exclusive OR circuit, said exclusive OR circuit being conditioned by said predetermined state from one of said second group of output terminals to complement the state of said data bit signal to correct the correctable error condition.

Claim 8

The system of claim 6 wherein said correctable error condition corresponds to a single bit error and said uncorrectable error condition includes double bit and check code bit error conditions.

Claim 9

The system of claim 1 wherein each group of data signals further includes a parity bit and said encoder is connected to receive at least one parity bit coded for indicating the validity of a group of data signals associated therewith, said encoder generating said group of check code bits from said group of data signals and said one parity bit to include at least one check bit signal for deriving the state of said one parity bit and wherein one of said plurality of decoder circuit means forces a predetermined one of said second group of output terminals to said predetermined state for indicating that said derived state of said one parity bit is in error, said EDAC correction circuits further including logic circuit means connected to said predetermined one of said second group of output terminals and said one check bit signal for producing a signal corresponding to the correct state of said one parity bit derived from said one check bit signal in parallel with any correction of said data bit signals.

Claim 10

The system of claim 8 wherein said logic circuit means includes: first logic gating means connected to receive said one check code bit signal and predetermined ones of said data bit signals required for deriving the state of said one parity bit signal; second logic gating means connected to predetermined ones of said first group of output terminals which indicate the correctness of said one check code bit signal and predetermined ones of said data bit signals; and output logic gating means connected to said first and second logic gating means, said output logic gating means being conditioned by said first and second logic gating means to generate said signal corresponding to the correct state of said one parity bit.

Claim 11

The system of claim 9 wherein said first logic gating means and output logic gating means each include an exclusive OR circuit.

Claim 12

A data processing system including a memory subsystem comprising a memory for storing data signals received from a plurality of devices, said data signals including a number of groups of data bits and a corresponding number of parity bits for indicating the validity of said groups of data bits, an encoder for generating a group of check code bits derived from said data signals for writing into said memory together with said number of data bits and a decoder for generating a plurality of syndrome signals from said number of data bits and check bit signals accessed from said memory for locating errors in said data signals, said memory subsystem further comprising: error location circuit means connected to said decoder for generating signals designating locations of single bit and double bit errors, said circuit means including a plurality of decoder circuits, each decoder circuit having a number of input terminals for receiving said syndrome signals and a number of output terminals for generating said signals indicating said locations of said single bit and double bit errors; a plurality of data bit correction circuits, each being connected to receive a different one of said number of data bits; and, conductor means for connecting each of said plurality of data bit correction circuits to a different one of said output terminals of one of said decoder circuits which designates the presence of single bit error in said different one of said number of data bits, said plurality of decoder circuits in response to said syndrome signals designating single and double bit errors being operative to produce a predetermined signal at a connected one of said output terminals to enable said plurality of correction circuits for correction of only single bit errors in said data bits.

Claim 13

A data processing system including a memory subsystem comprising a memory for storing data signals received from a plurality of devices, said data signals including a number of groups of data bits and a corresponding number of parity bits for indicating the validity of said groups of data bits, an encoder for generating a group of check code bits derived from said data signals for writing into said memory together with said number of data bits and a decoder for generating a plurality of syndrome signals from said number of data bits and check bit signals accessed from said memory for locating errors in said data signals, said memory subsystem further comprising: error location circuit means connected to said decoder for generating signals designating locations of single bit and double bit errors, said circuit means including a plurality of decoder circuits, each decoder circuit having a number of input terminals for receiving said syndrome signals and a number of output terminals for generating said signals indicating said locations of said single bit and double bit errors; a plurality of data bit correction circuits, each being connected to receive a different one of said number of data bits; and, conductor means for connecting each of said plurality of data bit correction circuits to a different one of said output terminals of one of said decoder circuits which designates the presence of single bit error in said different one of said number of data bits, said plurality of decoder circuits in response to said syndrome signals designating single and double bit errors being operative to produce a predetermined signal at a connected one of said output terminals to enable said plurality of correction circuits for correction of only single bit errors in said data bits.

Claim 14

The system of claim 11 wherein a number of said check code subsystem bits generated by said encoder designate the states of said number of said parity bits, and wherein said subsystem further includes logic circuit means connected to receive said number of said check code bits and connected to a number of connected and unconnected output terminals of said plurality of decoder circuits, said logic circuit means being operative to produce a number of signals corresponding to the correct states of said number of parity bits in parallel with any required correction of said data bits.

Claim 15

The system of claim 12 wherein said number of parity bits and check code bits is one and wherein said logic circuit means includes: first logic gating means connected to receive said check code bit and predetermined ones of said data bits required for deriving the state of said parity bit; second logic gating means connected to a predetermined one of an unconnected output terminal which indicates the correctness of said check code bit and to predetermined ones of said connected output terminals which indicate the correctness of said predetermined ones of said data bits; and, output logic gating means connected to said first and second gating means, said output logic gating means being conditioned by said first and second logic gating means to generate said correct state of said parity bit.

Claim 16

The system of claim 9 wherein said first logic gating means and output logic gating means, each include exclusive OR circuits.

Claim 17

The system of claim 11 wherein said group of syndrome signals includes first and second groups of binary signals, said first group of binary signals being coded to designate which one of said plurality of decoder circuits is to be enabled for operation and said second group of binary signals being coded to designate which one of said number of output terminals is to produce said predetermined signal.

Claim 18

The system of claim 15 wherein said number of input terminals of each decoder circuit includes a group of enable inputs and a group of select inputs, said enable inputs of each decoder circuit being connected to receive said first group of binary signals and said select inputs of each decoder circuit being connected to receive said second group of binary signals.

Claim 19

A data processing system including a memory subsystem having a memory for storing groups of data signals, each group including a number of data bits and at least one parity bit for indicating the validity of said data bits and error detection and correction (EDAC) means including a encoder for generating a group of check code bits from said number of data bits and said parity bit of each group for storage with said number of data bits of said each group and a decoder for generating pairs of complementary syndrome signals in reponse to said data bits and said group of check code bits, said pairs of complementary syndrome signals for detecting double bit errors and single bit errors in said number of data bits, said group of check code bits and said parity bit, said memory system further comprising: error locator circuit means connected to said decoder for receiving predetermined ones of said pairs of said complementary syndrome signals, said error locator circuit means including a number of decoder circuits, each decoder circuit having a number of input terminals connected for receiving a different combination of said predetermined ones of said pairs of complementary syndrome signals and a number of output terminals for generating predetermined output signals indicating the location of single bit errors in said data bits and check code bits and double bit errors; a plurality of data bit correction circuits, each being connected to receive a different one of said number of data bits and being connected to a predetermined one of said output terminals of one of said decoder circuits which designates the presence of a single bit error in said different one of said number of data bits; and, logic circuit means for generating said parity bit, said circuit means being connected to receive at least one of said check code bits and predetermined ones of said data bits and said circuit means being connected to a number of said output terminals of predetermined ones of said decoder circuits which generate signals indicate the location of single bit errors in said one of said check code bits and said predetermined ones of said data bits, said plurality of decoder circuits in response to said predetermined ones of said pairs of complementary syndrome signals being operative to force different ones of said output terminals to a predetermined state for conditioning said plurality of data bit correction circuits and said logic circuit means for correction of only single bit errors enabling the correction of said number of data bits and the generation of said parity bit to proceed concurrently.

Claim 20

A data processing system including a memory subsystem having a memory for storing groups of data signals, each group including a number of data bits and at least one parity bit for indicating the validity of said data bits and error detection and correction (EDAC) means including a encoder for generating a group of check code bits from said number of data bits and said parity bit of each group for storage with said number of data bits of said each group and a decoder for generating pairs of complementary syndrome signals in reponse to said data bits and said group of check code bits, said pairs of complementary syndrome signals for detecting double bit errors and single bit errors in said number of data bits, said group of check code bits and said parity bit, said memory system further comprising: error locator circuit means connected to said decoder for receiving predetermined ones of said pairs of said complementary syndrome signals, said error locator circuit means including a number of decoder circuits, each decoder circuit having a number of input terminals connected for receiving a different combination of said predetermined ones of said pairs of complementary syndrome signals and a number of output terminals for generating predetermined output signals indicating the location of single bit errors in said data bits and check code bits and double bit errors; a plurality of data bit correction circuits, each being connected to receive a different one of said number of data bits and being connected to a predetermined one of said output terminals of one of said decoder circuits which designates the presence of a single bit error in said different one of said number of data bits; and, logic circuit means for generating said parity bit, said circuit means being connected to receive at least one of said check code bits and predetermined ones of said data bits and said circuit means being connected to a number of said output terminals of predetermined ones of said decoder circuits which generate signals indicate the location of single bit errors in said one of said check code bits and said predetermined ones of said data bits, said plurality of decoder circuits in response to said predetermined ones of said pairs of complementary syndrome signals being operative to force different ones of said output terminals to a predetermined state for conditioning said plurality of data bit correction circuits and said logic circuit means for correction of only single bit errors enabling the correction of said number of data bits and the generation of said parity bit to proceed concurrently.

Claim 21

The system of claim 17 wherein said logic circuit means includes: first logic gating means connected to receive said one check code bit and said predetermined ones of said data bits; second logic gating means connected to said predetermined ones of said output terminals which indicates the correctness of said one check code bit and said predetermined ones of said data bits; and, output logic gating means connected to said first and second logic gating means, said output logic gating means being conditioned by said first and second logic gating means to generate said one parity bit.

Claim 22

The system of claim 18 wherein said first logic gating means and said output gating means each include exclusive OR circuits.

Claim 23

The system of claim 19 wherein said predetermined ones of said pairs of complementary syndrome signals first and second groups of binary coded signals, said first group of binary coded signals designating which one of said number of decoder circuits is to be enabled and said second group of binary coded signals designating which one of said number of output terminals of said designated decoder circuit is to produce one of said predetermined output signals.

Claim 24

The system of claim 20 wherein said number of said decoder circuits is equal to more than one-half said number of check code bits and less than said number of said check code bits.