JPS5848937B2 - Error detection and correction method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an error detection and correction method for correcting multiple bit errors.

Conventionally, main memory devices of information processing devices have used single error correction/double error detection codes that correct 1-bit errors and detect 2-bit errors, mainly for the purpose of relieving storage element failures. using error correction detection equipment;
Improvements in equipment reliability have come a long way.

On the other hand, with the progress of LSI integration technology, memory elements that have data output of multiple bits per element have appeared, unlike the conventional elements that output data of one bit per memory element.

In this multi-bit output LSI storage element, when a failure occurs in one element, there is a possibility that the error spreads to the plural bits output from the failed element.

For this reason, when the current single error correction/double error detection code is applied to a multi-bit output element, it is not always possible to repair the failure of one storage element, which is always repaired under the present circumstances.

In other words, the improvement in the reliability of the main memory device due to the code is insufficient.

On the other hand, Bossen (D, C, Boss
en ; b - Adjacent Error C
orrection. , IBMJ. Res. Deve
lop, July 1970) has the ability to correct any errors that occur within a predetermined block of multiple bits (b bits).
Single associated b-bit error correction code (single b, Adjac
ent-r-error correction code (Single badj
acent bit group error
(Correction code) hereinafter referred to as SbEC code.

) was proposed.

According to this SbEC code, all failures in a single storage element can be completely repaired even for a multi-bit output element.

On the other hand, with current single error correction/double error detection codes, the double error detection function of the code makes it possible to completely detect 2-bit errors that occur as a result of two element failures at the same address. .

In contrast, the SbEC code has insufficient ability to detect errors of two or more bits that occur across two blocks of b bits.

Therefore, in devices using multi-bit output storage elements and SbEC codes, errors occurring across two b-bit blocks resulting from two element failures cannot be completely detected.

As a result, in a device using the SbEC code, the probability of a double failure of an element being overlooked without being detected increases compared to the current main memory device.

In order to solve the problems of the SbEC code mentioned above and deal with multi-bit output storage elements, it is necessary to correct errors of one or more bits that occur within a block of b bits, and also to correct errors that occur across two blocks. 2. more than a bit,
Single b-Adjacent error correction, double b-A, detects errors up to 2-B bits
d jacent error detection code (Single
b-adjacent bit-group Err
orCorrection Double b-ad
jacent bit-group Error
l)ection code, ) (hereinafter referred to as Sb
It is called EC-DbED code.

)is necessary. As this SbEC-DbED code,
Conventionally known Reed-Solomon SbEC
-DbED code (I, S, Reed &G,
Solomon; PolynomialCode
overCertain F inite F
ields,,J. Soe, Ind, A
ppl, Math,, vol, 8, Jun
e1960, refer to), when constructing an encoding/decoding circuit as it is, the circuit does not have repeatability, so LS
It has the disadvantage that the number of LSI pattern codes increases when integrated.

In addition, due to the form of the parity check matrix, a quasi-parallel decoding method that can reduce the amount of hardware in the decoding circuit (Imai, Kamiyanagi; Regarding B2 type burst error correction code, IEICE technical research report AL-76- 54) is difficult to adopt.

It is an object of the present invention to be able to correct any errors within a single pre-delimited b-bit block, and yet to
This error detection/correction method has the ability to detect errors of up to 2.b bits across blocks, and also provides a repeating structure to the encoding/decoding circuit, making it suitable for LSI implementation. It is about providing.

Another object of the present invention is to enable the encoding/decoding circuit to be configured with as few gates as possible.

Examples will be described in detail below.

FIG. 1 is a block diagram of an embodiment of the present invention, in which information 6 is added to a check bit generation circuit 1 constituting an encoding circuit, a check bit 7 corresponding to information 6 is generated, and information 6 and This check hit 7 is added to the processor 2, which collectively refers to a storage device, various transmission paths, and the like.

The output information 9 of this processor 2 is applied to a syndrome generation circuit 3.

The syndrome generating circuit 3, the syndrome decoding circuit 4, and the error correction circuit 5 constitute a decoding circuit. The error position pointing information bit 10 and the information 8 corresponding to the information 6 in the output information 9 are added to the error correction circuit 5, and after the error is corrected, the reproduced information 11 is generated. is output.

The check bit generation circuit 1 has 2 bits each consisting of b bits.
・K data blocks Dl 5 D2 ,...
・Assuming D2k as one piece of information, each b to be added to it
Three check blocks C1, C2, C consisting of bits
3 according to the following relational expression.

■ is the identity element of the finite field GF (2 b), and A1
,A2,...Ak is a finite field GF (2 b
), and addition, multiplication, and division are defined in the finite field GF(2b).

Also, b is an integer greater than 1, and k is Ik<:2b -1-
Ax, an integer that satisfies 1, can be any element of the finite field GF (2b), but Ay that satisfies Ax is Al I A2 ,...Ak
must not be included in the

