JPH04181833A - Synchronization error correction system - Google Patents

Abstract

PURPOSE:To detect and correct a data error including out of synchronism of a communication line by adopting a synchronization error correction code able to correct a synchronization error including an optional error within one symbol error for an information series for k-symbol each comprising q-bit. CONSTITUTION:A received data is blocked as shown in the following; a parity arranged at a head and a data are blocked for each prescribed bit number from the head of the received data, parities P0, P1, P3, P5, P7, P9 arranged at an end of a code word are blocked from the end of the received data for each prescribed bit number. Moreover, the parities P0, P1 are generated by handling the head parity as the data. In order to form each parity as bits of a multiple of (q), a dummy bit is inserted before and after the code series. A parity analysis section 4 at a receiver side counts bit number of the received data and the parities P0-P11 are blocked from the heat and the end for each prescribed bit number to separate them correctly.

Description

[Detailed description of the invention] [Industrial application field]

The present invention relates to an error correction system, and more particularly, to an error correction system capable of effectively detecting and correcting data errors, particularly synchronization shifts, in communication channels such as optical disks, magneto-optical disks, optical communications, and satellite communications.

[Conventional technology]

For example, errors in data on communication channels such as optical disks, magneto-optical disks, optical communications, and satellite communications include errors in which bits are reversed from 0 to 1 or from 1 to O, missing bits,
Or the error may be due to bit insertion. In the following explanation, an error in which an error is added to a certain bit and its value is reversed from O to 1 or from 1 to O will be simply referred to as an "error", and the code that corrects it will be referred to as an "error correction code". It is called. Furthermore, errors in which bits are shifted due to bit omission or bit insertion are referred to as ``synchronization errors,'' and the code that corrects them is referred to as ``synchronization error correction code A.'' Much research has been conducted on error correction codes until now. ,
Codes that are superior to random errors and burst errors have been proposed.

[Problem to be solved by the invention]

However, error correction codes cannot effectively correct synchronization errors. This is because even if the synchronization error is one bit missing or one bit inserted, all the bits after that will be shifted, and according to the conventional Hamming distance concept, all the bits after the bit shift will be errors. This is because the error correction capability exceeds the limit. In addition, synchronous error correction codes are not very effective in practice because they only deal with synchronous errors and do not consider cases where other errors occur due to bit reversal. As the name suggests, a synchronization error is thought to occur when a clock or the like is out of synchronization with data. Such synchronization errors may occur more often than simple errors, depending on the communication system used. Furthermore, when such a synchronization error occurs, it is expected that errors due to bit inversion will also occur concentrated before and after the synchronization error. However, until now no code has been proposed that simultaneously corrects errors and synchronization errors.

[Problem to be solved by the invention]

The present invention has been made for the purpose of solving the above-mentioned problems, and includes the following configuration shown in FIG. 1 as a means for solving the above-mentioned problems. FIG. 1 is a functional block diagram of an embodiment according to the present invention, and the function can be achieved by a hardware configuration or by a CPU.
This may also be achieved by providing a CPU and operating the CPU using a program. That is, it is an error correction system that corrects errors in received data with respect to transmitted data constituted by a plurality of symbols consisting of predetermined bits, and at least on the transmitting side 100, error positions are detected when the weights of received data with respect to transmitted data 101 are different. weighted parity generation means 102 that generates parity for detecting error positions; and error parity generation means 103 that generates parity for detecting error positions in cases other than when the weight of received data with respect to transmission data is not different and the pattern of error symbols deviates. , deviation parity generating means 104 for generating parity for detecting the error position when the weight of the received data is not different from the weight of the transmitted data and the pattern of the error symbol is only shifted,
In both cases, the receiving side 200 includes a weight parity detection means 202 for detecting an error position from parity when the weight of the received data is different from the weight of the transmitted data 201, and when the error symbol pattern deviates when the weight of the received data is not different from the transmitted data. Error parity detection means 203 that detects error positions other than the above from parity; and shifted parity detection means that detects error positions from parity when the weight of received data with respect to transmission data is not different and the pattern of error symbols is only shifted. 204. Alternatively, the following configuration shown in FIG. 2 is provided. In other words, it is an error correction system that corrects errors in received data with respect to transmitted data consisting of a plurality of symbols consisting of predetermined bits. A first parity Pa generation means 151 that generates parity Pa, and a second parity Pa generation means 1 that multiplies the sum of bits that are set to 1 in one symbol of transmission data by a certain different weight.
52, a third parity Pa generation means 153 that calculates the sum of the binary representation of the bit that is the first 1 in one symbol of the transmission data as the least significant bit; The fourth parity Pa generating means 154 adds a value expressed in binary by multiplying the bit expressed as a binary number by a certain different weight, with the bit where 1 is set as the least significant bit; A fifth parity Pa generating means 155 calculates the sum of the values expressed in binary as the lower bits, and a fifth parity Pa generating means 155 calculates the sum of the values expressed in binary numbers as the lower bits, and inverts the transmission data and sets the first bit of 1 in one symbol to 2 as the least significant bit.
The sixth step is to multiply and add a value expressed in base numbers by a certain different weight.
The parity P of the generation means 156 and the seventh parity P consisting of the sum of the number of consecutive 1 bits between symbols of transmission data
parity Pa generating means 157, and eighth parity P generating means 158 which multiplies the number of consecutive 1 bits between symbols of transmission data by a certain different weight and adds the result.
a ninth parity Pa generating means 159 consisting of the sum of the number of consecutive O bits between symbols of the transmission data;
A tenth parity P that is added by multiplying the number of consecutive O bits between symbols of transmission data by a certain different weight.
a generation means 160, and an eleventh parity P consisting of the sum of the number of consecutive O bits up to the first 1 in one symbol of the transmission data. a generating means 161, and a twelfth parity Pa generating means 1 consisting of the sum of the number of consecutive 1 bits up to the first 0 in one symbol of transmission data;
62, at least on the receiving side, the received data 201
The first one that generates parity by the sum of the bits that are set to 1.
a second parity Pa generating means 252 that multiplies and adds a certain different weight to the sum of bits that are set to 1 in one symbol of received data; A third parity Pa generating means 253 calculates the sum of the values expressed in binary numbers with the bit where 1 is set as the least significant bit, and a value expressed in binary numbers where the first bit where 1 is set in one symbol of the received data is the least significant bit. a fourth parity Pa generating means 254 which multiplies and adds a certain different weight to the received data, and a fourth parity Pa generating means 254 which inverts the received data and calculates the sum of the values expressed in binary numbers with the first bit set to 1 in one symbol as the least significant bit. 5 parity Pa generation means 255, and a sixth parity P that inverts the received data and adds a value expressed in binary with the first bit set to 1 in one symbol as the least significant bit, multiplied by a certain different weight.
a generating means 256, and a seventh parity P consisting of the sum of the number of consecutive 1 bits between symbols of received data.
a generation means 257, an eighth parity Pa generation means 258 which multiplies the number of consecutive 10 bits between the symbols of the received data by a fixed different weight, and adds the sum of the number of consecutive 0 bits between the symbols of the received data. a ninth parity Pa generation means 259 consisting of; and a first O parity P9 generation means 2 which multiplies the number of consecutive O bits between symbols of received data by a fixed different weight and adds the result.
60, an eleventh parity P Io generating means 261 consisting of the sum of the number of bits in which O stands at the beginning in one symbol of received data, and O stands at the beginning in one symbol of received data. a twelfth parity Pz generating means 262 consisting of the sum of the number of consecutive bits of 1 up to;
the first parity Po, the second parity P1 and the first parity Po;
The error position when the weight of the received data relative to the transmitted data deviates by more than 1 from the intersection of the straight line generated from the parity P, and the second parity P1, and the straight line representing the symbol deviation of the actual communication data. If the first error position detecting means 270 to detect and the weight of the received data with respect to the transmitted data differ within 1, the error position is generated from the difference in weight of other symbols or the parity of the above-mentioned 22 to P- and Qz to Q9. (P+++ -Q+++)/ (P i-Q
i) (i = 2゜4.6.'8), and the second error position detection means 271 detects the error position using Pi-Qi (i = 10.11). Error position checking means 271 is provided.

[Operation] With the above configuration, it is possible to propose a code for correcting synchronization errors including errors that occur in communication data, and to provide a synchronization error correction system that corrects synchronization errors including errors using the code. This synchronization error correction code is capable of correcting synchronization errors including any errors within one symbol in an information sequence of symbols with q bits as one symbol.

【Example】

Hereinafter, one embodiment of the present invention will be described in detail with reference to the drawings. <Configuration of the system of this embodiment> FIG. 3 is a block diagram of a synchronization error correction system according to an embodiment of the present invention. The control unit that controls the
Reference numeral 2 denotes a ROM in which a program, etc., which will be described later, is stored; 3, a reception section that receives reception data including parity from the communication path 11; 4, a parity analysis section that analyzes the parity of the reception data received by the reception section 3; 5; 6 is a reception buffer, 6 is a parity generation unit that generates synchronous error correction parity etc. from the transmission data from the control unit 1, and 6 is a transmission buffer that temporarily stores the transmission data to which parity has been added. Further, 15 is a host that sends and receives communication data. Error Correction Principle of this Embodiment> The principle of synchronous error correction carried out in the control section 1, parity analysis section 4, and parity generation section 6 of this embodiment having the above configuration will be outlined below. Now, the information series ■ to which data is transmitted from the transmitter 7 is set to [1
,,1,9,...,I2. I, ]. However, 〈〉 is a symbol consisting of q bits as shown below. (I+, = represents bit) L= [L9,,L
Q-9,...L, 2. L9, ] Next parity P from the transmitter. -P++ is generated and sent together with ■. However, the following is an integer operation. p, = Σ (Σ 1.9,) (1) P,
=Σ(Σ 11..)・i (2)P2=Σr
all (3) P3=ΣI
*z ・i (4) p, = Σengine. 1 (5) Ps”Σ■1゜,・i
(6) Pg”Σ (s 1 , +r
1 +-+) (7) P, = Σ (s 1
, +r 1 +-+) ・i (8)P, =Σ
(s O+, + r O+-+) (9) P,
=Σ (s O+・+ r O=−+) ・i
(10) P. =Σ sl, (
11) P3. =Σ so+ (1
2) Here, Sl9 and So represent the number of bits counting from the LSB in the i-th symbol until the first 1 or 0, respectively. Also, I all is 2 in the i-th symbol with 81□+1st bit as the least significant bit.
Value expressed in base number, ie. I 5+1 ” I 1.h ・2h−1・2nd information sod Ql is expressed, I sa+ is the value obtained by inverting 1°0 in the i-th symbol, R+, r+ = (I +
, h + 1) mod 2, the value expressed in binary with the sol+1st bit as the least significant bit, ie. I8゜I = R1,h ・2h−1・2−(iol+″
06q). (1, 9, , 1, . 1 is a binary representation of 1 and 0 from the bit where 1.0 is set first, and here, it is a branch chain due to l and a branch chain due to O, respectively. In addition, r 1 l-+ and r 0I-r represent the number of bits counting backward from the MSB in the i-1th symbol to the last bit where 1.0 stands. Therefore, S1+ +r 1+-+ , sO+ +rO+
−+ represents the number of consecutive 1 or 0 bits from the i-1th symbol to the i-th symbol. Further, i' represents a positive odd number. Therefore, in formulas (7) to (lO), sl+ +rl
B-+, so+ +rO+-+ are calculated every l symbol. Here, bits ■1 in symbol ■3 during transmission. ．． is omitted and the error eJ,h is added to the other bits of ■, then each bit of symbol Ij except Ij,9 becomes I,1
．． h+6,1. It is expressed as h (eJ, h is 1 when the engineering jh is incorrect from O to 1, and -l when the engineering 9, h is incorrect from 1 to 0.
, expressed as O when there is no error). In addition, the receiving side knows in advance the parity P o "" P r and the total number of bits of the code word consisting of the information sequence I, and a synchronization error occurs because the number of bits of the received data is the same as the code word. Suppose that it can be detected because it is different from the number of bits. At this time, synchronization errors including errors can be corrected by the following three procedures. (Step 1) Correction of errors with different weights The weight of the incorrect symbol due to a synchronization error including an error is
Error correction when it changes between sending and receiving. Alternatively, even if the weight of a symbol erroneously caused by a synchronization error that includes an error does not change between transmission and reception, error correction is performed when the weights of symbols that have been shifted are different before and after the synchronization error symbol. In this case, parity P is generated from the weight of the transmitted data. , Pl determines the error position. (Step 2) Correcting errors with slightly different weights without changing the weights of symbols erroneously caused by synchronization errors, including errors that could not be corrected in step 1, do not change between transmission and reception;
Error correction when the weight of the shifted symbol also does not change. The error position is determined in P2 to P5. However, it is assumed that the branch chain of erroneous symbols differs between transmission and reception. (Procedure 3) Procedure for correcting errors where weights and branches are not different 1.
The weights and branch chains of incorrect symbols due to synchronization errors, including errors that could not be corrected in step 2, are not converted between transmission and reception, and
Error correction when the weight of the shifted symbol also does not change. Hereinafter, steps 1 to 3 will be explained in detail. [Procedure 1] Error correction method with different weights From the received data, perform the same calculation as P9 and P to obtain the next Q. , Ql is generated. Qo” Po−I9, p・j+Σe1.
(13) Ql= PI-IJ, p'j+Σ ej,
h'ko+Σ L9, (14) Therefore, Po−Q
9, P, -Q, is expressed as follows. P, -Q, =I9,, -Σ eJ, h
(15) P, -Q, = (L, -ΣqeJ, h)
j-'X-I 1, q= (P, -Qo) ・j
-'
It is. Therefore, let j; When q is y, the relationship between X and y is as follows from equation (16). y=(Po Q.) X-(PI-Q, ) (
17) From equation (16), PI-Q<O, so equation (
17) is a positive value Q when x=00, like the straight line a in Figure 4.
, -P, is expressed by a straight line that monotonically decreases as X increases. However, the relationship between X representing the actual symbol position and y, the total deviation of 1 up to that point, is monotonically non-decreasing from the value of y=O when x=O as shown by the straight line in Figure 4. (When 1.,=1, it increases, but when 1.Q=O, it does not change with respect to X). Therefore, straight lines a and b always have one intersection. Since j should simultaneously satisfy the straight line a in Equation (17) and the straight line S representing the actual deviation, J is the value of X at the intersection of a and b. [When (P, -Q, ) > 1, let j = x, and the sum of the deviations of 0 for each symbol up to x-1 (x-1) ~ Σ ■, 9 is the equation (16 ) becomes as follows. 3' = (P o Q o 1) x+
(P, -Q, -1) (18) Formula (16)
Since (P, -Q, -1)>O, equation (18), like equation (17), is a positive value P, -Q when X=O, as shown by straight line a in Figure 1. , expressed as a straight line that monotonically decreases from -1 to X. Also, the relationship between X, which represents the actual symbol position, and y, the total deviation of O up to this point, is as shown by the straight line in Figure 1, where x = O.
When y=Q, the value becomes monotonically non-decreasing according to X. Therefore, the same argument as when (Pa Qo)<Q holds true, and the value of X at the intersection of straight lines a and b becomes j. [When PO-Qo = Q or Pa-Qo = l]
Po-Q0:KaP. - When Q0=1, formula (17)
, (18) is parallel to the X axis as shown in FIG. At this time, if the straight line representing the actual deviation continues to increase monotonically before and after the intersection with straight line a, then straight line a
and b intersect at one point, and the error position j can be specified. but,
As shown in FIG. 5, when the straight line stops increasing from the point where it intersects with the straight line a, the straight lines a and b do not intersect at one point and the error position j cannot be specified. When P, -Q0=O, it means that the weight of the symbol in which the error occurred does not change, and the part where the straight line does not increase means that 1.9,=0 is continuous. That is, it means that the weight of the symbol does not change due to the shift. In the case of Po-Q0=1, a similar argument holds when considered with a weight of 0. Therefore, it can be seen that the only case that cannot be corrected by the operation in step 1 is when the weight of 0 or 1 of each symbol is erroneously changed so as not to change due to a synchronization error including an error. Therefore, if the error position cannot be identified by the operation in step 1, the synchronization error position including the error is determined using P2 to P as follows. The next Q is calculated from the received data by calculations similar to P9 and P.
. Generates +Q+. Qo'' P(+-, IJ, p'j+ΣeJ, h(13
) Paste = P+-I=, p'j+Σqe7. l'l'
j+'X−L, , (14) Therefore, P, −Q9
, P, -Qo is expressed as follows. Po-Go=IJp-ΣeJ, n (
15) P, - pasted = (IJ9, -Σ eJo)・j-Σ
-■, 9= (P Q-QO) -j-'nee Il,
Q (t6) What is undetermined in equation (16) are j and Σ 1. , Q. So (Pa −
Q, ) <. When j=x, Σ I 1, which is the sum of 1 shifts for each symbol up to x-1. When Q is y, the relationship between X and y is expressed by equation (16
) becomes the following. 3'= (Po Qo) x (P + Q+
) (17) When P, -Q, from equation (16) P
Since +-Q+<0, equation (17) is the straight line a in Figure 4.
It is expressed by a straight line that monotonically decreases from the positive value Q, -P when x=O. However, the relationship between X, which represents the actual symbol position, and y, the total deviation of 1 up to that point, is the fourth
As shown in the straight line shown in the figure, when x=o, the value of y=Q is monotonically non-decreasing according to X (when I, Q=1, it increases, but when I9, Q=O, it increases with (no change)
. Therefore, straight lines a and b always have one intersection. Since j should simultaneously satisfy the straight line a in Equation (17) and the straight line S representing the actual deviation, the value of X at the intersection of the straight line lea and the straight line S is j. Also, when (Pa - Qo) > i, j=x. It is the sum of the deviations of O for each symbol up to x-1 (x-
1) -Σ-L9, is y, then from equation (16), when (Po -Qo ) > 1, (PI
-Q, -B >o, so equation (18) becomes equation (17)
Similarly, it is expressed by a straight line that monotonically decreases in accordance with X from the positive value (P, -Q, -1) when x=0, like the straight line a in FIG. In addition, the relationship between X representing the actual symbol position and the sum y of the deviations of 0 up to that point is also monotonically non-decreasing from the value of y = Q according to X when x = O, as shown in Figure 4, line 11b. Become. Therefore, the same argument as when (P, -Q.)<0 holds true, and the value of X at the intersection of straight line a and straight line S becomes j. At this time, in order to find the original value of IJ where the error occurred,
The deviations of the symbols after j, where deviations have occurred, are restored to the original state, and the symbols other than I are determined. From P R+ P 10, Iall of the confirmed symbol
+ Sll (1"1"'n+ 1≠j), 1. ,J,SL, is obtained,■,.・
21m1J mo6 Ill =: ■9.・2h-
From the operation of 1, the original value of . The above is a method for correcting synchronization errors including errors when o>(po-Qo)<1. However, when P, -Q,=Q or Pa-Qo=t, the straight line a representing equations (17) and (18) becomes parallel to the X axis as shown in FIG. At this time, if the straight line representing the actual deviation continues to increase monotonically before and after the intersection with the straight line a, the straight line a and the straight line A intersect at one point, and the error position j can be identified. However, as shown in FIG. 5, when the straight line IS b stops increasing from the point where it intersects the straight line a, the straight line a and the straight line A do not intersect at one point, making it impossible to identify the error position j. P, -Qo=O means that the weight of 1 of the symbol with an error does not change, the straight line increases, and the missing part is I
9, q=O is continuous, meaning that the weight of 1 in the symbol does not change due to the shift. Therefore, it can be seen that the only case that cannot be corrected by the operation in step 1 is when the weight of O or 1 of each symbol is erroneously unchanged due to a synchronization error including an error.゛ Therefore, if the correction could not be made using step 1,
Using P2 to P, synchronization errors including errors are performed as follows. (Step 2) Without correcting errors with only a few different kernels without changing the weight,
Here P, -Q. Consider the case where =0. If the error position J could not be identified by the operation in step 1, there are no errors other than the symbols for which the error position could not be identified, so first, restore the deviation to p2. A value P2° p,° is calculated by subtracting the value of Iall+811 of the symbol whose deviation has been restored from p,. If j cannot be specified between symbol positions X1 and x2, then p2', p
, ° can be expressed as follows. P2″=Σ Is++ (19) Ps
""Σ Im++ e i (20) Next, Qg of the part where the error rank 1 cannot be identified from the received sequence
', Q-''. As mentioned above, the part where the error position cannot be identified is
, 20 are consecutive, meaning that the weight of the symbol by 1 does not change due to the shift. This is because the shift is completed within l symbols without affecting the symbols, and if we consider that the first 1 is the least significant bit, it can be considered that the branch chain caused by 1 does not change regardless of the shift. However, the branch chain of the symbol in which the error occurs is considered to be different. Therefore, the branch chain ■3,1 of the symbol in which no error has occurred remains unchanged, and the branch chain at the error position j is I! When IJ becomes I slJo, Q2°, Q, and ° can be expressed as follows. Therefore, Pa"-Q2°P3'-Q3° is. P2°-Q2°=I□, -I g9, ' (23
)P3'-Q3°= (1,lJ-Iall')
・j becomes P2'-Q2° =I Sll -I
If $lj° ≠ O, the error position j can be found from (P3° - Q, °) / (Pa '' - Q2°). Next, if P o Qo = 1, the error position cannot be specified. In the part, I9,, = 1 is continuous, and when considering the weight of O, the weight of the symbol does not change due to the shift. Therefore, in the case of P o Q o '' 1, P4. If we make a similar argument regarding P5,
P4° Q 4' = I5oJ-IsoJ'
It is clear that when ≠0, the error position j can be found from (Ps'Qs°)/(P4°-Q4°). After identifying the error position j as described above, the original value of symbol E is determined using the same method as in step 1. But here, Q2°-p,' = o, or Q4°
If −p,°=O, the error position j cannot be specified. Therefore, the error position j cannot be specified by the operations in steps 1 and 2 when the weights of each kernel symbol do not change due to synchronization errors including errors, and the tangent values do not differ. Errors that cannot be corrected by steps 1 and 2 are corrected using 26 to 2 ports as follows. (Step 3) Procedure for correcting errors where the weight and tangent value are not different 1.
If the weight and the tangent value do not differ due to a synchronization error including an error that cannot be corrected by 2, it is when the bits constituting the tangent value are collectively shifted within the symbol in which the error occurs. At this time, in step 3, correction is performed by changing the length of the bit sequence that does not constitute a tangent value. KuP. When -Qo=0, the length of the bit sequence that does not form a tangent value due to sl is indicated by sl+ +rlt which generates P6. Here, for the symbols after the error position j, the start of the tangent value changes from sl+ to si+ +1 due to the shift, and r1□ becomes r1+
-1, so the length of the bit sequence that does not constitute a tangent value of 1 does not change due to the shift. However, at the error position j, the beginning of the tangent value due to 1 becomes sl,
sl, +x, rl at error position j
, becomes rl, -(x+1), so the length of the bit sequence that does not constitute a tangent value of 1 changes only at error position j. At this time, p6. p9, QslQ9 with the same operation as Plo,
Q. can be expressed as follows. Q6=Σ (S11'+rll-+)+a
(25) Q, = Σ (sL'+rL9, l・i'+a
-y (26) Here, since i' of Pa and P= is an odd number, when the error position j is an odd number, slJ is SI
It changes to J+X and becomes y=J+a=X. When the error position j is an even number, rlJ-1 is rlJ-+ -(x
+1), so y = j + 1, a =
−(x + 1). a, y are (P-Qa) = a (28) P y
−Q7 = −a−y (29)(P, −Q
, )/(P, -Q-)=y (30). Also, Pro-Q10=-(j-1+x) (31
), so whether the value of error position j is odd or even is determined by a obtained from equations (28) and (30).
+ y and equation (31), if (y-1+a)=P+o Q+o, then odd number (y3
+ a ) = P + o Q + a, it can be seen that it is an even number. Also, consider the case where a obtained from equation (28) is O. If y=j, a=x=o, the magnitude of the deviation at j+1 is -(x+1)=-1, and the position of the deviation is determined from equation (31) by j
+ 1 "2 (Plo-Q+.) Also, even if we assume that y=j+1.a==-(x+1)=O, the size of the shift is X=-1 and the position of the shift is 2-
CP, 0-Q,. ). Therefore, equation (28) is 0
In this case, the start of the tangent value of the 2-(P, .-Q, .)-th symbol is shifted by 1 due to the omission of O bits. <When P o −Qo = 1> It can be similarly determined by the length of the bit sequence that does not constitute a tangent value due to 0. Therefore, p9,p, when P,-Qo =Q. P. If similar calculations are performed using p9, p9, and p9 corresponding to , the error position j can be found. It has been explained above that the position of synchronization errors, including errors in the case of missing bits, can be found using this code, but the original value of I, where the error has occurred, can be found as follows. First, the deviations of the symbols after j, where deviations have occurred, are restored to their original positions, and the symbols other than ``k'' are determined. P9, P. ■, l□ of the symbols determined from. By subtracting sl+ (i=1・-n, 1sj) respectively, ■. , sl, is obtained. Therefore, I9,
, m 2 f@IJ man Ql = IJ, l,
From the operation 2+'l-1 (7), the original value of . In addition, in the case of bit insertion, the reverse of the case of bit omission, that is, the received sequence in the case of bit omission and the parity P0 to C++ generated from it are transmitted, and I12. bit is inserted, e4. Considering that r+ errors are added, it is clear that synchronization errors including errors can be corrected by similar processing. Furthermore, even when there is no synchronization error and no error occurs, the parity P2 to P1 when no error affects between symbols.
It is clear that the correction can be made using 1. As a result of the above, assuming that the parity is correct, 1
We have shown a code that can correct synchronous errors, including errors within symbols. Here, we will discuss the redundancy of this code and the case where its parity is incorrect. First, consider redundancy. Parity P0 is q≧Po Qa≧−q+1,
Po and Qo can be modulo 2q. In this case, Po-Q with 2q-1≧Po-Qo≧q+1
o means a negative value, and the negative value is obtained by Po −Qo −2q. After that, the position of the synchronization error can be found using the above procedure, so the bits required for Pa become log22q. Similarly, the bits required for P and -P9 are P and -P9, respectively.
The maximum value of -Ql (i=1...11) is as follows. However, the number of bits required for PO to pH is
It is expressed as ゞp+. 1) o = 10gz 2Q, I) + = lOga k. p2 = Q, p3 = 10g2k. pa = Q, ps = 10 g2k. pg = 1 oga 2q, pt =
logz k/2゜ps ”1 Ogz 2q, p
i = l Ogz k/2゜p+o:10 gx 2
k, pth = 10 g2 Next, consider the case where the parity is incorrect. Parities P0 to P are arranged as shown in FIG. 6, and the received data is divided as follows. Parity and data placed at the beginning are separated by a predetermined number of bits from the beginning of the received data,
Parity Pa placed at the end of the code word, p9, p9,
p9, p9, p are separated by a predetermined number of bits from the end of the received data. It is also assumed that p9 and p are generated by treating the leading parity as data. Consider the following cases where the error occurred. ■If an error occurs in the first parity, p9 and p used in step l are not incorrect, so step 1
There are two possible situations: either the incorrect leading parity is identified as the error position, or the error position cannot be identified because the weights are different. If the error position cannot be identified, step 2 is performed, but since the parities at the end of the word P 3 , P s , P 7 , and P 9 are correct, and the first parity is not treated as data, P, −Q, = O(i= 3.5, 7.9). Po
When -Qo=O, P, -Q,=0(i=3.5,7.
9) occurs when the information sequence is all O and one bit of 0 is missing, and when PG-QO=1, Pl-
Q= =O (i=3.5, 7.9) when the information sequence is all 1 and one bit of 1 is missing. Therefore, if the information sequence part of the received data is all 0's or all 1's, there is a parity error, and if it is all 0's or all 1's, O or 1 may be inserted at any position. (2) If P9, P9, P9, P are incorrect The first parity and the parities po, p used in step 1 are correctly separated. Therefore, Po−Q,=0 and P+ Ql =O
(i=2.4, 6°8). In this case as well, as in case (2) above, there is no case other than the case where the information sequence is all O's, so if the information sequence of the received data is all O's, it can be seen that there is a parity error. (2) If Po or P+ is incorrect, the first parity is specified as the error position in step 1, or if the error position cannot be specified, the same process as (2) is performed. If a certain byte in the information sequence is mistakenly determined to be an error, after deriving the error pattern at the error position of the square and performing error correction, P 10+ = 0 (i = O, . . .
・, 11). If the correction is correct, P I Ql = (i = 0..., 11), but if the correction is incorrect, P r Ql = O (i = O,..., 11). No. It is clear that it is an erroneous correction unless P + Ql = O (1 = 0. 1), but P + Q
Even when +=0 (i=0.1), incorrect correction can be detected for the following reasons. In other words, bits are inserted into an error-free information sequence due to error correction, and furthermore, P
'+ -Ql = N = o, 1), then step 1
In this case, the error position cannot be identified. Therefore, if step 2.3 is executed, the incorrectly corrected bit insertion will be detected by the correct leading parity, and P+ −
Ql = O (i = 2.4°6.8, 10.11) does not hold. Therefore, after performing error correction in step 1, P +
By confirming that Ql = O (i = O...11), errors in Pa and P+ can be detected. ■If the information sequence part is incorrect If it is other than ■~■, it is an error in the information sequence, so
Corrected correctly by the above steps. Furthermore, as described above, parity cannot be divided into q bits, which is a unit of one byte. However, the code sequence is divided into a leading parity section, an information sequence section, and a trailing parity section, and it can be said that if the error does not span these three blocks and the synchronization error includes an error within 1 byte, it can be corrected. (A parity error may span multiple parities within one block.) Therefore, if the leading parity part and the ending parity part each consist of bits that are multiples of q, the code can correct synchronization errors including all 1-byte errors. In order to configure each parity part with nine multiple bits, the following p
Dummy bits of m++9m2 bits may be inserted before and after each of the code sequences shown in FIG. p war = m 1・q− (pz + p< +I) a + p+o+ pz)・
Pa2: m2・q− (1)3+1)8+1) fu + pe +p
, ) However, m 1 ” r (pz +p4+p6+p1o+ 1
)+□)/q” m2= r (1)s +ps +p7 +pe +p
l ) /q'' From the above, it can be seen that even if the parity is incorrect, it can be determined if there is a one symbol error. <Description of synchronous error correction processing including errors> An algorithm for correcting synchronous errors including errors on the receiving side, based on the above results, is shown in FIG. To verify the operation of this algorithm, we set q=3. A simple example is shown with =5. The processing described below is performed by the control section 1, parity analysis section 4, and parity generation section 6 shown in FIG. On the transmitting side, the next information series I and parities Po to P are arranged and sent as in the data format shown in FIG. Po and P+ also include the leading parity as data, so
First, generate parity after P2, then Po, Pl
generate. (However, the explanation will omit the dummy bits.) IIs lI4113112 III 11 = [1
00110001010011]P2 = 1 +3+
1 + 1 +3=9=Omod3P3=5・1+4
・3+3・1+2・1+'l ・3=25=Omod5 P4 ==3+1+3+5+1=13=1 mod3
P s ” 5 ・ 3 + 4 ・ 1 + 3 ・
3+2 ・5+ 1 ・1 =39=4
mod5P a = 2 + 1 + O = 3
= 3 mod6P7 =5 ・ 2 + 3 ・ 1
+1 ・ 0= 1 3= 1 mod3 Pa =2+ 1 +2=5=5 mod6P
9 = 5 ・ 2 + 3 ・ 1 + 1 ・ 2 = 15 =
Omod3 P+o=2+ 1 +o+ 1 +○+=4=
4mod7P++=O+O+ 1 +O+2=3=
3 mod7Po =O+1+2+2+1+2+1
+2+1+ 1 +2= 1 5=3 mod
6P + = 1 1 ・O+10 ・1
+9 ・2+8・27・l+6・2+5・1
+4.2 +3.1+2.1+1.2 =83=3mod5 As a result, the transmitted data becomes as follows. P21P41P61P81P101P11118114
11311211roc = [00010111011
00011100110001010011P31P5
1P71P91POIP1 0[]01000100011011] In this case, for example, symbols 1. of j=3 during transmission. = [000
The following will mainly explain the case where ko is mistaken as [01] as an example. The parity analysis unit 4 on the reception side first counts the number of bits of received data in step S1. Then, in step S2, the parities PO to pH are correctly separated by dividing them into a predetermined number of bits from the beginning and end. and step S3
Then, it is checked whether the number of bits of the code word and the number of bits of the received data are equal. If the bit numbers are equal, the process advances to step S21. In step S21, Pl-Qi(i
=o, . . . , 11) and check whether Pi−Qi=◯. If Pi-Qi=◯, there is no error, and the process advances to step S22 to end the correction process. On the other hand, if Pi-Qi=0, there is an error and the process proceeds to step SIO. In a case like the above example, the received data is 1 bit less than the transmitted data, so the number of bits differs in step S3, and since there is an error in the information sequence, the process advances to step S4, and the process shown in FIG. Step 1 described above with details shown in
Execute the process. Subsequently, in step S5, it is checked whether the error position has been identified. If the error position J has been identified, the process proceeds from step S5 to step S6, where an error pattern is determined and corrected using the above-described process. Then, in the following step $7, it is checked whether Pi-Qi=O. If Pi-Qi=0, there is no error and the correction ends. On the other hand, if Pi-Qi=O, there is an error in Po and P+, and the error position is identified and the process proceeds to correction processing. On the other hand, if the error position cannot be specified in step S5, the process proceeds from step S5 to step SIO, and Pi-Qi (
i=2.4, 8, 10.11), and Pi−Qi=
If O, proceed to step Sll, P3+ Ps, Pt
, there is an error in the pH, the error position is identified, and the process moves to correction processing. If Pi−Qi=O, the process advances to step S12, and Pi
-Qi (i = 3.5, 7.9). Pi-
If Qi=O, the process proceeds to step S13, where the leading parity is in error, the error position is identified, and the process proceeds to correction processing. If Pi−Qi=O, the process advances to step S15. If the error position j is not specified in step 1, for example in the case of the above example, in step 1, the received information sequence processing and the leading parity, Qo and Q+ calculated therefrom are
becomes as follows. P21P41P61P81PlOIP111Is” l
I4°113'l12°llll'IC'=[00010
1110110001110011001010011
]Qo =O+1+2+2+1+2+1+2+1+ 1
+2= 15=3 mod3 Ql=11・0+10 bow+9・2+8・27・1+6
・2+5 bow+4・2 +3・1+2・1+1・2 =83 =3mod3 In this case, Pa Qo ”O, Pl−Q+ =0, and y”=ΣIi, q is also always O, so step 1 is incorrect. Unable to determine location. In such a case, the process proceeds to step S15, and the process of step 2 described above, the details of which are shown in FIG. 9, is executed. Subsequently, in step S8, it is checked whether the error position has been identified, and if the error position J has been identified, the process advances to step S18. On the other hand, in the case of the above example, when Q2゜Q3 is calculated in step 2, Q2 = 1 + 3 + 1 + 1 + 3 = 9 = 3
mod3Q3=5・1+4・3+3・1+2・1+1−
3=25=○ mod5, P2 Q2 =O, P3 Qs =O and f
Therefore, even in step 2, the error position cannot be specified. In such a case, the process advances from step S16 to step S17, and the process of step 3 described above, the details of which are shown in FIG. 10, is executed. Then, in step S18, an error pattern is obtained through the process described above and a correction process is performed. Then, in step S19, Pi-
Calculate Qi (i=o, . . . 11) and check whether Pi−Qi=O. Pi
If -Qi=O, there is no error and the correction ends. On the other hand, if Pi-Qi=O, there is an error, and the process advances to step S20 to detect the error position and proceed to correction processing. For example, in the case of the above example, from Qa, Q7゜Q+o, Pa -Qa, Pt -Q7, Pt
o Calculate Q+o, Qa=2+l+○=3=3mod6 Qfu=5・2+3bow+1・O=13=1mod3 Q+o=2+ 1 + 1 +2=6=6 mod? P
a Qs ``Pt -Q? = O P 1.- Q 9, = -2 Therefore, it can be seen that 2- (P to Q+.) = the symbols after the fourth are shifted by 1 bit. Also, P. -Ql.≠0, Ps Qs≠O, so it can be seen that there is no parity error, so the information series I°
Insert O in front of the fourth symbol of P2, or set j=3 and return the other symbols to their original positions as follows:
．． Calculate the correct pattern in ■3 from PIO. ll5lI4+131121111 1 = [1001107?7010011]Is+3
=Pz -(1+3+1+3)" 8=1 mo
d3 S 1 s ”P to (2+ 1 + 1 +O
)=0=Omod7 I3=I+113・2″′3=1・2゜=1=[OO1
] From the above, it can be seen that the error part is [001], and the error will be correctly corrected. It is clear that errors can be correctly corrected in exactly the same way in other error cases as well. As explained above, according to the encoding method and error correction device for correcting synchronization errors including errors of the present embodiment, errors occur in a concentrated manner before and after the synchronization error in the communication channel where the synchronization error occurs. Even in cases where it is expected that 1. Since synchronization errors including any errors within a symbol can be corrected, the above-mentioned errors can be dealt with and correction can be performed with simple calculations. As described above, according to this embodiment, data errors including synchronization errors with respect to the communication channel can be detected and corrected. Moreover, since they are all made up of integer operations, the parity analysis section 4 and the parity generation section 6 can be easily realized using a memory for storing code words and an integer operation circuit.

【Effect of the invention】

As described above, according to the present invention, data errors including synchronization errors with respect to a communication channel can be detected and corrected with a simple configuration.

[Brief explanation of drawings]

FIG. 1 is a functional block diagram of an embodiment according to the present invention, FIG. 2 is a functional block diagram of another embodiment according to the present invention, and FIG. 3 is a block diagram showing the configuration of an embodiment according to the present invention. , Fig. 4 is a diagram explaining the case where the error location can be identified in step 1 of this embodiment, Figure 5 is a diagram explaining the case where the error location cannot be identified in step 1 of this embodiment, and Figure 6 is the diagram FIG. 7 is a flowchart showing error correction processing on the receiving side of this embodiment; FIG. 8 is a flowchart showing details of step 1 in FIG. 7; FIG. 9 is a flowchart showing details of step 2 in FIG. 7, and FIG. 10 is a flowchart showing details of step 3 in FIG. In the figure, 1... control unit, 2... ROM, 3... receiving unit, 4... parity analysis unit, 5... receiving buffer,
6... Parity generation unit, 6... Transmission buffer, 15
. . . host, 100 . . . sending side, 102 . . . weight parity generation means, 103 . , 152... Second parity Po generation means, 153... Third parity Po generation means, 154... Fourth parity Po generation means, 15
5... Fifth parity Po generation means, 156... Sixth parity Po generation means, 157... Seventh parity Po generation means, 15B... Eighth parity Po generation means, 159. ... Ninth parity Po generation means, 16
0... 10th parity Po generation means, 161...
Eleventh parity P to generation means, 162...first
2 parity P'++ generation means, 200...receiving side,
202... Weighted parity detection means, 203... Error parity detection means, 204... Shifted parity detection means, 251... First parity P. generation means, 252.
...Second parity P, generation means, 253...Third parity P2 generation means, 254...Fourth parity P
3 generation means, 255...Fifth parity P4 generation means, 256...Sixth parity P5 generation means, 257.
...Seventh parity P6 generation means, 258...Eighth parity P, generation means, 259...Ninth parity P
8 generation means, 260... 10th parity P9 generation means, 261... 11th parity P to generation means,
262... 12th parity P l+ generation means, 27
0: first error position detection means, 271: second error position detection means. 7□1□−11□□

Claims (3)

[Claims] (1) An error correction system that corrects errors in received data with respect to transmitted data consisting of multiple symbols consisting of predetermined bits, and at least on the transmitting side, errors that occur when the weight of received data with respect to transmitted data is different weight parity generation means for generating parity for detecting a position; error parity generation means for generating parity for detecting an error position except when the weight of the received data relative to the transmitted data is not different and the pattern of the error symbol is shifted; deviated parity generation means for generating parity for detecting the error position when the weight of the received data with respect to the transmitted data is not different and the pattern of error symbols is only shifted; weight parity detection means for detecting error positions from parity when the weights of the received data are different; and error parity detection means for detecting error positions from parity except when the error symbol pattern is shifted when the weights of received data with respect to transmission data are not different. and a deviation parity detection means for detecting the error position from the parity when the weight of the received data is not different from that of the transmitted data and the pattern of error symbols is only shifted. (2) An error correction system that corrects errors in received data with respect to transmitted data consisting of a plurality of symbols consisting of predetermined bits, in which at least the transmitting side calculates parity by the sum of bits that are set to 1 in the transmitted data. a first parity P_0 generation means for generating a parity P_0; a second parity P_1 generation means for multiplying and adding a sum of bits that are 1 in one symbol of transmission data by a certain different weight; The third parity P_2 generating means calculates the sum of the values expressed in binary numbers, with the bit that is set to 1 being the least significant bit, and the bit that is set to 1 first in one symbol of the transmission data is expressed in binary numbers as the least significant bit. a fourth parity P_3 generation means that multiplies the value by a certain different weight, and a fourth parity P_3 generation means that inverts the transmitted data and calculates the sum of the values expressed in binary with the first bit set to 1 in one symbol as the least significant bit. 5 parity P_4 generation means, and sixth parity P_5 generation means that inverts the transmission data and multiplies a value expressed in binary with the first bit set to 1 in one symbol as the least significant bit by a predetermined different weight. , a seventh parity P_6 generating means consisting of the sum of the number of consecutive 1 bits between the symbols of the transmission data, and an eighth parity P_6 generating means that adds a sum of the number of consecutive 1 bits between the symbols of the transmission data by multiplying the number of consecutive 1 bits between the symbols of the transmission data. Parity P
_7 generation means and a ninth parity P_8 consisting of the sum of the number of consecutive 0 bits between symbols of transmission data.
a 10th generation means for multiplying and adding a constant different weight to the number of consecutive 0 bits between symbols of the transmission data;
an eleventh parity P_1_0 generating means consisting of the sum of the number of consecutive 0 bits up to the first 1 in one symbol of the transmission data; The twelfth parity P_1_ consists of the sum of the number of consecutive 1 bits until .
1 generation means, at least on the receiving side, first parity Q_0 generation means for generating parity by the sum of bits in which 1 is set in the received data; a second parity Q_1 generating means which multiplies and adds different weights, and a third parity Q_2 generating means which calculates the sum of the values expressed in binary with the first bit set to 1 in one symbol of the received data being the least significant bit. and a fourth parity Q_3 generating means which multiplies and adds a value expressed in binary with the first bit set to 1 in one symbol of the received data as the least significant bit by a certain different weight, and a fourth parity Q_3 generating means which inverts the received data and A fifth parity Q_4 generating means that takes the sum of the values expressed in binary numbers, with the first bit set to 1 in a symbol as the least significant bit, and a fifth parity Q_4 generation means that inverts the received data and sets the first bit set to 1 in one symbol as the least significant bit. A sixth parity Q_5 generating means that multiplies and adds a value expressed as a binary number by a fixed different weight, and a seventh parity Q_6 generating means that consists of a sum of the number of consecutive 1 bits between symbols of received data; Eighth parity Q that multiplies and adds a certain different weight to the number of consecutive 1 bits between symbols of received data
_7 generation means and a ninth parity Q_8 consisting of the sum of the number of consecutive 0 bits between symbols of received data.
a 10th generation means for multiplying and adding a constant different weight to the number of consecutive 0 bits between symbols of received data;
an eleventh parity Q_1_0 generating means consisting of the sum of the number of consecutive 0 bits up to the first 1 in one symbol of the received data; The 12th parity Q_1_ consists of the sum of the number of consecutive 1 bits until .
1 generation means, the straight line generated from the first parity P_0 and the second parity P_1, the first parity Q_0 and the second parity Q_1, and the straight line representing the deviation of the symbol of the actual communication data. a first error position detection means for detecting an error position when the weight of received data relative to transmitted data deviates by more than 1; Weight shift, P_2 to P_9, Q_2
It is generated from the parity of ~Q_9 (Pi+1−Qi+
1)/(Pi-Qi) (i=2, 4, 6, 8); An error correction system characterized by comprising an error position checking means for checking an error position. (3) The error correction system according to claim 2, further comprising error correction means for correcting the expressions of 1 and 0 in each of the parity generation means by combining cases where they are inverted and cases where they are not. system.