JPS5947340B2 - error check correction circuit - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a correction circuit that generates an error correction code that can be expressed as a pariday check matrix, generates a syndrome for error correction using the error correction code, and performs error correction.

2. Description of the Related Art In information processing devices, particularly storage devices, it is known to use error checking and correction circuits in order to achieve high reliability of the device.

The error check and correction circuit in the storage device generates and adds an error correction code to the input information data written to the storage device, and also generates a syndrome in the data read from the storage device, and if there is an error due to the syndrome, it is detected. It has a function to correct this. Conventionally, this type of circuit has been realized using a large number of small-scale integrated circuits, and there have been problems with the reliability and economic efficiency of the error check and correction circuit. However, with the development of semiconductor integrated circuit technology, there is a trend toward large-scale integrated circuits (hereinafter referred to as LS) to achieve higher reliability and lower costs. When converting an error check and correction circuit into an LS, it is necessary to improve its versatility and heatability (repetitive use of the circuit) from the viewpoint of economy. For this reason, it has been proposed to provide expandability to the data length by configuring an 8-byte length by using, for example, four 2-byte length slices of the input information data length as an error checking and correction circuit. ing. In this case, the code structure uses a basic part H matrix to which rows consisting of all 0" elements are added as a parity check matrix (hereinafter referred to as H matrix) that expresses the error correction code, and expands the input information data length. In this case, an H matrix is used, which is constructed by chaining together a plurality of basic part H matrices whose constituent rows are shifted in the column direction.From this point of view, the error check and correction circuit is based on the basic part H matrix. Based on the configured circuit, when expanding the input information data length, a plurality of basic circuits were used and the rows of the basic partial matrix were shifted in the column direction and connected in a chain. Therefore, the error correction code/syndrome generation circuit and the syndrome decoding circuit have expandability.In other words, such an error correction circuit uses only the basic circuit to constitute an error check and correction circuit for short code lengths, and furthermore, the error correction code/syndrome generation circuit and syndrome decoding circuit have scalability. On the other hand, in order to reduce the number of test patterns in the storage device and test execution time, and to facilitate maintenance, each row of the H matrix is given an even weight (an even number of 1's). ).

When realizing an H matrix with even weight rows using the error check and correction circuit, there are the following drawbacks.

Since the input information data length and the basic part H matrix of the basic circuit are fixed, an error check and correction circuit using a plurality of basic circuits and connected in a chain so that the rows of the basic part matrix are sequentially shifted will have a fixed value of the basic part H matrix. Even if each row has an even weight, each row does not necessarily have an even weight. In order to solve these shortcomings, a basic part H matrix consisting of even weight rows is used, and when these constituent rows are shifted in the column direction and chained, each row of the H matrix as a whole becomes an even weight row. One column of the basic partial H matrix is selected and one element is added or deleted so that the H matrix is used to obtain an error correction code or syndrome and correction result.

In this way, an error check and correction circuit that can realize even weight rows not only for the basic circuit but also for arbitrarily extended input information data lengths can be obtained. This will be explained in detail below with reference to the drawings. FIG. 1a shows an example of a basic part H matrix (hereinafter abbreviated as "mountain").

HO is a basic part H matrix of the error check and correction circuit constructed by slicing the input information data length 2 bytes (16 bits). The 7th and 8th rows are all composed of 60' elements, and the remaining rows are all composed of non-zero elements. Further, a unit matrix of 6 rows and 6 columns is provided as the inspection section C. 81 (0,0,...O),
1hij:l:(HlltsuHi2゜゜゜゜゜゜hil6
) is 0 Figure 1b is H.

By removing [Yes] in the 7th and 8th lines, we get the following code:
(22,16) SE for data length of 2 bytes
It constitutes an H matrix of C-DED code (single bit error correction, 2 bit error detection). Figure 1c shows (40, 32) SEC-D for a data length of 4 bytes.
It is an H matrix of ED code, and the left half is H. And the right half is H. This is a matrix obtained by cyclically moving in the column direction so that the fourth row 1hS' becomes the first row.

Figure 1d shows data length of 8 bytes (72,
64) H matrix of SEC-DED code, where the leftmost partial matrix is H.

The second partial matrix from the left is H. is rotated so that the 7th line [Yes] becomes the 1st line,
The third and fourth partial matrices from the left are matrices obtained by sequentially shifting downward by two rows.
H here. It is clear that the columns of must be cyclic and independent of each other. H formed in this way
. By configuring this H. An error checking and correcting circuit constructed based on the above alone has an error checking and correcting function for input information having a data length of 2 bytes. Furthermore, with a length of 2 bytes, the minimum check bit length can be used. Also, if two or four of these error check and correction circuits are used, each 4 bytes,
The input information data length can be expanded to 8 bytes. Next, the H
. We will explain how to give each row an even weight using .
In order to give each row an even weight when the input information data length is 2 bytes, the number of "1" in the inspection section in each row is 1, so H.
Each row of must satisfy the following formula. J where i=1, 2...6, hij consists of 1 or O elements.

