JPH049342B2 - - 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 deviations due to synchronization errors in data strings transmitted in blocks. The present invention relates to an error control device.

Hereinafter, for convenience of explanation, a case will be described in which data transmission is performed in one input data column, but similar processing can be realized even in the case where n columns of input data are transmitted in parallel.

It is recognized that errors in data transmission are often caused by 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 transmits the data. A system is adopted in which the data is sent out on the road, and on the receiving side, errors in each block are detected and corrected based on the redundancy of the transmitted data string.

A well-known and widely used method for adding this redundant bit string is a method using a cyclic code. Details of cyclic codes are described in detail, for example, on pages 190 to 243 of the publication "Coding Theory" published by Shokodo Co., Ltd. in 1973. This method will be explained below with 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 done modulo 2, that is, 0+0=1+1=0, 0
This is done with +1=1+0=1. ) Such a polynomial is called a generator polynomial, and an example thereof is x ³ +x+1. Using this generator polynomial x ³ +x+1, the redundant bit sequence is determined as follows. For example, for the information bit sequence 1101, the polynomial 1 and
x ^7-1 +1・x ^7-2 +0・x ^7-3 +1・x ^7-4 =x ⁶ +x ⁵ +
The sequence 001 corresponding to each coefficient bit of the remainder polynomial 0.x ² +0.x+1 when x ³ is divided by the generator polynomial x ³ +x+1 is added as a redundant bit sequence. Then, the series 1101001 is sent out onto the transmission path as one block. From this,
The polynomial corresponding to each block, each consisting of 7 bits, is constructed so that it is always divisible by the generating polynomial x ³ +x+1 unless a bit error occurs on the transmission path, and on the receiving side, the polynomial corresponding to each block is It is determined whether the sequence is error-free and permissible by dividing it by the generator polynomial and checking whether the coefficient bits of the remainder polynomial are all 0.

If it is determined that there is an error, the error bits in the received data bits are corrected based on each coefficient bit of the remainder polynomial. However, as it is, for example, a sequence obtained by cyclically shifting the sequence 1101001,
1110100, 0111010, 0011101, 1001110, 0100111,
1010011 are information bit strings 1110, 0111, and
0011, 1001, 0100, and 1010 are converted into a 7-bit series using the method described above. 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 synchronization Each 7-bit sequence that has become out of synch will become 1/2 2 and 1, respectively, if 2 bits, 3 bits, 4 bits, 5 bits, and 6 bits are out of synchronization with a probability of ^1/2 . Even if the sequence has a probability of /2 ³ , 1/2 ³ , 1/2 ² , or 1/2, it will still be accepted as a correct and acceptable sequence, even though it is wrong. The received sequence is then converted into an incorrect information bit sequence and received.

Therefore, conventionally, when transmitting a cyclic code, instead of sending it as is, a number of specific bits determined in advance of each block are inverted and then sent onto the transmission path. After inverting the specific bit of the received data string again and returning it to the original cyclic code, error detection and
Corrections are being made.

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 synchronization has been lost, the delimiter of each block is shifted by 1 bit, and if the coefficient bits of the remainder polynomial when dividing the polynomial corresponding to the new block by the generator polynomial are all 0, it is assumed that synchronization has been recovered. , if it is not 0, shift the delimiter of each block by one more bit and perform the same test,
Determining whether synchronization has been restored. Similar operations are continued until synchronization is restored, at which point normal bit error detection and correction operations are resumed.

However, in such a conventional method, after determining that synchronization is out of synchronization, in order to remove the influence of the erroneous inversion of the specific bit, at least one block length (the number of bits included in one block) is determined.
Therefore, the number of bits required for synchronization recovery is 1
This has the disadvantage that the number of bits is greater than the block length, and the synchronization recovery time is long.

The object of the present invention is to reduce the number of bits required for the above-mentioned synchronization recovery to at most (N
-1), and therefore the synchronization recovery time can be reduced.

