JPS5845738B2 - Error detection/correction device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an apparatus for detecting and correcting errors in data read from, for example, a storage device.

In recent electronic computers, it is common practice to correct 2 or more bits (hereinafter referred to as multi-bit) errors, 0), and 1-bit errors on data read out from the main pupil unit. ing.

FIG. 1 is a block diagram showing a storage device and its surroundings that detect multi-bit errors and correct 1-bit errors.

Assuming that 8-byte data length is to be handled, 8-byte data 1 and 8-bit parity 2 given from an external device such as an arithmetic processing unit are given to the Hamming code generation circuit 3, where parity 2 is replaced by 8-byte data 1 and 8-bit parity 2. An 8-bit syndrome 4 is created, and data 1 and syndrome 4 are given to the storage device 5 as write data.

Furthermore, the 8-byte data 6 and the 8-bit syndrome 7 read from the storage device 5 are sent to the Hamming code inspection circuit 8.
Error detection is performed here.

The Hamming code checking circuit 8 determines whether there is an error or not, and generates an error code 9 depending on the content of the error.

This error code 9 and the read data 6 are applied to an error correction circuit 10, where the data 6 is corrected according to the error code 9 if it has a 1-bit error.

In the case of an error of 2 bits or more, correction is impossible and another process is started.

The error correction circuit 10 further creates 8-bit 0 parity based on the read data 6 or the corrected data, and sends the data 6 and parity 11 to an external device.

Note that the number within 0 indicates the number of bits.

The above configuration is for dealing with malfunctions of the storage device 5, but if the peripheral circuits such as the Hamming code generation circuit 3, Hamming code inspection circuit 8, and error correction circuit 10 fail, the data is sent to the outside. Data cannot be guaranteed.

For example, if the Hamming code generation circuit 3 malfunctions and the Hamming code inspection circuit 8 detects it as a multi-bit error, there is no problem because the data is not corrected and the process immediately moves on to another process, but if it is detected as a 1-bit error. If this happens, correct data will be incorrectly corrected.

As a result, the external device will process data different from the contents of the storage device, causing a serious problem in data processing.

Therefore, a first object of the present invention is to provide an error detection and correction device that prevents errors that are originally uncorrectable from being erroneously corrected due to a failure of a circuit for performing the error detection and correction function. .

A second object of the present invention is to make it possible to realize the above-mentioned error detection and correction device without adding a large amount of circuitry compared to conventional devices.

The present invention improves at least one of a code generation circuit and a code check circuit provided to perform error detection and correction functions.

The code generation circuit generates a code for error detection and correction based on data given to a system to be detected and corrected.

The code checking circuit also creates information indicating error detection and correction for the data based on the data from the system and the code obtained with this data.

According to the present invention, at least one of these circuits is duplicated for at least a portion where a partial failure of the circuit is determined to be an error that can be corrected in the code inspection circuit, and the outputs of the two are compared. A means is provided to do so.

With this configuration, correctable errors are double-judged, and correct data is virtually never corrected by mistake.

(probability is very small) thus reliable error detection.

You can get a correction device. In addition, only a portion of the circuit is duplicated, allowing for low-cost error detection.

You can get a correction device. An embodiment of the present invention will be described below.

The specific configuration of the Hamming code generation circuit is as follows.

The data is 8 bytes - 64 bits, the syndrome is 8 bits, and each bit 5o-87 of the syndrome is obtained by exclusive ORing one part of the 64 bits of data as shown in FIG.

First, four Q element data Pim(
i is a byte position from 0 to 7, m is a byte position from 0 to 3), and this raw data is used to create a syndrome.

FIG. 3 shows a circuit for generating raw data Pim, in which PG is an even parity generator well known in this field.

In other words, the bits constituting the data are Dij (i is 0 to 7
, and J indicates the bit position from O to 7), then Pi□=DiO■Di, ■Di2■D s 3■Di4
■D t 5 ■D l 6 ■Di7 Pi1=Di4■Di5■D+6■Di7P I 2
=D 12■D t 3■D i 6■D t 7P
i3 =D t 1■D t 5■D i5■D r
7 (However, ■ indicates exclusive OR).

Figure 4 shows syndrome S using raw data.

~S7 is shown, in which PG is an even parity generator.

The syndrome bits are SO””P30■P40■P50■IF'cto■P7
0S1=P00■P10■P20■P60■P70S2
=P10■P20■P40■P50 S3=Poo■P20■P30■P50■P70s4:
P01■P11■P, 21■P31■P41■P51
■P61■P7, s5= P02■P12■P22■P32■P42■P
52■P6□■P72 s6= P03■P13■P23■P33■P43■P
53■P63■P73 s7= P00■P10■P20■P30■P40■P
,.

■pao■P70■So■S1■S2■S3■S4■S
5■S6 becomes.

