JPS623619B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION When correcting bit errors occurring in digital data using a cyclic code, the present invention is capable of correcting errors in parallel in units of n bits, where n bits are an integer of 2 or more. The present invention relates to a bit error correction device that performs processing.

When transmitting digital signal data or storing data in a storage device, bit errors may occur in received data or data read from the storage device due to the influence of noise and the like. Generally, in such cases, a method is used in which redundant bits are added to transmit data as a code that follows algebraic theory, such as a cyclic code. Addition of such redundant bits and execution of error correction are conventionally carried out in a serial manner in which data is sequentially processed bit by bit, which has the disadvantage that error correction cannot be performed at high speed.

SUMMARY OF THE INVENTION The present invention aims to speed up error correction and provides an apparatus that performs error correction processing for n bits in parallel.

In explaining the present invention, a general bit error correction method will be explained.

When dealing with error correction codes, data is generally expressed as a polynomial. For example, when the data "10101" appears one bit at a time on the signal line from the left, this is expressed as x ⁴ +x ² +1. That is, it is expressed by a polynomial in which the bit that appears earlier in the time series is a series of higher-order terms of the polynomial. Next, this is divided by a polynomial called a generator polynomial, the remainder is subtracted from the polynomial representing the data to be transmitted, and this is used as transmission data. However, in calculations that handle binary values, ie, 0 or 1, calculations are performed modulo 2. Therefore, subtraction is the same operation as addition. i.e. ±1+0
It follows the rule: =1,0±0=0,1±1=0.

On the receiving side, the received data is divided by the previous generator polynomial. Since the remainder is subtracted from the transmitted data, if no bit error occurs during transmission, the received data will be divisible by the generator polynomial.
If a remainder occurs as a result of division, it can be considered that a bit error has occurred. In addition, by appropriately selecting the information bit length of the transmitted data and the generator polynomial, the position of the bit error and the error pattern can be determined based on the pattern of the remainder when the received data is divided by the generator polynomial (this is generally called a syndrome). can be determined.

By the way, when data is directly divided by the generating polynomial and the remainder is subtracted from the original data as described above, the resulting code looks different from the original data to be transmitted, which may be inconvenient to handle. For this reason, in general, after multiplying the data to be transmitted by the term of the highest degree of the generator polynomial,
The method used is to divide this by a generator polynomial. That is, for example, if the generator polynomial G(x) is G(x) = x ⁶ + ^{x 5 +} x ^{4 +} )
Divide by In other words, in an operation modulo 2, the remainder is x ⁵ +
Since x ⁴ +x, the transmission code is x ⁶ (x+1) + (x ⁵ +x ⁴ +x) = x ⁷ +x ⁶ +x ⁵ +x ⁴ +x. In this case, the first two bits match the bit pattern of the original transmission data.

FIG. 1 shows an example of a general error correction encoder and decoder. In the figure, 1 is an encoder, 2 is a decoder,
3 indicates a transmission path, □ indicates one stage of memory means using a shift register, and indicates exclusive OR.

The circuit shown in Figure 1 has a code length of 12, a ^data length of ⁶ , and a length of up to ³ , generated by the generator polynomial G(x) as follows ^: This is an example of a cyclic code that can correct dense errors (burst errors).

Algebraically speaking, the code generated by the generator polynomial in equation (1) above is a code with a code length of 15 and a data length of 9, but when this code is later applied to the present invention, it is handled by dividing it into 6 bits. An example is shown. Therefore, here, the upper three bits of the data part of the code are treated as 0, and the code length is shortened.

When the code length is shortened, when dividing by G(x) on the receiving side, an x term corresponding to the order of the shortened number of bits is received, that is, if the code length is shortened by 3 bits, ^x3 terms are received. Multiply the data and convert it to G(x)
What is being done is dividing by This is because the number of stages of the shift register for storing data when performing error correction is reduced by 3 bits.

4 in FIG. 1 is a division circuit using G(x).
Data consisting of 6 bits to be transmitted is input to encoder 1 through signal line 5 in the figure. The changeover switch 6 is initially set to the a side, and the data input from the signal line 5 is input to the divider circuit 4 and is outputted to the transmission line 3 via the changeover switch 6. When the transmission of 6-bit information is completed, each shift register of the divider circuit 4 has a remainder obtained by dividing the data multiplied by x ⁶ by the generator polynomial G(x), and the switch 6 is set to b. Turn to the side and return gate 8
After opening the shift register to prevent feedback, the contents of the shift register are sent to the transmission line 3.