According to the present invention, such a synchronization error control device receives a bit string in which a redundant bit string is added and a predetermined specific bit is inverted, and corrects bit errors and synchronization errors. The device includes a buffer register that stores the received bit string, a gate circuit that gates the bit string read out from the buffer register depending on the presence or absence of an out-of-synchronization detection signal, which will be described later, and a buffer register that stores the received bit string, and a gate circuit that gates the bit string read out from the buffer register depending on the presence or absence of an out-of-sync detection signal, which will be described later. a code polynomial division circuit which receives as input the bit sequence supplied to the buffer register and the buffer register, and inputs the bit sequence read from the buffer register to the code polynomial division circuit in response to an out-of-synchronization state. means for modifying the residual bit pattern of the code polynomial division circuit in response to a change in the bit string read from the buffer register in the process of establishing synchronization; means for determining whether the residual bit pattern obtained is a predetermined bit pattern and detecting whether or not the synchronization is out of synchronization according to the determination result; Depending on the bit pattern and the predetermined bit pattern, bit errors in the bit string read out from the buffer register are corrected and bit errors in the bit string read out from the buffer register are corrected. The error control device is realized as an error control device characterized by having as a component a means for inverting and outputting the bits of the error control device. Furthermore, the synchronization error control device according to the present invention has a redundant bit string added,
Further, in an apparatus for receiving a bit string obtained by inverting a predetermined specific bit of the redundant bit string and correcting bit errors and synchronization errors, the apparatus includes a buffer register for storing the received bit string, and a buffer register for storing the received bit string; a gate circuit that gates a bit string read from the buffer register depending on the presence or absence of an out-of-synchronization detection signal, which will be described later; and a code whose inputs are the bit string supplied from the gate circuit and the bit string supplied to the buffer register. a polynomial division circuit; means for inputting a bit string read from the buffer register to the code polynomial division circuit in response to an out-of-synchronization state; means for modifying the surplus bit pattern in response to a change in the bit string read from the buffer register; and whether or not the surplus bit pattern or the modified surplus bit pattern is a predetermined bit pattern. and means for detecting whether or not the synchronization is out of synchronization according to the determination result; The present invention is realized as an error control device characterized by having as a component a means for correcting bit errors in a bit string read from a buffer register and outputting the corrected bit errors.

Next, an embodiment of the 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 one embodiment of the present invention. In FIG. 1, a received bit string consisting of one block of N bits is divided into several consecutive blocks.
Buffer register 2 and sign polynomial division circuit 3
supplied to This received bit sequence is a sequence in which the predetermined specific bit is inverted as described above.

Note that each control pulse will be explained later using FIGS. 4 and 5, but it includes a master clock MCLK synchronized with the received bit string, a control pulse WCLK with a period N that matches the block length N, and It is assumed that at least a control pulse SCLK corresponding to the predetermined specific bit position is prepared. These control pulses are generated in a control pulse generation circuit indicated by reference numeral 4 in FIG.

Now, in FIG. 1, the gate circuit 5 inputs the received bits read out from the buffer register 2 one block length ago to the code polynomial division circuit 3.
It is a gate circuit that controls whether or not to send the
A control signal for this purpose is supplied via line 6. That is, the control signal supplied via line 6 is
The received bit of one block length ago is sent to the code polynomial division circuit, and if not,
This is a signal that sets line 7 to a low level state. The gate circuit 5 is, for example, an AND
Can be configured with a circuit.

Let's assume that no synchronization has occurred. At this time, it can be considered that there is no input from line 7, so the existence of this line can be ignored.

When the code polynomial division circuit 3 receives one block of data bits a _{1 '} , a _{2 '} , . ′x ^N-1 +a ₂ ′x ^N-2 +…a _N ′ is divided by the predetermined generator polynomial g(x), and each coefficient bit of the remainder polynomial r(x) is divided by the code polynomial. Stored in a register within the circuit.

In Fig. 2, code length N=7, generator polynomial g(x)=
An example of the configuration of a code polynomial division circuit in the case of x ³ +x+1 is shown. In Figure 2, 2-1, 2-2, 2-3
is an exclusive OR circuit, and R0, R1, and R2 are 1-bit registers. In this case, since there is no input from line 7, it can be considered that the input from line 1 is directly input to the exclusive OR circuit 2-2. Registers R0, R1, R2 contain 1
At the time when the received bits for the block, that is, 7 bits, are received, the coefficient bits r ₀ , r _{1 , and r 2} ^of the remainder polynomial r ₀ +r ₁ x+r ₂ x ₂ are stored, respectively.
Note that the division is executed using the master clock.
It is performed in synchronization with MCLK, but MCLK is shown in Figure 2.
has been omitted.

