JPS6135579B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a device that automatically corrects errors caused by the transmission or accumulation of digital data, and particularly to a device that automatically corrects errors caused by synchronization errors in data strings transmitted in blocks. The present invention relates to an error control device for correcting errors.

It is generally recognized that many errors that occur during digital data transmission are due to noise on the transmission path. Conventionally, in order to avoid the effects of such noise, the transmitting side divides the information bit string into several blocks, adds redundant bit strings to each block according to a certain rule, and then A method is adopted in which the data is sent out onto a transmission path, and on the receiving side, errors in each block are detected and corrected based on the redundancy of the transmitted data string. As a method for adding this redundant bit string, a method using a cyclic code is a method that is generally well known and used. For more information about cyclic codes, see, for example, Shokodo Co., Ltd. in 1973.
P.190 of the publication “Coding Theory” published in
Details are given on page 243. This method will be explained below by giving an example.

For example, an information bit sequence is divided into 4-bit units, a redundant bit sequence consisting of 3 bits is added to each 4-bit information bit sequence, and the sequence is converted into a bit sequence where 1 block consists of 7 bits and sent out onto the transmission path. Let's talk about the case. in this case,
First, a polynomial whose coefficients are only 0 or 1 that divides the polynomial x ⁷ +1 is determined in advance. (However, division is modulo 2, i.e. 0+0=1+1
〓〓〓〓
=0, 0+1=1+0=1. ) Such a polynomial is called a generator polynomial, for example x ³
+x+1 is one example. This generator polynomial x ³ +
Using x+1, the redundant bit sequence is defined as follows. For example, for the information bit sequence 1101, the polynomial 1 x ^7-1 corresponding to this bit sequence is
+1・x ^7-2 +0・x ^7-3 +1・x ^7-4 =x ⁶ +x ⁵ +x ³ is divided by the generator polynomial x ³ +x+1 and each coefficient bit of the remainder polynomial 0・x ² +0・x+1 The corresponding sequence 001 is added as a redundant bit sequence. Then, the series 1101001 is sent out onto the transmission path as one block. From this, it follows that the polynomial corresponding to each block of 7 bits is constructed so that it is always divisible by the generator polynomial x ³ +x+1 unless a bit error occurs on the transmission path. The polynomial corresponding to the block is divided by the generator polynomial, and by checking whether the coefficient bits of the remainder polynomial are all 0, it is determined whether the sequence is error-free and acceptable.

In this way, if it is determined that there is an error, the error bit in the received data bits is corrected based on each coefficient bit of the remainder polynomial. However, in this state, for example, the sequences 1110100, 0111010, 0011101, 1001110, which are cyclically shifted from the sequence 1101001,
0100111 and 1010011 are information bit strings, respectively.
1110, 0111, 0011, 1001, 0100, 1010 are converted into a 7-bit series using the above method. Therefore, if a bit is lost or added during data transmission, and the delimiter of each block is shifted by, for example, one bit, that is, if synchronization occurs by one bit, The sequence of each 7 bits that caused the synchronization is
If there is a probability of 1/2, and if 2 bits, 3 bits, 4 bits, 5 bits, and 6 bits are out of synchronization, then 1/2 ² , 1/2 ³ , 1/2 ³ , and 1/2, respectively. 2 ² , with a probability of 1/2 that it will be accepted as a correct and acceptable sequence even though it is incorrect. The received sequence is then converted into an incorrect information bit sequence and received.

For this reason, conventionally, when sending a cyclic code,
Rather than leaving it as is, it inverts a number of predetermined bits in front of each block before sending it out on the transmission path, and on the receiving side, the bits in the specific bits of the transmitted data string are inverted again. Errors are detected and corrected after being inverted and returned to the original cyclic code. In this case, it is known that even if synchronization occurs, the probability that the sequence will be correct and acceptable is extremely small. Therefore, if the sequence is determined to be unacceptable for several blocks in a row, , it is determined that the error is not a simple bit error but is due to an out-of-synchronization. After determining that the synchronization is out of sync,
The delimiter of each block is shifted by 1 bit, the polynomial corresponding to the new block is divided by the generator polynomial, and if the coefficient bits of the remainder polynomial are all 0, it is assumed that synchronization has been recovered, and if they are not 0, the delimiter of each block is further Shift by one more bit,
A similar test is performed to determine whether synchronization has been restored. Similar operations are arranged to continue until synchronization is restored, at which point normal bit error detection and correction operations are resumed.

However, according to the above method, the number of bits required from the time when synchronization is determined to the time when synchronization is restored is between N and ^N2 , where N is the block length (the number of bits included in one block). Therefore, the drawback was that the recovery time was extremely long.

SUMMARY OF THE INVENTION An object of the present invention is to provide a synchronization error control device that can reduce the number of bits required for the above-mentioned synchronization recovery to 2N at most, thereby making the synchronization recovery time extremely short.

According to the present invention, in an apparatus for correcting bit errors and synchronization errors by receiving a bit string in which redundant bits are added and a predetermined specific numbered bit is inverted, A bit inversion circuit that inverts a predetermined specific number of bits, a buffer register that stores the bit string supplied via this bit inversion circuit, and an out-of-synchronization control (described later) for the bit string read from this buffer register. A gate circuit that gates depending on the presence or absence of a detection signal, a code polynomial division circuit that receives as input the bit string supplied from this gate circuit and the bit string supplied to the buffer register, and this code polynomial division circuit. The above synchronization is detected in the bit patterns that are output in parallel.
A correction circuit that makes corrections depending on the presence or absence of a signal, and a correction circuit that judges whether the bit patterns output in parallel from this correction circuit are all zero bit patterns, and detects the out-of-synchronization depending on the number of times it is judged as negative. means for outputting a signal; means for correcting a bit string output from the buffer register depending on the bit pattern output in parallel from the correction circuit; There is obtained an error control device comprising an inversion circuit and means for generating a clock pulse for controlling the code polynomial division circuit.

Next, an embodiment of an error control device according to the present invention will be described in detail with reference to the drawings.

FIG. 1 is a block diagram showing the structure of an embodiment according to the present invention. Note that this example shows a case where a cyclic code having the aforementioned generator polynomial x ³ +x+1 is applied. In the figure, a plurality of received bit strings with block length N=7, number of information bits per block of 4, and number of redundant bits of 3 are successively supplied from an input terminal 1 to a bit inversion circuit 2. In this received bit string, the predetermined specific bit of each block is inverted, but for convenience of explanation, it is assumed here that all redundant bits are inverted. The bit inversion circuit 2 is
As seen in the time charts showing the synchronization state in Figure 2 and the synchronization recovery process in Figure 3, this circuit inverts the redundant bits of the received bit string using the control pulse SCLK, and is composed of an exclusive OR circuit. can do. The configuration method of the control pulses in Figures 2 and 3 will be described later, but a master clock (MCLK) synchronized with the received bit string and control pulses WCLK and SCLK with a period of 7 are prepared according to the block length. shall be taken as a thing. The positions of count numbers 1 to 4 in FIGS. 2 and 3 correspond to the positions of information bits, and the positions of count numbers 5, 6, and 7 correspond to the positions of redundant bits.

Now, if the bit string supplied to the buffer register 3 and code polynomial division circuit 4 via the bit inverting circuit 2 is properly block synchronized, the redundant bits that have been inverted in advance when received are , is the received bit string (b in Figure 2) that has been correctly inverted, and if the block synchronization is not properly achieved, some redundant bits that were previously inverted when received remain uninverted. Moreover, this is a received bit string (b in FIG. 3) in which some bits other than redundant bits are inverted. Line 5 is a line that supplies a detection pulse when it is detected that the block is out of synchronization, and line 8 is a line that supplies a detection pulse from the buffer register 3 via line 6 depending on the presence or absence of this detection pulse. This line supplies a bit string obtained by gated bit string in gate circuit 7. The gate circuit 7 connects the line 5 and the output line 6 from the buffer register 3.
It is constructed by connecting them with an AND circuit.

Assume that at this point, the out-of-synchronization detection pulse is not supplied via line 5.
In this case, since there is no input from line 7 to code polynomial division circuit 4, the existence of this line can be ignored. And sign polynomial division circuit 4
is one block of data bits a ₁ , a ₂ ,...
_… When _{a 6} ^{and a} ₇ are ^received _{, the} remainder polynomial ( r ₁ x ² + r ₁ x + r ₀ ) each coefficient bit r ₂ , r ₁ , r ₀
are stored in registers 4-4, 4-3, and 4-2, respectively. Then, when performing division on the data bits of the next block, in order to cancel the influence of the data bits of the previous block, the control pulse WCLK shown in FIG. is used to clear registers 4-4 and 4-3. The operation and principle of the coded polynomial division circuit 4 are described on page 116 of the aforementioned publication, so
The explanation will be omitted here.