Furthermore, the syndrome generation circuit 3 generates data blocks D; , D'2, . . .
′! Syndrome bits S1, S are calculated from k and check blocks C'1, C'2, Cl3 according to the following relational expression.
2. It has a structure that protects S3.

Syndrome bit S1 from syndrome generation circuit 3
. Correct the bit,
It is possible to detect an error in the most significant 2.b bits that occurs across two blocks.

The present invention is based on SbE by Reed-Solomon.
By transforming the C-DbED code into a new code representation, the encoding/decoding circuit can be configured to be suitable for LSI implementation, and at the same time, the amount of gates can be reduced by making it easier to apply quasi-parallel decoding. It aims at the above-mentioned Reed Solomon's SbEC-
The DbED code can correct any error that occurs within a pre-divided block of b bits, and can detect errors up to the thickest 2 b bits that occur across two blocks. It is a code that has the ability.

It is known that the parity check matrix is expressed as shown in FIG. 2a.

However, here, T is a b-row, b-column O, 1-element matrix expressed by the following formula, and a finite field GF with T as a generator
(2b) can be formed.

The zero element is a zero matrix with b rows and b columns, and the identity element is an identity matrix with b rows and b columns.

Here a.

, a1...ab-1 is an element of GF (2 }, and is an irreducible polynomial g(x) of degree b shown in equation (5).
is the coefficient of

Figure 2b shows Reed-Solomo when b=4.
This is a validity check matrix of S4EC-D4ED code of n, and the information length is 60 bits.

If an information length smaller than this is sufficient, columns may be appropriately selected from the parity check matrix shown in FIG. 2b.

As is clear from the example in FIG. 2b, the conventionally known Reed-Solomon SbEC-DbE
In the D code, if we focus on the parity check matrix of the data block part, in the third row, 2 of T is
The elements are increasing by the power.

Fully parallel decoding and quasi-parallel decoding are known as high-speed encoding/decoding methods for b-adjacent error correction codes.Compared to the former, the latter quasi-parallel decoding generally requires less It is possible to reduce the gate amount.

However, in order for this quasi-parallel decoding method to take advantage of its features, when focusing on a certain column of the parity check matrix, there is a gap of at most T1 elements between that column and adjacent columns for each row element. If so, it's convenient.

That is, the conventionally known Reed-Solomo
The SbEC-DbED code of n requires a circuit for multiplying by T2 in order to perform quasi-parallel decoding, and is not necessarily suitable for the quasi-parallel decoding method in terms of gate amount and decoding time delay.

Furthermore, the parity check matrix shown in FIG. 2b does not have repeatability and is therefore not suitable for LSI implementation.

On the other hand, FIG. 3 shows SbE according to the code representation of the present invention.
This figure shows a parity check matrix of a C-DbED code, and the parity check matrix shown in FIG. 2a is transformed into the parity check matrix shown in FIG. 3a by the following procedure.

First, the symbols in FIG. 2a are data block parts, that is, when paying attention to the column to the left of the broken line in FIG. 2a, all the elements in the first row are ■.

On the other hand, the first column from the left is unchanged, the second column is divided by T2, the third column is divided by T4, etc. so that the third row is I. Even if the transformations are made one after another, in the end only a code in which the rows of the code in FIG. 2a are replaced is obtained.

However, the second column from the left is divided by T1, the third column is divided by T2, etc. so that all the column elements of the information bit part in the second row of the code in FIG. By adding transformations one after another, a new code representation can be obtained.

It is clear that even with such modifications, the code detection and correction capabilities do not change.

The parity check matrix of this new representation of SbEC-DbED is shown in FIG. 3a.

Here, check bits are set to C1 for each block of b bits.
, C2, C3, check bit generation is performed using the following equation.

However, the encoded information is divided into D1 and D for each block of b bits.
2, Dk''.

Note that the second row in the left half of the parity check matrix in the data block part is equal to the third row in the right half, and similarly, the third row in the left half is equal to the second row in the right half. I have to do it.

That is, assuming that 2·k data blocks D1, D2, . , C2, and C3 can be generated by the following relational expression.

That is, similar to formulas (1a), (1b), and (1C), A1, A2, ......Ak are individual nonzero elements of the finite field GF (2b), k is I x k x 2b
-1-1, and Ax is a finite field GF
(2 b), Ay that satisfies the following formula for a certain Ax is A1, A2, ......Ax
cannot be included in

Here, as discussed above, (+) c,.

The circuit that generates Cll and the circuit that generates Cll can be realized with the same circuit configuration, (!!) The circuit that generates C20 and the circuit that generates C31 can be realized with the same circuit configuration, and (!!!) C s The circuit that generates o and the circuit that generates C21 can be realized with the same circuit configuration.