Furthermore, when performing division on the received bit string of the next block, in order to cancel the influence of the block, the control pulse shown in FIG.
Each register is cleared using WCLK.

The operation and principle of the code polynomial division circuit 3 are described on page 116 of the aforementioned publication, so the explanation will be omitted here.

By the way, let the predetermined specific bits be i ₁ , i ₂ , ..., i _s th bit, and the inversion polynomial P(x) is P(x)=x ^N-i1 +x ^N-i2 +...x ^{N- is} , the remainder polynomial r(x) when the received code polynomial A(x) is divided by the generator polynomial g(x) is the inverted polynomial P(x) unless a bit error occurs on the transmission path.
is equal to the remainder polynomial r￣(x) when divided by g(x). This is because, as mentioned above, the polynomial {A(x)−
P(x)} is the cyclic code itself, and is therefore configured to be divisible by the generator polynomial g(x). On the other hand, if block synchronization is not achieved correctly, the polynomial {A(x)−
The probability that P(x)} is divisible by the generator polynomial g(x) is extremely small, as stated in Japanese Patent Publication No. 43-11006 (which only mentions synchronization error detection and does not mention correction). Not known).

Therefore, the remainder polynomials r(x) and r￣(x) are
If they are not equal, is there a synchronization error?
It can be determined that either a transmission path error has occurred.

Since the probability that a bit error will occur over several blocks is small, for example, if the residual polynomials r(x) and r(x) are not equal in all eight blocks consecutively, at that point the out-of-synchronization detection pulse will be activated. is generated and the pulse is supplied on line 6 as the control signal.

This out-of-synchronization detection pulse is obtained by the out-of-synchronization detection circuit 11. This circuit consists of a bit pattern correction circuit 9 and a circuit 12 for generating an out-of-synchronization detection pulse. The bit pattern modification circuit 9 is a circuit that modifies the bit pattern output in parallel from the code polynomial division circuit 3 with the coefficient bit pattern of the remainder polynomial r(x). When the received bits of the block have been received, the difference between the remainder polynomials r(x) and r￣(x), that is, (r(x)
-r￣(x)).

Such a circuit uses the bit pattern and r￣(x) output in parallel from the code polynomial division circuit 3.
This can be realized as a circuit that takes the exclusive OR for each corresponding bit of the coefficient bit pattern.

Therefore, whether or not the output bit pattern of the bit pattern correction circuit 9 is a bit pattern of all zeros at the time when one block of received bits has been received indicates that synchronization is correct or that there is a synchronization error or a transmission path error. It can be determined whether this is occurring.

The circuit 12 is a circuit that counts the number of consecutive blocks of non-zero bit patterns and generates a synchronization error detection pulse when a predetermined count is exceeded. It is clear that it can be easily constructed using a gate circuit.

The synchronization error detection pulse generated by the circuit 12 is
It serves to shift various control signals sent to the control pulse generator 4 and output from the generator 4 by one bit.

On the other hand, the bit error detection pulse generating circuit 10 receives the output bit pattern from the correction circuit 9, and together with the correction circuit 9 constitutes a bit error position detection circuit 8.

The bit pattern supplied to the circuit 10 after receiving one block of received bits is as follows:
This is the coefficient bit pattern of the polynomial (r(x)-r(x)), and if there is no error on the transmission path and no synchronization error, the bit pattern will be all zeros. If the bit pattern is not all zeros, the error position corresponding to the bit pattern is detected by the circuit 10, and an error detection pulse is generated in synchronization with the output of the corresponding bit from the buffer register 2. is output from the circuit 10. The bit inverter 13 is constituted by an exclusive OR circuit, and inverts the error bit by the error detection pulse, and also inverts the error bit by the control signal output from the control pulse generator 4. This circuit also inverts the previously determined specific bit according to SCLK.

The specific configuration method of the bit error detection pulse generation circuit 10 has already been described on page 219 of the above-mentioned publication.
310 or PP.254-264, so the explanation will be omitted.

Furthermore, if all of the predetermined specific bits are redundant bits, there is no need to take the trouble to invert the specific bits in the bit inverter 13. This is because only the information bits are needed at the receiving end 14. Therefore, if all of the predetermined specific bits are redundant bits, the control signal
There is no need to input SCLK. Therefore, the configurations of the circuit 13 and the control pulse generator 4 are simplified accordingly.

