JPS647526B2 - - Google Patents

Description

[Detailed description of the invention]

The present invention relates to an error correction encoding and decoding system that automatically detects and corrects errors caused by the transmission or accumulation of digital data, and particularly relates to an error correction encoding and decoding system that automatically detects and corrects errors caused by the transmission or accumulation of digital data, and in particular, when digital data is transmitted by differential phase modulation. The present invention relates to an error correction system for differential codes that corrects errors occurring in storage media. Conventionally, when introducing an error correction code system in a differential phase modulation system, a system as shown in FIG. 1 has been adopted. In FIG. 1, transmission data is added with redundant digits in an error correction encoder 1, differentially encoded in a differential encoder 3 included in a modulator 2, and further modulated in a modulator 4. It is sent to a transmission or storage medium 5. Data received via a transmission or storage medium 5 is first demodulated in a demodulator 7 in a demodulator 6, then differentially decoded in a differential decoder 8, and then transmitted or transmitted in an error correction decoder 9. Errors occurring on the storage medium are corrected, resulting in correct transmitted data. However, in this method, the transmission or storage medium 5
For example, when a one-digit error occurs, the error is amplified by the differential decoder 8 and is always sent to the error correction decoder 9 as a two-digit error. For this reason, the method shown in FIG. 1 requires the use of an error correction encoder and decoder that have a higher error correction capability than the error rate on the transmission or storage medium 5, which has the disadvantage of unnecessarily increasing the scale of the device. have. In order to avoid this, as shown in Fig. 2 (however, devices 1', 3', 4', 5',
7', 8' and 9' are devices 1, 3, 4,
5, 7, 8, and 9 respectively), the order of the error correction encoder and differential encoder and the error correction decoder and differential decoder are swapped, respectively, and at the point when the error on the transmission or storage medium does not increase. A method of performing error correction decoding has also been considered in the past. However, in this method, error correction must be performed before performing differential decoding, so error correction must be performed in a state where the phase standards do not match between the transmitting side and the receiving side. For this reason, for example, as codes that can be used even if the phase standards do not match in the M-phase phase modulation method, there are M-adic error correction codes based on calculations modulo M, or especially in the case of the 4-phase phase modulation method. A well-known method is to use two binary error correction codes independently. FIG. 3 is a block diagram showing the latter method, where devices 1'', 3'', 4'', 5'', 7'', 8'' and 9'' in FIG. 3 are devices 1', 3' in FIG. ,4',5',7',
8' and 9', respectively. However, in the case of 4-phase, 1 digit corresponds to 2 bits, so the input/output lines in Figure 3 are represented by two lines, indicating that 2 bits are input simultaneously at each time point. . Also, reference numerals 1'-1 and 1''-2 are ordinary binary error correction encoders, and reference numerals 9''-1
and 9''-2 are also ordinary binary error correction decoders. However, the system shown in FIG. 2 or 3 has the following drawbacks. Conventionally, modulation and demodulation devices As shown in Figure 1, it has been developed to include a differential encoder 3 and a differential decoder 8, and if an error correction device is connected in some way to this modulation/demodulation device, In some cases, the modem and error correction device are geographically separated, and in this case, the error correction device is inserted into the modem as shown in Figure 2 or 3. It is virtually impossible to design such a system.Secondly, even if the modem and error correction equipment are located in the same area, there is no error correction system in the conventional modem. Re-designing the equipment by cutting it out will require various design changes to the conventional modulation/demodulation equipment, and may not be possible in practice. An object of the present invention is to provide a novel error correction system for differential codes in which error correction is eliminated. It is composed of a decoding device having a correction decoder and a differential decoder, and a transmission medium or storage medium provided between the two devices and including a differential phase modulation/demodulation device. The invention will be described in detail. Figure 4 shows a block diagram of an embodiment of the invention. In Figure 4, reference numerals 1, 2, 3
, 4, 5, 6, 7, 8 and 9 correspond to devices 1, 2, 3, 4, 5, 6, 7, 8 and 9 in FIG. 1, respectively. Furthermore, devices designated by reference numerals 11 and 14 are differential encoders, and devices designated by reference numerals 12 and 15 are differential decoders. Reference numerals 10 and 13 indicate the newly proposed encoding device and decoding device, respectively. Note that, as is well known, the differential encoder and differential decoder have M
In the phase modulation method, each phase data 0°, a°,
2a゜, ......, and (M-1)a゜ (however, a゜=
360°/M) can be expressed as 0, 1, 2, . . . and (M-1), respectively, as shown in FIGS. 5 and 6. In FIG. 5, reference numerals 16 and 16' indicate registers for storing one digit, and reference numerals 17 and 17' indicate an adder for adding modulo M and a subtractor for subtracting modulo M, respectively. . It is clear from FIGS. 5 and 6 that the differential encoder and differential decoder are devices having an inverse transformation relationship. Now, in FIG. 4, a transmission data string is first differentially encoded by a differential encoder 11, then redundant digits are added by an error correction encoder 1, and then differentially decoded by a differential decoder 12. After being converted, it is sent to the modulator 2'. As in the case of FIG. 1, the transmitted data string is sent from the modulator 2' to the transmission or storage medium 5, and further to the decoder 13 via the demodulator 6'. The modulator 2' transmission or storage medium 5 and the demodulator 6' may be collectively referred to as a transmission medium or storage medium including a differential phase modulation/demodulation device. As is clear from the figure, if no errors occur on the transmission or storage medium 5, the modulation device 2'
The input data string to the demodulator 6' and the output data string from the demodulator 6' are exactly the same. However, if an error occurs, the error is magnified and doubled to the next clock because there is a register for storing the one digit in the differential decoder 8 included in the demodulator 6'. . When the decoding device 13 receives the data string in which this error has been doubled, the differential encoder 14 first restores the received data string to the data before being input to the differential decoder 8. However, in general, the differential decoder 8 and the differential encoder 1
Since the initial data (that is, the data initially stored in the register that stores the one digit) is different from that of the differential encoder 14, as is clear from FIG. When compared with the input data string to the dynamic decoder 8, it can be seen that the data string is always added modulo M by the difference in initial data. Except for this difference in initial data, both data strings are completely equal, and the only erroneous digits are those that occurred in the transmission or storage medium 5. For the same reason, the output data string of the differential decoder 14 is compared with the input data string to the differential decoder 12.
It can be seen that the data string is always added modulo M by the difference between the initial data.
In other words, the output data string from the error correction encoder 1 and the input data string to the error correction decoder 9 are:
As in the case of FIG. 2 or 3, the only difference is in the phase reference, and apart from that, the two data streams differ only in the error digits generated in the transmission or storage medium 5. These are exactly the same data strings. Therefore, as the error correction code, a conventional code that can be used even if the phase reference does not match may be used, as in the case of FIG. 2 or 3. At this time, the error correction decoder 9 only needs to correct error digits generated in the transmission or storage medium 5. The phase reference difference can be removed by arranging the differential encoder 11 and the differential decoder 15 outside the error correction encoder 1 and the error correction encoder 9. Therefore, the input data string to the encoding device 10 and the output data string from the decoding device 13 are completely equal as long as the errors occurring in the transmission or storage medium 5 are within the correction capability of the error correction code used. It becomes a data column. In order to explain the above explanation even more concretely, in FIG. 4, we will take as an example a case where a 4-bit information bit string of 1111 is input to the differential code error correction encoder 10 according to the present invention. explain. For convenience of explanation, differential encoders 11, 3, 1
4 and the initial state of the differential decoders 12, 8, 15, that is, the register 1 shown in FIGS.
It is assumed that the initial states of 6 and 16' are 0 unless otherwise specified. At this time, the differential encoder 11
As can be seen from Figure 5, the output of is 1+0=1,
1+1=0, 1+0=1, 1+1=0 (mod2), that is, 1010. Next, error correction encoder 1
For example, is a cyclic code encoder with a code length of 7 bits determined by the generator polynomial x ³ + x ² + 1 and error correction capability.The general input-output relationship of this encoder is expressed as well-known. As per A.

[Table] As mentioned above, the input to the error correction encoder 1 is 1010, so the output is 1010001. next,
This code 1010001 is input to the differential decoder 12,
As can be seen from Figure 6, the output is 1-0=
1, 0-1=1, 1-0=1, 0-1=1, 0-
0=0, 0-0=0, 1-0=1 (mod2)
It becomes 1111001. Furthermore, this output 1111001 is input to the differential phase modulator 2', and first, the differential encoder 3 converts it into 1+0=1, 1+1=0, 1+0=1,
1+1=0, 0+0=0, 0+0=0, 1+0=
1 (mod2), that is, 1010001, a two-phase PSK signal according to this code string is generated by the modulator 4, and sent to the transmission or storage medium 5. On the receiving side, in the differential phase demodulator 6', the demodulator 7 first demodulates the 1010001 bit string. This demodulated bit string is processed by a differential decoder 8.
-0=1, 0-1=1, 1-0=1, 0-1=
1, 0-0=0, 0-0=0, 1-0=1
(mod2) That is, the sequence converted to 1111001 and input to the differential phase modulator 2' is restored. However,
In this case, the explanation has been made assuming that no phase rotation occurs in the demodulator 7, but if a 180° phase rotation occurs and 0 changes to 1 and 1 to 0 and is decoded, the demodulator 7 The output is different from 1010001,
It becomes 0101110. In this case, if the initial state of the differential decoder 8 is also 1 instead of 0, the output of the differential decoder 8 will be 0-1=1, 1-0=1, 0-1=1,
1-0=1, 1-1=0, 1-1=0, 0-1=
1 (mod2), that is, 1111001 is restored. Even if the initial state of the differential decoder 8 is 0, only the first bit will be different as 0-0=0, and this is a characteristic of the conventional differential phase modulation system. In reality, there is no problem. In other words, after inputting one dummy bit to the differential phase modulation system, the true bit string can be inputted. Note that the differential decoder 8 restores 1111001 in any case without knowing whether the phase rotation is warm or not, that is, without knowing the difference in phase references. This means that even if a 180° phase rotation occurs and each bit is inverted, that is, +1 with mod2,
Since all bits are +1 with mod2,
This is because the differential decoder naturally erases the amount added by +1. In other words, a 180° phase rotation occurs in bits a ₁ and a ₂ , and a ₁ +1, a ₂ +1
(mod2), the output of the differential decoder will be (a ₂ + 1) - (a ₁ + 1) = a ₂ - a ₁ (mod 2).
This is because the effect of +1 in mod2, that is, bit inversion, does not appear at all. In addition, the input to the differential phase modulator 2 in FIG.
The output is a bit string 1+0=1, 1+1=0, 1+0= which is obtained by differentially encoding 1111111.
1, 1+1=0, 1+0=1, 1+1=0, 1+
0 = 1 (mod2), that is, 2 phases according to 1010101
In contrast to the PSK signal, the input to the differential phase modulator 2' in FIG. obeyed 2
It is a phase PSK signal, and the bit string is
1010001 is the code word of the cyclic code. Therefore, the input/output to the differential phase modulator 6 in FIG. 1 and the differential phase demodulator 6' in FIG.
Assuming that there is no transmission path error, the input and output to the
PSK signal, bit string 1111001. Furthermore, a case will be described in which there is an error in the demodulation result of the demodulator 7 in FIG. 1 or the demodulator 7 in FIG. 4 due to a transmission path error. For example, if there is an error in the third bit and the result of demodulation is 1000101 in FIG. 1 and 1000001 in FIG. When there is no
1111111) and 1100001 (1111001 when there is no error), both of which have error bits at the 3rd and 4th bits. However, in the configuration shown in Figure 1, a bit string with 2-bit errors
1100111 is decoded by the error correction decoder 9 as 1100101, mistakenly thinking that a single bit error has occurred in the 6th bit, and 1100 is output. That is, the input 1111 is output with a 2-bit error, and it is not possible to correct a 1-bit error that occurs on the transmission path. On the other hand, in the present invention, 1-bit errors occurring in the transmission path can always be corrected. Regarding this,
This will be further explained using the above columns. In Figure 4,
As mentioned above, bit string 1100001 with errors in the 3rd and 4th bits (if there are no errors,
1111001) is input to the differential code error correction decoder 13 according to the present invention. First, the differential encoder 14 converts the bit string 1100001 with an error into 1+0
=1, 1+1=0, 0+0=0, 0+0=0, 0
+0=0, 0+0=0, 1+0=1 (mod2) In other words, it is converted to 1000001 (the value when there is no error is 1010001), and is input to the error correction decoder 9 with only the third error bit. and closest
It is decoded into a code word 1010001 and output as 1010. This bit string 1010 is processed by the differential decoder 15 such that 1-0=1, 0-1=1, 1-0=1,
0-1=1 (mod2), that is, it is converted to 1111 and restored correctly. In the above description, the differential encoders 11, 3, 14,
Although the initial states of the differential decoders 12, 8, and 15 have all been described as 0, in reality, they can take any value, such as 0 or 1. Therefore, as described above, it is necessary to send one dummy bit before sending the true bit string. However, even in that case, it is of course possible that the internal states of the differential decoder 12 and the differential encoder 14 differ due to the influence of the dummy bits. For example, when the initial state of the differential encoder 12 is 0 and the initial state of the differential encoder 14 is 1,
The input bit string 1100001 to the differential code error correction decoder 13 is converted into 1+1 by the differential encoder 14.
=0, 1+0=1, 0+1=1, 0+1=1, 0
+1=1, 1+1=0 (mod2), that is, converted to 0111110, which is exactly the form in which all bits of the converted bit string 1000001 when the initial state of the differential encoder 14 is 0 are inverted. In other words, the shape is the same as when a 180° phase rotation occurs. The cyclic code with a code length of 7 is a linear code with a code word 1111111, which is all 1, so it also includes the bit string 0101110 obtained by mod2 addition of 1111111 to the code word 1010001 for each bit as a correct code word, and performs error correction decoding. The bit string 0111110 is determined by the circuit 9 as an error in only the 3rd bit, and the code word 1010001 is inverted with all bits.
Decoded to 0101110. Then, 0101 becomes the input to the differential decoder 15 as the output of the error correction decoder 9. If the initial state of the differential decoder 15 is also 1, its output is 0-1=1, 1-0=1, 0-1
=1, 1-0=1 (mod2), that is, it becomes 1111 and is restored correctly. The initial state of the differential decoder 15 is 1
Otherwise, only the first bit differs as described above. In the differential decoder 15, as in the case of the differential decoder 8, correct decoding is performed irrespective of whether or not a 180° phase rotation has occurred in the input bit string. Further, the code change due to phase rotation is an inversion of all bits, which is a conversion from one code word to another code word, and the error correction decoder 9 does not detect any error. This is because, as described above, a code word in which all bits are inverted is also a correct code word. The error correction code in the example just described is an error correction code that corrects only one arbitrary bit within the block length of 7 bits, so it is designed to detect and correct an error of only one bit. Next, as an example of the use of conventional codes that can be used even if the phase reference is not correct, we will discuss the case where two binary error correction codes are used independently, especially in the case of a four-phase phase modulation method. Referring to Figure 7,
Explain in detail. Here, the binary error correction code is a linear error correction code that has the following property of a normal binary error correction code, that is, a code pattern of all 1s (11...1) as one correct code word. do. At this time, a code word obtained by inverting all of the bits of a given code word also becomes the code word of the error correction code. An example of such an error correction code is a cyclic code in which the number of terms in the generator polynomial is an odd number. Show the reason. When the code length is n and the generating polynomial is G(x), G(x) divides x ⁿ -1 due to the nature of a cyclic code. On the other hand, x ⁿ
-1 is x ⁿ -y=(x ^n-1 +x ^n-2 +......+x+1)(x-
1) It can be decomposed as follows. By the way, since the number of terms in G(x) is odd, G(1) is not 0, and therefore G(x) does not have x-1 as a factor. Therefore, G(x) is
Divide x ^n-1 +x ^n-2 +……+x+1. This fact is based on the nature of cyclic codes: x ^n-1 +x ^n-2 +……+x
This means that +1 corresponds to a code word, that is, a code pattern of all 1s (11...1) is a code word. From the above, it has been shown that a cyclic code in which the number of terms in the generator polynomial is an odd number is a linear error correction code in which a code pattern of all 1s (11...1) is used as one code word. In Figure 7, reference numerals 1'''', 2'', 3'''', 4
′′′′, 5
′′′′, 6″, 7′′′′, 8′′′′, 9′′′′
,10',11'1
The devices designated 2', 13', 14' and 15' correspond to the devices 11, 2' and 15', respectively, in FIG.
3, 4, 5, 6', 7, 8, 9, 1
Corresponds to 0, 11, 12, 13, and 14. Reference numerals 1'''''-1 and 1-2 refer to identical binary error correction encoders; reference numerals 9'''''-1 and 9'''
′−
2 indicates the same binary error correction decoder. Now, each of the phase data 0, 1, 2, and 3 in the four-phase phase modulation system can be expressed as 2-bit data, but in normal input and output with a modulation/demodulation device, it is expressed in the form of a so-called Gray code. Treat it as a thing. That is, each phase data of 0, 1, 2 and 3 is 00, 01, 11 and
It is treated as being expressed in two bits in the form of 10. Therefore, each phase data 0, 1,
2 and 3 are assumed to be represented in the form of Gray codes. At this time, it is included in a differential encoder and a differential decoder. The M=4 method, that is, the mod 4 adder and subtracter output calculation results according to the operation tables shown in Tables 1 and 2 below, respectively. In FIG. 7, the input bit strings to error correction encoders 1'''''-1 and 1'''''-2

【table】

[Table] are {Pi} and {Q′i}, respectively, and the output bit strings after adding redundant bits are {Pi} and {Q′i}, respectively.
Let {Qi}. At this time, the error correction decoder 9′′′′−
The input bit strings to 1 and 9''''-2 vary depending on the difference between the initial data in the differential decoder 12' and the differential encoder 14', and can be expressed as shown in Table 3 below. can. This can be easily derived by examining, based on Table 1, how the 2 bits change when the difference i between the initial data is added to some arbitrary 2-bit expressed data. Note that in Table 3, the * mark indicates a series to which some error has been added only on the transmission or storage medium 5''''. Also, the ~ mark indicates that each data bit is a series in which all are inverted. In Table 3, suppose, for example, that the difference in the initial data is 1 (that is, 90°). At this time, as can be seen from Figure 5, the difference in the initial data is 0.
Compared to the above case, each digit is all incremented by 1 in the differential encoder 14' and then input to the error correction decoder 9''. As can be seen from Table 1 (0,
When each digit of 0), (0, 1), (1, 1), (1, 0) is increased by 1, it becomes (0, 1), (1, 0), respectively.
1), (1, 0), (0, 0). In other words, (P,
The digit Q) changes to the digit (Q, P〓). The initial data difference is 2 (i.e. 180°)
In the case of (0, 0), (0, 1), (1, 1),
Each digit of (1, 0) is (1, 1)
Changes to (1, 0), (0, 0), (0, 1). In other words,
The digit (P, Q) changes to (P〓, Q〓). Furthermore, if the difference in the initial data is 3 (i.e. 270°), (0, 0), (0, 1), (1, 1), (1
,
Each digit of 0) is (1, 0),
Changes to (0, 0), (0, 1), (1, 1). In other words,
The digit (P, Q) changes to (Q〓, P).

[Table] As seen from Table 3, error correction decoder 9''''-
The input bit strings to 1 and 9′′′′-2 are {P ^* i},
It can be seen that it is one of {P〓 ^* i}, {Q ^* i}, and {Q〓 ^* i}. However, when a normal binary error correction code is used, if the error on the transmission or storage medium 5'' is within the correction capability, the input bit string {P ^* i} {P 〓 ^* i }, {Q ^* i} and {Q〓 ^* i} are respectively {P′i}, {P〓′ _i
},
{Q′ _i } and {Q〓′i}. {P ^* i}, {Q ^* i}
It is obvious from the definition that are {P′i} and {Q′i}. On the other hand, {P〓 ^* i}, {Q〓 ^* i} are {P〓′i}, {Q
〓′i} is obtained because, as mentioned above, in a normal binary error correction code, the inverted version of the correct code word is also the correct code word, so it is decoded to the nearest code word. If redundant bits are removed, {P〓′i},
This is because {Q〓′i}. As mentioned above, {P′i} and {Q′} are input bit strings to error correction decoders 1′′′′-1 and 1′′′′-2, respectively, so for example, error correction decoding Vessel 9
If the output bit strings of ``''''-1 and 9''''-2 are the bit strings {Q〓′i} and {P′i}, respectively, then the error correction decoder 9′′′′ As can be seen from Table 1 or Table 3, the output data string from the error correction decoder 1'' is a data string obtained by adding 3 to all the data in the input data string to the error correction decoder 1''. Recognize. This phase reference difference is removed by arranging the differential encoder 11' and the differential decoder 15' as described above, so that the input data string to the encoding device 10' and the decoding The output data string from the conversion device 13' is exactly the same. Error correction decoder 9
The same applies when the output bit strings ``''''-1 and 9''''-2 are combinations of other bit strings. As described above, the differential code error correction system according to the present invention can be used as is without redesigning the conventional modulation/demodulation device for the differential phase modulation method, and can be used for transmission or storage. This is an extremely efficient system that only needs to correct errors that occur on the medium. Although the present invention has specifically explained the case of the four-phase phase modulation method in detail, the conventional M-adic error correction code based on calculation modulo M can also be used in the case of other M-phase phase modulation methods. Therefore, it is easy to understand that a differential code error correction system having the same characteristics as above can be constructed.

