METHOD AND APPARATUS FOR DECODING PUNCTURED TRELLIS CODE MODULATED DATA BACKGROUND OF THE INVENTION Trellis-coded modulation (TCM) combines channel coding and modulation at a transmitter. Information bits are sent into a TCM encoder in parallel. The least- significant bits (LSBs) are convolutionally encoded. The most-significant bits (MSBs) are usually left uncoded and combined with the output of the convolutional coder to form a symbol on a signal constellation through a signal mapper. One advantage of TCM is that although no error control coding is performed on any bit other than the LSB of the input information data, the decoder is able to provide error correction on all bits. Therefore, significant coding gain over uncoded modulation can be achieved.

The best convolutional codes for TCM were described in the paper"Channel Coding with Multilevel/Phase Signal", G. Ungerboeck, IEEE Transactions On Information Theory, pp. 55-67, January 1982. Unfortunately, for any particular code rate, the maximum coding gain requires a different convolutional code. To achieve versatility, pragmatic TCM (PTCM) was developed, as described in"A Pragmatic Approach to Trellis-Coded Modulation", A. J. Viterbi et al., IEEE Comm.

Magazine, pp. 11-19, July 1989. The fundamental concept in PTCM is that an industry standard convolutional code of rate 1/2, constraint length v=6 is used as the core coder inside the TCM encoder. A tradeoff relative to the Ungerboeck approach is somewhat lower coding gain is achieved. However, even though a lower coding gain is realized, it is very close to the optimum coding gain of the Ungerboeck codes at bit-error rates of interest. A key advantage of PTCM is that with a single standardized core convolutional coder/decoder, different types of TCM with various code rates can be easily constructed. This benefits the decoder design especially, since the same Viterbi decoder can be employed for different modulations.

Another advantage of the PTCM scheme is that the code rate can be made variable by puncturing the convolutional coder. Puncturing means that certain bits from the convolutional coder output are deleted. The resultant structure is called <BR> <BR> Punctured Pragmatic TCM (P2TCM), which was disclosed in llp2 Codes: Pragmatic Trellis Codes Utilizing Punctured Convolutional Codes", J. K. Wolf and E. Zehavi, IEEE Comm. Magazine, pp. 94-99, February 1995. In the P2TCM approach, the core of the trellis coder is a punctured version of the industry standard, rate l/2 convolutional code. This approach was shown to lead to a wide class of high-rate pragmatic punctured trellis codes of rate n/n+1 for both phase-shift keying (PSK) and quadrature amplitude modulation (QAM) modulations. For a digital satellite broadcasting application, for example, a rate 5/6 P2TCM 8-PSK coded modulation provides 25% higher throughput than a rate 2/3 PTCM 8-PSK coded modulation using the same amount of bandwidth. A tradeoff is that the rate 5/6 P2TCM 8-PSK coded modulation has an asymptotic coding gain approximately 1.4dB inferior to that of the non-punctured, rate 2/3 PTCM 8-PSK coded modulation.

In general, a trellis diagram can be used to represent the response of a convolutional coder to an input stream. Each trellis stage includes a fixed number of nodes that represent the possible states of the coder. The states are connected such that each state has inputs from disjoint states in the preceding stage and outputs to disjoint states in the succeeding stage. The connections represent possible state transitions and are more commonly referred to as branches.

The decoding of TCM signals can be performed efficiently using the well- known Viterbi algorithm. The Viterbi algorithm selects the best path along the branches of the trellis diagram to determine the originally transmitted input stream from a received sequence of symbols. The algorithm bases this selection on a measure of the accumulated squared (Euclidean) distance between the received symbols and possible points on a signal constellation. The Euclidean distance measurement is made for each branch of the trellis diagram and is referred to as a branch metric. At each trellis stage, the branch metric is added to the accumulated error for each state. This accumulated error is also called a state metric. A

comparison is made between the two incoming branches and the branch with the smaller accumulated error is selected as the survivor branch for each state of the trellis stage.

A sub-optimal algorithm for decoding punctured pragmatic TCM was disclosed in"Performance of Punctured Pragmatic Codes", T. Woerz and R.

Schweikert, Proc. IEEE Global Telecommunications Conference GLOBECOM'95, pp. 664-669, November 1995. That paper defined an approach wherein it is possible to use the original trellis diagram for decoding punctured convolutional codes of a P2TCM code with the Viterbi algorithm by applying a particular approximation of the standard branch metric. That approximation requires additional computations and comparisons beyond the standard branch metric in order to select survivor branches.

SUMMARY OF THE INVENTION The known approaches to decoding punctured TCM are computationally complex. It is desirable to use a simpler approach to achieve more efficient decoding.

The present invention provides an improvement to the decoding of punctured TCM which uses the standard branch metric for certain received symbols and for other received symbols uses a branch metric that is based on a partial distance metric. The present invention is applicable to PSK and QAM modulation schemes.

According to the present invention, a method and apparatus for decoding punctured symbols in a state machine includes computing a first partial distance metric for each state in a first interval and selecting a survivor path based on the first partial distance metric. In a second interval, a second partial distance metric is computed for each state and a survivor path is selected based on the second partial distance metric.