Next, the specific configuration of the Hamming code inspection circuit is as follows.

For 8 bytes of read data, four pieces of raw data Pim are created corresponding to each byte as in the case of the Hamming code generation circuit, and this raw data and the read syndrome S are generated.

-87 and error code E.

-Create E7. In other words, Eo-8o■P30■P40■P50■pao■P7゜El-81■POO■PIO■P20■pao■P70
E2-82■PIQ■P20■P40■P50E3-8
3■P00■P20■P30■P50■P70E4=
S4■P01■pH■P21■P31■P4,■P51
■P61■P71 E5=S5■P02■P12■P22■P32■P42
■P52■P62■P72 E6=S6■P03■P13■P23■P33■P43
■P53■P63■P73 E7=S7■P00■P1o■P20■P30■P40
■P50■pao■P70■So■S1■S2■S3■
If the syndrome bit created from the read data matches the syndrome bit read out, the corresponding error code bit becomes "0", and if they do not match, it becomes "1".

If all the F-codes are "O", it is determined that there is no error in the read data.

If E7 is "1" and Eo-E3 is as shown in Table 1, it is determined that there is a 1-bit error, and in this case, E.

The bits designated E4-E6 in Table 2 in the byte designated -E3 are determined to be in error, and correction is made by inverting this bit.

Further, if the error code is as shown in Table 3, it is determined that the syndrome 0) or 1 bit error shown in the table is present.

In this case, since there is no error in the data, no correction is performed.

If Eo-E3 is a code other than those shown in Tables 1 and 3, and E7 is 0'' and E.

If -E6 is not all O, it is determined that there is a multi-bit error.

Next, let's consider malfunctions of the Hamming code generation circuit and Hamming code inspection circuit.

First, if the PIO system of the circuit that creates the raw data Pim malfunctions due to a malfunction in the Hamming code generation circuit, the syndrome bit will be erroneous as shown in Figure 5, and upon reading, it will be determined that it is a 1-bit error or a multiple-bit error based on the error code. .

Note that in this table, an x mark indicates a malfunction. Also Pi
l, pi2. If the Pig system fails, syndrome bits S4 and S7. S5 and S7゜S6 and S7 are wrong, error code is “00001001” “0”
0000101" and "00000011", both of which are determined to be 1-bit errors of syndrome bits.

Next is Syndrome Bit S. ~ S of the circuit that creates S7
.

-If the 87 series fails, each syndrome bit S.

and S7, S1 and S7, S2 and S7, S3 and S7, S4 and S7, S, and S7, S6 and S7, S7 are wrong, error code is 10000001", "01000001"
“'00100001’“00010001” ”0
0001001” “0000010-1” “0000
0011" and "ooooooooi", both of which are determined to be 1-bit errors of syndrome bits.

Next, in the malfunction of the Hamming code inspection circuit, if the circuit system that creates the raw data Pr□) P'+11 Pt2 and Pt3 breaks down, the PiolPil, Pi2, and Pi3 systems of the Hamming code generation circuit described above will fail. It will be exactly the same as in the case of

Also error code E.

If the circuit system that creates -E7 breaks down, this will also be the S of the Hamming code generation circuit.

~It will be exactly the same as in the case of a failure in the S7 system.

From the above, the malfunction of the Hamming code generation circuit and Hamming code inspection circuit is due to the raw data P.

o, Plo. If only one P2O1P2O+ pcto creation circuit system fails, it will be determined as a 1-bit error,
At this time, it can be seen that normal data is incorrectly corrected.

Therefore, it can be seen that it is sufficient not to perform 1-bit error correction at this time.

In addition, each pin of raw data, syndrome, and error code
The probability that two or more zero generation circuit systems fail at the same time is very small, and therefore such a case is not considered in the present invention.

Therefore, according to the present invention, a circuit as shown in FIG. 6 is added to the Hamming code generation circuit and the Hamming code inspection circuit.

In FIG. 6, PG is an even parity generation circuit, to which data is given from the outside (in the case of a Hamming code check circuit, data read from a storage device) D 1
o-D I 7 is input, and the logic up to this point is exactly the same as the creation logic of the existing raw data Pi□, and the raw data PIO
is created twice.

The even parity generation circuit PG further contains existing raw data P.
IO is being input.

The purpose of this is to compare the new raw data created by the even parity generation circuit PG with the existing raw data Pi□.

The even parity generation circuit PG is connected to Poo, PIO, P2O, P2O, which is determined to be a 1-bit error in the event of a failure.
One is provided in each pao system, and five in total are provided in each of the Hamming code generation circuit and the Hamming code inspection circuit.

Therefore, i=0.1.3.4.6.

OR is an OR circuit that takes O and A of the output of the 5-0 even parity generation circuit PG, AND is an AND circuit that outputs the output of the OR circuit at the time of generation of the timing pulse TP, and FF
is a flip-flop which is set by the output of the AND circuit AND, and its output serves as a signal for inhibiting the 1-bit factory correction operation.

