JPS6041771B2 - double error correction circuit - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a dual error correction circuit, and more particularly to a dual random error correction circuit for parallel data.

Conventionally, single error correction and double error detection Hamming codes have been mainly used in memories of data processing devices in order to improve reliability.

This encoding system stores a specified number of data bits with a minimum number of check bits in memory, corrects single errors that occur when reading from memory, and also detects double errors. The features of the encoding system are that the number of check bits added is small and that the errors can be corrected and detected in parallel using a simple circuit. However, it is desirable to employ a dual random error correction system to further improve memory reliability. This double random error can also be corrected by, for example, the well-known double error correction ■... code, ie, the Bose-Chaudhuri code. However, when this BCH code is adopted, double errors can be corrected using a relatively simple circuit, which has the disadvantage of requiring a fairly large and complex logic circuit to correct double errors in parallel. The code includes a double error correcting code capable of majority voting. Using this code double random errors can be corrected in parallel by majority logic. The orthogonal Latin square code described in Patent Publication No. 4, 2013 is a good example of the double error correcting code capable of majority logic. In the orthogonal Latin square code, double random errors are corrected by adding 4m check bits to i data bits, where m is an arbitrary integer greater than 1. Although the error correction system using this code has the advantage that double errors can be corrected in parallel using a simple majority logic circuit, it adds 4m multiple check bits to one data bit. It also has the disadvantage of being necessary. Therefore, it is desired to realize an error correction system using a double error correction code capable of majority logic, which has less redundancy than the orthogonal Latin square code [here, redundancy is redundancy (number of check bits)] /(number of check bits + number of data bits), and the redundancy of the Latin square code is 4m/(d+4m)=4/(m+
4)]. However, until now there has been no dual error correction system as described above. SUMMARY OF THE INVENTION An object of the present invention is to provide a new double error correction circuit using a majority decodable double error correction code that has less redundancy than conventional majority decodable double error correction codes.

The double error correction circuit of the present invention includes an encoding circuit that adds 5+1 check bits to d+(m-1) data bits, where m is an arbitrary odd number of 3 or more; One or two random errors occurring in the data bits and check bits are corrected by connecting a circuit that generates syndrome bits from check bits and the output of this syndrome bit generation circuit using majority logic. and a decoding circuit having a majority voting circuit.

The present invention will be described in detail below with reference to the drawings.

FIG. 1 is a block diagram 5 showing the relationship between the memory in the data processing device and the error correction circuit of the present invention. In FIG. 1, an encoding circuit 1 generates check bits from data generated in an arithmetic circuit 4. This data is stored in memory 2 along with check bits. When needed later, this data is read out from the memory 2 together with the check bit, and after its errors are corrected by the decoding circuit 3, it is again supplied to the arithmetic circuit 4. Below, the configuration of the majority-decodable double error correction code used in the present invention and the configurations of the encoding circuit 1 and decoding circuit 3 of the code will be explained using an example.

First, the above codes and circuit configuration will be explained using the case where m=5 as an example. In this case, since m=5, 16 (=5+1) check bits are added to 31 [=d+艮(m-1)] data bits, and the double error correction code used in the present invention is can get.

Below, the 31 data bits are Dl, d2, d3.
, . . , D3O, d3l, and the 16 check bits are C. O, ClO9Cll9Cl29Cl39
Cl49C2O9C2l93O9C249C3O,C3
It is expressed as l,...,C3,. Here, D and CIJ are 1
or O. The encoding circuit 1 according to the present invention generates check bits from data bits in accordance with the following relational expressions (1), (2), (3), and (4). (Here, in all formulas that follow, the symbol 1 indicates exclusive 0R, and Σ4 indicates the summation regarding exclusive 0R.)
The above relational expressions (1), (2), which generate check bits,
If (3) and (4) are expressed by an encoding matrix j giving their coefficients, the equation is given in FIG.

However, the empty matrix element in the 211F5 is 0. Using the matrix ratios in Figure 2, the above relational expressions (1) and (2) can be obtained.
, (3), and (4) are expressed by multiplying a vector and a matrix as shown in the following equation. As already mentioned, the encoding circuit 1 in FIG.
is the formula (1), (2), (3) and (4), or the formula (
5), a check bit is generated from the data bit.

For example, the check bit ClO is generated by taking the exclusive bit ρR of the data bits Dl, d2, d3, d4, d5, and D26 as shown in equation (2), but this is generated using six This is easily realized by an exclusive 0R circuit 5 having an input. Other 14 check bits Cll
9Cl29Cl3? Cl49C2O9C2l9l9C2
The circuit that generates 49C'309C31, . Check bit C again. O is the exclusive 0R of all data bits Dl, d2, d3,..., D3O, d3l according to equation (1).
If we focus on equations (1) and (2) generated by taking
. O is also expressed by the following equation (6). Therefore, the formula (6
) according to check bit C.

O is the check bit ClO generated in the circuit of FIG.
It is generated by taking the exclusive OR of Cll, Cl2, Cl3 and Cl4. In other words, COO receives five inputs as shown in Figure 4. is generated by an exclusive 0R circuit 6 having an exclusive 0R circuit 6.

One check bit CO generated as above
O9Cll9Cl29Cl39Cl49C2O9l9C
249C knowledge..., C34 is 31 data bits Dl,
It is written to the memory together with d2,...,D3l. These check bits and data bits are read from memory as necessary. In the following, check bits and data bits read from memory will be represented with dashes. In other words, the read check bits are C″00C″10C″11, C12
,σ139C5149C'20919C'249σ30
▼Represented as 09C'34, data bits are d″1, d″
2, . Figure 5 is a block diagram of the decoder.

As shown in FIG. 5, the decoder 40 is composed of a syndrome bit generation circuit 20 and an error correction execution circuit 21. The 31 data bits and one check bit read from the memory 2 are first input to the syndrome bit generation circuit 20 and converted into one syndrome bit. This syndrome bit contains information necessary to correct an error, and the error correction execution circuit 21 decodes this information and executes error correction. In the following, the syndrome bit generation circuit 20 will be explained first. The syndrome bit generation circuit 20 has one check bit COO9ClO9Cll9Cl29Cl39Cl.
1 hat syndrome bit SOO9SlO9Sl corresponding to 49C2O9゜O9C249C3O9゜゜9C34
l9Sl29Sl39Sl49S2O9l9S249S
The syndrome bit SlO corresponding to O, for example ClO, which generates S34 is generated as follows. Cl
The formula for generating O is ClO=Dl4d2ld from equation (2).
34d44d54d8, which can be rewritten as the following equation. The syndrome bit SlO is the right side Dl of the above equation.
, d2, d3, d4, d5, dら, symbols d''1, d゛2, d''3, d''4, when ClO are read respectively.
Obtained by replacing d″5, d″ら, c″10.

That is, SlO is generated by the following equation. SlO=
d″14d″24d″31d″44d″54d″261
Similarly to C″10, check bit generation formula (1), (
From 2), (3), and (4), the following syndrome bit generation formulas (8), (9, [shares], (11)) are obtained.

That is, one - - -
--- "The above equations (8), (9), Al, and (11) can be expressed by matrix and vector operations as shown in the following equation by using the encoded matrix block shown in Figure 2. Syndrome bit generation The circuit 20 converts the syndrome bit of the first cap into the above (
8), (9), [Phase], This is a circuit that generates according to equations (11).

For example, the generation of the syndrome bit SlO is performed using the formula (9), as shown in FIG.
It can be carried out by Other syndrome bits are generated in the same manner. As mentioned above, the error correction execution circuit 21 in FIG. 5 decodes the syndrome bits generated by the syndrome bit generation circuit 20 to correct errors, so the syndrome bits contain information necessary for error correction. Must have. Equation (8), (
9), (10, (11)) It can be seen as follows that the syndrome bits generated by It should be noted that, assuming E, the data bit d1 read from the memory is expressed by the following equation (12).That is, if D, is incorrect, the error E, is E,= 1, and if correct, the prisoner = O.Similarly, the error that occurred in the check bit C, , is EiJ
Then, check bit Ci read from memory
j is expressed by the following equation (13). If you enter (7)
Since the formula holds true, it can be seen that SlO is expressed by the following formula (14).