In order to give each row of the H matrix an even weight when the input information data length is 4 bytes, it is necessary for each row of H to satisfy the following conditions, as shown in FIG. 1c.

However, in the case of 2 bytes, if each row has an even weight, then from the condition of equation (1), each term on the left side of the first row of equation (2) will be "1", and each term on the left side of the second row of equation (2) will be "1". The term is also "1", and the 1st, 2nd, 5th, and 6th rows of the H matrix do not have even weights. Therefore, in this invention, any one column from the 16 columns excluding the inspection part of H. 1 tears) and 1 line j
Add or delete element 1 in column or row 5 and column j,
Further, an element 1 is added or deleted from the 2nd row and the j column or the 6th row and the jth column to form the first basic part H matrix H. Correct this and define it as the second basic part H matrix. If an H matrix with an input information data length of 4 bytes is made into a matrix as shown in FIG. 1C using the second basic part H matrix, each row will have an even weight. The error correction code and syndrome are generated from an H matrix constructed from the second basic part H matrix. A specific example is shown in FIG. In the figure, only 1 in the main part of the matrix is shown, and descriptions of 0 elements are omitted. FIG. 2a shows a first elementary part H matrix H in which each row has an even weight. It is. Figure 2b
is an H matrix when the input information data length is 4 bytes. The first elementary part H matrix H, as indicated by the O symbol. 1 element in the first row, column 15 and the second row, column 15 is deleted, and this is used as the second basic part H matrix. Figure 2 b (7) The H matrix is the second basic part H
It is constructed using a matrix and Figure 1C. All rows have even weights. In this way, each row of the H matrix has an even weight even when the number of bytes is 4 bytes. To make each row an even weight with an input information data length of 8 bytes, use the first
H from figure d. Each row of must satisfy . But 2
If each row of the H matrix of bytes has an even weight (1)
Equation (3) holds true, and each row has an even weight even when the number of bytes is 8 bytes. FIG. 2C is an example of an H matrix when the input information data length is 8 bytes. This H matrix is constructed as shown in FIG. 1d using the first basic portion H matrix of FIG. 2a. All rows have even weights. Note that when the basic part H matrix is an odd weight sequence, an even number of elements are added or deleted.
In this case each column must be independent. An example of the configuration of an error check and correction circuit using the basic part H matrix described above will be explained with reference to the drawings.

FIG. 3a is a block diagram of the error correction code/syndrome generation circuit corresponding to the row in which the element 1 is added or deleted, and FIG. 3b is a block diagram of the syndrome decoding circuit corresponding to the selected column j. It is. In order to simplify the explanation below, a configuration will be described in which one element is added to form an even weight row. 1 is the first basic part H
This is input information data corresponding to the row to which the first element is added based on the matrix.

2 is an input information bit corresponding to the first column.

3 is a switching signal.

4 is a first switching circuit which receives input information bit 2 and switching signal 3 and outputs information bit 5;

Reference numeral 6 denotes an error correction code/syndrome generation circuit (hereinafter abbreviated as generation circuit) corresponding to the row to which element 1 has been added, which inputs input information data 1 and information bit 5 and generates error correction code bit or syndrome bit 7. Output.

The generating circuit 6 generally takes the exclusive OR of the parallel input of data corresponding to 1 in the corresponding row of the H matrix and the output 5 of the switching circuit 4. Here, the switching signal 3 is in the first state "O".
”, the first switching circuit 4 outputs the information bit 5 which is logically “0”, and the generating circuit 6 outputs the error correction code bit or syndrome bit based on the first basic part H matrix. is output.Switching signal 3 is the second
When state ``1'' is present, the first switching circuit 4 outputs information bit 5 equal to input information bit 2, and the generating circuit 6 outputs an error correction code bit or syndrome based on the second basic part H matrix. Output bits. In other words, the switching circuit 4 takes the AND of the information bit 2 and the switching signal 3. Here, the first basic part H matrix is a basic part H matrix in which each row has an even weight with an input information data length in repetition units, and the second basic part H matrix has an arbitrary input information data length and has even weight rows. so that the first
This is a basic partial H matrix obtained by adding 1 element to the j column of the basic partial H matrix. In Fig. 3b, 8 is the syndrome, and 9 inputs the syndrome 8 and the first
This is a syndrome decoding circuit corresponding to the j column based on the basic part H matrix, and outputs the first correction position designation signal 11.