Next, a description will be given of how the synchronization recovery operation is performed when the desynchronization detection pulse is supplied via line 6. First, when it is determined that synchronization is out of synchronization, it is necessary to shift the block separation of the received bit string by one bit.
By controlling the counter in the control pulse generator 4 using the out-of-synchronization detection pulse supplied via the line 6, the control pulse WCLK with a period N matching the block length N and the control pulse SCLK are generated. The generator 4 is delayed by one bit.
It is obvious to those skilled in the art that the output can be increased.

Furthermore, when the block delimiter is shifted by one bit, the coefficient bits of the remainder polynomial for the new block must be stored in the register of the code polynomial division circuit 3. To do this, it is necessary to cancel the influence of the first bit of the old block and incorporate the last bit of the new block.

For example, code length N=7, generator polynomial g(x)=x ³
+x+1, and the received bit strings are a ₁ ′, a ₂ ′,
. . , a ₇ ' is received as one block, and a ₂ ', a ₃ ', . . . , a ₈ ' are considered as new blocks for out-of-synchronization detection.

At the time of receiving the received bit a ₇ ', the code polynomial division circuit 3 contains a ₁ 'x ⁶ + a ₂ 'x ⁵ +...+
Coefficient bits of the remainder polynomial when a ₇ ' is divided by the generator polynomial g(x)=x ³ +x+1 are stored.

If we proceed directly to the next clock without canceling the influence of the received bit a ₁ ′, a ₁ ′x ⁷ +a ₂ ′x ⁶ +...+a ₇ ′x+a ₈ ′ will be stored in the code polynomial divider circuit 3. Coefficient bits of the remainder polynomial when divided by the generator polynomial g(x) are stored. However, as mentioned above, since the control pulse WCLK is shifted by one bit, the register in the code polynomial divider circuit 3 is not cleared and the process moves on to the next received bit _a8 '. It is necessary to keep this in mind.

Therefore, in order to eliminate the influence of received bit a ₁ ′,
The remainder when a ₁ ′x ⁷ is divided by the generator polynomial, that is,
It is sufficient to input a ₁ ' into the code polynomial division circuit 3 and subtract it at the time of processing the received bit a ₈ '. To this end, the leading bit of the old block that has passed through the gate circuit 5 is input into the code polynomial divider circuit via line 7 in FIG. More specifically, as shown in Figure 2,
The first bit of the old block that came through line 7
An exclusive OR circuit 2-1 is provided so that a ₁ ' is subtracted.

