JPH0691471B2 - Error correction circuit - Google Patents

Description

Description: TECHNICAL FIELD OF THE INVENTION The present invention relates to an error correction circuit used when receiving and decoding block code data having an error correction capability.

[Technical background of the invention and its problems]

In recent years, with the development of digital communication technology, error correction codes are widely used. In particular, error correction technology is an indispensable technology in wireless digital communication such as satellite communication and mobile communication, where the reliability of the transmission path is low, and in recent years, error correction technology has also been used for recording and reproducing digital signals in magnetic recording devices. Widely used. Error correction codes are roughly classified into block codes and convolutional codes. Among them, many block codes using cyclic codes are known to have various degrees of redundancy and error correction capability, and are widely used. Has been done.

By the way, BCH (portion chordry
Okkengem code is a code that corrects random errors, and various methods such as Peterson's method, Burenkamp's method, or Massy's method have been proposed as algorithms for determining error positions of 2 bits or more. . However, all of these methods are not considered to be practically useful methods because they require extremely multiple operations, academically anyway, and are generally not often used for correction of 2 bits or more. It was the actual situation.

A method of writing error correction information into each address of a memory (ROM) having addresses corresponding to all patterns of the error correction code, and inputting the error correction code as address data into the memory to read the error correction information. Is also considered. However, this method has a problem that an extremely large-capacity memory is required when the code bit length of input data (error correction code) becomes long.

[Object of the Invention]

The present invention has been made under such circumstances, and an object of the present invention is to provide an error correction circuit capable of determining an error position of 2 bits or more by an extremely simple method.

[Outline of Invention]

According to the present invention, the syndrome detection means for detecting the syndrome by dividing the acceptance data composed of the information bit and the redundant bit by the generator polynomial, and the syndrome output from the syndrome detection means are inputted as an address, and the syndrome is inputted. The storage device for storing the information of the bit position having an error in the received data determined by the binary data and storing and outputting the binary data, and the binary data from the storage device for each bit of the received data. It is characterized by further comprising means for converting and outputting the data indicating the presence or absence of an error and error bit correcting means for correcting the error bit of the received data by using the data indicating the presence or absence of the bit error.

〔The invention's effect〕

According to the present invention, a syndrome is given to an address of a storage device, and data indicating a bit error position determined by the syndrome is output from the storage device as output data. It can be performed without using a large-capacity storage device. Therefore, the circuit configuration can be simplified and the reliability of the communication system, the magnetic recording device, etc. can be improved. Such an effect becomes more remarkable as the number of correctable bits increases.

Example of Invention

 Examples of the present invention will be described below.

Here, a case where a BCH code is used will be considered as an example.

Now, the code word M (X) of the error correction code is the Galois field GF
(Q) and its generator polynomial G (X) is GF
The codeword M (X) is divisible by G (X) when defined by the elements of the extension field GF (q ^m ) of (q). If such a codeword M (X) is adopted, the input codeword M '
Whether or not an error has occurred can be determined by whether (X) is divisible by the generator polynomial G (X).

Now, when the input codeword M '(X) includes a transmission error, the remainder obtained by dividing the codeword M' (X) by G (X) does not become zero. The error bit is "1" and the others are "0"
Let E (X) be the code string of M ′ (X) = M (X) + E (X) (“+” is modulo 2 addition), so M ′ (X) is G
The remainder divided by (X) is equal to the remainder of E (X) / G (X), and this remainder is called syndrome S (X). If this syndrome S (X) can take different values for all patterns of errors up to 1 bit, the syndrome S (X)
It is possible to correct an error from (X) to 1 bit.

FIG. 1 is a diagram showing an embodiment of the present invention. The error correction circuit includes a syndrome detection circuit 11 for detecting the above-mentioned syndrome from the received data M ′ (X), and a syndrome S detected by the syndrome detection circuit 11.
Data (E) indicating the bit error position of the received data M '(X) determined by the syndrome S (X) with (X) as an input for each bit of the received data M' (X).
Based on the data E (X) output from the error position detecting circuit 12 and the error position detecting circuit 12 for inverting the error bit of the received data M '(X) to correct the error bit. And an inverting circuit 13. The error position detection circuit 12 is configured to include a ROM (see FIG. 4) for storing binary data indicating a bit error position as described later. (This binary data is binary
(Means a decimal code) Now, the received data M '(X) has a code bit length of 31 (information bit length of 16 and redundant bit length of 15) and can correct errors of up to 3 bits (31,16) BCH code Suppose And
The generator ^{polynomial, g (X) = X 15} + X 11 + X 10 + X 3 + X 8 + X 7 + X 5 + X 3 + X 2 +
Let X + 1.

When such 31-bit acceptance data M ′ (X) is input to the syndrome detection circuit 11, the syndrome detection circuit 11 divides the acceptance data M ′ (X) by the generator polynomial g (X) to generate the syndrome S. Calculate (X). The syndrome S (X) is 15-bit data because the degree of the generator polynomial g (X) is 15.

FIG. 2 shows an example of syndrome S (X) detection. Here, for simplification, an example in which the generator polynomial is g ′ (X) = X ⁵ + X ² +1 is shown.

That is, first of all, the delay circuits 21, 22, and 2 are input before data input.
3,24,25 are all cleared. In the EX-OR circuit 26, the received data sequentially serially input from the higher-order bits are subjected to exclusive OR with the output signal of the delay circuit 25 and given to the delay circuit 21. The bit data input to the delay circuit 21 is sequentially shifted to the delay circuits 22 to 25 according to a predetermined clock, but the EX-OR circuit 27 between the delay circuits 22 and 23 excludes the output of the delay circuit 25 again. Logical OR is taken. In the syndrome S (X), the last bit of the received data is input to the syndrome detection circuit 11 and EX
When it is output from the delay circuit 21 via the -OR circuit 26, it is obtained as the output signal of the delay circuits 21 to 25. Also in the case of the above-described 15th-order generator polynomial g (X), a detection circuit having exactly the same principle as that of the circuit of FIG. 2 can be configured by only 15 delay circuits.

The syndrome S (X) thus obtained is given to the error position detection circuit 12 as address data.

For example, if the lower 16th bit is incorrect, the syndrome is the remainder of dividing X ¹⁵ by g (X), so S (X) = X ¹¹ + X ¹⁰ + X ³ + X ⁸ + X ⁷ + X ⁵ + X ³ + X ² + X + 1 Becomes Therefore, address data 000111110101111 is given to the ROM address in the error position detection circuit 12. Then, it is indicated that there is an error in the position of X ^{15 in} the storage location of the ROM indicated by the dust address data.

Binary data 01111 is stored, which is read and output. The binary data output from the ROM is converted into data E (X) indicating an error position for each bit of the received data M ′ (X) and output from the error position detection circuit 12.

If, for example, the data of the lower 4 bits, 16th bit, and 17th bit is incorrect, the syndrome S
Since (X) is the remainder obtained by dividing X ¹⁶ + X ¹⁵ + X ³ by g (X), S (X) = X ¹² + X ⁷ + X ⁶ + X ⁵ + X ⁴ + X ³ +1. Therefore, the address data of 001000011111001 is given to the ROM address. Then, three data 00100, 10000, 10001 are stored in the storage location of the ROM indicated by this address data, and this is output.

Thus, it is addressed with the syndrome corresponding to all 1-bit errors, 2-bit errors, 3-bit errors
In each storage location of the ROM, 15-bit binary data indicating each bit error position is stored in advance. There are 31 1-bit errors that can be corrected and 2-bit errors.
_{Since there are 31} C ₂ = 465 ways and ₃₁ C ₃ = 4495 ways with ₃ -bit errors, this corresponds to about 1/6 of 2 ¹⁵ = 32,768 addresses. If no bit error has occurred, the address (00 ... 00) is specified from the syndrome detection circuit 11, so the data (00 ... 00) is stored at this location. And if any other address is specified,
This indicates that an error of 4 bits or more has occurred, and in this case, error correction is impossible. Therefore, special data notifying the uncorrectability, for example, the data of (11 ... 11) in which all 15 bits are "1" is stored in all the storage locations of the ROM designated by such an address. If the 31st bit is incorrect, for example, 11111,00000,00000 data is stored, so it can be distinguished from this.

In the error position detection circuit 12, since the output data of the ROM is binary data, the data indicating the 31-bit error position in which the bit corresponding to the error position is "1" and the other bits are "0", that is, Each bit of the received data M ′ (X) is converted into data E (X) indicating an error position and output to the error bit inverting circuit 13. For example, as described above, if the binary data 00100,10000,10001 is stored in the ROM, the data 0000000000000011000000000001000 is output from the error position detection circuit 12. When data (11 ... 11) indicating that there is an uncorrectable error of 4 bits or more is output from the ROM, data in which all 31 bits are all "1" is output specially. For example, it is configured as shown in FIG. That is, the received data M '(X) is serially input to the 31-bit shift register 31. When all the bits of the 31-bit reception data are stored in the shift register 31, the reception data is latched from the shift register 31 to the 31-bit latch circuit 32. Then, each bit data is respectively EX-OR circuit 33.
_1, 33 _2, ..., it is supplied to one input of 33 _31. On the other hand, the error position data E (X) from the error position detection ROM 12 is also latched by the 31-bit latch circuit 34, and each EX-OR circuit 3
3 _1, 33 _2, ..., is applied to the other input of 33 _31. Also,
The output of the latch circuit 34 is also input to the AND circuit 35.

Now, when there is no error in the received data, the outputs of the latch circuit 34 are all "0", so the received data and EX-OR circuit
33 ₁ , 33 ₂ , ..., 33 ₃₁ are not affected by anything and are output as they are.

On the other hand, when the received data has an error of 3 bits or less, the error position detection circuit 12 outputs data in which "1" is set at the error position, and therefore the input data is the EX-OR circuit 33.
_The data M (X) which has been inverted by ₁ , 33 ₂ , ..., 33 ₃₁ and the error of which has been corrected by the EX-OR circuits 33 ₁ , 33 ₂ ,
..., output from 33 ₃₁ .

Also, when an error of 4 bits or more occurs, the outputs of the latch circuit 34 are all "1", so the output of the AND circuit 35 is inverted from "0" to "1", which is an error detection signal. It is output as ERR.

As described above, according to this embodiment, a random error of 2 bits or more can be corrected by an extremely simple circuit configuration using the error position detection circuit 12 without using any complicated algorithm, and the error correction code can be put into practical use. It is clear that it will make a great contribution.

The present invention is not limited to the above embodiment.

For example, in the above embodiment, 31 EX-OR circuits were used to take EX-OR of the received data and the data indicating the bit error position in parallel, but since the received data is input serially, If the output data of the error bit inverting circuit 13 is also output one bit at a time, one EX-OR circuit will suffice. In such a configuration, the advantage of not requiring a third shift register 31 of 31 bits as shown in FIG, latches 32, 34 and 31 of the EX-OR circuit 33 _to 333 _31. An embodiment of the present invention having this configuration is shown in FIG.

In FIG. 4, error position detection ROM 51 and comparator 52
The counter 53 and the RS flip-flop 56 correspond to the error detection circuit 12 of FIG. 1, and the shift register 54 and the EX-OR
The circuit 55 corresponds to the error bit inverting circuit 13 in FIG. Here, in the error position detection ROM 51, the first area in which the highest address is "0", that is, the portion corresponding to the addresses from 00000 ... 0 to 01111 ... 1, and the highest address is "1" The second area, that is, the portion corresponding to the addresses from 10000 ... 0 to 11111 ... 1 is divided. Then, the data indicating the lower-order error bit position is stored in the address range of 00000 ... 0 to 01111 ... 1, and the address is
0 to 11111 ... 1 stores the data indicating the low-order error bit position. (If the number of bits of the syndrome is m, the number of bits of the address will be m + 1.)
Therefore, 5-bit binary data indicating the position of the higher-order error bit of the 2-bit error is stored in the storage location specified by the corresponding syndrome in the first area, and indicates the position of the lower-order error bit. The 5-bit binary data is stored in the storage location specified by the corresponding syndrome in the second area. Initially, the most significant bit of the address of ROM51 is set to "0". ROM5
The output of 1 is introduced to the first input terminal of the comparator 52. On the other hand, the output from the 5-bit counter 53 is given to the second input terminal of the comparator 52. The counter 53 is driven by the high speed clock φ,
The binary code from (0) to (31) is output.
The comparator 52 outputs "1" when both input data match. On the other hand, the received data M '(X) is stored in the shift register.
Introduced in 54. The shift register 54 is driven by the high speed clock φ of the counter 53. Therefore,
When "1" is output from the comparator 52, the bit data output from the shift register is incorrect. Therefore, when the output of the comparator 52 becomes "1", error correction can be performed by inverting the output of the shift register 54 by the EX-OR circuit 55. In addition,
Since the "1" output from the comparator 52 is given to the set (S) terminal of the RS flip-flop circuit 56, the output of the RS flip-flop circuit 56 is inverted from "0" to "1",
The most significant bit of the address of ROM51 is "1". Then, the error correction of the second bit is performed again by the same procedure. When the error correction is completed, the reset signal RS from the outside is given to the reset (R) terminals of the counter 53 and the RS flip-flop 56. If the number of error bits that can be corrected increases, the number of RS flip-flops should be increased.

With such a configuration, the capacity of the error position detection ROM 51 is 5t / 31 compared to the method of storing the error-free bit of the 31 bits as “0” and the error bit as “1”.
Can be reduced to However, t indicates the maximum number of correctable error bits.

In addition, the present invention may use another storage device such as a RAM or a magnetic disk as a storage device for detecting the bit error position from the syndrome.

Further, the type of cyclic code is not limited to BCH, and the present invention can be applied as long as it is a code having an error correction capability capable of specifying a bit error position from the syndrome.

[Brief description of drawings]

1 is a block diagram of an error correction circuit according to an embodiment of the present invention, FIG. 2 is a block diagram showing an example of a syndrome detection circuit in the error correction circuit, and FIG. 3 is an error bit inversion in the error correction circuit. FIG. 4 is a block diagram showing an example of a circuit, and FIG. 4 is a block diagram showing a part of an error correction circuit according to another embodiment of the present invention. 21 to 25 ... Delay circuit, 31 ... Shift register, 32, 34 ... Latch circuit, 56 ... RS flip-flop circuit.

Claims (2)

[Claims] 1. A syndrome detecting means for detecting a syndrome by dividing received data composed of an information bit and a redundant bit by a generator polynomial, and the syndrome output from the syndrome detecting means as an address, A storage device that stores binary information for bit position information having an error in the received data, which is determined from the syndrome, and stores and outputs the binary data, and the binary data from the storage device is stored in each bit of the received data. Each unit is provided with a unit for converting and outputting the data indicating the presence or absence of a bit error, and an error bit correcting unit for correcting the error bit of the received data using the data indicating the presence or absence of the bit error. Error correction circuit. 2. The storage device outputs data notifying only that the received data has an error when the bit position having an error cannot be determined from the syndrome. An error correction circuit according to claim 1.