Reference numeral 10 denotes a syndrome decoding circuit which inputs the syndrome 8 and corresponds to the j column based on the second basic part H matrix, and outputs a second correction position designation signal 12.

13 is a second switching circuit which inputs the first and second correction position designation signals 11, 12 and the switching signal 3 and switches the
A correction position designation signal 14 for input information bits corresponding to the column is output.

Here, when the switching signal 3 is in the first state "O", the second switching circuit 13 selects and outputs the first correction position designation signal 11, and when the switching signal 3 is in the second state "O", the second switching circuit 13 selects and outputs the first correction position designation signal 11. The second switching circuit 13 selects and outputs the second correction position designation signal 12. FIG. This is an example of the configuration of a generating circuit that switches between the two, and parts corresponding to those in FIG. 3 are given the same reference numerals.

Reference numeral 15 denotes a generation circuit, which receives the input information data 1 and generates error correction code bits or syndrome bits based on the first basic part H matrix, and outputs the error correction code bits or syndrome bits to the output terminal 1.
Output from 6.

Reference numeral 17 denotes a generating circuit which receives the input information bit 2 and the output of the generating circuit 15, generates error correction code bits or syndrome bits, and outputs the generated error correction code bits or syndrome bits from an output terminal 18.

Therefore, if output terminal 16 is selected, error correction code bits or syndrome bits based on the first basic part H matrix are selected, and if output terminal 18 is selected, errors based on the second basic part H matrix are processed. Obtain the correction code bit or syndrome bit. FIG. 5 shows an error check and correction circuit composed of two basic part H matrices with different input information data lengths, which are the basis of the repetition unit, and the first, second, third, and fourth This is an example of the configuration of a generation circuit that switches error correction codes or syndromes based on the basic part H matrix.

Here, the third basic part H matrix is the first basic part H
This is a matrix with an a (integer) column added to the matrix. The fourth basic part H matrix is a matrix obtained by adding the a column to the second basic part H matrix. In FIG. 5a, 19 is an output terminal, which outputs an error correction code or syndrome based on the first basic part H matrix generated by the generation circuit 15. 20 is input information data corresponding to the part of column a based on the third basic part H matrix, and 21 is a generating circuit that inputs the input information data 20. The information bit 5 and the output of the generation circuit 15 are used as inputs to generate error correction code bits or syndrome bits, and the generated error correction code bits or syndrome bits are output to the output terminal 22.

Therefore, from the output terminal 19, error correction code bits or syndrome bits based on the first basic part H matrix are obtained. The switching signal 3 is output from the output terminal 22 as the first
When the state is "O", error correction code bits or syndrome bits based on the third basic part H matrix are obtained. Furthermore, when the switching signal 3 is in the second state "1", if the input information data 20 is logically set to "O", the error correction code bit or syndrome bit based on the second basic part H matrix is input. If the information data 20 is input, error correction code bits or syndrome bits based on the fourth basic part H matrix are obtained.
In FIG. b, 23 is an output terminal, which outputs the error correction code bit or syndrome bit generated by the generation circuit 6.

Reference numeral 24 denotes a generating circuit which inputs the input information data 20 and the output of the generating circuit 6, generates error correction code bits or syndrome bits, and outputs the generated error correction code bits or syndrome bits to an output terminal 25.

Accordingly, from the output terminal 23, depending on the state of the switching signal 3, error correction code bits or syndromes based on the first or second H matrix are obtained. From the output terminal 25, depending on the state of the switching signal 3, error correction code bits or syndrome bits are obtained based on the third or fourth basic part H matrix. 6th
The figure shows an example of the configuration of a syndrome decoding circuit and an inverting circuit that switch correction position designation signals for input information data based on the first and second basic part H matrices by selecting an output terminal.

26 is an input information bit corresponding to the j column.

Reference numeral 27 denotes a first inverting circuit which receives the first correction position designation signal 11 and the input information bits 26, inverts and corrects any errors, and outputs the input information bits 26 to the output terminal 29.

28 is a second inverting circuit and a second correction position designation signal 1
2 and input information bits 26 are input, and if there is an error, the input information bits 26 are inverted and corrected and outputted to an output terminal 30.

Therefore, from the output terminal 29, the correction result of the input information data based on the first basic part H matrix is sent to the output terminal 3.
0 to obtain the correction result of the input information data based on the second basic part H matrix. In addition, in order to release the element 1 in the j column and make it an even weight row, the operation of the first switching circuit 4 in FIGS. 3 and 5 is changed between the switching signal 3 in the first state and the second state. This can be achieved by reversing each other. Fourth,
In the case of the configuration example shown in FIG. 6, no changes are made. Each of the configuration examples of the error check and correction circuit described above is an example for a code having an input information data length of 2 bytes and a SEC-DED function. It is clear that this method can be applied.