Generally, various code lengths are considered, and as mentioned above, a ₁ 'x ^N (N=7) is the generator polynomial g(x)
It is not necessarily divisible by . For example, in the above example, if N=6, the received bits
In order to remove the influence of a ₁ ′, the remainder polynomial when a ₁ ′x ⁶ is divided by the generator polynomial g(x)=x ³ +x+1
The coefficient ^bits (a ₁ ', 0, a _{1 '} ) of a _{1 '} I need to do it.

FIG. 3 shows a specific example of the configuration of the code polynomial division circuit 3 when the code length N=6. In Fig. 3, 3-1 to 3-4 are exclusive OR circuits, R0
~R2 is a 1-bit register. Line 7 is connected to exclusive OR circuits 3-1 and 3-4 so that the first bit _a1 ' of the old block that has come through line 7 is subtracted and input to registers R0 and R2. As mentioned above,
The structure is such that the coefficient bits (a ₁ ′, 0, a ₁ ′) of a ₁ ′x ² + a ₁ ′ are subtracted and input when the next received bit a ₇ ′ is processed. .

Therefore, according to the present invention, when an out-of-synchronization state is detected, it is possible to check whether or not the synchronization state is present by examining each coefficient of the remainder polynomial for each new block while shifting one bit at a time.

If the aforementioned out-of-synchronization detection pulse generation circuit 12 does not receive consecutive error blocks, that is, if it is determined that there is no error block even once, no synchronization error detection pulse will be generated, so at that point, the synchronization is locked. A counter for counting the number of consecutive error blocks in the out-of-synchronization detection pulse generation circuit 12 is configured to be cleared.

On the other hand, when a bit error occurs on the transmission path, the influence of the bit error is transmitted to the code polynomial divider circuit 3.
It will remain in the register. Therefore,
If synchronization is not restored even after shifting by one block, the counter for counting the number of consecutive error blocks is temporarily cleared. At this time, when the synchronization error detection pulse is cleared, the synchronization error detection pulse is not generated, and the synchronization is locked again, so that the control signal
At WCLK, the register in the code polynomial division circuit 3 is cleared as described above, and the division for N bits is newly executed from the beginning. Therefore, the influence of bit errors is eliminated.

However, since the probability that bit errors will occur over a large number of blocks is considered to be extremely low, the probability that such an operation will be performed many times is also considered to be extremely low. Furthermore, it is considered that the probability that the time point of synchronization recovery mode and the time point of bit error occurrence overlap is low. Therefore, the number of bits required for synchronization recovery can be considered to be at most (N-1) in most cases.

In the above explanation, the cyclic code with a code length of 7 was mainly used as an example, but codes with other code lengths can also be transmitted by fixing the first few bits of the cyclic code to 0. It is clear that the present invention is also effective for a shortened cyclic code in which the overall code length is shortened by avoiding the above, and is included within the scope of the present invention.

Furthermore, in the above embodiment, the case where blocks of code length N are received consecutively without any gaps was explained as an example, but it is also possible to receive the blocks with some dummy bits sandwiched between each block. 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 at most one block length. The recovery time is extremely reduced, and the effect of improving error control performance is significant.

[Brief explanation of drawings]

FIG. 1 is a block diagram showing a configuration example of an embodiment according to the present invention, and FIGS. 2 and 3 are diagrams showing a more specific example of the code polynomial division circuit in FIG. 1. In the figure, 1 is an input line, 2 is a buffer register, 3 is a code polynomial division circuit, 4 is a control pulse generator, 5 is a gate circuit, 6 is a line for selecting an out-of-synchronization detection pulse, and 7 is the buffer register. 8 is a bit error position detection circuit, 9 is a bit pattern correction circuit, 10 is a bit error detection pulse generation circuit, 11 is an out-of-synchronization detection circuit, 12 is an out-of-synchronization detection pulse generation circuit, 1
3 is a bit inverter, 14 is a receiving end, 2-1, 2-
2, 2-3, 3-1, 3-2, 3-3 and 3-
4 is an exclusive OR circuit, and R0, R1 and R2 are 1-bit registers.

Claims (1)

[Scope of Claims] 1. In an apparatus for correcting bit errors and synchronization errors by receiving a bit string in which a redundant bit string is added and a predetermined specific bit is inverted, the received bit string is A buffer register that stores the buffer register, a code polynomial division circuit that receives the bit string supplied to the buffer register, and a code polynomial divider that inputs the bit string read from the buffer register, and divides the bit string read out from the buffer register into the code polynomial divider in response to the out-of-synchronization state. means for inputting data to an arithmetic circuit; and means for modifying a residual bit pattern of the code polynomial division circuit in response to a change in the bit string read from the buffer register in the process of establishing synchronization;
means for determining whether or not the surplus bit pattern or the modified surplus bit pattern is a predetermined bit pattern, and detecting whether or not the synchronization is out of synchronization according to the determination result; Correcting bit errors in the bit string read from the buffer register depending on the bit pattern output from the polynomial division circuit and the predetermined bit pattern;
An error control device characterized in that it has as a constituent element means for inverting and outputting the predetermined specific bit of the bit string read from the buffer register. 2. In a device that receives a bit string to which a redundant bit string has been added and in which a predetermined specific bit of the redundant bit string is inverted, and corrects bit errors and synchronization errors, the received bit string is A buffer register to be stored, a code polynomial division circuit which inputs the bit string supplied to the buffer register, and a bit string read from the buffer register are subjected to the code polynomial division in response to an out-of-synchronization state. means for inputting into the circuit;
In the process of establishing synchronization, means for modifying the remainder bit pattern of the code polynomial division circuit in response to a change in the bit string read out from the buffer register; Determine whether the residual bit pattern is a predetermined bit pattern,
means for detecting whether or not the synchronization is out of synchronization according to the determination result; An error control device comprising as a component a means for correcting bit errors in a read bit string and outputting the corrected bit error.