[Brief explanation of drawings]

1, 2, and 3 are block diagrams showing a conventional differential code error correction system, FIG. 4 is a block diagram showing an embodiment of the present invention, and FIG. 5 is a block diagram showing a differential encoder. FIG. 6 is a block diagram showing a differential decoder, and FIG. 7 is a block diagram showing an example of application of an error correction system for four-phase differential codes according to the present invention. Figure 1, Figure 2, Figure 3
In the figures, FIGS. 4 and 7, reference numerals 1,
1′, 1″, 1 and 1′′″ are error correction encoders,
Reference numerals 3, 3', 3'', 3 and 3''''' refer to differential encoders; reference numerals 4, 4', 4'', 4 and 4
``'''' designates the modulator; reference numerals 5, 5', 5'', 5 and 5'''' refer to the transmission or storage medium; reference numerals 7, 7', 7'', 7 and 7''''' Reference numerals 8, 8', 8'', 8 and 8''''' refer to differential decoders; reference numerals 9, 9', 9'', 9 and 9
′′′′ represents an error correction decoder, respectively. In FIGS. 1, 4 and 7, reference numerals 2, 2' and 2'' refer to modulators, reference numerals 6,
6' and 6'' represent demodulators, respectively. In Figures 3 and 7, reference numerals 1''--
1,1''-2, 1'''''-1 and 1'''''-2 are binary error correction encoders, reference numerals 9''-1, 9''-2,
9''''-1 and 9''''-2 represent binary error correction decoders, respectively. 4 and 7, reference numerals 10 and 10' designate the encoding device newly proposed in the present invention, reference numerals 11 and 11' designate the differential encoder in the encoding device, and reference numerals 12 and 11' designate the differential encoder in the encoding device. 12' denotes a differential decoder in the encoding device with reference numeral 13.
and 13' designate a decoding device newly proposed in the present invention; reference numerals 14 and 14' designate a differential encoder in the decoding device; reference numerals 15 and 15' designate a differential encoder in the decoding device;
represent differential decoders in the decoding device, respectively. 5 and 6, reference numerals 16 and 16' indicate registers for storing one digit, reference numeral 17 indicates an adder for adding modulo the number of phase data, and reference numeral 18 indicates an adder for adding phase data modulo. Each represents a subtracter that subtracts the number modulo.

Claims (1)

[Claims] 1. An encoding device that differentially encodes a transmission data string, adds a redundant digit string to the differentially encoded transmission data string, and then performs differential decoding on the data string to which the redundant digit string has been added; A data string obtained by differentially encoding a string, correcting error digits generated in a transmission or storage medium, and adding a redundant digit string to the transmitted data string to the received data string in which the error digits have been corrected, and the received data string. A decoding device that performs differential decoding, and a decoding device provided between the differential encoding device and the differential decoding device, in order to remove a phase difference between the data string and the data string obtained by differentially encoding the and the transmission medium or storage medium including a differential phase modulator/demodulator.