JPH03186032A - error correction method - Google Patents

Abstract

PURPOSE:To correct an error in synchronism by comparing parity bits generated by 1st-4th specific parity generating means. CONSTITUTION:Respective bits of respective symbols of an information sequence I are applied to a register sequentially to generate parity P0. Further, the respective bits of the respective symbols of the information sequence I are weighted by a multiplier and applied to the register sequentially to generate parity P1. When the sent information sequence I has one bit lost during transmission to become I', a reception side which receives the parity P0 and parity P1 together with the sequence generates parity Q0 and parity Q1 by an encoder 3. A comparator 5 decides which of the parity Q0 obtained by the encoder 4 and the received parity P0 is larger and performs specific calculation. Consequently, the error in synchronism due to the bit omission or bit insertion by one bit can be corrected.

Description

[Detailed Description of the Invention] [Industrial Application Field] The present invention relates to an error correction method that uses codes to detect and correct errors in data that occur in communication channels such as optical disks, magneto-optical disks, and satellite communications. In particular, it relates to a method for detecting and correcting errors caused by data synchronization.

[Conventional technology 1] A data error occurs when a certain bit changes from O to 1 or from 1 to O.
There are two types of errors that can be considered: errors caused by a change in the number of bits, and errors caused by the omission of a certain bit or the insertion of an extra bit.

In the following, an error in which a bit changes from O to 1, or from 1 to 0, is simply referred to as an error, and a code for correcting it is simply referred to as an error code. The error is called a synchronous error, and the code for correcting it is called a synchronous error correction code.

Many studies have been conducted on error correction codes, and excellent codes for correcting random errors and burst errors have been proposed.

However, in the conventional correction 6 code that uses the Hamming distance concept, even if one bit is missing or inserted, all subsequent bits will be shifted, so all bits after the bit shift will be considered errors. It has not been possible to effectively correct synchronization errors because the limit of the error correction capability is exceeded.

Therefore, in the past, correction codes were not used for synchronization errors, and the occurrence of errors was prevented by frequently performing resynchronization.

[Problem to be Solved by the Inventionj] As the name suggests, a synchronization error is thought to occur when a clock or the like is out of synchronization with data. Depending on the communication system used, such errors may occur more frequently than simple errors, and the method described above, which requires frequent resynchronization, has the disadvantage of reducing overall transmission efficiency to a considerable extent. .

An object of the present invention is to solve the above-mentioned problems and provide an error correction method that can correct synchronization errors using simple codes.

[Means and operations for solving the problems] In order to solve the above problems, the error correction method of the present invention includes a first parity generation means that generates parity by the sum of each bit of transmission data, and a a second parity generating means that generates parity by sequentially multiplying each bit in a symbol by a different weight by 1 and then summing the sum for the entire symbol; and a third parity generating means that generates parity by summing each bit of the received data. a generating means; a fourth parity generating means for generating parity by sequentially multiplying each bit in one symbol of received data by a different weight by 1, and further summing the sum over the entire symbol; and the first parity generating means. a first calculation means for performing a comparison operation between the generated parity and the parity generated by the third parity generation means; and a parity generated by the second parity generation means and the parity generated by the fourth parity generation means. a second calculation means for calculating the exclusive OR of the corresponding bits of each symbol, and a calculation result of the first, second and third calculation means. By comprising a detection means for detecting an error in received data with respect to transmission data, and a correction means for correcting the detected error according to the detection result of the detection means, 1.
This makes it possible to correct synchronization errors caused by bit omissions or bit insertions.

[Example] In the following, a code for correcting a 1-bit synchronization error is shown.Synchronization errors can include bit omissions and bit insertions.
First, the case where one bit is missing will be explained.