This is SlO in equation (9), that is, SlO=d″14d
d″1, d″2, d″3, d″4, d″5 represented in ″24d″31d″41d″5, d″〉4C″10
, d″26, C″10 are wrong El9e29e3
Equivalent to replacing 9e49e59e269ElO.

Similarly, all d'' and C'' appearing in the syndrome bits of equations (8), (9), ACjj, and (11) are errors Ei, . Eventually all the syndrome bits are erroneous Ei, .
It is written only with Ejk. As mentioned above, all syndrome bits are error Ei. ．． Since it is expressed by Ejk, the error correction circuit first finds the error Ei from the necessary syndrome bits, and then substitutes the above found E into the equation D,=d″61ej, which is a rewrite of equation (12). Then, the error can be corrected and the original D can be obtained.

The error correction method and the error correction execution circuit 21 will be explained below.

First, a method and circuit for correcting an error occurring in data bit d1 will be described.

The syndrome bits containing d″1 in equations (8), (9), 00, and (11) are S.O, SlO, S9, and S.
It is 34. In other words, these are equations (8), (9), (1
This is from Cji, (11). 1”- 1- ””- 1”1 Linear sum including S(X) A=S
OOlSl. lSl, lS2. When 1S311S33 is created, this linear sum is expressed as equations (8), (9), Aa, (11
) is better.

As mentioned above, d″,,C appearing in the syndrome bit
'',, are replaced with the errors Ei...Eij, respectively, so the above A, SlO, S2O, and S34 are expressed as the following equation (15)
, (16), (17), and (18). That is, if we pay attention to the above equations (15), (16), (17), and (18), the error e1 is SlO, S2O, Sl34, A
is included in any formula, and also includes SlO, S2O, S
It can be seen that 34,A does not include any common error bits other than e1.

This fact shows that for any error of less than or equal to 2, e1 is S
This means that it can be correctly determined by majority logic that takes three out of four, lO, S2O, and S34. That is, the error e1 is determined by the following equation (19). Furthermore, the above-mentioned equation (12), that is, d″,=Djlei becomes D,=
If we pay attention to the fact that it is rewritten as d″, 4e, then d″1
The error is corrected by the following equation (20). In other words, d1 is determined by equation (20). (20)? A circuit for performing error correction is implemented, for example, as shown in FIG. In FIG. 7, the circuits 60, 61, 62, and 65 are exclusive OR gates with two inputs, the circuit 63 is an exclusive OR gate with four inputs, and the circuit 64 is an exclusive OR gate with four inputs. is a majority circuit with four inputs. The majority circuit 64 selects 3 out of 4 inputs.
It is already known that the output becomes a logic 1 only when two or more inputs become a logic 1 at the same time, and can be easily realized by, for example, an AND gate or an 0R gate. Generally, errors in data bits D, (where 1≦j≦25) are corrected as follows.

Formula (8). As can be seen from (9), Gα, and (11), syndrome bits containing data bits d″j (1≦j≦25) are generally expressed in the form S.O, Sla, S2b, S3. Data bit d'', (1≦j≦25)
Syndrome bit S including.

O, Sla, S2b, S. 3c, the error in d″j is corrected by the following formula: Ej = majority vote (Sla, S2
b, S3cA) However, A=S(X)11,S1 [a+sha]
)1-飄1S2] However, in formula (21), the symbol ( ) means [X]=XmOdLllO5, that is, [x] means the remainder when X is divided by 5.

It has already been explained using equations (15), (16), . . . , (20) that equation (21) correctly corrects errors when j=1.

In the following, we will show that equation (21) correctly corrects errors even when j=18. Since j=18, the syndrome bit containing d″18 is expressed by equations (8), (9), QO,
From (11), S. O, Sl3, S22 and S3l. According to equation (21), El8 can be determined by the following equation. However, A=SCX) 1S101S121S241S21
1S311S33 Sl3, S22, S3 of the above formula (22)
4, A is expressed by the following formula from formulas (8), (9), [shares], and (11) (however, d''4 and Cd''Ij are replaced with errors Ej and Eij, respectively).

As can be seen from equation (23) of VVVVlVVA, V&JXVVAV, Sl3, S22, S34, and A all contain El8, and do not contain any common errors other than El8.