Transmission data from transmission line 3 is transmitted from signal line 9 to G
(x) is input to the division circuit 11 and 12
Bit shift register 10 is entered. If an error bit occurs after the data and the remainder bits have been transmitted and input into the shift register 10, a syndrome has occurred in the divider 11, and the output of the shift register 10 is output. Signal line 15
While outputting one bit at a time, the contents of the shift register of the divider 11 are simultaneously shifted one bit at a time. This operation is repeated sequentially, and when all zeros are generated in the lower three bits of the shift register of the divider by the all-zero detector 12, the first c
Move the switch 16 that had been turned to the side to the d side,
The contents of the shift register of the divider 11 are outputted through the exclusive OR circuit 14, and the contents of the shift register 10 of the divider 11 are output.
The erroneous bits are corrected by performing an exclusive OR with .

Next, a parallel processing error correction apparatus according to the present invention will be described by way of an embodiment. FIG. 2 is a block diagram of an embodiment of an error correction device according to the present invention. In the figure, 20 is an encoder, 21 is a transmission path, and 22 is a decoder. First, the encoder and the combinational division circuit used therein will be explained. The data to be transmitted now is input to the encoder 20 from the signal line 23 in parallel every n bits (where n is an integer of 2 or more). The changeover switch 25 in the encoder 20 is initially turned to the a side, and the data input from the line 23 enters the parallel divider circuit 24 and is transferred to the changeover switch 25.
is output to the transmission line 21. Parallel divider circuit 2
4 is a generator polynomial G in units of n bits as described later.
This circuit performs division by (x), and when all bits of data have been input, the output signal line 37 receives the data
The remainder after dividing by (x) is output.

FIG. 3 shows the configuration of the parallel divider circuit 24 in FIG. 2. The data to be divided enters the combinational division circuit 53 via the exclusive OR circuit 52 via the input signal line 50 in n-bit parallel fashion. The combinatorial division circuit 53 is a circuit that divides the sent n bits by the generator polynomial, but as mentioned earlier, in order to distinguish between information bits and test bits, it multiplies the highest order term of the generator polynomial. The logic is to then divide by G(x). The output of the combinational divider circuit 53 is output to an output signal line 54, and is fed back to one input of the exclusive OR circuit 52 via the latch circuit 51. This is because the remainder generated from the combinational divider circuit 53 is added to the input signal that appears next on the input signal line 50. The specific operation shown in FIG. 3 will be described later using an example.

For the case of a cyclic code with a code length of 12 and a data length of 6, which is generated by G(x) = x ⁶ + x ⁵ + x ⁴ + x ³ + 1 (1), which was taken as an example in the case of the serial error correction method mentioned above, the parallel The division circuit is shown in FIG.
This is the case when data is processed as a 6-bit parallel signal.

In FIG. 3, the data serving as the dividend is input to the input signal line 50 in 6-bit parallel format. At this time,
The remainder generated on the signal line 54 prior to this is entered into the latch 51, and the input data and the output of the latch are exclusive ORed by the exclusive OR circuit 52 and entered into the combinational logic circuit 53. . The combinational logic circuit 53 includes 55 to 6 as shown in FIG.
It is composed of six exclusive OR circuits of 0, and the bits corresponding to the remainder when x ⁶ to x ¹¹ are divided by G(x) are input to the exclusive OR of 55 to 60. In FIG. 5, the remainders when x ⁶ to x ¹¹ are divided by G(x) are shown on the right side of each column of R ₁ to R ₆ . For example, the remainder when x ⁸ is divided by G(x) is R ₃
So, x ⁴ +x ² +x.

