JPS6013492B2 - Error detection and correction method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an error detection and correction method used in a storage device of an information processing device.

In the storage device of an information processing device, error detection and correction are performed for the purpose of improving reliability.

The error correction code most widely used in this error detection and correction system is a 1-bit error correction-2-bit error detection code (hereinafter abbreviated as SEC-DEO code). Due to the ability of this SEC-DED code, most errors caused mainly by storage element failures are corrected, and device reliability is greatly improved. With the recent increase in the integration of memory elements,
It is important to detect failures in control circuits that generate timing signals and the like for driving storage elements.

For example, a timing signal malfunction may cause information (consisting of encoded write information and check bits) to be read from an address location different from the address location to be read, but in conventional error detection and correction methods, the generation of check bits Since no information is involved, such timing signal failures go undetected and are ignored, causing serious malfunctions in the system. In view of the above-mentioned drawbacks, an effective and practical method was proposed in the 40th edition of the Japanese Patent Publication No. 1, which can detect failures in control circuits such as timing signal circuits by generating check bits from both encoded information and address information. It was disclosed in Publication No. 2433 "Digital Information System". According to this method, write information is written in do, d.・・・・・・・・・dn
-, , (n is an integer of 2 or more), address information indicating the address position to be written is ao, a.・・・・・・・・・a
m-,, (m is an integer greater than or equal to 1), check pit Co, C...... cr-,, (r is 1
or higher integer) is generated according to the following formula.

n--1 m-1cj=j
≧odi・h;, jyuj≧.

ai・hM, 1...
・・・・・・・・・{11 However, h;, j{0, 1}, i
=0, 1, 2...r--Here, hi and i are the elements of the i-th row and i-th column of the encoding matrix, and are determined according to the encoding capability according to the well-known encoding theory.

The reason for addition and multiplication in the above formula indicate exclusive OR and logical product, respectively. Write information 4, d.・・・・・・・・・dn-
・Check bit Co, CI・・・・・・・・・cr
-, becomes the code word to be written to the storage unit, which is the address position a to a.・・・・・・・・・It is stored in am-.

Next, by the read operation, the read information is o, d′,
......d'n-, and check bits c'o, c'.・・・
. . .c'r-, the address position is also taken out from a, . . . am-, and error detection and correction is performed. For error detection and correction, syndrome bits S are extracted from this starting codeword according to the following formula
o, S. ......Create Sr-. nh
1 m−1Si=j≧.

d'i. hi, jyuj≧. ai・hn+i,jyuc′j
・・・・・・・・・・・・
...'2} If there is no error in c'i, d'i and ai, Si=0 for all j. When read from the wrong address location, Si=0 for all j
, and the error can be detected. Even if there is an error in d'i, Si=0 will not hold for all i. However, the above prior art method has the following problems in diagnosing memory elements. Figure 1 is an explanatory diagram of the check bit generation circuit in the conventional error detection and correction system (“H
It is called "matrix". ). The code is Hsiao
This is an example of a 1-bit error correction code according to ``This is a diagrammatic representation of the following formula.As an example, in the case of address (moxibustion, a., a2, a3) = (1, 0, 1, 1), ,
(chi, d,, d2, scold): all “1” and all “0”
Suppose that a storage element is tested by encoding two types of information: ``.

The check bit values for odd parity are as follows. For all “1”; (co, c.……c7)
=(1・1・1・〇・1・〇・1・1) For all “0”: (co, c,……c7)=(1・1・1・〇・〇・1・〇・〇) As can be seen from this example, in the conventional error detection and correction method, when a memory element is tested with two types of patterns such as all “1” and all “0”, the value degenerates in the check bit. There's a bit there.

Therefore, in this conventional error detection and correction system, if a stuck-at fault occurs in the check bit section, the fault cannot necessarily be detected by using only two types of patterns. For this reason, it has conventionally been necessary to test memory elements with three to four different patterns. However, due to the increase in the number of patterns, the test time for the memory element increases, which leads to the complexity of the test program. Therefore, an object of the present invention is to enable testing of memory elements and address circuits using as few different test patterns as possible when testing memory elements including check bit sections and address circuits using a wide variety of information patterns. This aims to reduce program development costs.

Another object of the present invention is to reduce the execution time of a test diagnostic program and speed up its operation. The details of the present invention will be explained below with reference to Examples. FIG. 2 shows an example of the configuration of an error correction system for implementing the error detection and correction method of the present invention, in which 1 is an encoding circuit and 7 is a decoding circuit. The encoding circuit 1 consists of a check bit generation circuit 2, which generates check bits 5 from write information 3 and write addresses 4 sent from a central processing unit or a diagnostic device. Check bit 5 and write information 3 constitute write code word 6,
This is transferred to storage. The decoding circuit 7 includes a syndrome generation circuit 9, a syndrome decoding circuit 11, an error detection circuit 8, and an error correction circuit 17. The outgoing code word 13 read out from the storage section consists of a check bit 14 and outgoing information 15. Check bit 14, logical question information 15, and address 4 are sent to syndrome generation circuit 9, and syndrome 10 is generated. The error detection circuit 8 detects errors based on this syndrome. On the other hand, the syndrome 10 becomes information 12 indicating the error bit position in the syndrome decoding circuit 11. According to the instruction of this error bit position indication signal 12, errors in the drafting information 15 are corrected by the error correction circuit 17, and the correct drafting information 16 is obtained. When the syndrome decoding circuit 11 or the error detection circuit 8 detects a plot that cannot be corrected by the coding capability or an error in the address information, the operation of the storage device is stopped or a retry operation is performed.