According to an aspect of the invention, the partial distance metrics are accumulated in the state metrics for each state for punctured symbols in a sequence of received symbols, and the regular Euclidean distance metrics are accumulated in state metrics for each state for the unpunctured symbols in the sequence. The survivor paths are traced back from a state for a sequence of received symbols.

The symbols correspond to a signal constellation space having inphase (I) and quadrature (Q) coordinates. Each partial distance metric is computed from one component selected from the I and Q components of a distance measure between the received punctured symbol and signal points in the signal constellation.

According to an aspect of the invention, the received symbols represent punctured trellis code modulated data encoded according to an encoding format wherein input data bits are encoded as alternating symbols of first and second type, the first type symbol including at least one first uncoded data bit and a pair of unpunctured coded data bits, the second type symbol including at least one second uncoded data bit and a pair of punctured coded data bits. The first type symbols are decoded based on distance metrics computed from both I and Q components of the

distance measure between the received symbol and signal points in the signal constellation and the second type symbols are decoded based on the partial distance metrics.

According to another aspect of the invention, the distance measure for decoding symbols encoded without puncturing can be based on the LP-norm with Vp, 1 <p<2. When p=2, the L2-norm is the Euclidean distance.

The term"punctured symbols"is used to indicated symbols that are formed from punctured bits. The term"unpunctured symbol"is used to indicate symbols formed from unpunctured bits.

BRIEF DESCRIPTION OF THE DRAWINGS The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

FIG. 1 is a block diagram of an exemplary rate 2/3 PTCM encoder for 8-PSK modulation.

FIG. 2 is a block diagram of an exemplary rate 5/6 P2TCM encoder for 8- PSK modulation.

FIG. 2A shows the output of a convolutional coder of FIG. 2.

FIG. 3 is a diagram illustrating a signal constellation for 8-PSK modulation.

FIG. 4 illustrates a portion of a trellis diagram for rate 2/3 PTCM 8-PSK modulation.

FIG. 5 illustrates a portion of a trellis diagram for rate 5/6 P2TCM 8-PSK modulation.

FIG. 6 is a block diagram of an embodiment of a decoder in accordance with the present invention.

FIG. 7 is a flow diagram showing a decoding method in accordance with the present invention.

FIG. 8 is a diagram of bit-error rate curves for decoding rate 2/3 PTCM and rate 5/6 P2TCM 8-PSK through computer simulations.

FIG. 9 is a block diagram of a rate 3/4 PTCM encoder for 16QAM FIG. 10 is a block diagram of a rate 7/8 P2TCM encoder for 16QAM FIG. 11 is a portion of a trellis diagram for rate 3/4 PTCM for 16QAM FIG. 12 shows signal constellation for 16QAM.

FIG. 13 is a portion of a trellis diagram for rate 7/8 P2TCM for 16QAM.

FIG. 14 is a diagram of bit-error rate curves for decoding rate 3/4 PTCM and rate 7/8 P2TCM 16QAM through computer simulations.

DETAILED DESCRIPTION OF THE INVENTION The present invention is now described with reference to an embodiment that uses 8-PSK modulation. It should be understood, however, that the principles of the invention can be applied to other modulation schemes including M-ary QAM (e. g., 16-QAM).

FIG. 1 is an exemplary rate 2/3 PTCM encoder for 8-PSK modulation. As shown in FIG. 1, two information bits (the MSB is labeled"a,"and the LSB is labeled"ao") are provided as input to a TCM encoder. The"a,"bit is left uncoded and serves as the MSB on the 8-PSK constellation output from an 8-PSK signal mapper 12. The"aO"bit is convolutionally encoded by a rate 1/2 encoder 10, using the industry standard generator polynomials G, (D) =l+D+D2+D3+D5+D6 and G2 (D) =1+D+D2+D3+D6, to yield two bits labeled as bo (l) and bo (°). These two bits serve as the middle bit and LSB on the 8-PSK constellation, respectively.

FIG. 2 is an exemplary rate 5/6 P2TCM encoder for 8-PSK coded modulation. The rate 5/6 P2TCM encoder is very similar to the rate 2/3 PTCM 8- PSK encoder, except that the rate 1/2 convolutional coder is now punctured to a rate 3/4 convolutional coder 16. The encoder provides alternating symbols designated as Type I and II symbols respectively. The Type I symbol is constructed by using the