In FIG. 4, the outputs of exclusive ORs 55 to 60, that is, the output signal lines 61 to 66 are x ⁵ , x ⁴ . . .
The input of the exclusive OR circuit 55 which outputs the remainder bit of ^x5 is all the bits whose bits shown at the bottom of the x5 column in FIG. ⁵ are 1. It is a signal line. When a 6-bit signal is input as data to the input signal line 67 of the combinational division circuit 53, each bit has a weight of x ⁶ to x ¹¹ , and the output signal lines 61 to 66 have a weight of x ⁶ ~
The sum of all the remainders corresponding to the bit that is 1 out of ¹¹ bits is output. As a result, the remainder obtained by multiplying the data to be transmitted ^{by x6} and dividing this by G(x) appears on the output signal lines 61-66. This output signal line corresponds to the signal line 54 in FIG. An exclusive OR is performed by the exclusive OR circuit 52.

Now, in the encoder 20 of FIG. 2, 6-bit transmission data is input only once, so if the contents of the latch 51 are initially set to 0, then after one data input, the output 54 is A surplus appears immediately. If the data is 6 bits twice, i.e.
In the case of 12 bits, output 54 enters latch 51 and is exclusive ORed with the next 6 bit input.

In Fig. 2, 6-bit data is transferred to the transmission line 21.
After transmission, the changeover switch 25 is turned to the b side, and the output of the division circuit 24 is output to the signal line 21.

Next, the operation of the decoder will be explained. An example of a decoder configuration is shown within the solid line box 22 in FIG. In the decoder 22, the transmission data sent from the transmission line enters the bit-parallel storage means 27 through the input signal line 26, and enters the parallel divider circuit 29 via the first gate means 28. The parallel division circuit 29 has the same configuration as the parallel division circuit 24 in the encoder 20. The output of parallel divider circuit 29 enters multiplier circuit 30 . As described in the case of the serial error correction method, the role of this multiplication circuit is to correct the bit correspondence deviation that occurs between the data bits and the correction bit pattern when the code is shortened. , is a circuit that multiplies an x term (x ^l , where l is the number of shortened bits) of an order corresponding to the shortened number of bits. An embodiment of the multiplication circuit will be described later.

By multiplying by x ^l , the syndrome obtained from the divider circuit 29 can be made to match the error bit pattern. However, if the code is not shortened, this multiplication circuit 30 is not necessary.

The output of the multiplication circuit 30 is monitored by a zero detection circuit 31, which detects the sum of the numbers of zeros appearing on the upper bit side and the lower bit side of the output of the multiplication circuit, and detects when this sum is greater than or equal to a predetermined number. , the signal line 33 is set to logic 1, assuming that an error pattern has been detected. This opens the second gate circuit 34 and performs an exclusive OR between the output of the multiplication circuit 30 and the output of the data storage means 27. As a result, the logic of the data bit portion where the error occurred is inverted, and the error is corrected. However, the storage means 27 is of a shift register type in which the first input word is output every time one word is written. An embodiment of the zero detection circuit 31 will be described later.

Next ^, the generator polynomial G(x) used in the explanation of ^{the serial} error ^correction circuit can be expressed as The operation of the decoder 22 shown in FIG. 2 will be explained. As mentioned earlier, this code is an error correction code with a code length of 15, a data length of 9, and a check bit of 6, which can correct 3-bit clustered errors. Now, we will shorten this code to 12 bits, divide it into 6 bits each, and
Consider the case where bits are transmitted in parallel as one block.

Now, in this code, as an example of data 〓〓〓
Consider the case of transmitting 000011. However, here 3
Since the bits are shortened, the first 3 bits are always treated as 0 and ignored. If this code is expressed as a polynomial, it is x+1, and the encoder ²⁰ in FIG.
By adding the remainder after dividing by (x), a transmission code of x ⁷ +x ⁶ +x ⁵ +x ⁴ +x is generated. When written as a bit pattern, this is (000011110010), and since this is transmitted in parallel every 6 bits from the beginning, (000011), (000011), ( 110010) will be sent out sequentially. The decoder 22 in FIG. 2 receives these sequentially, but first receives (000011), takes this into the parallel storage means 27, and enters the parallel division circuit 29 via the gate means 28. The parallel divider circuit 29 has a configuration as shown in FIG. In FIG. 3, the latch 51 is initially set to 0, and the received data (000011) passes through the exclusive OR circuit 52 and enters the combinational logic circuit 53. The configuration of the combinational logic circuit 53 is as shown in FIG.
When an input of (000011) is obtained, the output is (110010). This output is taken into latch 51.