The information sequence I of k symbols is [I□I−1...1,,
Ill. However, each I is a symbol consisting of q bits as follows.

I + = [r+, q+ Il, @-1+..., I
ll, Il, l] On the transmitting side, the next parity P , , P , , Rl is generated from this information series ■, added to ■, and transmitted.

Pa”Σ (s:Il,h) (1)P
l = Σ (Σ I , h - t)
(2) P , = EXORI I 1 (3) However, EXORΣ indicates the exclusive OR of each bit of I+, and a bit omission occurs during transmission in which a certain bit E J1 is omitted, and other bits are omitted. Error in bit e
If J and TI are added, I40. of symbol I is added.
Each bit except 1. ．． It is expressed as l+eJ,h.

(e4.h is IJ, when 11 is incorrect from O to 1, l, IJ
, 11 erroneously changes from 1 to O, it is expressed as -1, and when there is no error, it is expressed as O. ) From the received data, P o , P +
If we generate Q,,Q, using the same procedure as, we get the following.

Q + = P + I a, 1j + Σ
e7. h'j + Σh,.

(5) Therefore, Pa Q-1P+ Ql is expressed as follows.

What is undetermined in equation (7) are j and Σ−L. Therefore, when P, −Q, ≦0, j
Let X be X, and let Σ-L, which is the sum of shifts of 1 for each symbol up to x-1, be y, then the relationship between X and y is as follows from equation (7).

y= (QO-Pa)x-(pt-Ql) (
s) When Po-Qo≦, P+-Qt≦0 according to equation (7), so equation (8) changes from a positive value Q IP + to a negative value when x=O, as shown by the straight line a in Figure 3. It has a slope of , and changes according to X. On the other hand, the relationship between X representing the actual symbol position and the sum y of the deviations of 1 up to that point is, as shown by the straight line in FIG. 3, y=O when x=0, and increases monotonically as X increases. Therefore, straight lines a and b always have one intersection,
j is the direct expression of equation (7)! Since a and b representing the actual deviation should be satisfied at the same time, the value of X at the intersection of straight lines a and b is j.

Also, when Pa Q(1>O, j=x, it is the sum of the deviations of O for each symbol up to x-1 (x-1)
-"X-'X 1, is y, then equation (7) is y =-
(Pa −Qo−1) x+ (P IQ l−
1) (9) When P o -Q -> O,
From equation (7), P.

Since Q + 1 > O, equation (9) becomes (8)
Similarly to the equation, when x=0, as shown in the straight line a in FIG.

−1) and varies according to X.

Also, the relationship between X representing the actual symbol position and the total deviation y of O up to that point is as shown in b in Figure 3, where x=
When 0, y=Q, and it increases monotonically according to X. Therefore,
The same argument as when P, −Q, ≦0 holds, and the straight line a
The value of x becomes j at the intersection 0 point t7) of and b.

In the above manner, the synchronization including an error - the position j where the error occurs is obtained. The error pattern is j
It can be directly obtained by restoring the subsequent symbol deviations, determining symbols other than I, and EXORing symbols other than E to R1.

When an error occurs due to bit insertion, it is clear that synchronization errors including errors can be corrected by similar processing, considering that it is the opposite of bit omission.

Furthermore, although the case where the synchronization error is one bit has been explained here, this code can also correct random S-bit synchronization errors within one symbol using the same method as in the above embodiment. .

A simple example is shown below.

Assuming q=3 and k=゛5, the following information series and parity P
, ,P, ,R, is transmitted.

I= [111101000100100]P0=7 P, =5・3+4・2+3・0+2・1 +1−1=
26 old=010 Here, if a synchronization error including an error occurs in the symbol Is"[0003 of j=3 during transmission, and Is=[11] is incorrect, the received information sequence I° and the information calculated from it. Q,,Q, becomes as follows.

I = [11110111100100] Q0 = 7 P, = s・3+4・2+3・3+2・1+1・1=34
Therefore, Pa-Q6, P, -Q, becomes: P, , -Q, =7-9=-2 P+-Q, =26-34=-8.