By the way, as mentioned above, the polynomial corresponding to each block is configured to be divisible by the generator polynomial x ³ +x+1, so as long as the blocks are properly synchronized and no bit errors occur on the transmission path, the registers 4-4, 4-3, 4-2
The remainder bits r ₂ , r ₁ , and r ₀ stored in are all zero. Furthermore, if block synchronization is not achieved correctly, the probability that the residual bits r ₂ , r ₁ , and r ₀ will all become zero is extremely small. For corrections, see 〓〓〓〓
(not mentioned) is already known. Also, at this point in time, the out-of-synchronization detection pulse is not supplied from line 5, so the correction circuit 9 that corrects the surplus bits r ₂ , r ₁ , r ₀
Output r ₂ , r ₁ , r ₀ as is. Therefore, if the output bit patterns r ₂ ', r ₁ ', r ₀ ' of the correction circuit 9 do not all become zero, it can be seen that either synchronization has occurred or a bit error has occurred. . Since the probability that a bit error will occur over several blocks is small, for example, if the output bit patterns r ₂ ', r ₁ ', and r ₀ ' of the correction circuit 9 do not all become zero in five consecutive blocks, At that point, it is determined that out-of-synchronization has occurred, and the out-of-synchronization detection pulse (c in FIG. 3) is supplied on line 5.

This out-of-synchronization detection pulse is obtained by the out-of-synchronization detection circuit 10. In this circuit,
The NOR circuit 10-1 is connected to the modification circuit 9, and outputs the output bit pattern r ₂ ' of the modification circuit 9.
This circuit detects whether r ₁ ', r ₀ ' are all zero, and outputs a detection pulse only when these bit patterns are all zero. When this detection pulse is output, it is assumed that no synchronization has occurred, and the counter 10-3 is cleared via the NOR circuit 10-2. The counter 10-3 is
It is driven by the control pulse WCLK shown in FIG. 2 and counts up. As a result, the number of consecutive blocks in which the modified surplus bits r ₂ ', r ₁ ', and r ₀ ' obtained from the modifying circuit 9 are not all zero is counted. This counter 10-3 is also cleared by an output pulse from the control circuit 11, which will be described later, when the out-of-synchronization detection pulse is output for a long period of time.
A NOR circuit 10-2 that performs a NOR between the output of -1 and the output of the control circuit 11 is provided. Further, the counter 10-3 is configured to output a count pulse when counting 4, for example. This count pulse and the NOR circuit 10-
AND circuit 10 that takes the logical product of the output pulses of 2 and 2.
-4 is, for example, when the modified surplus bits r ₂ ′, r ₁ ′, r ₀ ′ obtained by the modification circuit 9 for exactly 5 consecutive blocks are not all zero. It is used to output the desynchronization detection pulse immediately before entering the 6th block rather than from the start. By doing this, the synchronization recovery operation can be started immediately from the 6th block, as described below.

Next, a description will be given of how the synchronization recovery operation is performed when the desynchronization detection pulse is supplied via line 5. To this end, we will first describe how the control pulses shown in FIGS. 2 and 3 are generated by the control pulse generation circuit 12. First, a clock pulse MCLK synchronized with the received data bit string is output from the clock generator 12-1.
The counter 12-2 counts the number of pulses. The counted output is sent as a clear pulse to the counter 12-2 via the combinational logic circuit 12-3 when the count number of the counter 12-2 reaches six. In this way, by appropriately configuring the counter 12-2 for period 7 corresponding to the block length 7 and the combinational logic circuit 12-3, the control pulse WCLK as shown in FIGS. It is clear that and SCLK are obtained. Furthermore, since the time point at which the out-of-synchronization detection pulse is supplied is the time point when the second count number is 0, if the counter 12-2 is cleared by this out-of-synchronization detection pulse, the counter 12-2 2 will count 0 again and the clock will be shifted by 1 bit as a whole. Therefore, the next received bit is accepted as the last bit of the block.
The boundaries between blocks are also shifted by one bit. For this purpose, the line 5 and the output line of the combinational logic circuit 12-3 are connected to an OR circuit 12-4.
If the counter 12-2 is cleared by connecting the counter 12-2, a control pulse as shown in FIG. 3 can be obtained.

Even if the synchronization is shifted by one bit as described above, each register 4-4, 4-
It is necessary that the coefficient bits in the remainder polynomial of the new block for the bit pattern output (b in FIG. 3) of the inverting circuit 2 are stored correctly in 3 and 4-2. The operation will be explained below. First, immediately before the out-of-synchronization detection pulse clears the counter 12-2, it is stored in each register 4-4, 4-3, 4-2 of the division circuit 4.
The bits included are data bits for one block (b in Figure 3) 〓a ₆ ′, 〓a ₇ ′, ……, 〓a ₄ ″
，
The polynomial corresponding to a ₅ ″ (however, the bits marked with ~ indicate inverted bits) = _{a 6} ′x ⁶ + =a ₇ ′x ⁵ +…………+〓a″ ₄ x+a ₅ ″ These are the coefficient bits of the remainder polynomial when divided by the generator polynomial x ³ +x+1.The bit to be input as the last bit of the next new block is _a''6 . At this time, if no input is given from line 5 and line 8, the divider circuit 4 receives (〓a' ₆ x ⁶ +〓a' ₇ x ⁵ +…………+〓a ` <sub>`</sub> ⁴ x + a '^{' 5} ₎ a′ ₇ x ⁶ +a″ ₁ x ⁵ +a″ ₂ x ⁴ +〓a″ ₃ x ³ +〓a ₄ x ² +a″ ₅ x+a″ ₆ ………(2) Divide by the generator polynomial x ³ +x+1 Each coefficient bit of the remainder polynomial is stored in registers 4-4 and 4-4.
3, 4-2. To do this, equation (2) is obtained by adding 〓a′ ₆ x ⁷ to the polynomial in equation (1), and the monomial 〓a′ ₆ x ⁷ is added to the above-mentioned generator polynomial.
Since the remainder when dividing by x ³ +x+1 is 〓a' ₆ , the polynomial obtained by adding the polynomial 〓a' ₆ to the remainder polynomial when dividing equation (1) by the generator polynomial x ³ +x+1 is Each coefficient bit is stored in each register 4-4,
4-3 and 4-2. However, 1
Immediately before shifting the bit synchronization, the data bit 〓a' ₆
appears on the output line 6 of the buffer register 3, the data bit _a'6 is input to the divider circuit 4 from the line 8 via the gate circuit 7, thereby generating the equation (2). Each coefficient bit of the remainder polynomial when divided by the polynomial x ³ +x+1 is stored in registers 4-4, 4-3, and 4-2.

By the way, while the inverting circuit 2 generates the out-of-synchronization detection pulse, all the received bit strings are inverted, so at least (N+3)=10 bits after the out-of-synchronization detection pulse is generated, the register 4 -4, 4-3, and 4-2 store each coefficient bit of the remainder polynomial when the polynomial corresponding to the data bit string obtained by inverting the received bit string is divided by the generator polynomial x ³ +x+1. become. Also, suppose registers 4-4, 4-3, 4-
2, the data bit string of the regular block with all received bits inverted by the inversion circuit 2: a ₁ , a ₂ , a
₃ , polynomial corresponding to a ₄ , a ₅ , a ₆ , a ₇ 〓a ₁ x ⁶ +〓a ₂ x ⁵ +〓a ₃ x 4 +〓a ₄ x ³ +a ₅ ^{x 2 +} a ₆ x + a ₇ If the coefficient bits of the remainder polynomial when divided by the generator polynomial x ³ +x+1 are stored, the coefficient bits of this remainder polynomial are the remainder polynomial when the polynomial x ⁶ +x ⁵ +x ⁴ +x ³ is divided by the generator polynomial x ³ +x+1. x ² +
Equal to the coefficient bit of x+1. Because a ₁ x ⁶
＋a ₂ x ⁵ ＋a ₃ x ⁴ ＋a ₄ x ³ ＋a ₅ x ² ＋a ₆ x＋a ₇ is the generating polynomial
This is because the remainder polynomial when divided by x ³ +x+1 is 0. Therefore, when an out-of-synchronization detection pulse is generated, the correction circuit 9 consisting of a modulo-2 addition circuit, that is, exclusive OR circuits 9-1, 9-2, and 9-3, outputs a signal from the division circuit 4. By adding the supplied residual bits r ₂ , r ₁ , r ₀ and the coefficients 1, 1, and 1 of the residual polynomial x ² +x+1 modulo 2, the normal The correct modified remainder bits r ₂ ′, r ₁ ′, r ₀ ′ of the block are obtained.

