JPH03186031A - Error correction system - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

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 data errors that occur in communication channels such as optical discs, optical discs, magneto-optical disks, and satellite communications, and in particular, the present invention relates to an error correction method that uses codes to detect and correct data errors that occur in communication channels such as optical discs, optical discs, magneto-optical discs, and satellite communications. Part 6 relates to a method for detecting and correcting errors due to misalignment.

[Conventional technology]

Data errors include bits that may be 0, 1, or 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 0 to 1 or from 1 to ○ will be simply referred to as an error, and a code for correcting it will be 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, with conventional correction codes that use 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 treated as errors. This may exceed the limits of error correction ability.
It was not possible to effectively correct synchronization errors. 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 invention]

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 that it reduces the overall transmission efficiency to a considerable extent. there were. 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 problem] In order to solve the above problem, the error correction method of the present invention uses a first method that generates parity by sequentially multiplying each bit of data to be transmitted by a different weight by l. 1 parity generation means, a second parity generation means for generating parity in which each bit of the received data is sequentially multiplied by a different weight by 1;
calculation means for performing a comparison operation between the parity generated by the parity generation means and the parity generated by the first parity generation means; and detection means for detecting an error in the received data with respect to the transmission data based on the calculation result of the calculation means. , and correction means for correcting the detected error according to the detection result of the detection means, thereby making it possible to correct synchronization errors caused by bit omission or bit insertion. [Embodiment 1] Hereinafter, a code for correcting a 1-bit synchronization error will be shown. Synchronization errors can be thought of as bit omissions, bit insertions, and the like, but first, the case of 1-bit omission will be explained. k-bit information sequence [I ,, I 11-1+・
..., engineering. (2), ], the transmitting side adds the next parity P+, which is obtained by multiplying each bit E in this information sequence by a weight l, and transmits it. P+=Σ111 (1) If a bit is missing during transmission (bit missing b1), then
On the receiving side, the next 11 bits of information sequence processing and the parity Pt shown in equation (1) are received. I' = [1,, Im-+, -...IIJIII
IJ-II..., 1. ．． 1. ]l' to P+, L+Ik-'+..., IJ+l+IJ-11.
..., II, II are multiplied by -1, ..., 1 and added in order to calculate Q. At this time, I J-1 and subsequent numbers are multiplied by a coefficient that is 1 larger than the subscript, and the calculation is performed as follows. Q,=Sie,・i+Σ−11・(i+1) where P,
-Q, is calculated as (2), where the IJ where the bit loss occurred is O and ■, =
1, then P + -Q + > O from j>Σ-11. Therefore, P+-Ql
The value of ■4 that caused the bit loss can be determined by the positive and negative signs of . Also, when Pl-Ql≦O (IJ = O), I J-
It shows the total number of bits with a value of 1 up to 1, and counting from ■, it can be seen that the bit shift due to the bit omission of I,=O starts from IP+'-Q+11001. Therefore, P r −Q +11001
If O is inserted to the left of , the missing bit IJ will be corrected. P+ −(If 1>O, pt −Q+ −1=j−1
-Σ-■1 indicates the total number of O's that caused bit shifts from 11 to I, -3. (For example, the total number is O.) Therefore, by inserting 1 to the left of the P+-Q+-1st 0, the missing bit due to ■,=1 is corrected. Next, consider the case of 1-bit insertion. On the transmitting side, the 11-bit I' mentioned above is used as an information sequence.
= [I-, L=-+, ...+L*l+ IJ-1
+..., 1. ．． 1. ] and its parity as the following Pl
Suppose you send p, =ΣI 1(i-1) +Σ"11・i
(4) During the transmission of this information series, I is inserted,
Considering that the above I is received on the receiving side, I =
[Ii++L+-z..., L-1, IJ, L-1,...
..., 1. ．． 1. ], so Q1 and Q, -P,
is expressed as follows. In formula (6), ■. If Q+-P+=-Σd■,=1, If =O, then ≦O, and. Q+-P+=j-t-Σ-■, 20. Therefore, if Q + P + < O, IJ = O
If Ql - PI > 0, I, = 1, and in these cases, the error due to bit insertion can be removed by knowing the error position and deleting that bit, using the same argument as in equation (3). . Also, in the case of Q+-P+=O, if Q, -pH=Q and I,=O, then -Σl1=0, so IJ-1=...=I+=0, and Q+ P+=0 and I , = 1, then Σ−J, =
Since I, -1=...=I+=1 from j-1, IJ=...=I in either case, so the least significant bit can be deleted. With the above steps, a 1-bit insertion error can be corrected. Next, consider the case where a simple 1-bit error occurs instead of a synchronization error. The information sequence is set to 1 on the transmitting side, and its parity is (1)
It is assumed that Pl of the formula is transmitted, and during transmission, error eJ is added to bit IJ, resulting in I4+eJ. (e, is I
When , is 1, it is expressed as -1, and when , is 0, it is expressed as 1. ) At this time, Ql and Q, -P are calculated as follows. Q, = Σ■, ・ i + e J ・ j
(7) Q+-P+=9.・j
(8) Here, eJ is 1 or -l, so (8
), the value of e can be determined by the sign of Q, -P, and the error position j can be determined by j=IQI-pH. Therefore, this should be corrected. In this way, simple errors of one bit can be corrected. As described above, bit 1 in the information sequence as shown in equation (1). By using the parity Pl of the present invention, which is multiplied by a weight i, it has become possible to correct 1-bit synchronization errors due to missing bits or bit insertions, as well as simple 1-bit errors. 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. In the figure, a multiplier 1 is added to each bit of the information sequence.
is multiplied by weight i by , and sequentially added to register 2 to generate parity P. The generated parity P is transmitted together with an information sequencer using a transmitter (not shown). 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. If one bit is missing during transmission in the information sequence sent by the transmitter, resulting in a parity P, the receiving side receives the parity P with a receiver (not shown), and the encoder 3 Generate parity Q1. Here, the configuration of the encoder 3 is the same as that shown in FIG. 1 used on the transmitting side. The comparator 4 compares the parity Q obtained by the encoder 3 with the received parity P, and according to the discussion of equation (3), for example, if P, ≦Q, the arithmetic unit 5 , Ql
-p, and select the result with select:ri7. On the other hand, counter j counts the number of 1s, the result is selected by selector l(, the comparator/corrector 11 compares the values of selectors 7 and 10, and inserts O to the left of Ql-P1100. , the omission of one bit is corrected. Also in the case of P + > Q I, the arithmetic unit 6 and the counter ≦
It is assumed that 1-bit omission can be corrected in the same way using . [Effects of the Invention] In the codes used in the present invention, k≧P, −Q, and ≧− +1, so P. Ql can be modulo 2. In this case,
2 to 1 ≧P, -Q, ≧+1 and 2P + -Q +
means a negative value, and the negative value is obtained by P+-Ql-2k, after which the location of the error can be determined according to the procedure shown here. Therefore, since the bits required for P+ are 1og*2, synchronization errors can be efficiently prevented with sufficiently small redundancy compared to performing resynchronization.

[Brief explanation of drawings]

FIG. 1 is a diagram showing a block configuration of an encoder according to a first embodiment of the present invention, and FIG. 2 is a diagram showing a block configuration of a decoder according to a first embodiment of the present invention. l ... 2 ... 3 ... 4 ... 5, 6 ... 7, IO ... 8, 9 ... 11 ... Multiplier Register Signer Comparator Arithmetic unit Selector Counter comparison / Corrector diagram Figure 2

Claims (1)

[Claims] An error correction method for correcting errors in received data relative to transmitted data, the first parity generation means generating parity by sequentially multiplying each bit of the transmitted data by a different weight by 1. and a second parity generation means for generating parity by sequentially multiplying each bit of the received data by a different weight by 1, and parity generated by the second parity generation means;
a calculation means for performing a comparison calculation between the parity generated by the first parity generation means; a detection means for detecting an error in the received data relative to the transmitted data based on the calculation result of the calculation means; and detection according to the detection result of the detection means. An error correction system characterized by comprising: a correction means for correcting an error caused by the error.