Since P o −Q o≦0, according to equation (8), y
= (po-QO')X-(p+-Ql)=-2x
+8 This and y'="X-"1. Comparing the values of x=:
y and yo match only when . Therefore, j=3. ! Then, the subsequent symbols 1, , 1 . Restore Nozuzai,
Return the symbols other than ■ and salt, and confirm the symbols other than ■ as follows.

[11110,1777100100] By EXORing symbols other than I to R1, 1. = [0
00] is obtained, and the μs period error including the error is corrected.

Next, a method of implementing the present invention using an actual circuit will be described.

FIG. 1 is a diagram showing the configuration of an encoder used on the transmitting side of the present invention.

1st rI! In I(a), each bit I of each symbol I of the information sequence 1. I+ is in turn added to register 2 to generate parity Po. In FIG. 1(b), each bit I of each symbol E of the information sequence ■1.1
1 is multiplied by weight i by multiplier 3, and in turn register 2
is added to generate parity P1. The generated parity P, ,p is transmitted using a transmitter (not shown) together with the output signal R from the information processor EXOR.

FIG. 2 is a diagram showing the configuration of a decoder used when one bit is missing on the receiving side of the present invention.

When the information sequence I transmitted by the transmitter loses one bit during transmission and becomes ■°, the receiving side receives the parities P0 and Pl with the encoder 3 by a receiver (not shown). Parity Q, ,Q, is generated by. Here, the configuration of the encoder 3 is the same as that shown in FIGS. 1(a) and 1(b) used on the transmitting side.

The comparator 5 compares the parity Q0 obtained by the encoder 4 with the received parity P0, and according to the discussion of equations (7) to (9), for example, if P0≦Q0, y = < p o −Qo > x −< p r
-Ql) and selects the result using selector 8. On the other hand, the counter 9 counts the number l, the result is selected by the selector 11, the comparator/corrector 12 compares the values of selectors 8 and 11, and when the two match, the value of X is set as j, do.

In the manner described above, the position j where a synchronization error including an error occurs is obtained. The error pattern can be directly obtained by restoring the deviation of the symbols after j, determining the symbols other than ■, and EXOHing the symbols other than I to the RI.

[Effect of the invention] In the code used in the present invention, since q≧Pa-Qo≧-q, the bits necessary for p are log*2q, and the bits necessary for PlRl are each logs sk, q.

Therefore, for example, q=8. When = 253, the required number of parity pits is 4 pits for Po, and when only one bit of synchronization difference (s = = 1) is targeted,
This is necessary because 8 bits are required for each PIR1, so a total of 20 bits are required. Even compared to the Reed-Solomon code, which is said to have the lowest redundancy among linear error codes, in the case of one-symbol correction,
The Reed-Solomon code requires 16 bits, and the difference is only 4 bits. Considering that the code of the present invention is not just an error correction code, but also corrects synchronization errors, this is a sufficiently small redundancy. Aq. Synchronization errors can be efficiently prevented.

[Brief explanation of drawings]

1A and 1B are diagrams showing the block configuration of an encoder according to the first embodiment of the present invention, and FIG. 2 is a diagram showing the block configuration of the decoder according to the i embodiment of the present invention. FIG. 3 is a graph showing the relationship between signs. l, 2...3...4...5...6,7...8,11...9,lO...12...Register multiplier sign comparator operator selector Counter comparison/corrector Figure ■ ( ) Figure ( ) Figure 2

Claims (1)

[Claims] An error correction method for correcting errors in received data with respect to transmitted data constituted by a plurality of symbols consisting of predetermined bits, the first parity generation method generating parity by the sum of each bit of the transmitted data. a second parity generating means for generating parity by sequentially multiplying each bit in one symbol of the transmitted data by a different weight by 1, and further calculating the sum for the entire symbol; a third parity generating means for generating parity; a fourth parity generating means for generating parity by sequentially multiplying each bit in one symbol of received data by a different weight by 1, and adding the sum to the whole symbol; a first calculation means for performing a comparison operation between the parity generated by the first parity generation means and the parity generated by the third parity generation means; a second calculation means for performing a comparison operation with the parity generated by the four parity generation means; a third calculation means for calculating the exclusive OR of the corresponding bits of each symbol; An error correction method comprising: a detection means for detecting an error in received data relative to the transmitted data based on a calculation result of the calculation means; and a correction means for correcting the detected error according to the detection result of the detection means.