As explained above, the present invention uses a basic partial H matrix consisting of even weight rows, and selects one column of the basic partial H matrix so that when the rows are sequentially shifted and chained, each row becomes an even weight row. By adding or deleting element 1 and obtaining error correction codes or syndromes and input information data correction results by switching switching signals or output terminals, it is possible to control not only the length of input information data in repetition units but also the length of input information data arbitrarily. There is an advantage that even weight rows can be realized for the expanded input information data length.

Another effect is that by using a configuration in which switching is performed at the output terminal as shown in Figures 4 and 6, error correction codes or syndromes and correction results can be obtained without increasing delay time because a switching circuit is not included. . Another effect is that by using FIG. 5, even weight rows can be realized even in an error check and correction circuit in which basic part H matrices having different input information data lengths in repetition units coexist. Further, FIG. 5a has the advantage that an error correction code or syndrome can be generated for a specific input information data length without increasing the delay time. In the configuration example described above, it is only necessary to slightly increase the number of input/output terminals, so the effect of LSI integration is large and a highly versatile LSI can be realized.

[Brief explanation of the drawing]

FIG. 1 shows the basic part H matrix used in this invention.
FIG. 2 is a diagram showing a specific example of the H matrix; FIG. 3 is a diagram showing an example of the configuration of the error correction code/syndrome generation circuit and syndrome decoding circuit in the error check and correction circuit according to the present invention. 4 is a block diagram showing another configuration example of the error correction code/syndrome circuit, FIG. 5 is a block diagram showing still another configuration example of the error correction code/syndrome circuit, and FIG. 6 is a syndrome decoding block diagram. FIG. 7 is a block diagram showing another example of the configuration of the circuit. 1 two human-powered information data, 2: input information bit, 3: switching signal, 4: first switching circuit, 5: information bit, 6: error correction code/syndrome generation circuit, 7: error correction code bit or syndrome bit, 8: Syndrome, 9: Syndrome decoding circuit, 10: Syndrome decoding circuit, 11: First correction position designation signal, 12:
Second correction position designation signal, 13: Second switching circuit, 1
4: Correction position designation signal, 15: Error correction code/syndrome generation circuit, 16, 18, 19, 22, 23, 25,
29, 30: Output terminal, 17, 21, 24: Error correction code/syndrome generation circuit, 26: Input information bit, 2
7: first inversion circuit, 28: second inversion circuit.

Claims (1)

[Scope of Claims] 1. In an error check and correction circuit configured based on a parity check matrix that expresses an error correction code and in which each row has an even weight, input information data and the above parity check matrix in the data are provided. inputting the input information bits corresponding to one column selected by the above, and generating a first signal which is either a first error correction code or a first syndrome for the input information data using the above parity check matrix; The above selected 1 in the parity check matrix
A second error correction code and a second syndrome for the input information data and the input information bits using a second matrix in which at least one column element is changed so that the number of logical 1s in at least one row is an odd number. an error correction code/syndrome generation circuit that generates a second signal that is one of the above, and selects and extracts one of the first signal and the second signal; a first syndrome decoding circuit into which the first syndrome is input;
A second syndrome decoding circuit configured based on the second matrix and inputting the second syndrome, and inputting each output of these first and second syndrome decoding circuits and the input information data. and means for obtaining error-corrected data. 2. The error correction code/syndrome generation circuit includes a switching circuit that is controlled by a switching signal to switch between a logic 0 output and the input information bit, and is supplied with the output of the switching circuit and the input information data. 2. The error check and correction circuit according to claim 1, comprising a circuit that generates and outputs either the first signal or the second signal according to an input. 3 The error correction code/syndrome generation circuit receives the input information data and generates the first signal.
a second circuit into which the output of the first circuit and the input information bits are input to generate the second signal; output terminals of the first circuit and the second circuit are selected to generate the first signal;
2. The error check and correction circuit according to claim 1, further comprising means for extracting any one of the second signals. 4. The means for obtaining the error-corrected data includes a switching circuit that is controlled by a switching signal to switch and output one of the outputs of the first and second syndrome decoding circuits;
Claim 1 comprising an inverting circuit that receives the output of the switching circuit and input information data and corrects errors.
Error checking and correction circuit described in Section 1. 5 The means for obtaining the error-corrected data includes a first inverting circuit to which the output and input information data of the first syndrome decoding circuit are input, and a first inverting circuit to which the output and input information data of the second syndrome decoding circuit are input. 2. An error check and correction circuit according to claim 1, comprising: two inverting circuits; and means for selecting one of the output terminals of the first and second inverting circuits to extract error-corrected data.