The codeword to which these check blocks C1, C2, and C3 have been added is subjected to processing such as storage and transmission, and the resulting data block is the data block D'1, C2, I)'3''.
"""'I)X' and check blocks C'1, C'2
, C'3, decoding requires first generating syndrome bits and then decoding the syndrome.

Syndrome bits are divided into b-bit blocks S1, S2,
When expressed as three blocks S3, S1, S2, and S3 are given by the following equations similar to equations (3a), (3b), and (3c).

In the circuit that creates this S1, S2, and S3, (1)
The circuit that generates S1o and the circuit that generates Sll have the same configuration. (!!) The circuit that generates S20 and the circuit that generates 83 have the same configuration. (iii) The circuit that generates S3o and the circuit that generates 821 have the same configuration. This means that circuits can be created with the same configuration.

Furthermore, the syndrome decoding circuit that decodes the syndrome bit and points out the error pit position can also be implemented entirely by two identical circuits as shown below.

That is, for example, it is a circuit that detects the establishment of a column and outputs an error pattern ei.

Formulas (l7a) to (17c) and formulas (19a) to (19c)
), it can be seen that if the S3 signal and the 82 signal are input to the decoding circuits 82 and 83 of the column of equation (16), respectively, they can be used as they are as the decoding circuit of the column of equation (18). Recognize.

Furthermore, if the syndrome bit l is not non-zero even though no error pattern is output from this syndrome decoding circuit, an error occurring across two blocks is detected.

Next, an example of an error detection and correction device constructed from the parity check matrix shown in FIG. 3a will be shown.

FIG. 4b shows a parity check matrix used in the error detection and correction device explained below, and its GF (2
) is shown in Figure 4C.

Also, FIG. 4a is an example of a conventional configuration, and a and b in FIG.
It can be seen that the code of FIG. 4b using the structure of the present invention has a repeatability of 2 in its H matrix.

FIG. 5 shows a check bit generation circuit constructed based on the parity check matrix shown in FIG.
16) is input from the top and summed by the parity check tree 13.

Information 6 corresponds to each next block D1-D4.

The two parts surrounded by the dashed line in FIG. 5 have exactly the same circuit configuration, and the check bit generation circuit has two repetitions in this part.

14 is a two-man exclusive or gate, C O ”
Generate check bit 7 consisting of ``'= C 11 .

Here, the number of gates required in the circuit indicated by the one-dot chain line is 32 gates in terms of two-man exclusive OR gates.

In addition, if the exclusive OR gate 13 group is allowed to have some overlap (redundancy), it is easy to have repetition 2, and if it is accommodated in one LSI together with the portion indicated by the dashed-dotted line,
An encoding circuit can be configured with two LSIs of one code.

As described above, by using the method of the present invention, the check bit generation circuit can generate one code L by allowing a small amount of redundancy.
It was shown that it can be configured with two SIs.

Furthermore, the syndrome generation circuit 3 is almost the same circuit as the check bit generation circuit 1, only that a part for inputting check bits is added.

That is, the syndrome generation circuit in the encoding circuit and the decoding circuit can be configured with four LSI codes for the syndrome generation circuit.

The decoding circuit includes, in addition to the syndrome generation circuit 3, a syndrome decoding circuit 4 and an error correction circuit 5.

Here, the error correction circuit 5 is a circuit that restores correct information by adding the error pattern detected from the syndrome decoding circuit 4 to the received information, and a two-man exclusive OR circuit is provided for each bit. Bye.

That is, if the error pattern for the bit in which an error exists is rB, the received information is inverted by exclusive OR and becomes correct information.

FIG. 6 shows an example of the structure of a syndrome Tecode circuit for the code shown in FIG. 4B.

A quasi-parallel decoding method is used here.

The number of exclusive OR gates used here is 38, but if the fully parallel decoding method is used, the number of two-man exclusive OR gates will increase by about 20%.

As can be seen from FIG. 6, the syndrome decoding circuit using the code construction method of the present invention can be constructed from two identical LSIs by simply replacing the syndrome inputs.

That is, if a decoding circuit corresponding to the column in FIG. 4b is created, the decoding circuit for the column can be obtained by simply replacing the syndrome signals in the second and third rows.

Here, the decoding of the check block is omitted because it is usually not necessary.

In FIG. 6, 66 is a syndrome bit, which is all "0" if no error exists in the received information.

Further, 60 is a multiplication circuit that multiplies 4-bit information by TI, and is composed of one two-man exclusive OR gate.
is a knot gate that produces an inverted error pattern.

62 is a logic circuit consisting of a two-man exclusive OR gate and an OR gate for generating a signal indicating that an error has occurred in the 4 bits in the D3 block, which (i) indicates that an error has occurred in the block; When there is (ii
) All input syndromes are “0” (no error)
In the two cases, the output signal 63 becomes rOJ.

On the other hand, if there is at least one non-zero bit in the syndrome, the signal 65 becomes "0".

Therefore, an error pattern is output from the gate 64 only in the case (1) above.

A decoding circuit that generates error patterns for blocks D1 and D2 is indicated by 69, and can be realized with the same circuit configuration as the decoding circuit for blocks D3 and D4, so the internal configuration is omitted from illustration.

Here, if at least two of the syndromes S1, S2, and S3 are non-zero, and no error pattern is output from the syndrome decoding circuit, there is an error that cannot be decoded, and two Errors that span blocks are detected.

Finally, a more practical application example of the present invention will be shown below.

In the main storage device, the information length is often 64 bits or 128 bits.

At this time, Reed-Solomon's SbEC-
The DbED code lacks code length for b=2, 3, and 4.

That is, as the main memory code, b = 4 and the information length is 64, 12.
Minimum 16 for S4EC-D4ED code for 8 bits
It is known that pit inspection bits are required.

FIG. 7 shows a configuration sequence of the S4ECD4ED code, which provides the encoding/decoding circuit with cyclicity suitable for LSI implementation.

Although these codes were obtained as a result of computer generation, one repeating unit is a code that satisfies the gist of the present invention.

FIG. 7a shows a code with an information length of 64 bits, and FIG. 7b shows a code with an information length of 128 bits, with 300 gates or less, 40
Encoding and decoding circuits can be configured using two LSI codes with ~60 signal pins.

LS for encoding/decoding with information length of 128 bits in Fig. 1b
I is the data length 64 bits, 32 bits S4 as is.
It can also be used as an LSI with ECD4ED code.

As explained above, in the error detection/correction circuit using the SbECDbED code, the present invention can provide the repeatability of 2 to the encoding/decoding circuit.

Furthermore, the quasi-parallel decoding method can be easily applied to the decoding circuit, and the amount of gates can be reduced.

If only one of the blocks of b bits contains one or more error bits, all the error bits can be corrected, and the most common error bits occurring across two blocks can be corrected. It is possible to reliably detect errors up to b bits.

Brief description of the drawings: Figure 1 is a block diagram of an embodiment of the present invention, Figures 2a and b are conventional Reed-Solomon SbECDbEC
Parity check matrices of codes, FIGS. 3a and 3b are parity check matrices of an embodiment of the present invention, FIG. 4a is a conventional parity check matrix, and FIG. 4b is a parity check matrix of an embodiment of the present invention. Figure 4C shows the parity check matrix of Figure 4b under GF(2b), Figure 5 is a block diagram of a check bit generation circuit based on Figure 4C, and Figure 6 shows the parity check matrix of Figure 4C. FIGS. 7a and 7b are explanatory diagrams of examples of code configurations according to the embodiment of the present invention.

1 is a check bit generation circuit, 2 is a processor, 3 is a syndrome generation circuit, 4 is a syndrome decoding circuit,
5 is an error correction circuit, 6 is information to be encoded, 7 is a check bit, 8 is output information corresponding to the information to be encoded, 9 is output information of the processor, 10 is error position pointing information, 11 is restoration information, 12 is a syndrome bit, 13 is a parity check tree, and 14 is an exclusive-OR gate.

Claims (1)

[Claims] 1 2·k data blocks D each consisting of b bits
1, D2, . . . D2k as one piece of information, and means for generating three check blocks C1, C2, C3 each consisting of b bits to be added to the information according to the following relational expression, is the identity element of finite field GF (2b), Ai is finite field GF
Each non-zero element of (2 b), b is an integer greater than 1, k is an integer satisfying 1 x 2b-1-1, AX is any element of the finite field GF (2 b), Ay that satisfies Ay - Ax is not included in Ai. ) After performing processing such as storing and transmitting the code word added with the check block generated by the above means, the processed information is stored in data blocks D1tD4, . . . D
4k and check block C; , C≦CS, then a circuit that generates certain syndrome bits S1, S2, S3 from a block of b bits according to the relational expression, and a correct data block D1 based on the syndrome bits S1, S2, S3. , D2, . The most dog 2 that occurred across blocks
An error detection and correction method characterized by detecting errors up to b bits. 2 The generation circuits for CtO and C1, the generation circuits for C2o and C3, and the generation circuits for C3o and C21 for generating the check blocks C1, C2, and C3 have the same configuration, and the syndrome bit S1 , S2, and S3, the generation circuits for S20 and 331, and the generation circuits for S30 and 821 have the same structure, and the syndrome bits S1, S2, and S3 have the same structure. 2. The error detection and correction system according to claim 1, wherein a circuit for restoring correct data blocks D1 to Dk and a circuit for restoring correct data blocks Dk+t to D2k have the same structure.