Now, if these modified surplus bits r' ₂ , r' ₁ , r' ₀ are all zero, it is assumed that the out-of-synchronization has been resolved and synchronization has been restored, and the counter 10-3 is set as described above.
It is cleared by the detection pulse supplied via the NOR circuits 10-1, 10-2, but if the surplus bits are not all zero, the NOR circuits 10-1, 10-2 and the counter 10 Since there is no change in the output pulse -3, the out-of-synchronization detection pulse is still being supplied to line 5. Therefore, by further shifting the synchronization by one bit,
A similar operation will be performed. This operation continues until synchronization is restored and counter 10-3 is cleared, but since the block length is 7,
The number of bits within 2 x 7 = 14 bits at most, in this example 〓〓〓〓
Synchronization will be restored by shifting 10 bits. However, if a bit error occurs on the transmission path, the effect of the bit error will remain in the register of the divider circuit 4, so if synchronization is not restored even after shifting 10 bits, the counter 10- Clear 3 and start 7 from the beginning
It is necessary to remove the effects of bit errors by re-executing the bit division. However, since the probability of bit errors occurring over a large number of blocks is considered to be extremely low, the probability of performing such an operation many times is also considered to be extremely low.

The control circuit 11 is a circuit for removing the influence of this bit error, and includes a counter 11-1 and a counter 11-1 that count the number of out-of-synchronization detection pulses output from the out-of-synchronization detection circuit 10. Counter 1 when counts 10
0-3 and a combinational logic circuit 11-2 for outputting a pulse that clears the counter 11-1. Note that the counter 11-1 is driven by a master clock.

On the other hand, the bit error position detection circuit 13 is connected to the output line from the correction circuit 9.
Pulses are output depending on the bit patterns of registers 4-4, 4-3, and 4-2. This output pulse is then applied to the correction circuit 14, where the bit errors occurring in the bit string output from the buffer register 3 are corrected. The correction circuit 14 is composed of an exclusive OR circuit. Note that the specific method of configuring the position detection circuit 13 has already been described in the above-mentioned publication.
The explanation is omitted as it is written on P.219, P.310, or P.254 to P.264.

In the above embodiment, a case was described in which a cyclic code with a code length of 7 is received, and data bits in which all redundant bits are inverted are received, but codes with other code lengths or with other predetermined data bits are received. It will be readily understood from the above description that the scope of the present invention also falls within the scope of the present invention even when data bits in which predetermined specific bits are inverted are received.

Furthermore, in the above embodiment, the case where blocks of code length 7 are received consecutively without any gaps was explained as an example, but it is also possible that blocks with a code length of 7 are received with some dummy bits sandwiched between them. Needless to say, it can also be applied to cases.

As is clear from the above description, according to the present invention, with a simple configuration, the number of bits required for self-synchronization recovery can be reduced to a value that does not exceed two block lengths at most, and thereby, synchronization can be prevented. The recovery time is extremely reduced, and the effect of improving the performance of error control is significant.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the configuration of an embodiment according to the present invention, FIG. 2 is a team chart for explaining the operation of the embodiment in FIG. 1 in a synchronous state, and FIG. 3 is a block diagram of the embodiment in FIG. This is a time chart for explaining the synchronization recovery process. In the figure, 2 is a bit rotation circuit, 3 is a buffer register, 4 is a sign polynomial division circuit, 7 is a gate circuit, 9 is a correction circuit, 10 is an out-of-synchronization detection circuit, 11 is a control circuit, and 12 is a control pulse generation circuit. 13 is a bit error position detection circuit, 14 is a bit correction circuit, 4-1 is an exclusive OR circuit, 4-
2, 4-3, 4-4 are registers, 9-1, 9-
2, 9-3 are exclusive OR circuits, 10-1, 10
-2 is a NOR circuit, 10-3, 11-1 is a counter, 10-4 is an AND circuit, 11-2, 12-3
is a combinational logic circuit, 12-1 is a clock pulse generator, 12-2 is a counter, and 12-4 is a
It is an OR circuit. 〓〓〓〓

Claims (1)

[Claims] 1. A device that receives a bit string with redundant bits added and further inverts a predetermined specific bit, and corrects bit errors and synchronization errors. A bit inversion circuit that inverts a specific bit, a buffer register that stores the bit string supplied through the bit inversion circuit, and the presence or absence of an out-of-synchronization detection signal, which will be described later, for the bit string read from the buffer register. a gate circuit gated by the gate circuit, a code polynomial division circuit which receives as input the bit string supplied from the gate circuit and the bit string supplied to the buffer register, and outputs in parallel from the code polynomial division circuit. a correction circuit that corrects the bit pattern to be output based on the presence or absence of the out-of-synchronization detection signal; and a correction circuit that judges whether or not the bit patterns output in parallel from the correction circuit are all zero bit patterns; means for outputting the out-of-synchronization detection signal depending on the number of times; means for correcting the bit string output from the buffer register depending on the bit pattern output in parallel from the correction circuit; An error control device comprising means for receiving a detection signal as an input and generating a clock pulse for controlling at least the bit inversion circuit and the code polynomial division circuit.