At the next timing, next data (110010)
is taken into the storage means 27 in FIG. At this time, (110010) also appears at the input of the parallel divider circuit in FIG. 3, and as a result of exclusive ORing between this and the output of latch 51, the outputs become all zero.
Therefore, the output of the parallel divider circuit is also zero, indicating that no error has occurred in this case, and at the next timing, the data stored in the storage device 27 in FIG. 2 is processed through exclusive OR. Output signal line 3 as is
It will be taken out on the 6th.

Next, as a result of an error occurring in the data (000011) and (110010) mentioned above in the transmission line 21 in Figure 2, the data bits changed by 3 bits to (001 x 1 x 1 x 1) and (110010). do. (3-bit burst error) At this time, (001101) is input to the parallel divider circuit of FIG. Since latch 51 is initially cleared, this data goes directly into combinational divider circuit 53, and (000011) appears at its output, which is stored in latch 51. Next, (110010) appears on the signal line 50, and by performing an exclusive OR with the latch 51, (110001) becomes an input to the combinational division circuit 53. At this time, the combinational division circuit 53
The output will be (100011). Since the original transmission data has been shortened by 3 bits, an error pattern can be obtained by further multiplying this by ^x3 . However, since the operation in this case is a multiplication modulo G(x), it is actually an operation of x ³ /G(x). Generally, the operation of x ^l /G(x) (l is an integer) can be realized with the same configuration as the combinational division circuit 53 shown in FIG.
The idea is the same.

In Figure 9, x ³ /G(x) (G(x) = x ⁶ + x ⁵
+x ⁴ +x ³ +1). In the figure, 70 is an input signal line, 71 is an exclusive OR circuit, and 72 is an output signal line. This circuit is equivalent to multiplication circuit 30 in FIG. Now, when the output (100011) of the combinational division circuit 29 of FIG. 2 described above is input to the input signal line 70 of FIG. 9, the output becomes (001110). This output is input to the zero detection circuit 31 shown in FIG. The zero detection circuit 31 monitors the sum of the number of zeros from one end of the input data and the number of zeros from the other end, and since the sum is 3 or more in this case, it is assumed that an error has been detected. The signal line 33 in FIG. 2 is set to logic 1 and the gate 34 is opened. At this time, the previous data (001101) stored in the storage means 27 mentioned above is read out and exclusive ORed by the exclusive OR circuit 35.

(0011001) (001110) = (000011) As a result, error-corrected data is taken out to the output signal line 36.

The 3-bit error pattern detected by the zero detection circuit 31 is as shown in FIG. 6, and the sum of the numbers of zeros at both ends is three. If the error is 2 bits or less, the sum of the number of zeros will be 4 or more.

Note that if an error occurs in the test bit, there is no particular need to correct it; however, if correction is necessary, input the two sets of data into the combinational division circuit 29 in FIG. 2, calculate the syndrome, and then By feeding this syndrome back to the combinational division circuit 53 through the latch 51 in FIG. 3, it can be handled in the same way as when an error occurs in the upper part of the data as described above.

Next, a configuration example of the zero detection circuit 31 shown in FIG. 2 will be explained. This is a specific number that is the sum of the number of signal lines that are logic "0" when counted from one end and the number of signal lines that are logic "0" counted from the other end on multiple parallel signal lines. (or more or less).

FIG. 7 is a block diagram thereof. In FIG. 7, 101 is k parallel signal lines whose number of 0's is to be detected. Connect these signal lines to S ₁ , S ₂ ,...
Let it be S _k . 102 and 103 are priority circuits, the circuit diagram of which is shown in FIG. In FIG. 8, 117 is k input signal lines, which are connected to i ₁ ,
i ₂ ...i _k . Of the input signal lines 117, i ₁ is directly connected to one of the output signal lines 118. This output signal line is O ₁ , and the rest are O ₂ ~ _{O k}
shall be. The signal line O ₂ ~O _k is AND gate 11
It is the output of each gate A ₂ to A _k of 6, and A ₂ to A k
The inputs of the AND gate of A _k are input with the signal lines i ₂ to _{i k} and the logics of the signal lines with lower subscripts than the input signal lines that are negated.

