US 4,035,767 AGrant
Error Correction Code and Apparatus for the Correction of Differentially Encoded Quadrature Phase Shift Keyed Data (DQPSK)
Issue Date:1977-07-12
•3 Claims
•4 Drawing Sheets
Abstract
This specification describes a convolutional code and apparatus for the correction of errors in differentially encoded quadrature phase shift keyed data (DQPSK). In each sequence of forty bits 24 are information bits and the remainder are parity bits. Two parity bits are generated for each three information bit set in the sequence in accordance with the following equations: where i.sub.8.sup.a, i.sub.8.sup.b and i.sub.8.sup.c are the three information bits in the set associated with the parity bits P.sub.8.sup.a and P.sub.8.sup.b while the other information bits are from the seven sets of the sequence preceding the set associated with the parity bits.
Metadata
Assignee
- IBM Corporation
Inventors
- Chin Long Chen
- Robert A. Rutledge
Application Information
Application Number:US 6624936
Filing Date:1976-03-01
Priority Date:1976-03-01
Art Unit:236
Classifications
IPC:
G06F 1112
Field of Search:
340325146.1 AQ;146.1 AV41
Patent Drawings (4 sheets)
Description
Background
The present invention relates to the correction of errors occuring in the transmission of data and more particularly to the correction of errors occurring in the transmission of differentially encoded quadrature phase shift keyed data (DQPSK)
Differentially encoded quadrature shift keying (DQPSK) is a highly efficient modulation technique for satellite communication channels. In a typical DQPSK system each sequential two binary bits of information in a string of binary bits i.sub.1, i.sub.2. . . i.sub.n causes a shift .theta. in the phase .psi. of the carrier signal by the mapping of the combination [(0,0), (0,1), (1,1), (1,0)] of the two bits i.sub.n, i.sub.n.sub.+1 into shifts, .theta., of [0.degree., 90.degree., 180.degree., 270.degree.] respectively in the phase .psi. of the carrier signal. To put it another way, with DQPSK, information .theta. on each two sequential bits i.sub.n, i.sub.n.sub.+1 is encoded as the difference between successive phases, .psi..sub.i.sub.+1 - .psi..sub.i.
The advantages of phase shift keying (PSK) is that it is more efficient than frequency shift keying and the advantages of differential phase shift keying (DQPSK) is that it eliminates the need to transmit a reference phase to prevent ambiguity in decoding of the transmitted data. However, one disadvantage of DQPSK is that if a single bit error or an error of 90.degree. in the phase occurs during the transmission of .psi..sub.i, the output of the differential decoder will contain two single-bit errors: one in the estimate of .psi..sub.i - .psi..sub.i.sub.-1 and one in the estimate of .psi..sub.i.sub.+1 - .psi..sub.i. Thus, the bit error rate is doubled and bit errors are correlated. The correlation of errors is the more serious problem because it severely degrades the efficiency of a random-error correcting code. If, for example, a single-error correcting convolutional code is used for forward error correction, there is no guarantee that it will correct any double-bit errors.
One solution to the problem is to perform error correction before differential decoding of the data. In this scheme, the error correction code (ECC) decoder need not contend with double-bit errors, but is faced with the same phase ambiguity that the differential encoding is used to resolve. Techniques to resolve this ambiguity include an acquisition search at start-up and whenever the modem undergoes a 90.degree. phase slippage; much of the benefit of differential encoding is lost.
Another approach is to transmit adjacent bit pairs on different channels and then interleave the outputs so that single-bit errors are not automatically mapped into double-bit errors. The difficulty with this approach is that it increases the amount of hardware necessary to transmit and correct the data and increases the error rate in the transmitted data.
The other alternative approaches would be to use a code that corrected errors occuring in 4 bit bursts or to use a two bit error correction code to correct for single-bit phase errors. Both of these techniques are very inefficient.
The Invention
Therefore in accordance with the present invention a convolutional code is provided that corrects for all single-bit errors and most double-bit errors occurring in DQPSK.
An (mn.sub.0, mk.sub.0) convolutional code has the truncated parity check matrix
where D is an (n.sub.0 -K.sub.0)m .times. n.sub.0 binary matrix and T is the shift matrix defined by ##EQU1##
For a code in systematic form, columns i.sub.1, i.sub.2, . . . , i.sub.kO of D correspond to information bits, and the remaining n.sub.0 -k.sub.0 columns correspond to parity bits. Let M(i.sub.j) be the submatrix of H obtained by deleting all rows in which the i.sub.j th bit is zero. This code is a majority decodable, double error-correcting code if, for j = 1, 2, . . . , k.sub.0,
1. The i.sub.j th column of M(i.sub.j) has weight four.
2. Every other column of M(i.sub.j) has weight zero or one.
In other words, the parity check equations corresponding to M(.sub.j) are orthogonalized on the i.sub.j th bit. Any such code will correct all single and double-bit errors, and therefore will correct any single DQPSK channel errors (which are two-bit errors).
The code described above cannot in general correct double DQPSK channel errors. A double channel error is either a single 180.degree. phase shift or two distinct 90.degree. phase shifts. This code will correct 180.degree. phase shifts if, for j = 1, 2, . . . , k.sub.0 and i = 1,2, . . . , Mn.sub.0 -3,
3. The Exclusive OR of columns i, i+1, i+2, i+3 of M(i.sub.j) has weight zero or one if i.sub.j < i or i.sub.j > i+3
4. The Exclusive OR of columns i, i+1, i+2, i+3 of M(i.sub.j) has weight three or four if .sub.j - i = 0, 1, 2, or 3.
The code will correct two 90.degree. phase shifts if, for j = 1, 2, . . . , k.sub.0 and i = 1, 2, . . . , Mn.sub.0 -1,
5. The Exclusive OR of columns i and i+k of M(.sub.j) has weight zero or one if i.noteq.i.sub.j and i+k.noteq.i.sub.j, for k=l, 2, 3.
6. Column iof M(i.sub.j) has weight zero for .vertline. i-i.sub.j .vertline. 23 4.
In the preferred embodiment a 40% redundancy code or a (40, 24)code is used with n.sub.0 = 5, k.sub.0 = 3 and m = 8. In each sequence of 40 transmitted bits 24 are information bits and the remainder are parity bits. Two parity bits are used to correct for each three information bit set in the sequence. The two parity bits are generated in accordance with the following equations:
(1)
where i.sub.8.sup.a, i.sub.8.sup.b and i.sub.8.sup.c are the information bits in the set corrected by the parity bits P.sub.8.sup.a and P.sub.8.sup.b while the other information bits are from the seven sets in the sequence preceding the set i.sub.8.sup.a, i.sub.8.sup.b and i.sub.8.sup.c.
If P'.sub.8.sup.a, i'.sub.8.sup.a, i'.sub.8.sup.b, P'.sub.8.sup.b, and i'.sub.8.sup.c is a block of received bits at time k. The syndrome bits are calculated as follows:
Let e.sub.k.sup.a, e.sub.k.sup.b, e.sub.k.sup.c be the error bits corresponding to information bits a, b, c, respectively, at time k.
Then,
The value of error bit e.sub.1.sup.a is estimated as ##EQU2## If e.sub.1.sup.a is estimated to be 1, then i'.sub.1.sup.a is EXCLUSIVE ORed with e.sub.1.sup.a to yield i.sub.1.sup.a. In this case, the syndrome bits S.sub.1.sup.a, S.sub.1.sup.b, S.sub.3.sup.b, and S.sub.6.sup.b are complemented before the next bit is decoded. the complementation removes the effect of e.sub.1.sup.a from the syndrome bits. Similarly, the estimates of e.sub.1.sup.b and e.sub.1.sup.c are determined by the following rules: ##EQU3##
This preferred code satisfies conditions 1, 2, 3 and 4. It is not possible to satisfy conditions 5 and 6 for all cases; however, this code satisfies 5 and 6 for as many cases as is possible; that is, it satisfies 5 for 299 out of 327 cases and satisfies 6 for 6 out of 15 cases. Thus while the code is incapable of correcting all possible double-bit errors, it is possible to correct for approximately 70% of double-bit differential errors.
Therefore it is an object of the present invention to provide error correction for DQPSK data.
It is a further object of the present invention to provide means for correcting all single-bit and most double-bit errors in DQPSK data.
Other objects of the invention are to provide error correction for DQPSK with the minimum amount of redundancy and error correcting apparatus.
The Drawings
These and other objects, features and advantages of the present invention will be apparent from the more particular description of the preferred embodiment of the invention of which:
FIG. 1 shows a DQPSK system incorporating the present invention;
FIG. 2 shows an encoder used to generate the parity bits in the system of FIG. 1.
FIG. 3 shows the apparatus for calculating the syndromes in the system of FIG. 1; and,
FIG. 4 shows the decoder for generating the corrected information bits in the system of FIG. 1.
Description of the Drawing
Referring now to FIG. 1, in any 24 bits of data the information bits i are split into sets of 3 bits each. These 3 bit sets are fed into the error correcting decoder 10 where the parity bits are generated in accordance with the equation 1. Parity bits and the information bits are then placed into a phase encoder 12 where each 2 bits in sequence are redefined in terms of a phase change .theta. as shown in chart 14. Dependent on the state of each of the bits these phase changes are then used to modulate the phase of the carrier in the differential encoder 16 so that after the first phase change the phase of the carrier will be .psi. .sub.1 = .theta..sub.1. After the second phase change the carrier phase will be .psi. .sub.2 = .psi..sub.1 + .theta..sub.2 and so on so that the data is in the form of a shift in the phase of a carrier signal. The carrier signal with its phase encoded data is transmitted to a second station where a differential decoder 20 decodes the changes in carrier phase back to shifts of the phase so that the output, .theta.', of the differential decoder after the second phase change will be equal to .psi..sub.1 ' and after the second phase change will be equal to .psi..sub.2 ' - .psi..sub.1 40 and so on.
The phase data is fed into a phase decoder 22 that converts the data back into binary signals including two parity bits, P.sub.8.sup.b and P.sub.8.sup.b and three information bits, i.sub.8.sup.a ', i.sub.8.sup.b ' and i.sub.8.sup.c ' in each set. Using the parity and data bits of the set and some of the bits from the preceding sets, with the assumption that they are correct, the ECC decoder 24 provides the corrected data bits of the i.sub.8.sup.a, i.sub.8.sup.b and i.sub.8 c present set.
Referring now to FIG. 2, it can be seen how the parity bits are generated. A serial string of data bits is fed into one input of each of three AND gates 26. The other input to the three AND gates 26 is from a separate output of a three position ring counter 28 synchronized with the rate of the data transmission so that each bit of any 3 bit set is gated through a different one of the 3 AND gates. The outputs of each of these AND gates 26 goes to a separate eight position shift register 30 containing information bits from the 7 sets in the sequence. Certain of the bits are then Ex ORed in Ex OR gates 32 in accordance with equations (1) to generate the parity bits for the present set. The bits for the present set and the generated parity bits are then each placed into a separate AND gate 34. The other input to the AND gate 34 is from a ring counter 36 which sends a pulse to activate the gates in sequence to provide a serial string of 2 parity bits and 3 information bits from each set at the common output to the AND gates 34. These 5 bit sets are then fed into the phase encoder 10.
Referring to FIG. 3 it can be seen how the syndrome bits are generated. The serial string of data bits from decoder 22 is fed through the AND gates 38 controlled by ring counter 40 into separate shift registers 42 containing data from the last sets of the sequence. These bits are Ex ORed with each other and with the present set of parity bits in Exclusive OR circuits 44 to generate the syndrome S.sub.8.sup.a and S.sub.8.sup.b in accordance with equations (2). These syndromes are then fed into two additional shift registers 46 and the output of all 5 shift registers is fed in parallel to the error correcting circuitry of FIG. 4.
In FIG. 4, 3 sets 48, 50 and 52 of 3 shift registers each receive the syndromes and data bits of one set of bits. Each set of shift registers receives one of the 3 information bits, i.sub.8.sup.a ', i.sub.8.sup.b ' or i.sub.8.sup.c ', and both the syndromes S.sub.8.sup.a and S.sub.8.sup.b as shown. The syndrome bits are then summed in modolo 2 adders 54 in accordance with the formulas (4) (5) and (6). The results are then Ex ORed in Exclusive OR circuits 56 with the information bits i.sub.1.sup.a ', i.sub.1.sup.b ', and i.sub.1.sup.c ' to generate the corrected information bits i.sub.1.sup.a, i.sub.1.sup.b and i.sub.1.sup.c. The outputs of each of the set of shift registers are then fed into an AND gate 58 which also receives a separately timed signal from a ring counter 60 so that the output of the AND gates contain a serial string of the corrected data bits.
Therefore while the invention has been particularly shown and described with reference to a preferred embodiment thereof, it will be understood by those skilled in the art that the above and other changes in form and details may be made therein without departing from the spirit and scope of the invention.
Claims
What is claimed is:
1. In error correction apparatus for correcting errors in binary information that has been transmitted using apparatus encoding and decoding the data as differentially encoded quadrature phase shift keyed data and using an (mn.sub.0, mk.sub.0) convolutional code with the truncated parity check matrix: where D is an (N.sub. 0 -K.sub.0)m.times. n.sub.0 binary matrix and T is the shift matrix defined by ##STR1## where m(i.sub. j) is a submatrix of H deleting all rows in which the i.sup.th bit is zero, the i.sub.j th column of M(i.sub. j) has a weight four and every other column of M(i.sub. j) has weight zero or one, the improvement comprising: first shift register means, coupled to the input of apparatus for encoding the data as differentially encoded quadrature phase shift keyed data, for dividing a sequence of said data bits into a plurality of sets and generating parity bits for each set of the binary information bits in the sequence in accordance with the submatrix (Mi.sub. j) where the EXclusive OR columns i, i+1, i+2i+3 of M(i.sub. j) has a weight zero or one if i.sub.j < i or i.sub.j > i+3, and the EXclusive OR of columns i, i+1, i+2, i+3 of M(i.sub. j) has weight three or four if i.sub.j - i=0, 1, 2 or 3; second shift register means, at the output of the apparatus decoding differentially encoded quadrature phase shift keyed data, for dividing a sequence of decoded data bits into a number of sets including the information bits and parity bits of encoded sets, and; third shift register means, coupled to the output of the second shift register means, for receiving said generated syndromes of the sequence and the data bits of the sequences to correct said data bits.
2. The apparatus of claim 1 wherein the first, second and third shift register means encode and decode in accordance with the submatrix (Mi.sub. j) where the EXclusive OR of most of columns i and 2+K of M(i.sub. j) has a weight zero or one if i.noteq.i.sub.j and 2+K.noteq. i.sub.j for K=1, 2, 3 and part of column i of M(I.sub. j) has weight zero for .vertline.i-i.sub.j .vertline. .ltoreq. 4.
3. The apparatus of claim 1 wherein; the first shift register means includes means for splitting up the sequence of 24 information bits into 8 sets of 3 bits each and generating two parity bits for each of the sets in accordance with the equations: i.sub.1.sup.b .sym. i.sub.3.sup.c .sym. i.sub.2.sup.c i.sub.5.sup.b .sym. i.sub.8.sup.c .sym. i.sub.4.sup.c where i.sub.8.sup.a, i.sub.8.sup.b and i.sub.8.sup.c are the information bits in the set corrected by the parity bits P.sub.8.sup.a and P.sub.8.sup.b while the other information bits are from the seven sets in the sequence preceding the set i.sub.8.sup.a, i.sub.8.sup.b and i.sub.8.sup.c, the second shift register means includes means for generating the syndromes in accordance with the equations: .sym. i'.sub.6.sup.b .sym. i'.sub.1.sup.b .sym. i'.sub.3.sup.c .sym. i'.sub.2.sup.c .sym. i'.sub.3.sup.a .sym. i'.sub.5.sup.b .sym. i'.sub.8.sup.c .sym. i'.sub.4.sup.c the third shift register means corrects the bits in error in accordance with the equations: where ##EQU4##
Patent Citations (2)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US3891959 | 1975-06-01 | Tsuji et al. | |
| US3988677 | 1976-10-01 | Fletcher et al. |
Non-Patent Literature (2)
- Forney, Jr. and Bower, A High-Speed Sequential Decoder: Prototype Design and Test, IEEE Transactions on Communication Technology, vol. Com-19, No. 5, Oct. 1971, pp. 821-835.
- Chen and Rutledge, Error Correcting Codes for Satellite Communication Channels, IBM Journal of Research and Development, Mar. 1976, pp. 168-175.