Error Detection System

This invention relates to an error detection apparatus and more particularly to an error detection apparatus suitable for detecting block errors. A block error is an error in at least three of the bits in a set of bits. The invention is particularly applicable to detecting and correcting single bit errors, detecting double bit errors in a data word, detecting single block errors in a data word, and detecting a three or more bit burst error in a block or in a (b-1) bit block where b is the number of bits in a data block. The (b-1) bit block is contained in a data block or may extend across the boundary of two data blocks in the data word.

The following systems (1) and (2) are known conventionally as an error correction/detection system using SEC-DED-SbED codes (Single bit Error Correcting-Double Bit Error Detecting--Single b bit byte Error Detecting Codes):

(1) A system using the codes described on pages 593-598 of the journal of Electrocommunication Society, May, 1984, Japan.

(2) A system using the codes described on page 129 of IBM J.R&D, Vol. 28, No. 2, March, 1984.

The SEC-DED-SbED code is the code obtained by adding the detection capacity of the mass of a plurality (b) of bits such as a byte to a 1-bit error correction/2-bit error detection code (SEC-DED code) that is widely used for a main memory unit. This code is helpful in improving the reliability of a semiconductor memory devices using a memory element having data output of a plurality of bits. In the new SEC-DED-SbED codes described in the item (a), the maximum code bit length L.sub.0 is given by

where r is the number of inspection bits (r.gtoreq.b+2) and b is a byte length.

When the byte length b.ltoreq.16 bits, it has a code length longer than the conventional codes. When the number of inspection bits r=b+2, it provides a circulating minimum weight code suitable for improving the operation and packaging density of LSI for the coding/decoding circuit. In the meantime, it may be required to detect block errors for block division of two or more kinds of blocks. When, for example, an IC memory of a 4-bit structure is driven by a driver IC of a 3-bit structure, it is desired to detect the block error for the 4-bit block and at the same time, to detect also the block error for the 3-bit block. In this case, if the SEC-DED-SbED code is constituted according to the prior art technique described above, the 4-bit block error can be detected but the 3-bit block error spreading over the 4-bit blocks cannot be detected generally.

A purpose of the present invention is to provide an error correction/detection system which solves the problem of the prior art technique as described above, detects a b-bit block error and at the same time, a block error of up to (b-1)-bit block and can further detect an error inside arbitrary continuous (b-1)-bits [(b-1)-bit burst error] by use of the SEC-DED-SbED code.

In accordance with the invention, an error detection apparatus comprises means for generating information which has a plurality of bits; means for obtaining syndrome on the basis of the information and a parity matrix containing at least one of the following b*b partial parity matrices Ao to Ab and means responsive to the obtained syndrome for detecting error of the information:

where Ai (i=0.about.b) is a b*b matrix with Ai=B.multidot.C.sup.i, and C.sup.i (i=0.about.b) is a b.times.b matrix multiplied i times by C, that is ##EQU3## B is a b.times.b matrix obtained by arbitrarily replacing the rows and columns of C.sup.i.

By this means, the apparatus will effect 3-or-more-bit error detection inside the same block/burst of more than 3 arbitrary bits but below (b-1) bits. The alternative form of the partial parity matrices Ai(0=i to b) is obtained by circulatingly replacing by i bits each row of Ao, where ##EQU4## Ab is defined by I which is a b.times.b unit matrix.

Both forms of the parity matrix P comprises a b.times.b matrix, which has row vector D.sub.0 and b-1 different row vectors selected from b row vectors D.sub.1 to D.sub.b wherein D.sub.0 . . . D.sub.b are defined as follows: ##EQU5##

According to the invention, it can be detected whether even number bit error or odd number bit error occurs because of row vector D.sub.o. If the even number bit error occurs, syndrome for the row vector D.sub.o is "0". If the odd number bit error occurs, syndrome for the D.sub.o is "1".

According to the invention, it can be detected whether 1-bit error or 3-or-more error occurs because of b-1 different row vectors selected from b row vectors D.sub.1 to D.sub.b. If a 1-bit error occurs, the syndrome of these vectors is "1". If a 3-or-more bit error occurs, the syndrome is "3" or more.