uncoded bit"a,"as the MSB and unpunctured bits bo (l) and bo (°) (middle bit and LSB respectively). The Type II symbol is constructed by using another uncoded bit"a3" as the MSB and punctured bits b''and b (middle (middle and LSB respectively).

FIG. 2A shows the output of the convolutional coder 14. Note that two bits, b2 (°) and b4 (i), have been deleted due to the puncturing function. The alternating symbols are mapped to signal points of the 8-PSK constellation by 8-PSK signal mapper 16 for transmission over a channel to a receiver.

There is one-to-one correspondence between the 3 bits at the output of the signal mapper 12,16 and a signal point on the 8-PSK constellation. In the preferred embodiment, a specific mapping between binary digits and phases of the 8-PSK signal is assumed as shown in FIG. 3 in an I, Q (inphase, quadrature) plane coordinate system. The mapping is 5°=001,67. 5°=011, 5°=100,202.5°=101,247. 5°=111 and 292.5°=110. A grid of squares or cells 18 is shown superimposed over the constellation and is described further herein.

As noted above, PTCM encoding uses the industry standard rate 1/2 convolutional encoder. This can be modeled as a finite-state machine having 64 states which correspond to the industry standard convolutional encoding polynomials G, (D) and G2 (D). More specifically, Eq. (la) CI [k] = I [k] + I [k-2] + I [k-3] + I [k-5] + I [k-6] Eq. (lb) C2 [k] = I [k] + I [k-1] + I [k-2] + I [k-3] + I [k-6] where C, and C2 correspond to bits bo and bo (FIG. 1) and I represents the input to the convolutional coder.

It can be seen that each state is a function of {I [k-1], I [k-2], I [k-3], I [k-4], I [k-5], I [k-6]}, with transitions from one state to another state depending on I [k].

The indices of the 64 states in the trellis represent the status of the registers inside the convolutional coder. For example, S6 indicates that {I [k-1], I [k-2], I [k-3], I [k-4], I [k-5], I [k-6]} = {0,0,0,1,1,0}

and S32 indicates that {I [k-1], I [k-2], I [k-3], I [k-4], I [k-5], I [k-6]} = { 1,0,0,0,0,0} and so on.

Reference is now made to FIG. 4 which shows a portion of a trellis diagram for the rate 2/3 PTCM 8-PSK. There are three trellis stages shown (m, m+1, m+2).

The branches between states Si are indicated by dashed lines 20 and solid lines 22.

The dashed lines 20 represent branches in which the uncoded bit a, =0 and the solid lines 22 represent branches in which the uncoded bit a, =1. The branches are further labeled according to the format I (input)/C, C, (output). For example, the branch label"0/11"indicates that an input at the convolutional coder of a 0 data bit provides output data bits 11 according to Eqs. (l a) and (lb).

For each state in the present trellis stage (e. g., stage m+1), there are two arriving branches merging from two states in the previous trellis stage (e. g., stage m). Each of the merging branches in turn comprises parallel transitions 20,22 due to the fact that the uncoded data bit a, can have a value of either 1 or 0. The two states in the previous stage share the same values of I [k], I [k-1], I [k-2], I [k-3], I [k-4], I [k-5] but have different values of I [k-6]. Also for each state, there are two leaving branches diverging to two states in the next stage of the trellis (e. g., stage m+2).

These two states in the next stage share the same values of I [k-1], I [k-2], I [k-3], I [k- 4], I [k-5], I [k-6] but have different values of I [k]. Therefore, for each transition between two arbitrary states, complete information for the values of {I [k], I [k-1], I [k-2], I [k-3], I [k-4], I [k-5], I [k-6]} is available, which in turn determines the output bits of the convolutional coder based on Eqs. (1 a) and (lb). Along with the uncoded bit (either a, =0 or a, =l for the 2 parallel transitions), a complete description of the 3 bits at the TCM output is available, corresponding to a signal point on the 8-PSK constellation. This signal point is what is expected to be received if the corresponding transition is indeed part of the optimal path in the trellis.

As noted above, the trellis code modulated data is sent over a transmission channel to a receiver. In general, the received signal in the complex, discrete time domain can be modeled as follows:

Eq. (2) r (n) = s (n) + z (n) where r (n) is the received signal, s (n) is the original transmitted symbol (one of 8 possible signal points of the 8-PSK constellation) and z (n) is additive white Gaussian noise (AWGN) with independent I, Q components that follow the Gaussian distribution N (O, (J2).

The error between the received signal r (n) and the original transmitted symbol s (n) is defined as: Eq.(3)|r(n)-s(n)|2= This squared error measure is usually used assuming the additive noise is strictly white Gaussian, since the optimal metric measure is L ; nom for AWGN. An improvement to the squared error measure is described further herein which uses an Lp-norm.

A description of trellis decoding for the rate 2/3 PTCM 8-PSK modulation is now provided. This will be followed by a description of decoding for the rate 5/6 P2TCM 8-PSK modulation.

As noted in the background, the decoding of TCM signals is typically performed using the well-known Viterbi algorithm wherein the best path along the branches of the trellis diagram is selected to determine the originally transmitted input stream from a received sequence of symbols. The selection is based on a measure of the accumulated Euclidean distance between the received symbols and possible points on the signal constellation. The Euclidean distance measurement or branch metric is made for each branch of the trellis diagram. At each trellis stage, the branch metric is added to the accumulated error or state metric for each state. A comparison is made and the branch with the smaller accumulated error is selected as the survivor branch for each state of the trellis stage. This add-compare-select operation is typically performed in a Viterbi decoder. Thus, such processing of all 64 states at a particular trellis stage yields 64 survivors (one survivor for each state)

and 64 new state metrics (one metric for each state). This process repeats along the trellis diagram as new symbols arrive.

The branch metric calculation (Eq. (3)) is performed before the add-compare- select (ACS) operation and can be implemented via look-up table. The look-up table may partition the 2-dimensional I-Q plane into a finite number of cells 18 (FIG. 3).

Each cell 18 stores eight values which are the respective distances to the eight signal points for the 8-PSK constellation.

Each state Si can be implemented as a data structure which contains: the indices of the two previous states to which this state is connected; a pointer indicating the survivor branch; data bit value of 0 or 1 corresponding to the uncoded bit a,; and data bit value of 0 or 1 corresponding to the convolutional coder input bit 1. In addition, an array of 64 elements stores the up-to-date state metric for each state.

Referring again to FIG. 4, when the k"symbol arrives, for example, at stage m, an initial determination is made as to which branch of the 2 parallel transitions 20,22 for each state participates in the above-noted ACS operation. Recall that the parallel transitions are due to the uncoded bit a, being equal to either 1 or 0. This determination is made by comparing the branch metrics (Eq. (3)) for the parallel transitions and selecting the smaller metric. This selection of the parallel transition is independent from the Viterbi decoder, and is a modification that is made to a standard Viterbi decoder to provide a trellis decoder.

Next, for each state, since the two previous states are known from the stored indices in the state data structure, the"old"or previous state metrics associated with these two states are retrieved. The branch metrics obtained from Eq. (3) are used to update the two respective state metrics, and a comparison is made to see which branch provides a smaller overall metric. This is the aforementioned ACS operation.

The pointer is set to the state that is connected by the branch with the smaller overall metric. This branch is the survivor for the state under consideration. Finally, the state metric for that state is updated. This process is repeated until all 64 states are

considered. Then the process continues with the next trellis stage (e. g., stage m+1) when the (k+l) St symbol arrives.

The above algorithm relates to trellis decoding of standard rate 2/3 PTCM 8- PSK. Now a description of decoding for punctured rate 5/6 TCM 8-PSK is provided in accordance with the present invention.

Trellis decoding for P2TCM requires some modifications to the approach described above. The difference between PTCM and P2TCM is evident from the partial trellis diagram shown in FIG. 5. The partial trellis diagram for rate 5/6 P2TCM 8-PSK includes four trellis stages (m, m+l, m+2, m+3). The trellis interval between stages m and m+1 is designated as Type I symbol. The succeeding trellis intervals between stages m+1, m+2 and m+2, m+3 are designated first and second intervals, respectively, of Type II symbol. The branches between states Si in the Type I interval are indicated by dashed lines 30 and solid lines 32. The dashed lines 30 represent branches in which the uncoded bit a, =0 and the solid lines 32 represent branches in which the uncoded bit a, =1. The branches between states S ; in the Type II first and second intervals are indicated by dashed lines 40 and solid lines 42. The dashed lines 40 represent branches in which the uncoded bit a3=0 and the solid lines 42 represent branches in which the uncoded bit a3=1. The branches are further labeled according to the format I (input)/C, C, (output). In the Type I symbol interval, for example, the branch label"0/11"indicates that an input at the convolutional coder of a 0 data bit provides output data bits 11 according to Eqs. (la) and (lb) and corresponding to bits bo (') and bo (°) of the 8-PSK signal. In the first Type II symbol interval, the branches are labeled e. g.,"0/OX"to indicate corresponding output bit b2 (') and the erased bit b2 (°). Likewise, in the second Type II symbol interval, the branches are labeled e. g.,"0/X1"to indicate corresponding the erased bit b4 output bit b4 (where"X"means"don't care").

The difference between the trellis diagram in FIG. 5 and that in FIG. 4 is that for the punctured symbol (Type II), two trellis intervals are required to represent the transitions caused by one incoming symbol. Also, the uncoded bit a3 (see FIG. 2 for the labeling conventions of the modulator) must be consistent within the two trellis

intervals for Type II symbol. In other words, if a3 is 0 (or 1) for the first trellis interval, it must also be 0 (or 1) for the second trellis interval.

Decoding for the Type I symbol is identical to the standard trellis decoding approach described above for the rate 2/3 PTCM. The optimal decoding approach for Type II symbol would be to wait at the end of the second interval of the trellis and select the survivor branches at that time. However, this would require that each state have four incoming branches that merge. Thus, the trellis decoder would be time-varying (i. e., selecting a survivor from 2 branches for Type I symbol and selecting a survivor from 4 branches for Type II symbol).

In order to use the same standard 64-state Viterbi decoder, i. e., to be able to select a survivor out of 2 merging branches at every stage of the trellis, requires a sub-optimal solution. The approach of the present invention uses a partial distance metric for decoding the Type II symbol: Eq-(4a) ds2 = l r, (n)-s(4a) ds2 = l r, (n)-s (n) 12 Eq. (4b) dQ'rQ (n)-sQ (n) The partial distance metric uses only one of the orthogonal components I, Q rather than both components as is used in the standard branch metric of Eq. (3). Which orthogonal component I, Q to use depends on the value of the middle data bit b2 in the first interval. If data bit b2 (') is 1, then the quadrature phase measure is used to form the branch metric; if data bit b2 (') 0, then then inphase measure measure used. used. becomes evident in the following example.

In general, for this decoding approach, as in the decoding of the Type I symbol, an initial determination is made as to which branch of the 2 parallel transitions 40,42 for each state participates in the ACS operation. Recall that the parallel transitions are due to the uncoded bit a3 being equal to either 1 or 0. This determination is made by comparing the partial branch metrics (Eq. (4a) or (4b)) for the parallel transitions and selecting the smaller metric. Next, a survivor is selected between 2 merging branches using the ACS operation. In the second trellis interval

branch metric; if data bit b2 (') is 0, then the inphase measure is used. This becomes evident in the following example.

In general, for this decoding approach, as in the decoding of the Type I symbol, an initial determination is made as to which branch of the 2 parallel transitions 40,42 for each state participates in the ACS operation. Recall that the parallel transitions are due to the uncoded bit a3 being equal to either 1 or 0. This determination is made by comparing the partial branch metrics (Eq. (4a) or (4b)) for the parallel transitions and selecting the smaller metric. Next, a survivor is selected between 2 merging branches using the ACS operation. In the second trellis interval of Type II symbol, a survivor is selected between 2 merging branches using the decoded information from the first interval.

The following example is used to explain the foregoing decoding approach of the present invention with reference to FIG. 5.

As noted above, the Type I symbol is decoded easily using the standard trellis decoder. Now it is best to view processing of the Type II symbol from the first interval at trellis stage m+2, at for example state So, and look backward at the previous trellis stage m+1. There are 2 branches merging from states So and S,, respectively. Each branch is in fact 2 parallel transitions 40,42 because the uncoded bit a3 may be either 0 or 1. To eliminate one of the parallel transitions 40,42, e. g., those transitions linking state So to state So in the first interval, a determination is made whether the received symbol is closer to the two signal points OOX or to the two signal points 10X. This implies, from the signal constellation of FIG. 3, that a comparison is made between lrlnphase- OOX Inphasel2 (from So to So with uncoded bit a3 being 0) and lr, npha5e- (10X) lnpha5el2 (from S0 to S0 with uncoded bit a3 being 1),

Note that this measure is the partial distance using Eq. (4a) since the value of the middle data bit b2 (') is 0. The parallel transition that has the bigger error is then eliminated.

To eliminate one of the parallel transitions 40,42 linking state S, to state So, a determination is made whether the received symbol is closer to the two signal points O l X or to the two signal points 1 IX. This implies that a comparison is made between |rQuadraute-(01X)Quadrature|2 (from S@ to So with uncoded bit a3 being 0) and IrQuadrature- IX Quadraturel2 (from S, to So with uncoded bit a3 being 1), Note that this measure is the partial distance using Eq. (4b) since the value of the middle data bit b2 (l) 1. The parallel transition transition that the bigger bigger error then eliminated.

This parallel elimination process is independent and followed by the ACS operation.

The survivor at state So is selected by adding the partial distance d, or dQ2 as computed above to the state metric at the previous stage (stage m+1) and then comparing and selecting the survivor.

The process is the same for each of the other states. For example, consider the steps for state S, at stage m+2 of the first trellis interval. First one of the parallel transitions 40,42 linking stateS2 tostate S, is eliminated by determining whether the received symbol is closer to the two signal points 01X or to the two signal points 1 IX. Again from FIG. 3, this implies a comparison between |rQuadrature-(01X)Quadrature|2 (from S2 to S, with uncoded bit a3 being 0) and 12 (from S2 to S, with uncoded bit a3 being 1),

and elimination of the parallel transition that has the bigger error. To eliminate one of the parallel transitions linking state S3 to state S,, a determination is made whether the received symbol is closer to the two signal points OOX or to the two signal points 10X. This implies a comparison between IrInphase- OOX)Inphaselz (from S3 to S, with uncoded bit a3 being 0) and IYInphase- (1XInphasel2 from S3 to S, with uncoded bit a3 being 1), and elimination of the parallel transition that has the bigger error.

In the second interval of Type II symbol, consider the process for deciding the survivor for state So. Note that states So and S, in the first interval at stage m+2 connect to the current state under consideration, namely state So at stage m+3. Note also that the survivor branches have already been chosen for those two states in the first interval. For example, assuming OOX is the survivor branch for state So, then the partial distance, which is contributed by the second interval, that is, the transition 50 linking So to So, is given by IYQuadrature-OOOQuadraturel2 (f'om So to So with first interval survivor being 00X).

Likewise, if 11X is the survivor branch for state S, in the first interval for example, then the partial distance, which is contributed by the second interval, i. e., the transition 52 linking S, to So, is given by |rInphase-(111)Inphase|2 (from S, to So with first interval survivor being 10X).

In summary, the distance of the received symbol to a certain point on the 8-PSK constellation is decomposed into 2 orthogonal (inphase and quadrature) components, i. e.,

Eq. (5) d = d, + du2 Referring now to FIGs. 6 and 7, an embodiment of a decoder of the present invention will now be described. The decoder includes an 8-PSK demodulator 102, a symbol stuffing block 104, a branch metrics block 106, a trellis decoding block 108, an error growth monitor 112 and an error accumulation manager 114. The 8- PSK demodulator 102 and symbol stuffing block 104 are conventional. The demodulator 102 receives symbols that are resolved to I and Q components in the signal constellation. The symbol stuffing block 104 depunctures the symbols by symbol repetition. The output of the stuffing block 104 is input to the branch metrics block 106 in which the branch metrics are prepared. For type I symbols, the metrics are based on the standard Euclidean distance using both the I and Q components. For the type II symbols, the metrics are based on the partial distance described above wherein the distance uses one of the I and Q components.

The branch metrics are input to the trellis decoding block 108 which includes a Viterbi decoder. In the trellis decoding block 108, the uncoded bits are predetermined by selecting the parallel branch of each state-to-state transition that has the shorter metric. The trellis decoder also provides the standard ACS operation for each state. That is, the branch metric is added to the previous accumulated error (state metric), the error sums for the two incoming branches are compared and the survivor is selected by choosing the branch that yields the smaller total error. The ACS operation is performed for each of the 64 states at each trellis stage.

For the first trellis interval of the type II symbol, the survivor outcome is also recorded, i. e., the uncoded bit and the non-punctured bit. This information is necessary for the metric definition of the second trellis interval of the type II symbol as described in the example above. The trellis decoder provides the decoded bits by tracing back the merged survivor path.

The error growth monitor 112 is used to provide synchronization of the type I and type II symbols and facilitate phase ambiguity resolution. The error accumulation manager 114 is used to prevent error overflow.

A flow diagram of the decoding method implemented by the decoder of FIG.

6 is shown in FIG. 7. Symbols are received and stuffed for the punctured trellis intervals in block 202. In block 204, branch metrics are prepared for trellis decoding. In the case of punctured symbols, the metrics are based on the partial distance measure using either the I or Q components. At block 206, the metrics are compared to predetermine the uncoded bits. The survivor paths are selected in block 208 using the branch metrics and accumulated errors. In block 210, information from the first trellis interval for the type II symbol is stored for use in the metric determinations of the second interval. In block 212, a trace back of the survivor path occurs every 5*K trellis intervals, where K is the constraint length.

A simulation of the punctured, rate 5/6 P2TCM 8-PSK scheme includes a rate 5/6 P2TCM 8-PSK modulator, an AWGN channel, and a trellis decoder for punctured trellis codes. The trace-back is set at 60 trellis stages. In the simulations, the signal-to-noise ratio is Es/No, where Es=l for MPSK signals and No=202, where o2 is the variance of the I (or Q) component of the additive Gaussian noise in Eq. (2).

Hence, Eb/No = Es/6m *No) where m is the number of information bits transmitted in each symbol. For rate 2/3 PTCM 8-PSK, m=2 bitslsymbol, and for rate 5/6 P2TCM 8-PSK, m=2.5 bitslsymbol. The simulation also includes the rate 2/3 PTCM 8-PSK with trace back set to 40 stages.

The bit-error rate curves in FIG. 8 show results for encoding/decoding 150 blocks of information bits. In the 2/3 PTCM 8-PSK, each block has 24000 information bits. In the 5/6 P2TCM 8-PSK, each block has 20000 information bits.

As noted above, the squared error measure is usually used assuming the additive noise is strictly white Gaussian, since the optimal metric measure is L2- norm for AWGN. An improvement to the squared error measure uses an Lp-norm.

In practice, the noise may be impulsive and thus may slightly or severely deviate from the Gaussian distribution assumption. If this is the case, a more robust metric may be used, that is, the Lp-norm with Vp, 1 <p<2 : Eq.(6) jP = | r (n)-s (n) IP

Because the metric calculation is done before the ACS operation, thep parameter can be left to be adjustable. With the foregoing Lp-norm, the distance metric shown in Eq. (3) can be adjusted accordingly. This use of the Lp-norm can be applied to MPSK or M-ary QAM with regular code rates, i. e., where there is no puncturing in the underlying convolutional coder. Thus, for example, it can be applied to decoding of rate 2/3 PTCM 8-PSK.

Having described the approach for M-PSK, the application of the present invention is now described for QAM.

Pragmatic trellis coded modulation (PTCM) 16QAM at code rates 3/4 and 7/8 can be used for digital video broadcasting over satellite. For 16QAM at code rate 3/4, the convolutional encoder works at the regular rate of 1/2 and generates 2 coded bits for each input bit. These 2 coded bits are then combined with 2 new uncoded source bits to form a 16QAM symbol following a specified bits-to-symbol mapping 312. For 16QAM at code rate 7/8, the convolutional encoder works at punctured rate of 3/4 and generates 2 pairs of coded bits (4 bits) for every 3 input bits. Each pair of the coded bits are then combined with 2 new uncoded source bits to form a 16QAM symbol. FIG. 9 illustrates the encoding scheme for 16QAM at code rate 3/4.

As shown in FIG. 9, there are 3 source bits (the most-significant-bit is labeled as"G", the mid-bit is labeled as"H", and the least-significant-bit is labeled as"I") input to the TCM encoder 310."G"and"H"are uncoded, and serve as the MSB and 2"-to-MSB of a symbol on the 16QAM constellation."I"is convolutionally encoded and yields 2 bits labeled as C, (from generator G, (D)) and C2 (from generator G2 (D)). These 2 bits serve as the 2nd-to-LSB and LSB of a symbol on the 16QAM constellation, respectively. The rule for bits-to-symbol mapping is: G H Cl C2 (from MSB to LSB). For example, 0000 is mapped to a complex symbol (3lVlO, 31VIO), 0110 is mapped to a complex symbol (-lit10, 1/JlO). The factor \/10 is to ensure average transmitted signal energy is 1.

Note that a different scheme is adopted for designating bits in the QAM description to help to distinguish the PSK examples.

An advantage of the pragmatic TCM is that the code rate can vary by puncturing the convolutional encoder. By puncturing the underlying rate'4 convolutional encoder 314,316 to rate 3/4, the aforementioned 16QAM then has a <BR> <BR> code rate 7/8 as shown in FIG. 10. The puncturing block punctures C, bits and C2 bits using the following pattern (1 for transmitted bit, 0 for deleted bit) C,: 110 C2: 101 Therefore, the C, sequence at the output of puncturing is C, [0], C, [1], C, [3], C [4], CI [6], CI [7],...; the C2 sequence at the output of puncturing is C2 [0], C2 [2], C2 [3], C2 [5], C2 [6], C2 [8],... These bits are then combined with the uncoded bits G and H to form symbols according to the 16QAM symbol mapper shown above.

Due to puncturing, there are 2 types of symbols alternating at the output of the modulator: Type I symbol: bits G [0] H [0] C, [0] C2 [0] mapped to a complex symbol Type II symbol: bits G [1] H [1] C, [2] C, [1] mapped to a complex symbol Type I symbol: bits G [2] H [2] CI [3] C2 [3] mapped to a complex symbol Type II symbol: bits G [3] H [3] C2 [5] C, [4] mapped to a complex symbol and so on... where the bit pattern is expressed as MSB to LSB.

The modulation schemes in the DVB standard are not rotationally-invariant, so the demodulator synchronization loops and trellis decoder must be designed to resolve phase ambiguity and avoid cycle-slip and phase snaps.

For the rate 3/4 pragmatic TCM 16QAM, the trellis decoder is the standard 64-state Viterbi decoder with 4 parallel transitions for each branch 320 that is arriving or leaving a node (a state). The 4 parallels correspond to the 4 possible combinations of the 2 uncoded bit (G and H). The metric is the squared error between the received symbol and the ideal symbol corresponding to a specific transition, as demonstrated above in Eq. (3). Similar to the description for 8PSK

earlier, a trellis diagram can be constructed. Part of the complete trellis diagram is illustrated in FIG. 11. Note that here each transition line actually represents 4 parallel transitions.

The metric calculation (Eq. (3)) is done before the ACS operation and may be implemented via look-up table. The look-up table may partition the 2-dimensional I-Q plane into cells. As shown in FIG. 12, each cell may store 16 values which are the distances to the 16 signal points for the 16QAM constellation.

To illustrate the decoding, consider the following. When the kth symbol arrives, we first decide which branch of the 4 parallel transitions yields the smallest incremental error and thus should be selected to participate in the ACS operation.

Then for each state, the regular ACS operation is carried out to select the survivor for each state and update the metric. This procedure is repeated until all 64 states are considered. Then we move on to the next trellis stage when (k+1) S symbol arrives.

The above trellis decoding algorithm is for the standard rate 3/4 pragmatic TCM 16QAM. When we puncture the core convolutional coder to rate 3/4, we obtain a rate 7/8 punctured pragmatic TCM (P2TCM) 16QAM. The trellis decoder is different for P2TCM as shown in FIG. 13. For Type I symbol, each transition still has 4 parallels due to the 2 uncoded bits G and H, the pre-selection (parallel elimination) and the ACS operation mains the same as in rate 3/4 pragmatic TCM 16QAM. But for Type II symbol, the 2 uncoded bits G and H must be consistent over 2 trellis intervals. Each interval has 1 coded bit deleted. The dash line in Type II symbol reflects the fact that the uncoded bits are shared by 2 stages of trellis diagram. The solid line in Type II symbol reflects the underlying convolutional encoding and puncturing.

The difference is that for the punctured symbol (Type II), two trellis intervals are required to represent the transitions caused by one received symbol. Also, the uncoded bits G and H must be consistent within the two trellis intervals for Type II symbol. In other words, if G and H are 00 for instance during the first trellis interval, they must also be 00 for the second trellis interval. Decoding for the Type I symbol is identical to the standard trellis decoder. But the optimal decoding

approach for Type II symbol would be to wait at the end of the second interval of the trellis and select the survivor. However, each node (state) would have 4 incoming branches merging. Thus the trellis decoder would be time-varying (selects a survivor from 2 branches for Type I symbol and selects a survivor from 4 branches for Type II symbol, and alternates).

To use the same standard 64-state Viterbi decoder, i. e., select a survivor out of 2 merging branches at every stage of the trellis, the present invention partial metric based on I-Q decomposition is used.

Observing the bits-to-symbol mapper in FIG. 9, we realize that among the 4 bits,"H"bit and LSB determine the inphase component of a symbol, and"G"bit and 2"-to-LSB determine the quadrature component. For instance: if H=0 and LSB=0, then the symbol must be one of symbols 0,2,8,10 if H=0 and LSB=1, then the symbol must be one of symbols 1,3,9,11 if H=1 and LSB=0, then the symbol must be one of symbols 4,6,12,14 if H=1 and LSB=1, then the symbol must be one of symbols 5,7,13,15 each group of symbols have common inphase component. Similarly: if G=0 and 2"-to-LSB=O, then the symbol must be one of symbols 0,1,4,5 if G=0 and 2"d-to-LSB=l, then the symbol must be one of symbols 2,3,6,7 if G=1 and 2nd-to-LSB=0, then the symbol must be one of symbols 8,9,12,13 if G=1 and 2nd-to-LSB=1, then the symbol must be one of symbols 10,11,14,15 each group of symbols have common quadrature component.

This observation allows us to separate decoding of the 2 uncoded bits into 2 independent processes. Each interval decodes one uncoded bit based on a partial distance. More specifically, we decode the uncoded bit"H"at the first interval of Type II symbol's trellis, select a survivor between 2 merging branches. The metric involved in this first interval of Type II symbol is the inphase distance between the received symbol and the expected symbol. Then we proceed to the second interval of Type II symbol's trellis and decode the uncoded bit"G", select a survivor between 2 merging branches. The metric involved in this second interval of Type II

symbol is the quadrature distance between the received symbol and the expected symbol. We illustrate the invention through the following example.

Imagine that we are standing at the node at the first interval of Type II symbol's trellis, say state So, and looking backward. There are 2 branches coming from states So and S,, respectively. Each branch has in fact 4 parallel transitions because the uncoded bits G and H may either be 0 or 1 independently. However, since we use inphase component as partial distance for this trellis interval,"G"bit can be treated as"don't care". Thus each branch now only has 2 parallel transitions depending on whether"H"is 0 or 1. To eliminate one of the parallel transitions linking state So to state So, we may find out whether the received symbol is closer to the signal points XOXO or closer to the signal points X1XO ("X"means"don't care"). This implies, from 16QAM constellation FIG. 9, we compare dl2 = |rInphase-(X0X0)Inphase|2 (from S0 to So with uncoded bit"H"=0) with dl2=|rInphase-(X1X0)Inphase|2 (from S0 to So with uncoded bit"H"=1), and eliminate the parallel transition that has a bigger error. To eliminate one of the parallel transitions linking state S, to state So, we find out whether the received symbol is closer to the signal points XOX1 or X1X1. This implies that we compare d2 IYlnphase- XOXl) Inphaselz(from S, to So(from S, to So with uncoded bit"H"=0) with du IYlnphase- xlXl) lnphasel2 (from S, to So with uncoded bit"H"=1),

and eliminate the parallel transition that has a bigger error. This parallel elimination process is independent pre-selection process and it is followed by ACS operation.

The survivor at state So is selected by adding the partial distance d, 2 as shown above to the total error accumulated up to the previous stage then comparing and select the survivor for So.

At the second trellis interval of Type II symbol, let's say we try to decide the survivor for state So, looking backward. There are 2 branches coming from states So and S,, respectively. Each branch has in fact 4 parallel transitions because the uncoded bits G and H may either be 0 or 1 independently. However, since we use quadrature component as partial distance for this trellis interval,"H"bit can be treated as"don't care". Thus each branch now only has 2 parallel transitions depending on whether"G"is 0 or 1. To eliminate one of the parallel transitions linking state So to state So, we may find out whether the received symbol is closer to the signal points OXOX or closer to the signal points 1XOX ("X"means"don't care"). This implies, from 16QAM constellation FIG. 9, we compare du = |rQuadrature-(0X0X)Quadrature|2 (from S0 to So with uncoded bit"H"=0) with dQ2 = |rQuadrature-(1X0X)Quadrature|2 (from S0 to So with uncoded bit"H"=1), and eliminate the parallel transition that has a bigger error. To eliminate one of the parallel transitions linking state S, to state So, we find out whether the received symbol is closer to the signal points OX1X or lXl X. This implies that we compare dQ = lrQuadrature- (0X1X) Quadraturel2 (from S, to So with uncoded bit"H"=0) with dQ2 = |rQuadrature-(1X1X)Quadrature|2 (from S, to So with uncoded bit"H"=1),

and eliminate the parallel transition that has a bigger error. This parallel elimination process is independent pre-selection process and it is followed by ACS operation.

The survivor at state So is selected by adding the partial distance dQ2 as shown above to the total error accumulated up to the previous stage then comparing and select the survivor for So.

Simulations of the rate 3/4 pragmatic TCM 16QAM and rate 7/8 punctured pragmatic TCM 16QAM are shown in FIG. 14. The simulations include a rate 3/4 or 7/8 pragmatic TCM 16QAM modulator, AWGN channel, trellis decoder for punctured trellis codes. The trace-back is set at 60 trellis stages. In the simulations, the signal-to-noise ratio is Es/No, where Es=1 for 16QAM signals and No=2, where zizis the variance of the I (or Q) component of the additive Gaussian noise.

Hence, EblNo = Esl (m *No) where m is the number of source bits transmitted in each<BR> symbol. For rate 3/4 pragmatic TCM 16QAM, m =3 bits/symbol, and for rate 7/8 P2TCM 16QAM, m=3.5 bitslsymbol.

The bit-error-rate curves are obtained after encoding/decoding 500 blocks of source bits. In rate 3/4 PTCM 16QAM, each block has 3600 source bits. In rate 7/8 P2TCM 16QAM, each block has 2800 source bits.

While this invention has been particularly shown and described with references to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention as defined by the appended claims.