Now, if logic " ₁ " (hereinafter simply abbreviated as 1) is input to i 1, output signal line O ₁ becomes logic 1.
However, since the other output signal lines O ₂ to O _k are gated with the negation of i ₁ , the output is 0 regardless of the value of the input signal. Similarly, i _I (I
When 1 appears for the first time in natural numbers ≦k,
Gates below this are prohibited, and 1 appears only on the output signal line O _I. In other words, the priority circuit in Figure 8 is
This is a circuit in which logic 1 appears only in the output of the signal line that first becomes logic 1 when viewed from the _i1 side.

In FIG. 7, the input signal lines i ₁ to i _k of the priority circuit 102 are 101 signal lines S ₁ to S _{k ,} respectively.
In the priority circuit 103, the input signal lines are connected in exactly the opposite relationship to the case of 102, such as i _k to S ₁ and i ₁ to S _k . The outputs of the priority circuits 102 and 103 enter the encoders 106 and 107 via signal lines 104 and 105, and are input to the encoders 104 and 105.
2 corresponding to the position where logic 1 of the signal line occurs
Converted to decimal code. 110 is a binary addition circuit, which adds the binary codes obtained by 106 and 107. The output of the adder circuit 110 is 1
It is compared with the specific binary value given by the signal line 111 by the numerical value comparator 12, and if it is larger, it is 1.
1 is output to the signal line 13, if they are equal, 1 is output to 114, and if they are smaller, 1 is output to 115. As a result of the above, it is detected that a predetermined number of consecutive zeros indicated by the above-mentioned specific binary numbers have occurred at one end and the other end of the signal line 101, and it can be considered that an error pattern has been detected.

According to the present invention, by performing error correction on n bits of one data in parallel as described above, error correction processing can be speeded up.

[Brief explanation of the drawing]

Figure 1 is a diagram explaining a general error correction method.
FIG. 2 is a block diagram showing an embodiment of the parallel error correction system of the present invention, FIG. 3 is a diagram showing a parallel divider circuit used in the present invention, and FIG. 4 is a combinatorial divider diagram used in the parallel divider circuit. FIG. 5 is a diagram showing the logic of the combinational division circuit, FIG. 6 is a diagram explaining error bit patterns, and FIG. 7 is an example of the zero detection circuit used in the present invention. FIG. 8 is a diagram showing a priority circuit used in the zero detection circuit, and FIG. 9 is a diagram showing an embodiment of an arithmetic circuit for x ³ /G(x). 20... Encoder, 22... Decoder, 24... Parallel division circuit, 27... Storage means, 28... First gate means, 29... Parallel division circuit, 30... Multiplication circuit, 31 . . . zero detection circuit, 34 . . . second gate means, 35 . . . exclusive OR means.

Claims (1)

[Claims] 1 A reception method that corrects bit errors that occur during data transmission using an error correction method using a cyclic code, in which n bits of the cyclic code (n is an integer greater than or equal to 2, and each bit is _{a -1 a} o- ₂ . a first gate means for gating the received cyclic code; and a first gate means for gating the received cyclic code;
a dividing means for dividing the output from the gate means by an m-th order generator polynomial determined in the cyclic code and calculating the remainder; and an output b of the dividing means.
_n-1 b _n-2 …at b ₀ , b _n-1 +b _n-2 +……+b _n
The maximum i that satisfies _−i < 1 is i _nax , b ₀ +b ₁ +...
+b _i-1 < 1, where i' _nax is the maximum i, and zero detection means for determining i _nax +i' _nax , and the output of the zero detection means is greater than or equal to a certain value predetermined by the generating polynomial. a second gate means which outputs an output b _n-1 b _n-2 ...b _{0 of} the dividing means when it detects that
b _n-2 ... b ⁰ and the output of the storage means a _o-1 a _o-2 ...
has exclusive OR means for performing an exclusive OR with a ₀ and outputting this result as an error correction output, and
The dividing means feeds back the previously calculated remainder output to the input side, and divides the upper n bits of this remainder b _n-1 b _n
-2 ...b _no and the next n bits of data received
a' _o-1 a _{' o-2} .... After performing exclusive OR with a' ₀ , division is performed by the generator polynomial, and the upper m-n bits of the resulting remainder are b' _{n- 1} b′ _n-2 ...b′ _no and the lower bit of the previous remainder output b _no-1 b _no-2 ...b ₀
Take the exclusive OR between and get the result
b″ _n-1 b″ _n-2 …b″ An error correction device configured so that ₀ is output as a new remainder.