The weight of the syndrome is 1 or 2 if a 1-or-2-bit error occurs. If a 3-or-more bit error occurs, the weight of the syndrome is 3 or more.

Thus, this invention distinguishes 3-or-more bit error from 1-or-2-bit errors.

The invention may take form in certain parts and arrangements of parts which will be described in detail in this specification and illustrated in the accompanying drawings which form a part thereof and wherein:

FIG. 1 is a diagram of the parity matrix used by the error correction/detection system of the present invention;

FIG. 2A is a diagram of a parity matrix used in one embodiment of the present invention;

FIG. 2B is a diagram of a check bit generation matrix;

FIG. 3 is an overall configurational view of an error correction/detection apparatus in one embodiment of the present invention;

FIG. 4 is a detailed configurational view of the check bit generator shown in FIG. 3;

FIG. 5 is a detailed configurational view of the syndrome generator shown in FIG. 3;

FIG. 6 is a detailed configurational view of the syndrome/correction circuit shown in FIG. 3;

FIG. 7 is a diagram of the parity matrix used by the error correction/detection system of another embodiment;

FIG. 8A is a diagram of a parity matrix used in the other embodiment;

FIG. 8B is a diagram of a check bit generation matrix of the other embodiment;

FIG. 9 is a detailed configurational view of the check bit generator shown in FIG. 3 embodying FIGURE 8(b); and,

FIG. 10 is a detailed configurational view of the syndrome generator shown in FIG. 3 embodying FIG. 8(A).

The reason this invention can detect a b-bit block error and a (b-1)-bit burst error is the embodiment of decoding information consisting of a plurality of blocks made up of a plurality of (b) bits in a parity matrix. The parity matrix P=[A.sub.0. . . A.sub.0 A.sub.1. . . A.sub.1. . . A.sub.b. . . A.sub.b ] and will be described in detail below.

First, the properties of the matrix Ai and P will be explained.

The matrix C.sup.i (i=0.about.b) is as follows: ##EQU6## The matrix B is a b.times.b matrix obtained by arbitrarily replacing the rows and columns of C.sup.i (i=0.about.b). The matrix B is composed by selecting b different row vectors from among the following (b+1) row vectors D.sub.0 to D.sub.b : ##EQU7##

When the kth row of the matrix B is the row vector D.sub.j (j=0.about.b), the kth row of the matrix P becomes as follows by calculating the product between the vector D.sub.j and the matrix C.degree..about.C.sup.b :

When j=0; D.sub.0. . . D.sub.0 D.sub.b. . . D.sub.b. . . D.sub.1 ...D.sub.1

When j=1; D.sub.1. . . D.sub.1 D.sub.0. . . D.sub.0. . . D.sub.2. . . D.sub.2. . .

when j=b: D.sub.b. . . D.sub.b D.sub.b-1. . . D.sub.b-1. . . D.sub.0. . . D.sub.0

The following can be derived from above.

(Property i)

The matrix Ai is composed of b different row vectors among the row vectors D.sub.0 to D.sub.b.

(Property ii)

The b.times.2b matrix [AiAi+l] as part of the matrix P is composed by selecting b different row vectors from among the following (b+1) row vectors E.sub.0 to E.sub.b : ##EQU8##

A parity matrix containing the matrix P as derived above is used by the apparatus for decoding information on the basis of the properties described above, a b-bit block error and a (b-1)-bit burst error can be detected. Since an arbitrary 2-bit error can be detected by the SEC-DED code, a 3-or-more-bit error inside a b-bit block and a 3-or-more-bit but less than (b-1)-bit burst error can be detected by combining the two methods. This is accomplished by calculating the weight of the b-bit syndrome, Sp, which is defined by the matrix P. The weight of the b-bit syndrome is defined as follows:

When a 1-bit error occurs, the weight is the number of "1"s in the column corresponding to the bit where the error occurred.

When the 2-bit error occurs, the weight is the number of "1"s in the modulo-2-sum of the two columns which correspond to the two bits where the errors occurred.