By doing this, the raw data Pi□ of the Hamming code generation circuit and the Hamming code inspection circuit (however, i=o,
If the generation circuit system in 1.3.4.6) malfunctions and produces an incorrect output, the even parity generation circuit PG will output, and the flip-flop FF will be set at the time the timing pulse TP is generated. The output inhibits 1-bit factory correction operations.

In the above, regarding the circuit system for generating raw data Pi□, if the existing even parity generation circuit and the newly added even parity generation circuit fail at the same time, it will be mistakenly determined as a 1-bit error and a correction operation will be performed. To put away
This probability is so small that it can be considered virtually impossible.

Furthermore, in the above, the circuit system for generating raw data PIO is duplicated with i=o and 1.3.4.6.

However, if you do this, if the circuit that creates the raw data Pi is mounted on a separate board for each byte, Pi.

It is necessary to prepare two types of boards: one with a duplicated circuit system and one without.

Therefore, in order to eliminate this inconvenience, raw data Pi
Regarding the circuit system to be created for o, all of them, i.e., i=0 to 7, may be duplicated.

Even in this case, the remaining raw data Pi1, P12, P
It is clear that the number of circuit elements is much smaller than when all of the circuit systems 1 and 3 are duplicated.

Further, in the above explanation, failure of the error correction circuit was not mentioned, but this will be explained below.

FIG. 7 shows an error correction circuit, in which the area above the broken line is a data correction section, and the area below is a parity bit generation section.

20 is error code E. - A decoder group that specifies error bits of data based on E7, and each bit of data H)i
It has a decoder DEC1 corresponding to j.

21 is an exclusive OR circuit group for correcting (inverting) data based on the output from the decoder group 20, and has an exclusive OR circuit EX1 corresponding to each bit Dij of data.

The exclusive OR circuit EXI has a corresponding data bit Di.
j and the output of the decoder DEC1 are input.

22 is a decoder group that specifies an error byte when a 1-bit error is determined, and a decoder DEC is specified for each byte.
It has 2.

23 is an exclusive OR circuit group that corrects (inverts) the parity bit based on the output from the decoder group 22, and has an exclusive OR circuit EX2 corresponding to each byte.

The exclusive OR circuit EX2 receives the corresponding raw data Pi(1
and the output of the decoder DEC2 are input.

Since the raw data Pl□ is obtained by the even parity generation circuit PC, it becomes a parity bit as it is.

In this error correction circuit, data bit D. 0~D7□
If not corrected, the raw data PIO-F70 is output as is as a parity bit, but if the data bit is corrected, the raw data corresponding to the byte to which the bit belongs is inverted and used as a parity bit.

In this error correction circuit, decoders DEC1 and D
Since EC2 and exclusive OR circuit EX1EX2 are both independent circuits, if one of them fails, a parity 1' check will result in a parity error in the receiving device.

Therefore, it is possible to detect a failure of such an error correction device.

Although an embodiment in which the present invention is applied to an error detection and correction device for a storage device has been described above, the present invention is not limited to this.

For example, it is clear that the present invention can be applied to a data transmission system that transfers data from one device to another, or a system that stores or transmits data serially bit by bit.

According to the present invention as described above, correctable errors are double-judged, and it is possible to virtually eliminate the possibility of incorrectly correcting correct data.

Furthermore, the configuration for this purpose is very simple because the entire circuit is not always duplicated, and the device can be manufactured at low cost.

[Brief explanation of the drawing]

Figure 1 is a block diagram showing a storage device that performs multi-bit error detection and 1-bit error correction and its surroundings, Figure 2 is a table for explaining the syndrome creation method, and Figures 3 and 4 are the same as Figure 1. FIG. 5 is a table diagram for explaining failures in the Hamming code generation circuit, and FIG. 6 is a diagram illustrating a Hamming code generation circuit and a Hamming code inspection circuit according to the present invention. FIG. 7 is a diagram showing the configuration of an error correction circuit. In the figure, 3... Hamming code generation circuit, 5...
・Storage device, 8... Hamming code inspection circuit, 10.
...Error correction circuit, PG...Even parity generation circuit.

Claims (1)

[Claims] 1. A code generation circuit that creates a code for error detection and correction based on data given to a system subject to error detection and correction and supplies it to said system together with the data;
An error detection and correction device comprising a code inspection circuit that creates information indicating error detection and correction for data based on data from the system and the code obtained with the data, the code generation circuit and the code inspection circuit. At least one of the Q circuits is duplicated for subdivisions in which a partial failure of at least the Q circuits is determined to be an error that can be corrected in the code checking circuit, and a means is provided for comparing the outputs of both Q circuits. An error detection and correction device characterized by: