Modem and Method for 8 Dimensional Trellis Code Modulation

This invention relates to a modem and trellis code modulation and more specifically to a 64-State 8D Encoder having a 20-point 2D constellation.

In communication systems, the received signal constellation may be rotated with respect to the transmitted signal constellation, due to phase hits. Phase hits or jumps occurring in the communication medium may result in a rotation of the received signaling alphabets as compared to the initial determination of phase. This ambiguity in phase can cause errors in all subsequently received data and thereby seriously degrade the performance of the system. This rotation may cause the phase of the received signal to jump permanently to a new value. More specifically, if there is a phase hit, the received signal might be rotated by multiples of 90.degree..

It is known in the prior art that encoding the data at the transmitter of a modem using a convolutional encoder and performing maximum likelihood (Viterbi) decoding at the receiver decreases the error rate of the modem at a given signal-to-noise ratio (SNR), assuming that the major impairment is Gaussian noise.

The idea of jointly selecting a trellis code and a signal constellation to optimize performance for band limited channels was first discussed by Ungerboeck in his article entitled "Channel Coding with Multilevel/Phase Signals", IEEE Transactions on Information Theory, Vol. IT-28, January 1982, pp. 55-67. Ungerboeck showed that for 2D codes, almost all of the gain theoretically achievable, by adding redundancy through coding and increasing the number of constellation points, could be gained by using a rate (n-1)/n code and a coded constellation with twice the number of points as the uncoded one. Lee-Fang Wei, in an article entitled "Rotationally Invariant Convolutional Channel Coding with Expanded Signal Space--Part II: Nonlinear Codes", IEEE Journal on Selected Areas in Communications, Vol. SAC-2, No. 5, September 1984, pp. 672-686, extended Ungerboeck's ideas and created 2D nonlinear trellis codes that are rotational invariant to 90.degree. phase shifts. One of Wei's codes was selected for the V32 CCITT specification. More recently, Wei discovered multi-dimensional trellis codes that give improved performance over the 2D codes. The codes are designed for encoders that accept seven data bits per baud. This work is referenced in another article by Ungerbocck entitled "Trellis-Coded Modulation with Redundant Signal Sets, Part II: State of the Art", IEEE Communications, Vol., 25, No. 2, February 1987, p. 21 and one of the codes is, also, used in the CODEX 19.2 kbps modem.

In accordance with the present invention, a 64-state 8D code with a 160-point 2D constellation is replaced with a 64-state 8D code with a 20-point 2D constellation. The new code accepts 4 bits per baud. Thus, a baud rate of 2400 symbols/sec. gives the data rate of 9600 bits per second (bps). The 20-point constellation and the performance of the new code are described herein. Also, described are the 64-State 8D Encoder and the 8D Viterbi Decoder.

An international standard, CCITT V32, exists for a 9600 bps modem. The CCITT V32 includes an uncoded mode with a 16 point 2-dimensional constellation and a coded mode using a 2-dimensional 8-state trellis code with a 32-point 2D constellation. The V32 code gives a 4 dB improvement over the uncoded mode. The present invention gives additional improvement by using a more powerful code. This involves reducing a 160-point constellation to a 20-point constellation. The modem accepts 4 bits/baud and transmits at 2400 baud for a data rate of 4.times.2400=9600 bps. In the uncoded case, the 4 bits require a 16-point 2D constellation. The code of the present invention gives a 5.23 dB improvement over the uncoded mode.

The standard V32 code has a 32-point 2D constellation versus the 20-point 2D constellation of the present invention. A constellation with fewer points has some very practical advantages. With fewer points, the signal is affected less by channel phase jitter, non-linearity, and noise.

Disclosed is a modem having an 8-dimensional 64-state trellis code that achieves a 5.23 dB performance gain in terms of signal-to-noise ratio over the uncoded 4.times.4 QAM V32 mode and a 1.23 dB gain over the standard 2-dimensional 8-state V32 trellis coded mode. The 64-State 8D Encoder (42) operates on blocks of 16 consecutive data bits taken 4 bits per baud over four bauds. The trellis encoder (18) adds one check bit to the 16 data bits and the resulting 17 bits are mapped into an 8D point consisting of a sequence of four 2D signal points each selected from a 20-point 2D constellation. The standard V32 code selects signal points from the 32-point cross 2D constellation. The fact that a 20-point constellation is used, each baud for the 8D code, rather than the 32-point constellation, makes the 8D code of the present invention more immune to phase jitter and channel non-linearities. In addition, when the received baseband signal point is used for equalizer updating and carrier tracking, the 20-point constellation gives more reliable decision directed performance.

An object of the present invention is to use a modem having an 8D trellis code with a 20-point 2D constellation for transmitting at 9600 bps.

Another object of the present invention is to provide a specific 20-point constellation.

Still a further object of the present invention is to perform a method for the optimum slicing regions.

Another object of the present invention is to provide a method of slicing subsets B, C, and D by rotating the received point by the appropriate multiples of 90.degree. and using the A slicer.

Still another object of the present invention is to provide a trellis code which gives a higher coding gain for high signal-to-noise ratios.

FIG. 1 shows 16 possible signal points of a 4.times.4 two dimensional QAM.

FIG. 2(a) shows a system block diagram for the transmitter.

FIG. 2(b) shows a memory block diagram for the 64-State 8D Encoder.

FIG. 3 shows a 20-point 2D signal constellation for the 8D code.

FIG. 4 shows the block diagram of the 64-State 8D Encoder system.

FIG. 5(a) shows the encoder trellis state transitions from even number states to the next state.

FIG. 5(b) shows the encoder trellis state transitions from odd number states to the next state.

FIG. 6(a) shows the system block diagram for the receiver.

FIG. 6(b) shows a memory block diagram for the 8D Viterbi Decoder.

FIG. 7 shows the general flow chart for the 8D Viterbi Decoder.

FIG. 8 shows the optimum decision regions for subset A.

An uncoded V32 modulation scheme accepts 4 bits per baud and maps the 16 possible combinations into the 4.times.4 two dimensional QAM (Quadrature Amplitude Modulation) constellation shown in FIG. 1. The minimum distance between points in this constellation is d=2. The average signal power, which is the sum of the squared distances of the signal points from the origin divided by 16, is S=10=2.5d.sup.2. The symbol error probability in the presence of additive white Gaussian noise can be shown to be as follows:

where

SNR is the signal-to-noise ratio measured in the Nyquist band and ##EQU1## where y=-t.sup.2 /2.

The standard V32 trellis encoder also accepts 4 bits per baud. An 8 state rate 2/3 trellis encoder generates one check bit and the resulting 5 bits are mapped to the 32-point cross 2D (D is an abbreviation for dimensional which will be used throughout the specification and claims) constellation. At high signal-to-noise ratios, this code gives a 4.01 dB coding gain over the uncoded 4.times.4 QAM mode.

FIGS. 2(a) and (b) show in block diagram the transmitter of the present invention.

To generate an 8D code that accepts L bits/baud, a 2D constellation of 2.sup.L points on a rectangular lattice is first selected. The 64-State 8D Encoder (42) accepts L=4 bits/baud. Thus, the 4.times.4 constellation as shown in FIG. 1 is selected. These points are called the inner points. A set of 2.sup.L /4=4 outer points selected from the rectangular lattice to preserve symmetry and have minimum energy are added to the inner points resulting in the 20-point constellation as shown in FIG. 3. The 4.times.4 set of inner points is shown enclosed by the dotted lines. These 20 points are partitioned into the 4 subsets A, B, C, and D as shown in FIG. 3. Each subset contains 5 points and the minimum distance between points in a subset is df=4. Under 90 degree clockwise rotations, subset A points rotate into subset C points, C rotates into B, B rotates into D, and D rotates into A. This is one reason why the code is transparent to 90 degree rotations.

A block diagram of the 64-State 8D Encoder (42) is shown in FIG. 4 and is comprised of a trellis encoder (18) which adds a check bit, a bit converter (16) to convert the eight bits into a sequence of four 2D subsets, and a differential encoder (14) which makes the code transparent to 90 degree rotations. Each of these components is described in more detail hereinafter.

The 64-State 8D Encoder (42) accepts blocks of 16 successive bits from the data source taken four bits per baud. In the block diagram of FIG. 4, these are labelled I1n,I2n,I3n,I4n,I1n+1,I2n+1,I3n+1,I4n+1,I1n+2,I2n+2,I3n+2, I4n+2,I1n+3,I2n+3,I3n+3,I4n+3. The bits are taken from the data source sequentially in time from left to right. The subscripts n, n+1, n+2, and n+3 indicate four successive bauds.

The 9 data bits (I4n+1,I1n+2,I2n+2,I3n+2,I4n+2,I1n+3, I2n+3,I3n+3, and I4n+3) determine the specific 8D point within the 8D subtype. The number of points within an 8D subtype is 2.sup.17 /256=2.sup.9. This is the number of distinct values the 9 data bits can have.

The 8D BLOCK ENCODER (12) shown in FIG. 4 maps the 9 data bits into the 12 Z bits (Z2n+i, Z3n+i, Z4n+i) for i=0, 1, 2, and 3. These triplets of Z bits specify the sequence of four 2D constellation points corresponding to the sequence of four 2D subsets of the 8D subtype selected. The assignments of (Z2, Z3, and Z4) to 2D points is shown in FIG. 3 and Table 1.

The assignment of (Z0, Z1, Z2, Z3, Z4) can be implemented by a 32.times.2 look-up table (48) such as shown in FIG. 2(b). Notice that when Z2n+i=1 an outer pont is selected and when Z2n+i=0 an inner point is selected. Either a sequence of four inner points or one outer point and three inner points must be selected. The 8D BLOCK ENCODER (12) makes this assignment according to the rules in Table 2.

The data bit I4n+1 determines if an outer point is included. When I4n+1=0 no outer point is included and when I4n+1=1 an outer point is included. The bits (I1n+2,I2n+2) determine which of the four positions the outer point occupies.

The first three data bits (I1n, I2n, I3n) drive the systematic, rate 3/4, 64 state, feedback convolutional encoder (18). The rate 3/4 convolutional encoder (18) generates one check bit from the first three data bits and its present state. The convolutional encoder (18) generates the one check bit labelled YOn. The logic equations for the trellis encoder (18) are

The symbol, +, on the right side of the equations represents exclusive or.

The input bits I1n, I2n, and I3n direct the convolutional encoder (18) through a sequence of states. The trellis-encoder state consists of the six W bits in FIG. 4. Each state can make a transition to eight distinct next states and each state can be arrived at from eight distinct previous states. The three input bits can be uniquely determined from two successive states. An 8D subset is assigned to each state transition. These transitions and subset assignments are displayed as a "trellis" diagram when there are only a few states. In this case, the trellis encoder (18) has 64 states so the transitions and subset assignments have been displayed in FIGS. 5(a) and (b) which can be stored in memory (46).

The resulting 17 bits are mapped to a 2.sup.17 point 8D constellation. The 8D points consist of a sequence of four 2D points each selected from the 20-point 2D constellation of FIG. 3. The 8D points are selected such that at most one outer point is transmitted in the sequence of four 2D points. That is, either four inner points or one outer and three inner points are transmitted per block. The number of ways of selecting all inner points is

and the number of ways of selecting one outer and three inner points is

Thus the total number of 8D constellation points is

which is the required number of points.

The probability of selecting a point from the inner set on a given baud is

and the probability of selecting an outer point on a particular baud is

This can be shown in the following way. An inner point is selected in the first baud if four inner points are transmitted or if an inner point is transmitted first and one of the remaining three points is an outer point. The number of ways this can happen is

The number of ways an outer point can be selected in the first baud is

then Pin=Nin/(Nin+Nout) and Pout=1-Pin.

The average transmitted signal power for each baud is ##EQU2## The minimum free Euclidean distance for the 64-State 8D Encoder (42) is equal to the minimum distance between points within one of the 2D subsets which is df=4. At high signal-to-noise ratios, the coding gain is ##EQU3##

The differential encoder (14) shown in FIG. 4 differentially encodes the bits (I3n+1,I2n+1) to make the code transparent to 90 degree rotations. A truth table for the differential encoder (14) is given in Table 3 which could also be stored in a memory such as memory (44).

If the pairs of bits are considered to be two bit binary numbers, the differential encoding rule is (I3n+1', I2n+1')=(I3n+1, I2n+1)+(I3n-3', I2n-3') mod 4. Here the symbol, +, on the right side represents ordinary decimal addition. The differential decoder in the receiver performs the inverse operation and is also described by Table 3 for the equation

The 2.sup.17 8D constellation points are partitioned into 16 subsets labelled 0, 1, . . . 15. The subsets are formed by first partitioning the 20-point 2D constellation into the four subsets, A, B, C, and D as shown in FIG. 3. The minimum Euclidean distance between points within a 2D subset is d=4. Next, eight 4D subsets are formed by concatenating pairs of 2D subsets as shown in Table 4.

The minimum Euclidean distance between points in the 4D subsets is also 4. Finally, pairs of 4D subsets are combined to form sixteen 8D subsets as shown in Table 5.

It should be noted that the integers under the column labelled 8D types refer to the 4D types defined in Table 4.

Again, the minimum Euclidean distance between points in an 8D subset is 4. Each 8D subset consists of four 8D types and each 8D subset type contains four 8D subtypes so that each 8D subset contains sixteen 8D subtypes. Thus, there are 16.times.16=256 8D subtypes. The four bits (I3n, I2n, I1n, YOn) determine the 8D type, while the four bits (I3n+1', I2n+1', I1n+1, I4n) determine the subtype within the 8D type.

The bit converter (16) shown in FIG. 4 maps these eight bits into a sequence of four 2D subsets specified by the eight Z bits, Z1n, ZOn, Z1n+1, ZOn+1, Z1n+2, ZOn+3, Z1n+3, ZOn+3). Each pair (Z1, ZO) specifies a 2D subset according to the following rule.

Notice that these are assigned so that under 90 degree clockwise rotations, each 2D subset becomes the one below it. An algorithm for selecting the 8D subtype is shown in Table 6.

A block diagram of the receiver system is shown in FIGS. 6(a) and (b). The demodulator (26) sends received 2D symbols to the 8D Viterbi Decoder (28). The general flow chart for the 8D Viterbi Decoder (28) is shown in FIG. 7. Each 2D symbol consists of a pair of x and y coordinates that represent the baseband received 2D symbol. Each block of four consecutive 2D symbols is a received 8D symbol. The 8D Viterbi Decoder (28) must first quantize the received 8D point to the nearest point in each of the sixteen 8D subsets. This can be efficiently accomplished by going from 2D to 4D to 8D decisions as described hereinafter.

In the decoding process, each received 2D point must be sliced to the nearest point in each of the four 2D subsets. These subsets are labelled A, B, C, and D. Each subset contains 5-points and a 90.degree. rotation of any subset becomes another subset. The optimum way to slice a received point is to choose the closest ideal point. Since each subset is a 90.degree. rotation of subset A, their slicers can be implemented by first rotating the received point by the appropriate multiple of 90.degree. and then using the A slicer.

The 8D Viterbi Decoder (28) first quantizes each received 2D symbol to the closest constellation point in each of the 2D subsets A, B, C, and D. For each of these four subsets, the 8D Viterbi Decoder (28) saves the Z bits (Z2, Z3, Z4) and the corresponding squared Euclidean distance between the received and quantized points. If the received point is (X, Y) and the ideal point is (x, y), the squared Euclidean distance is

This process is performed for a block of four 2D symbols that make up an 8D symbol.

The optimum decision regions for subset A are shown in FIG. 8. The equations describing each decision region are given in Table 7.

Under 90 degree clockwise rotations, A.fwdarw.C.fwdarw.B.fwdarw.D, the decoder (28) can use the subset A slicing routine for the C, B, and D subsets also by rotating the received 2D point by 90, 180, and 270 degrees counterclockwise, respectively. Using this method, the 90 degree counterclockwise rotation of the point (x, y) is (x, y) rotated 90 degrees counterclockwise=(-y, x).

The next step is to combine pairs of 2D decisions into two 4D decisions. Let the squared Euclidean distance determined in the 2D decisions previously described for 2D subset "s" in baud n+i be as follows,

For the first pair of received 2D symbols each of the eight 4 subsets listed in Table 4 is compared and the point that has the smallest squared Euclidean distance in the pair of 4D types associated with the subset is selected. Next, the associated set of Z bits and corresponding squared distances are recorded. The process is repeated for the second pair of received 2D symbols and so forth. For example, consider the first pair of received 2D symbols and 4D subset 0 of Table 4.

The best point in (A,A) or (B,B) must be found. The two 4D squared Euclidean distances are calculated as

Next, the two D's are compared and the smallest is retained together with the Z bits for the corresponding pair of 2D subsets. The same operation is performed for 4D subsets 1, 2, 3, 4, 5, 6 and 7.

The next step is to combine the 4D decisions described into 8D decisions, one for each of the sixteen 8D subsets defined in Table 5.

It is important to note that the integers under the column labelled 8D types refer to the 4D types defined in Table 4.

For each of the 8D subsets, four 8D types must be compared. The squared Euclidean distances for the 8D types are the sums of the corresponding pairs of 4D distances computed as previously described. Again, the smallest distance for each 8D subset is saved along with the corresponding Z bits.

The procedure just described for finding the closest 8D constellation point to the received 8D point can fail in one way. This procedure does not guarantee that at most one outer point appears in the sequence of four 2D symbols. The decoder (28) could check if more than one outer point was selected and go back and alter intermediate decisions. However, the probability that this occurs is very small and the easiest strategy would be to move the 2D outer points with largest squared Euclidean distance to the nearest inner points in the same 2D subset so that the resulting 8D point has only one 2D outer point.

Now the Viterbi algorithm is performed to update the decoder trellis paths. A general description of the algorithm will be given first. The basic principle of the Viterbi algorithm is that for each received 8D symbol, the best path to each of the 64 possible encoder states is determined. The best path to a state is the one with the smallest cumulative sum of squared Euclidean distances and is called the survivor to the state. The corresponding cumulative squared Euclidean distance is called the surviving metric for the state. This operation is performed for each new received 8D symbol recursively. There are 8 possible paths that can converge to each state and these can be determined from the encoder state transition equations or from FIGS. 5(a) and (b) along with the 8D subset associated with the transition. For each present state, the eight metrics for the paths that can enter the state are computed from the metrics for the eight possible previous states and the squared Euclidean distances for the subsets corresponding to the transitions. The smallest of the eight resulting metrics is selected and the corresponding previous state is designated as the best previous state. This operation is repeated for each of the present 64 states. In principle, this process should be repeated for the entire transmitted message with the resulting best path selected as the decoded message. In practice, the trellis can only be stored for some time into the past. Therefore, the present state with the smallest metric is selected and the symbol farthest back in the trellis on the path leading to this state is selected as the estimate of the transmitted symbol for that time instant.

Some details of the 8D Viterbi Decode: (28) implementation will now be described. These principles can be applied in any programmed implementation. For each received 3D symbol, an array of 64 records is created, one record for each encoder state. The arrays for successive received 8D symbols are stored in a circular buffer. A record for current state i consists of the best previous state leading to state i and the twenty Z bits for the best 8D point in the subset corresponding to the state transition. A 64.times.2 array is used to store the surviving metrics. Half this array is used to store the surviving metrics for the previous 8D symbol while the other half is used to store the surviving metrics being determined for the present symbol. Two 64 word arrays are required since the previous metrics are used in computing the metrics for several present states and cannot be destroyed before they are used for all the metric updates. The new surviving metrics are written into the half of the array that has metrics for two symbols ago and, hence, flip-flop between the two array halves for successive symbols. Metrics for states farther back in the trellis than the previous state are not needed. Let D(k,i) be the surviving metric at the current 8D symbol time k for state i, and d(k-1,k,i,j) be the squared Euclidean distance for the 8D symbol determined by the quantization of the received 8D symbol described above for the 8D subset specified by the transition from state j at time k-1 to state i at the present time k. Also let J(i) be the set of eight previous states that can converge to state i. The metrics are updated by performing the following calculation for i=0, . . . , 63: ##EQU4## The value of j that gives the minimum is the best previous state converging to state i. As described hereinabove, the encoder state transition information is stored in a table. There are 64 records in the table, one for each present state. The first eight entries in a record i are the states that can converge to state i and are the set J(i). The second eight entries are the 8D subsets corresponding to the transitions from j to i. Using this table in evaluating D(k,i) is the most computationally efficient method. The surviving metrics D(k,i) grow monotonically with k. Therefore, in a practical implementation the size of the metrics should be checked periodically, and if they become too large, a constant should be substracted from all 64 of them. A reasonable choice for this constant is the smallest metric. This resets the smallest metric to zero. Since the surviving metrics correspond to the best path to each state, these metrics tend to remain close in size.

Once the metrics are updated, the next step is to find the current state, i*, with the smallest metric. Starting with this state, the trellis is traced back to its end. The trellis record for i* points to the record for the previous best state leading to i* which points to the record for its previous best state, etc. The decoded 20 Z bits are found at the end of the trellis path.

The final step is to convert the twenty Z bits back into sixteen data bits. The eight Z bits Z0n, Z1n, Z0n+1, Z1n+1, Z0n+2, Z1n+2, Z0n+3, Z1n+3 can be converted into the seven information bits I1n, 12n, I3n, I4n, I1n+1, I2n+1', I3n+1' most easily by using a table look-up memory such as a 256 entry table. This table can be generated by first forming a bit converter table using the rules in Table 6 and then forming an inverse bit converter table from it. Bits I2n+1' and I3n+1' must be differentially decoded to I2n+1 and I3n+1. This can be performed quickly by a 16 entry table with input (I2n-3', I3n-3', I2n+1', I3n+1') and output (I2n+1, I3n+1) as shown in Table 3. Alternatively, it can be performed by subtraction module 4 as previously shown. The remaining twelve Z bits could be 8D block decoded by a table look-up memory also. However, this memory table will be relatively large. A more practical method would be to use a software procedure to perform the inverse of the 8D Block Encoder operations described in Table 2.

The major portion of the decoder computation is trellis updating. This requires additions and comparisons. The decoder (28) must also form squared Euclidean distances which requires multiplication or a large look-up table memory. Storage for the trellis with depth between 16 and 32 is also required. An ordinary microprocessor would perform the required computation quite slowly. However, a digital signal processor comparable to the TMS320C25 will be fast enough and allow access to sufficient internal and external RAM and ROM.

Changes and modifications in the specifically described embodiments can be carried out without departing from the scope of the invention which is intended to be limited only by the appended claims.