JPS5878241A - Error detecting and correcting system for coded data - Google Patents

Abstract

PURPOSE:To detect one-bit and two-bit errors without adding an excess gate quantity, by correcting one-bit errors in the present situation and adding the same 8-check bits as a code for detection of two-bit errors to 64-bit data to be coded. CONSTITUTION:64-bit data 1 to be coded is applied to a check bit generating circuit 10, and check bits 2 are generated by expression (1), and coded data 3 is generated with data 1 and bits 2. This coded data 3 applied to a syndrome generating circuit 11, and a syndrome 4 is generated by expression (2) and is applied to a syndrome decoding circuit 12 and error detecting circuit 14. Data 1 is applied to an error correcting circuit 13, and errors are corrected by an error bit position designating signal 5 from the circuit 12, and data 6 to be coded after error correction is outputted. The output of the circuit 12 is applied to the circuit 14, and errors of the syndrome 4 are detected to output an error detection reporting signal 7. Thus, one-bit and two-bit errors and the error of a single 4-bit block are detected.

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an error detection and correction method capable of 1-bit error correction, 2-bit error detection, and single 4-bit block error detection of encoded data.

Current storage devices using semiconductor memory add 8 check bits to 64 bits of encoded data to create a code (8EC-DED) that corrects 1-bit error and detects 2-bit error. codes) are widely used. In contrast, future storage devices will output multiple bits of data (for example, it is highly likely that it will be 4 bits), whereas current memory elements output one bit of data. It seems likely that memory devices with

For this reason, research is underway to add the ability to detect errors in blocks of multiple focus (b bits) to the current 5EC-DED code. SE that can detect this single block error ("-DE, D code,
Below, we will refer to the 5EC-DED-8bED code and the 11.P code (5bED means Singleb-bit g
(abbreviation for roupError Detection).

By the way, in the theoretical construction method of the conventional 5EC-DED-8bED code, 5BC-DED-84E with a data length of 64 bits, which is considered to have a high possibility of being put into practical use,
In the case of D code, the number of check pits of 9 bits is required, which is 1 bit more than the current 8BC-DED symbol month. Method of constructing codes (see 1981, written by Shigebe Kaneda). In this case, since the memory element has a 4-bit data output, in order to store 9 check bits,
Either three 4-bit output elements or two 4-bit output elements and one l-bit output element must be used. This means that the addition of the 54ED function deteriorates the economic efficiency of the device, and even if a 1-bit output memory element is mixed in to minimize the deterioration in economic efficiency, it will require extra memory compared to the current situation. Requires an element. Since the data bus system does not yet have a ζite configuration, an extra gate amount must be added to the control logic section.

The present invention eliminates the above-mentioned drawbacks and improves the current S E C-DE
It enables 1-bit error correction, 2-bit error detection, and single 4-bit block error detection by simply adding 8-bit check bits, which are the same as the D code, to 64-bit encoded data. The drawings will be explained in detail.

FIG. 1 shows a schematic block diagram of an error detection and correction system. In FIG. 1, 1 is coded data, and the coded data 1 is a check bit generation circuit 1.
0 becomes check bit 2, and code word 3 is constructed from check bit 2 and encoded data 1. Therefore, the check pit generation circuit 10 can also be called an encoding circuit.

The code word 3 that may contain an error is inputted to the syndrome generation circuit 11 and syndrome information 4 is generated. This syndrome information 4 includes information indicating the error bit position, and is turned into an error bit position indicating signal 5 by the syndrome decoding circuit 12. Error detection circuit 14
generates a signal 7 reporting the occurrence of an error according to the syndrome information 4 (and information from the syndrome decoding circuit if necessary). Encoded data 1 that may contain errors is sent to an error correction circuit 13, and error-corrected encoded data 6 is generated by inverting the erroneous bits according to the error pit position indication signal 5. Made.

The error/correction circuit 13 performs a two-man exclusive OR (X-OR)
) can be arranged by the bit width of the encoded data.

Now, the 5EC-DED code (1
Bit error correction/2 bit error detection code -), 64
An 8-bit check bit 2 is added to the 1-bit encoded data. On the other hand, let us consider a SEC-DEL') code that has added block error detection capability, that is, a 5BC-DED-8bED code.

This code is capable of not only 1-bit error correction and 2-bit error detection, but also detects any block error up to b pits occurring in a single block consisting of a plurality of bits (b bits). The pit width of the block, i.e. b, is
In practical terms, it is thought that b=4.8.9 or so will appear, but among these, it is considered that there is a high possibility that a block length of 4 bits will be used for the main storage device.

1) = 4 5EC-DED-8bED code, i.e.
An example of a code conventionally proposed as the 5EC-DED-84ED code is shown in FIG. In FIG. 2, blanks are "0". In this conventional example, the encoded data (DOLDI
・D63) has a 9-pit check bit (COlCl
...C8) must be added. 5EC
-IIED-84ED code construction methods have been proposed in various ways, but as shown in Figure 2, all of them require at least 9 check bits for the data length example pits to be encoded. It's only 4.

On the other hand, the present invention uses a code given by a parity check matrix as shown in FIG. 3a. This code uses the parity check matrix of a 5EC-DED code (a code without S4ED capability) whose IJ matrix satisfies the properties of an odd weight sequence as a starting point, and uses column compatibility to block as many blocks as possible. This code is obtained by modifying the parity check matrix to increase the probability of error detection. In Figure 3a, the blank is “0”.
This code generation method uses a type of vertical search called "one-hill climbing method" in artificial intelligence, but the detailed explanation of the 4-code generation program itself is not directly related to the present invention. Therefore, it will be omitted. The code in FIG. 3a differs from the code in FIG. D4, D
5, D6, D7)...(D60XD61, D62,
D63) (C1, C2, C3 to C) (C4, C5, C
6, C7) can detect any error of 2 or more bits. In the code shown in FIG. 3a, each column of the parity check matrix has an odd weight, so it is possible to correct a 1-bit error and detect a random 2-bit error.

