Dual function error correcting system

A dual function error correcting system for alternately correcting a single random 1-bit error in a data word having M-1 data byte positions and one check byte position, each of which consists of b bits, or a multi-bit error in a defective byte position of said data word by processing the same non-zero syndrome byte resulting from exclusive-ORing a write check byte and a read check byte, each bit of said check bytes representing the modulo-2 sum of the binary value of the data bits in different bit positions of said data word during reading and writing respectively, said different bit positions being selected in accordance with a parity check matrix H' which is developed from a parity check matrix H corresponding to an m-sequence having 2.sup.b -1 columns and b rows by systematically selecting M groups of b columns from said matrix H such that adjacent groups are spaced apart in said H matrix .lambda.-b columns where .lambda. is equal to or greater than b and does not result in two of said M groups having an overlapping relationship;

• means for exclusive-ORing said read check character and said write check character to develop said syndrome byte;
• a processing circuit for non-zero syndrome bytes, including:
• (a) a b stage register for receiving said developed syndrome byte when a non-zero syndrome pattern is present;
• (b) a logic block associated with each stage having an output connected to the input of each stage and an input connected to outputs of predetermined stages;
• and
• (c) means to cycle the contents of said register through said associated logic blcks back to said register whereby the pattern of said developed syndrome byte is changed after each cycle in a predetermined manner to a different pattern;
• and
• means connected to said cycling means to selectively control the number of cycles taken by said processing circuits depending on whether said developed syndrome byte is being processed for a random single-bit error or a multi-bit error in said defective byte location.

An error correcting check byte generator for generating a b bit check byte, each bit of which represents the modulo-2 sum of the binary value of the data bits in different bit positions of a data word having M-1 bytes, each of which also consists of b bits, said different bit positions being selected in accordance with a parity check matrix H' which has been developed from a parity check matrix H corresponding to an m-sequence by systematically selecting from said matrix H, M groups of b columns, which groups are spaced .lambda.-b columns apart, where .lambda. is equal to or greater than b and M.lambda. is less than 2.sup.b, said generator comprising:

• a b stage register;
• a separate logic block connected to the input of each said stage;
• means connecting the outputs of selected stages to said inputs of each said logic block;
• means for supplying said data word to said generator serial by byte;
• and
• means for supplying to other inputs of each said logic block data bit signals from each byte during successive cycles, said data bit signals supplied to each said logic block being selected from bit positions of each byte determined by a matrix T.sup..lambda. which is spaced .lambda.-b columns from the identity matrix of said m-sequence, each said logic block functioning to provide the modulo-2 sum of the signals supplied thereto from said data byte and said register stages during each cycle of operation, whereby after M-1 cycles said check byte is positioned in said b stage register.

An ECC circuit for processing a dual function non-zero syndrome byte which has been developed by exclusive-ORing a b bit write check character and a b bit read check character to establish either the location of a single random 1-bit error in a data word comprising M byte positions each having b bit positions or the error pattern of a multi-bit error in one predetermined defective byte location of said data word where each bit of each said check character represents the modulo-2 sum of the binary value of the data bits in different positions of said data word, said different positions being prdetermined in accordance with a parity check matrix H' comprising Mb contiguous columns and b rows, said contiguous columns corresponding to M groups of b columns of a parity check matrix H which represents a maximal length shift sequence of length 2.sup.b -1, the spacing between said successive groups of b contiguous columns in said H matrix being .lambda.-b columns where .lambda. is equal to or greater than b and none of said M groups overlap one another, said circuit comprising:

• a b stage register adapted to receive said syndrome byte;
• a separate logical block connected to the input of each stage of said register, each block having a plurality of inputs which are summed modulo-2 by said block and stored in said register once each cycle;
• means connecting the output of selected stages of said register to said inputs of each said logical block whereby the binary values stored in selected stages of said register at the beginning of said cycle are summed modulo-2 during said cycle and stored in each stage prior to the end of said cycle, the output connections from each said stage to selected logic blocks being predetermined in accordance with a b.times.b matrix T.sup.-.lambda. spaced in said sequence -(.lambda.-b) columns from the identity matrix of said sequence;
• and
• means to cycle said processing circuit through at least M cycles to determine if said syndrome byte represents a correctable single-bit random error.

The method of correcting two separate types of errors in a data word having M-1 data byte positions and one check byte position where each of said positions consists of b bit positions as said word is read from a memory having M failure independent units, each of which is associated with the same byte position of successive data words, said method comprising:

• generating a syndrome byte S by exclusive-ORing a dual function write check character and a dual function read check character, each said dual function character representing the modulo-2 sum of the value of data bits from bit positions of each byte position of a data word which have been selected in accordance with a parity check matrix H' that has been developed from a parity check matrix H corresponding to an m-sequence of length 2.sup.b positions by systematically selecting M groups of b.times.b submatrices which are spaced in said m-sequence .lambda.-b columns aparat, where .lambda. is equal to or greater than b and M.lambda. is less than 2.sup.b ;
• checking M different columns of said matrix H disposed at .lambda. intervals in said m-sequence from the location of said non-zero syndrome in said m-sequence for any 1-bit pattern;
• and
• correcting the 1-bit error in said data word by logically combining said any 1-bit pattern with the data located in a byte position of said data word corresponding to the number of said .lambda. intervals between said positions of said syndrome byte and said any 1-bit pattern in said m-sequence when the number of intervals is M or less, or correcting an error in said data word by logically combining the data byte located at a known defective byte location with a pattern in said m-sequence which is disposed K.lambda. columns from the position of said syndrome byte in said m-sequence where K is a function of the known defective byte location.

The method of correcting two separate types of errors in a data word having M-1 data byte positions and one check character position where each of said positions consists of b bit positions as said word is read from a memory having M failure independent units, each of which is associated with the same byte position of successive data words, said method comprising:

• generating a syndrome byte S by exclusive-ORing a write check character and a read check character;
• cycling each said syndrome byte having a non-zero pattern through a predetermined logical operation for at least M cycles to generate a modified syndrome byte;
• detecting if said modified syndrome byte comprises a pattern having a single 1 bit after each cycle until M modified syndrome bytes have been generated;
• counting the number of cycles said syndrome byte is cycled through said logical operation and correcting the single-bit error in said data word using said detected 1-bit pattern and the number of cycles taken before said 1-bit pattern is detected;
• or alternately, correcting either one or both types of said errors by processing said non-zero syndrome byte through said predetermined logical operation a predetermined number of cycles related to the known defective byte location in said data word to generate the correct error pattern.

In a dual function error correcting system for correcting either a random single-bit error or a multi-bit error in one byte of a data word by processing one b bit syndrome byte developed by exclusive-ORing one b bit write check byte and one b bit read check byte in which each said data word comprises M-1 data byte positions and one check byte position, each byte position comprising b bit positions;

• a method of developing at least one of said check bytes comprising:
• (a) generating b binary bit signals during each cycle of an M cycle process where each group of b binary signals corresponds to one data byte of said data word having M byte positions;
• (b) combining on a corresponding cyclic basis the values in bit positions of a b bit vector with the values in corresponding bit positions of each byte position, said bit positions of said bit vector being predetermined in accordance with a matrix T.sup..lambda., spaced in an m-sequence of length 2.sup.b -1, .lambda.-b columns from the identity matrix of said m-sequence;
• and
• (c) either storing the b bit vector resulting after M-1 cycles as said write check byte or transferring the b bit vector resulting after M-1 cycles to a syndrome generation circuit as said read check byte.

In a dual function error correcting system for correcting either a random single-bit error or a multi-bit error in one byte by processing one b bit syndrome byte developed by exclusive-ORing one b bit write check byte and one b bit read check byte in which each said data word comprises M-1 data byte positions and one check byte position and each byte position comprises b bit positions;

• a method of developing at least one of said check bytes where each bit of said check byte represents the modulo-2 sum of the binary value of the data bits in different bit positions of said data word, which different said bit positions have been selected in a predetermined systematic manner, said method comprising the following steps:
• (a) selecting a b.times.b matrix from a b.times.2.sup.b -1 matrix corresponding to an m-sequence, said selected b.times.b matrix being spaced .lambda.-b matrix columns from the b.times.b identity matrix of said m-sequence, where .lambda. is equal to or greater than b and M.lambda. is less than 2.sup.b ;
• (b) generating a b bit vector where each bit of said vector represents the modulo-2 sum of the binary value of the corresponding bits in the columns of a b.times.b matrix which correspond to each said bit position of the 0th byte of said data word which contains a binary 1;
• and
• (c) generating M-1 successive b bit vectors where each bit of each said successive M-1 b bit vector represents the modulo-2 sum of the value of the corresponding bits in columns of said selected matrix which columns are selected by exclusive-ORing the last generated b bit vector with the next data byte until M-1 bytes of data have been sequentially processed, whereby said b bit vector resulting after processing said M-1 bytes of data corresponds to said check character.