Therefore, El8 is equal to Sl3 for any error of less than or equal to 2.
, S22, S34 and A by majority vote. Therefore, the previous equation (21) becomes j=18, that is, d″1
It was shown that 8 errors can be correctly corrected.

In general, the error of d″,, (1≦j=≦25) is also caused by the previous equation (21
), but the explanation will be omitted.

The error correction execution circuit for d''j (1≦j≦25) according to the above equation (21) is constructed in the same manner as the error correction circuit for Jd''1 in FIG. 7, which has already been explained, so the explanation thereof will be omitted. Above, we have explained the method and circuit for correcting the error of d″j (1≦j≦25). Below, we will explain the method and circuit for correcting the error of d″, (26≦j≦
Let us show a method and circuit for correcting the error in 31). First, a method and circuit for correcting the error in d''26 will be explained.

As can be seen from equations (8), (9), Ql, and (11), d′
Syndrome bits containing 26 are SOO9SlO9Sl
It is l9Sl2. Linear sum B = SOO4S including SOO
If 2OlS2llS224S23lS244Sl3 is created, from equations (8), (9), Ql, (11), SlO,
As can be seen from the previous equation (24), Sll, Sl2, B is expressed by the following equation by the errors Ei and Eij, SlO, S
ll, Sl2, B all contain E26, and E26
Contains no other common errors.

Therefore E26 is SlO for any error of less than 2
, Sll, Sl2, and B by taking a majority vote. That is, the error in d''9 can be corrected using the following equation. A circuit for correcting the error in d''26 in accordance with equation (25) is implemented, for example, as shown in FIG.

In FIG. 8, circuits 70, 71, and 72 are exclusive 0R circuits, and circuit 73 is a majority circuit having four inputs as described above. Data bit d'', (26≦j≦31)
Syndrome bits including
0) and (11), generally S. O, sabl
Sa(b+1), Sa(5+., etc.) Generally, the syndrome bits including data bit d''j (26≦j≦31) are expressed as SOO9Sab)Sa(b+1)~Sa
It is shown that the error of (b+2) and 1pad'' is corrected by the following equation (26), but the explanation is omitted.-
JV7J' However, in the previous formula (26), the symbol ku1+1〉 is ku1+1
〉=2, 〉2+1〉=3 and 〉3+1〉=1.

Also, the symbol [ ] indicates [X]=XmOdL]105.

For example, to correct the error in d″31 in 4 lines, the formula (8
), (9), AO, and (11), the syndrome bit containing d''31 is SOO9S329S339S34, so from equation (26), the error in d''31 is corrected by the following equation. 11.4j1W331 The error correction execution circuit for d''j (26≦j≦31) according to the previous equation (26) is constructed in the same way as the error correction execution circuit for d''26 in FIG. 8, which has already been explained. The explanation will be omitted.

In the above, the encoding circuit 1 conforming to the encoding matrix ratio according to the present invention when m=5 in FIG. 2, the syndrome bit generation circuit 20, and the data bits d''1, d''2, d''
3, .

Next, the encoding method and error correction method according to the present invention will be explained in the general case where m is an arbitrary odd number of 3 or more.

The encoding matrix when m=5 is given by H5 in FIG.
The encoding matrix for the general case of m is given by Hm in FIG. The partial line in Hm in FIG. 9 is given in FIG. From Figures 9 and 10, the encoding matrix is 0m
It is a matrix of +1) As shown in FIGS. 9 and 10, the method of constructing the encoding matrix Hm is considered to be obvious, so no further explanation is necessary. Now R=
d+? (m-1) data bits Dl, d2, d3
,..., DR-1, dR, dynamic+1 check bits COO9ClO9Cll9Cl299Cl(m-
2) 9C1 (m-1) 9C209C219C229
C2(m-1)9C309C319C32999C3(
m-1), the check bit is generated by vector-matrix multiplication using the data bit and the encoding matrix Hm as shown in the following equation. The check bits are stored in memory along with the data bits.

However, R=d+? (m-1).

Next, how can we represent the check bits and data bits read from memory by adding dash symbols? +1 syndrome bit S(X), SlO, Sll, Sl2?
″″? S1 (m-2) 9S1 (m-1) 9S distribution 9S21
9S229019S2 (m-1) 9S309S319S
32919S3(m-1) is generated by matrix and vector operations as shown in the following equation.

However, R=I+? (m-1).

Using the syndrome bit given by the above equation (29), an error in data bit d' (where 1≦j≦I (m-1)) can be corrected as follows.

In the previous equation (29), the syndrome bits including d'', (1≦j≦a) are generally S(X), Sla, S3,
It is expressed in the form of This S. The error correction for d″, (1≦j≦771′) using O, Sla, S2b, and ji is as follows:
30). Vj-JV-J However, in the above formula, the symbol [ ] means [X] XmOdulOm.

Next, in the previous equation (24), d″,≦i+?(m−1)
Syndrome bits containing S.

O,Sab9Sa(b+1)9Sa(b+2). This Sl9Sab9Sa(b+1)9Sa(
b+2) using)d″, (d+1≦j≦bo+艮(m−
Error correction in 1) can be performed using the following equation (31). However, in the above formula, [ ] symbol [X] = XmOdLllOm, and a+1> symbol is 1
It means +1>=2, <2+1>=3, and <3+1>=1.

Therefore, the error correction method according to the present invention can be summarized as the encoding method according to the above equation (28), the syndrome bit generation method according to the above equation (29), and the error correction execution method according to the above equations (30) and (31).

That is, 5+1 check bits are generated from d+(m-1) data bits according to equation (28),
Both data bits and check bits are stored in memory. The next I+? read from memory? (m-1
) data bits + 1 check bit according to the formula? +1 syndrome bits are generated, and then using the 5+1 syndrome bits, the formula (30
) and (31), i+? Two or less random errors occurring in the (m-1) data bits and master+1 check bits are corrected.

Therefore, the error correction circuit according to the present invention includes an encoding circuit according to the above equation (28), a syndrome bit generation circuit according to the above equation (29), and an error correction execution circuit according to the above equations (30) and (31). It would be a good idea to realize the circuit.

As already explained, as an example of the present invention, when m=5, the code circuit is implemented as shown in FIGS. 3 and 4, the syndrome bit generation circuit is implemented as shown in FIG. 6, and the error correction execution circuit is implemented as shown in FIG. The circuit was implemented as in FIGS. 7 and 8.

Similarly, the encoding circuit, the syndrome bit generation circuit, and the error correction execution circuit for a general case of m (where m is an odd number) can also be constructed, so their explanation will be omitted. In the above description, a memory is configured between the encoding circuit and the decoding circuit, but it is clear that the present invention can also be applied to a transmission line. As described above, when m is any odd number greater than or equal to 3, the present invention provides the following method: i+? (m-1) data bit? It has a configuration that corrects any two or less errors by adding +1 check bit.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the relationship between memory in a data processing device and the error correction circuit of the present invention, and FIG. 2 is a block diagram used to generate one check bit from 31 data bits in the present invention. Code line old. A diagram showing
3 and 4 are diagrams showing an example of a circuit that generates a check bit, FIG. 5 is a block diagram showing an example of a decoding circuit, and FIG. 6 is a diagram showing an example of a circuit that generates a syndrome bit. FIG. 7 and FIG. 8 are diagrams showing an example of a circuit that performs error correction, and FIG. 9 is a diagram showing an example of a circuit that performs error correction. (m-
FIG. 10 is a diagram showing a submatrix H1 in the matrix Hm of FIG. 9. In the figure, 1 is an encoding circuit, 2 is a memory, 3'' is a decoding circuit, 4 is an arithmetic circuit, 5, 6, 50, 60, 61, 6
2, 63, 65, 70, 71 and 72 are exclusive 0R circuits, 40 is a decoding circuit, 20 is a syndrome bit generation circuit, 21 is an error correction execution circuit, and 64 and 73 are majority decision circuits.

Claims (1)

[Claims] 1 Let m be any odd number of 3 or more ▲ There are mathematical formulas, chemical formulas, tables, etc. ▼ An encoding circuit that adds 3m + 1 check bits based on the data bits, and The circuit includes a circuit that generates 3m+1 syndrome bits based on data bits and check bits, and a majority circuit that decodes the output of the syndrome generation circuit by majority logic. 1. A double error correction circuit comprising: a decoding circuit for correcting any two or less errors that occur.