Since the circuits that control these operations are well known, illustration thereof will be omitted. Further, in the embodiment shown in FIG. 2, the check bit generation circuit 2 and the syndrome generation circuit 9 are separate circuits, but they may be shared and one circuit may be used by switching. If the result of the check bit generation circuit that generates the check bit 5 from the write information 3 and the address information 4, that is, the H matrix, is given, the configuration shown in FIG. 2 can be immediately realized using known techniques. Therefore,
The following explanation of the date matrix will suffice to explain the structure of the present invention. FIG. 3 shows an example of wiring of an encoding circuit used in an embodiment of the present invention.

This figure is a diagrammatic representation of the following equation. Figure 3 is the first
Compared to the figure, the structure of the code itself is the same, but the wiring for generating check bits is completely different.

This is clear from the check bit generation equations {31 and 4-. That is, the wiring according to the present invention connects data bits do to d, . The point is that an odd number of them are used to generate each check bit, and in the example of FIG. 3, three data bits are taken in to generate any check bit. Any number of address bits may be incorporated based on the gist of the present invention. In the above example, address (heat, a,, a2, a8) = (1, 0, 1
, 1), when the information of all "1" and all "0" is encoded, the value of the check bit at odd parity is as follows.

For all "1" (co, c, ......c7) = ku1
, 〇・1.1, 1.1・〇・1) for all “0” (co, c, state…c7) = (0, 1・〇・〇・〇・〇・1・〇) It is clear that the value of the check bit part is not compressed in this way.

When encoding all "1" write information and all "0" write information, if an odd number of check bits in the write information are used to generate each check bit, the check bits will be generated regardless of the code ability. The value of will not be flipped vertically.
It should be noted here that when comparing FIG. 1 and FIG. 3, there is no change in the amount of gates required to generate check bits. Similarly, from a comparison of FIG. 1 and FIG. 3, it should be noted that there is no change in the number of logical stages of exclusive OR gates required to generate check bits. As described above, according to the error detection and correction method of the present invention, two of all "1" and all "0"
It is possible to test and diagnose the storage element including the check bit portion by using different types of information patterns. Figure 4 shows SEC-D
1 is an embodiment of the present invention in an ED code.

Write information (d ■, fu......do7, d
,o,d,. ,……d,7,Moge……・d77) and the check bit (co, c,………c7) from the address information (ru, a.………father) is being generated. The number of 1's in the row direction (horizontal direction) of the entire H matrix of codes is an odd number or an even number. However, for the write information 8B (byte) portion, the columns are selected so that the number of 1s in the row direction of the corresponding portion of the H matrix is an odd number. As a result, each check bit is generated from the address information and an odd number of bits in the write information. Fourth
In the figure, if two types of information, all "1" and all "0", are encoded, the check bits will not shrink no matter what value the address information has. As explained above, according to the error detection and correction method of the present invention, failures in storage elements and failures in address circuits can be detected using only two types of data patterns, which has the advantage of reducing the execution time of test diagnostic programs. be.

Furthermore, according to the present invention, it is possible to diagnose the failure of the memory element section using only two types of data patterns, so the cost of the test diagnosis program can be reduced. When implementing the present invention, which has such advantages, it is not necessary to increase the number of gates in any way compared to conventional error detection and correction systems, and moreover, compared to conventional error detection and correction systems, coding and No additional logical delay is required for decoding. Furthermore, according to the present invention, when diagnosing a fault in a storage element section using only two types of data patterns, it is possible to more completely detect a fault in a storage element compared to a conventional error detection and correction system. It becomes possible.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing the wiring of the encoding circuit of a conventional error detection and correction system, FIG. 2 is a block diagram showing the configuration of a system used in an embodiment of the error detection and correction method of the present invention, and FIG.
Figure 4 shows the wiring of the encoding circuit of the system used in one embodiment of the error detection and correction method of the present invention. Figure 4 shows the wiring of the encoding circuit of the system used in another embodiment of the method of the present invention. figure. 1... Encoding circuit, 2... Check bit generation circuit, 3... Write information, 4......
Address information, 5... Check bit, 6...
...Writing code word to storage unit, 7...Decoding circuit, 8...Error detection circuit, 9...
Syndrome generation circuit, 10... Syndrome, 11... Syndrome decoder circuit, 12... Error bit position indication signal, 13... Sign transfer from storage unit, 14... ...Go to check bit 15...
... Read information, 16 ... Proposal information after error correction, 17 ... Error correction circuit. O1 figure O3 box O2 figure 4 figure

Claims (1)

[Claims] 1. Means for generating a check bit based on address information and write information of a plurality of bits written in a position indicated by the address information, and creating a code word composed of the check bit and the write information, and a means for generating a code word after the code and the address information. In the error detection and correction method, the check bit includes means for generating a syndrome based on the address information, correcting an error in the code word according to the syndrome, and detecting that the code word is read from an erroneous address location. An error detection and correction method characterized in that the value is equal to the exclusive OR of at least one bit of information in the write information and an odd number of bits in the write information.