When a 3-bit error occurs, the weight is the number of "1"s in the modulo-2 sum of the three columns which correspond to the three bits where the errors occurred.

When 4 and more bits error occurred, the weight is obtained the same manner as explained above.

From the property (i), the weight of each column of the matrix A1 is 1 or 2; therefore, the weight of Sp for a 1-bit error is 1 or 2.

(1) The weight of Sp for the 3-or-more-bit inside a block is at least 3. For, from the property (i) of the matrix Ai which defines the bits within a block:

(a) The weight of Sp is equal to the error bit number and at least 3 when Ai does not contain D.sub.0 ;

(b) The weight of the syndrome corresponding to the (b-1)th row of Ai exclusive of D.sub.0 is at least 3 for 4-or-more-bit errors;

(c) When Ai contains D.sub.0, the weight of the syndrome for the (b-1) row of Ai exclusive of D.sub.0 is 2 or 3 for a 3-or-more-bit error and the syndrome for the D.sub.0 th row is "1"; therefore, the weight of Sp is at least 3.

(2) The weight of Sp for the up-to-b bit but 3-or-more bit burst error spreading over two blocks having the same matrix Ai is at least 3. This is true since the column vectors constituting the matrix that corresponds to the b-bit burst error is equivalent to the column vectors constituting the matrix Ai. Thus, the same discussion in the item (1) holds true for this case.

(3) The weight of Sp for the up-to-(b-1)-bit but 3-or-more-bit burst error spreading over two blocks having two different matrices Ai and Ai+1 is at least 3. This occurs because the matrix X.sub.ij corresponding to the (b-1)-bit burst is composed of b different row vectors among the following (b+1) row vectors, F.sub.0 .about.F.sub.b, from the property (ii): ##EQU9## (a) When X.sub.ij does not contain F.sub.0 or F.sub.1 the weight of the syndrome of the matrix X.sub.ij corresponding to the (b-1)th row other than F.sub.0 and F.sub.1 is at least 3;

(b) When X.sub.ij contains F.sub.0 and F.sub.1, the weight of the syndrome of the matrix X.sub.ij corresponding to the (b-2)th row other than F.sub.0 and F.sub.1 is at least 3 for the 4-or-more-bit errors;

(c) When X.sub.ij contains F.sub.0 and F.sub.1, the weight of the syndrome of the matrix X.sub.ij corresponding to the (b-2)th row other than F.sub.0 and F.sub.1 is 2 or 3 for the 3-bit errors and either one of the syndromes corresponding to the F.sub.0 th or F.sub.1 th row is "1"; therefore, the weight of Sp is at least 3.

From the items (1), (2), and (3) described above, the weight of Sp for the 3-or-more-bit error inside the block and the up-to-(b-1)-bit but 3-or-more-bit burst error is at least 3, and they can be detected without being mistaken as the 1-bit errors having the weight of 1 or 2.

FIG. 1 is a diagram showing one structural example of the parity matrix used in the present invention. Here, a code length can be secured to maximum 60 bits for b=5 and check bits of 8 bits. The parity matrix shown in FIG. 1 consists of the partial matrices Ai (upper five rows) and the lower three rows for odd number weighting which are used for extending the code length and for adding the SEC-DED function. If the parity matrix shown in FIG. 1 is used, the weight of the syndrome determined by the upper five rows becomes 1 or 2 for a 1-bit error but becomes 3 or more for a 3-or-more-bit error inside the 5-bit block and inside an arbitrary 4-bit burst.

For example, when 1-bit error occurs in first data bit, a syndrome is obtained as (01010) of first column and the weight of the syndrome becomes "2". When 3-bit error occurs in first, second, and fourth data bits (thus, a 3-or-more-bit error has occurred inside the 5-bit block), a syndrome is calculated as:

01010+00011+00110=01111 (modulo-2) and the weight of the syndrome becomes "4". When 3-bit error occurs in fourth, fifth, and seventh data bit (this means a 3-or-more-bit error occurred inside an arbitrary 4-bit burst), a syndrome is obtained as:

00110+10010+00011=10111 (modulo-2), and the weight of the syndrome becomes "4". The weight for the 3-or-more-bit error inside the 5-bit block and inside an arbitrary 4-bit burst is at least 3, and they can be detected without being mistaken as the 1-bit errors.

Hereinafter, it will be assumed that this embodiment deals with the case where reads and writes are made to a memory unit with 3-byte (24-bit) data and 8 check bits. The memory unit is comprised of 8 IC memories with a 4-bit structure and 6 driver/receivers of a 6-bit structure. The check bits necessary for adding the SEC-DED function to the 24-bit data may be 6 bits, but the check bits are increased to 8 bits because the 4-bit IC memory structure is used. However, the number of IC memories is not increased.

FIG. 2A shows a parity matrix applied to one embodiment of the present invention and FIG. 2B shows a check bit generation matrix.

The parity matrix shown in FIG. 2A is obtained by reducing the parity matrix for a code length of 42 bits to 32 bits for b=6 and check bits of 8 bits.

Numeral 11 denotes data bit positions, numeral 12 denotes check bit positions, numeral 13 denotes syndrome and numeral 14 denotes computed check bits. When a 1-bit error occurs in data bit position d.sub.0, the syndrome (S.sub.0, S1, . . . S7) is obtained as (00110010) which is the first column of the parity matrix. When the parity matrix shown in FIG. 2A is employed, 3-or-more-bit errors in the 6-bit block and in an arbitrary 5-bit burst can be detected in addition to 1-bit error correction/2-bit error detection. Therefore, even if one IC memory (having a 4-bit structure) or one driver/receiver (having a 6-bit structure) is out of order, the trouble can be detected without error correction.

The matrix shown in FIG. 2B illustrates a check bit generation matrix. The matrix is used for obtaining the check bits (C0, C1 . . . C7). For example, to obtain C.sub.0, data bits corresponding to first row positions having the value "1" are selected. In this case, d0, d1, d2, d5, d6, d7, d10, d11, d12, d15, d16, d17 d20, d21, d22, and d23 are selected. The check bit C is the modulo-2 sum of these data bits.

FIG. 3 is an overall configurational view of an error correction/detection system showing one embodiment of the present invention.

When data is written into a memory unit 3, the write data 10 (SD.sub.0 .about.23) written from the processor 1 is applied to a check bit generator 2. The check bit generator 2 generates the check bits 20 (CO.about.7) on the basis of the matrix shown in FIG. 2B. The detailed description of the check bit generator 2 is explained by using FIG. 4 later on. The check bits 20 thus generated are written into the memory unit 3 together with the write data 10. The memory unit 3 is comprised of 4-bit IC memories and 6 drive/receivers as described above.

When the data is read out of the memory unit 3, the read data 30 (FDO.about.23) and the read check bits 31 (FCO.about.7) are applied to a syndrome generator 4. The syndrome generator 4 generates the syndrome 40 (SO.about.7) on the basis of the parity matrix shown in FIG. 2A and supplies it to a syndrome decoder 5. The detail of the syndrome generator 5 is explained by using FIG. 5. The syndrome decoder 5 decodes the syndrome 40 on the basis of the parity matrix shown in FIG. 2A, generates and supplies a 1-bit error correction signal 50 to a correction circuit 6 and reports a correctable error (CE) and an uncorrectable error signal (UCE) to the processor 1 through a signal line 51. The correction circuit 6 corrects the read data 30 on the basis of the 1-bit error correction signal 50 and supplies the corrected data 60 to the processor 1.

FIG. 4 shows one configurational example of the check bit generator 2 shown in FIG. 3.

The check bit generator 2 consists of eight 9.about.18-input exclusive-or gates 21.about.28. Each exclusive-or gate generates the 1-bit check bit on the basis of the matrix shown in FIG. 2B. The exclusive-or gate 21, for example, generates the check bit Co by computing the modulo-2 sum of the write data bits SD0.about.2, SD5.about.7, SD10.about.12, SD15.about.17, and SD20.about.23 on the basis of the first row of the matrix shown in FIG. 2B. If the number of write data bits whose value are "1" is an odd-number, the result of the addition is "1".

FIG. 5 shows one configurational example of the syndrome generator 4 shown in FIG. 3.

The syndrome generator 4 consists of eight 6.about.19-input exclusive-or gate gates 41.about.48. Each exclusive-or gate generates the 1-bit syndrome on the basis of the parity matrix shown in FIG. 2A. The exclusive-or gate 41, for example, generates the syndrome S0 by adding the modulo-2 of the read data FD4, FD9, FD14, FD19, and the read check bits FC0, FC6, FC7 on the basis of the first row of the parity matrix shown in FIG. 2A.

FIG. 6 shows on configurational example of the syndrome decoder 5 and the correction circuit 6 shown in FIG. 3.

The syndrome decoder 5 consists of a decoder 52, or gates 53, 54, a NOT gate 55 and an AND gate 56, and the correction circuit 6 consists of twenty-four 2-input exclusive-or gates 61 corresponding to the read data FD0 to FD23. The decoder 52 detects a syndrome pattern corresponding to each column of the parity matrix shown in FIG. 2A and generates thirty-two 1-bit error correction signals. When, for example, the syndrome (So.about.S7) is "00110010" (50 in decimal notation) corresponding to the D0 column of the parity matrix, it excites the 1-bit error correction signal T50 of the read data FD0.

T50, T42, . . . T13 corresponding to the d0, d1, d23 columns of the parity matrix are inputted to exclusive-or gates 61, which output the corrected data FD0'.about.FD23'. All the 1-bit error correction signals which include T128, T4, . . . T161 corresponding to the C0 . . . C7 columns of the parity matrix are inputted to the exclusive-or gate 54 and a correctable error report signal CE is generated. An uncorrectable error report signal UCE is excited when at least 1-bit syndrome is "1" and is not a correctable error (CE).

As described above, this embodiment can detect the 3-or-more-bit errors inside the 6-bit block and inside the 5-bit burst so that the trouble of both the IC bit having the 4-bit structure and the driver having the 6-bit structure can be detected and reliability can be improved. In addition, the embodiment described above can realize the above mentioned detection capacity without increasing the number of IC memories.

Another embodiment is described below. In this embodiment, the parity matrix P is defined as follows:

circulatingly replaced by i bits each row of ##EQU10##

The principle whereby a bit block error and a (b-1)-bit burst error can be detected will be explained in detail.

In the present invention, the weight of a syndrome S.sub.p of b-bits defined by a partial matrix P is 1 or 2 for the 1-bit error. On the other hand, all the 3-or-more-bit errors inside the b-bit block and inside the (b-1)-bit burst can be detected for the following reasons:

(a) The weight of S.sub.p for the error of 3-or-more-bit inside the b-bit block is at least 3 based on the structure of Ai and I.

(b) The weight of S.sub.p for the error of 3-or-more bits but below (b-1) bits spreading over two b-bit blocks having the same partial matrix Ai or I is at least 3 according to the item (a).

(c) When its rows and columns are replaced, a bx(b-1) partial matrix A' for the (b-1)-bit burst spreading over two b-bit blocks having different partial matrices Ai and Ai+1 become: ##EQU11##

The weight of S.sub.p for the 3-or-more bit error inside this burst is at least 3.

(d) When its rows and columns are replaced, the bx(b-1) partial matrix A" for the (b-1)-bit burst spreading over two b-bit blocks having different partial matrices Ab.sub.-1 and I become: ##EQU12##

The weight of S.sub.p for the 3-or-more-bit error in this burst is at least 3.

From the items (a) to (d) described above, the 3-or-more-bit errors inside the b-bit block and the (b-1)-bit burst can all be detected.

Hereinafter, one embodiment of the present invention will be described in detail with reference to the drawings.

FIG. 7 is a diagram showing one structural example of another parity matrix. Here, a code length can be secured up to maximum 60 bits for b=5 and check bits of 8 bits.

The parity matrix shown in FIG. 7 consists of partial matrix P (upper five rows) and lower three rows for odd numbered weighting that are for extending the code length and for adding SEC-DED function. In the code language shown in FIG. 7, each of the syndromes S0, Si, . . . S7 is a value which is the result of calculating the exclusive-or of the corresponding row code d1 (i=0, 1, . . . 51) and the corresponding check bit row Ci (i=0, . . . 7). All of them become 0 when no error exists in the information code. If there is the error, on the other hand, the weight of Si of the row containing such an error becomes always 1 in the case of the 1-bit error and the weight of Si of the row containing the error becomes 0 but not 1 in the case of the 2-bit error. Therefore, 1-bit error correction/2-bit error detection is possible. In other words, if there is the 1-bit error, the bit number which becomes 1 is odd numbered among the syndromes S0.about.S7 and if there is the 2-bit error, the bit number which becomes 1 is even numbered among the syndromes S0.about.S7. In addition, if the parity matrix shown in FIG. 7 is used, the weight of the syndrome determined by the upper five rows is 1 or 2 for the 1-bit error but is at least 3 for the 3-or-more-bit error inside the 5-bit block and inside an arbitrary 4-bit burst in this embodiment. Thus, this embodiment can detect such errors.

FIG. 8A shows a parity matrix applied to another embodiment of the present invention and FIG. 8B shows a check bit generation matrix.

In the embodiment, it will be assumed that read and write is made to the same memory unit as the embodiment of FIG. 3. The check bit necessary for adding the SEC-DED function to the 24-bit data may be 6 bits, but the check bit is increased to 8 bits because the IC memory structure is of 4-bits used. However, the number of IC memories is not increased.

The parity matrix shown in FIG. 8A is obtained by reducing the parity matrix for a code length of 42 bits to 32 bits. When the parity matrix shown in FIG. 8A is employed, 3-or-more-bit errors in the 6-bit block and in an arbitrary 5-bit burst can be detected in addition to 1-bit error correction/2-bit error detection. Therefore, even if one IC memory (having a 4-bit structure) or one driver/receiver (having a 6-bit structure) is out of order, the trouble can be detected without error correction.

The matrix shown in FIG. 8B illustrates a check bit generation matrix which is obtained by applying a known equivalent row operation to the parity matrix shown in FIG. 8A so that the check bit portion (C0 to C7) becomes a unit matrix.

The matrix shown in FIG. 8B is used for obtaining the check bit portion (Co to C7) in the check bit generator of FIG. 3, and the matrix shown in FIG. 8A used for the syndrome (S0 to S7) in the syndrome decoder of FIG. 3.

FIG. 9 shows one configurational example of the check bit generator of the embodiment. The check bit generator consists of eight 9.about.17-input exclusive-or gates 21.about.28. Each exclusive-or gate generates the 1-bit check bit on the basis of the matrix shown in FIG. 8B. The exclusive-or gate 21, for example, generates the check bit C0 by adding modulo-2 of the write data SD0.about.SD9, SD12.about.SD14, SD18 and SD19 on the basis of the first row of the matrix shown in FIG. 8B.

FIG. 10 shows one structural example of the syndrome generator of the embodiment.

The syndrome generator consists of eight 7.about.21-input exclusive-or gates 41.about.48. Each exclusive-or gate generates the 1-bit syndrome on the basis of the parity matrix shown in FIG. 8A. The exclusive-or gate 41, for example, generates the syndrome by adding the modulo-2 of the read data FD0.about.FD5, FD11, FD16, FD21, and the read check bits FC2, FC7 on the basis of the first row of the parity matrix shown in FIG. 2A.

The syndrome decoder and the correction circuit has the same construction as the embodiments in FIG. 6.

As described above, the present invention can detect the (b-1)-bit burst error in addition to 1-bit error correction/2-bit error detection/b-bit block error detection. Therefore, the present invention can accomplish error correction and detection with a high degree of differentiation in the types of errors detected.

The invention has been described with reference to the preferred embodiments. Obviously, modifications and alterations will occur to others upon reading and understanding the preceding specification. It is intended that the invention be construed as including all such alterations and modifications insofar as they come within the scope of the appended claims or the equivalents thereof.