FIG. 3b shows the syndrome of 3 pits and 4 bits in a block for the code of FIG. 3a, in order to confirm the function of the code. Here, (a) is 3 in the block
Bit error syndrome (72 types), (b) is a syndrome of 4 bit errors in a block (18 types), and the syndrome is all "0" or matches one of the column vectors in Figure 3a. There isn't. In addition, in FIG. 3b, the blank is also "0 pa" (however, in the case of (b), each block has only one pattern).

Next, the syndrome generation circuit (
(If a check bit is not input, it becomes a check bit generation circuit as it is), a specific configuration example of a syndrome decoding circuit and an error detection circuit will be explained.

FIG. 4 shows an example of the configuration of the syndrome generation circuit.

In FIG. 4, encoded data DOXD1, D2, .
. . D63 and check bits C0XC2, .

FIG. 5a, FIG. 5b and FIG. 5C are syndrome decoding circuits. That is, syndrome information 5O1S11・
...S7 is input to a total of 72 AND gate circuits, and error bit position pointing signals EO, El, ...E63,
EC01EC11... Ecrt is improved. The ``.'' mark at the input of the AND gate circuit indicates that an AND operation is performed on the negation of the signal. Here, for example, E2.1 in Fig. 5b is a signal indicating that there is an error in bit 24 of the encoded data, and ECO in Fig. 5c is a signal indicating that there is an error in the check bit CO. If there is, it outputs "l".

FIG. 6 shows an example of the configuration of the error detection circuit. Here, it is detected that 1-bit error correction has been performed by ORing the errorlet position indication signals EO-, E63, and BCO to EC7, and on the other hand, ORing the syndrome information SO to Si
An example of detecting the occurrence of an error by taking . Two error detection report signals7. ．． 7° is syndrome information S
When O to S7 are not all “0” and 1-bit error correction is possible (signal 7), and when the syndrome information is not all “0” but 2-bit error or single block error, 1 It is reported that the error cannot be treated as bit error correction (signal 72).

It is necessary to generate a code as shown in FIG. 3a by a computer program, and various code high-IJT check matrices can be obtained by using the 5EC-DED code given as an initial value. FIG. 7 shows an example of another H11 test matrix having the same functionality as FIG. 3a.

In addition, in FIGS. 3a and 7, the matrix used for parity detection is an odd numbered weight sequence, but an even numbered weighted matrix can also be used.

As mentioned above, the present invention enables 1-bit error correction, 2-bit error detection, and single 4-bit block error detection by simply adding 8-bit check pits to 64-pit encoded data. be. Therefore, errors in multiple pit output elements can be detected with the same number of redundant bits as the current 1-bit error correction 02-bit error detection code.

Further, according to the present invention, even if a single 4-bit block error detection function is added, high-speed encoding and decoding equivalent to the current 1-bit error correction/2-bit error detection code is possible.

Furthermore, according to the present invention, since the data bus system of the storage device has the same byte configuration as the current one, there is no need to add extra gates to the storage device control logic.

However, the present invention can be applied to a data bus system LSI logic for a control logic section having an 8-bit width or a 12-bit width.

[Brief explanation of the drawings] Figure 1 is a schematic block diagram of the error detection and correction system;
3A is a diagram showing an example of a code used in the conventional error detection and correction method, FIG. 3B is a diagram showing an example of a code used in the error detection and correction method of the present invention, and FIG. FIG. 4 is a diagram showing a configuration example of a syndrome generation circuit for the code of FIG. 3a, FIGS. 5a to 5c are diagrams showing a configuration example of a syndrome decoding circuit, FIG. 6 is a diagram showing an example of the configuration of an error detection circuit, and FIG. 7 is a diagram showing another example of codes used in the error detection and correction system of the present invention. 1... Encoded data, 2... Check bit, 3
...Encoded data, 4...Syndrome, 5...
Erroneous bit position designation signal, 6... Coded data after error correction, 7... Error detection report signal, 10... Check pit generation circuit, 11... Syndrome generation circuit, 12. ...Syndrome decoding circuit, 13...
error correction circuit, 14... error detection circuit; Figure 1 0

Claims (1)

[Claims] 164 pit encoded data (Do, DI,...
Do3) to 8-bit check bit (CO9CI,
...C7) is expressed by the following formula, where lhi (""0+ 1 +...63) is a binary column vector of 8 rows and 1 column, T is generated according to transposition, and is generated from fast wave encoded data and check bit. code word (Do −Do3, C'0~C,7)
Syndrome information (So, 81...87) is generated according to the following equation, an error bit position indicating signal is generated from the syndrome information, and occurrence of an error is detected, and 1-bit error correction in the code word is performed. - In the error detection and correction method that performs 2-bit error detection, the column vector Ih□ e Ihl + "' Ih63 t 1h6 in the above formula (2)
4t...'1h7□ is the column vector of the parity check matrix in a 1-pit error correction/2-bit error detection code that satisfies the properties of an odd or even weight sequence with a data length of 64 pits and a check bit of 8 pits. and rearrange the 72-bit code word into block 1 of every 4 bits.
8 bits (divides into two, corrects any 1-bit error in the codeword, detects any 2-bit error, and can also detect any 3-bit or 4-bit error that occurs in one block) An error detection and correction method for encoded data, characterized in that: