Trellis-Coded Modulation [TCM] - MJ telecom

1 1 Trellis-Coded Modulation [TCM] Limitations of conventional block and convolutional codes onbandlimited channels Basic principles of trellis coding: state, trellis, and set partitioning Coding gain with trellis codes System mechanization: application of the Viterbi Algorithm fordecoding Systems issues Applications to wired and wireless channels Advanced concepts: multi-dimensional trellis codes Three aspects of TCM [or any code] Design the code Determine the performance of the code (coding gain) Mechanize the encoder and decoder (Viterbi Algorithm2 Classic Coding Information theory tells us that for optimal communications we should designlong sequences of signals, with maximum separation among them; and at thereceiver we should perform decision making over such long signals rather thanindividual bits or symbols.)

2 If this process is done properly, then the message error probability willdecrease exponentially with sequence length, n provided that the rate R is less than R0, which in turn is less than the ShannonCapacity. This is the idea behind coding. In conventional coding, the coding is separatefrom Modulation . Coding occurs at the digital level, before Modulation andgenerally involves adding bits to the input sequence. The resultant redundancyrequires added bandwidth. At the receiver, hard decoding occurs after demodulation. The decodingoperation is based on hard decisions, since a digital bit (or symbol) stream feesthe decoder and is either in error or not. Decoding can also be done based onthe analog received samples, and this is called soft decoding.

3 The theoreticalloss due to hard [vs soft] decoding leads to a ~2dB performance )(0 <3 coded Modulation Optimum 2-D Modulation uses dependency between in-phase andquadrature symbols. 4-D Modulation introduces dependency between symbols of twosuccessive intervals. Trellis coding introduces dependency between every successivesymbol. Trellis and multi-dimensional codes are designed to maximize theEuclidean distance between possible sequences of transmitted symbols Distance between the closest possible [ie, minimum distance]sequences of transmitted symbols in signal space determines theperformancepower noise theis and sequences signalbetween distance minimum theis where ,~22min2/22min dePde 4 Trellis coded Modulation The key idea is that the operations of [baseband] Modulation and coding arecombined.

4 The bandwidth is not expanded: same symbol rate, but redundancy isintroduced by using a constellation with more points than would be requiredwithout coding. Typically, the number of points is doubled The symbol rate is unchanged The power spectrum is unchanged Since there are more possible points per symbol, it may appear that the errorprobability would increase for a given S/N. As in conventional coding, dependencies are introduced among differentsymbols ---only certain sequences of successive constellation points areallowed. By properly making use of these constraints during reception, the errorprobability actually decreases. A measure of performance improvement is the coding gain.

5 Which is thedifference is S/N between a coded and uncoded system of the sameinformation rate that produces the same error of Trellis-Coded ModulationRotationallyInvariant TCMwith M-PSK1988 TCM withBuilt-In TimeDiversity1988 - 1990 TCM withTomlinsonPrecoder1990 - 1991 TCM withUnequal ErrorProtection1990 MultilevelCodingwith TCM1992 - 1993 ConcatenatedCodingwith TCM1993 - presentMultidimensionalTCM1984 - 1985 RotationallyInvariant TCM1983 UngerboeckInvented TCM1976 SatelliteCommunications WirelessCommunicationsTrials DigitalSubscriberLoops HDTV BroadcastChannels SatelliteCommunications HDTV CATV DBS DigitalSubscriberLoops Voiceband Modemsup to Kbps Voiceband Modemsup to Kbps6 Key Elements of Trellis coded Modulation To improve power efficiency, use channel coding to introducememory into {Pn} To compensate for the redundant bits introduced by the channel encoder, use alarger constellation with more than 2m symbols.

6 To reduce the decoder complexity, design the channel encoder and constellationmapper +rModulatorOutputDataViterbiDecodermDemo dulatorPnChannel~PnInput DatamBits/SymbolTrellis coded Modulation7 Trellis Coding---the basics It can be shown for the Gaussian channel that there is an input discretealphabet that has capacity very close to the capacity with continuousinputs As shown on the next chart, an eight- level system can achieve acapacity of 2 bits/symbol This suggests that it is only necessary to double the signalconstellation to get good coding gains (increasing the signal alphabetwill not improve the coding gain) Note that at about 19 dB we can achieve with a four-levelconstellation With coding, using an 8-level constellation we can theoreticallytransmit 2 bits/symbol error free down to about 13dB Hence using coded Modulation we could gain as much as 19-13 = 6 dB The bandwidth has not been expanded (same symbol rate)510 8 Trellis Coding The BasicsThe Information Conveyed by a Real-Valued Discretetime Channel with Additive Gaussian Noise16-AM8-AM4-AM2-AMSNR (dB)432100102030C (Bits/Symbol) log2(1+ / 2)10-510-5 Uncoded10-5 Shannon Capacity9 Trellis Coding The Basics (QAM Modulation )64-QAM32-AMPM8-AMPM8-PSK4-PSK SNR (dB)653200102030C3 (Bits/Symbol)10-5log2(1+ / 2)

7 10-516-PSK10-5 Shannon Capacity16-QAM42-PSK110-510-532-PSK10 Trellis Coding ---QAM Modulation Given a channel with a bandwidth limitation, first determine the maximum symbol ratethat can be transmitted. Determine the size of the alphabet, , that is needed to produce the desired bit rate. Double the size of the constellation and introduce a channel coder that produces oneextra bit The coder need not code all the incoming bits There are many ways to map the coded bits into symbols. The choice of mapping willdrastically affect the performance of the code. Ungerboeck produced a good heuristic technique called mapping by set partitioning The encoding philosophy is to first partition the larger constellation intosmaller subsets The Euclidean distance between sequences of signal points in different subsets issubstantially increased (and may be on the order of the distance between points inthe same subset) Performance will be determined by the distance between sequences in differentsubsets.

8 Trellis coding produces a dramatic increase in the Euclidean (free) distance betweensequences of signal points and the Viterbi Algorithm is used to detect the signal Results also hold for 2-dimensional modulationL212+L11 Trellis Coding Summary Ungerboeck (1976) showed that for bandlimited channels substantial codinggains could be achieved by convolutional coding of signal levels (rather thancoding of binary source levels)] He joined Modulation and coding to increase the Euclidean distance betweensignal sequences Called channel trellis coding because the sequence of states in the finite statemachine which encodes the signal levels follows a trajectory in a trellis ofpossible trajectories The larger Euclidean distance between signal sequences, the lower the errorrate, which for moderate to large SNR is Codewords consist of modulated level sequences.

9 Trellis coding uses densesignal sets but restricts the sequences that can be used. This provides a gain inminimun distance and the code imposes a time dependency on the allowedsignal sequences that allows the receiver to ride through noise bursts as it isestimating the transmitted sequence. Since the pulse shape and symbol rate are unchanged ---> no bandwidthexpansion2/2)( and ,at sequences ofnumber average the where),2/(xfreefreefreefreeeexQdNdQNP == 12 Trellis coded Modulation : Example SystemUncoded System: 4 PSK, BER = 10-5, Encoder & Mod are IndependentCoded System: r = 2/3, 8 PSK, Demod BER = 10-2, Decoded BER ~ 10-5 ChannelModulatorDemodulatorEncoderDecode rCoding Channelr = 2/38 BER = 10-2 BER = 10-513 Limitations of Conventional Coding Techniques for Bandlimited Channels For the example uncoded 4-PSK and rate 2/3 coded 8-PSK system [same customerdate rate] if the uncoded system has a BER = 10 -5, the coded system will have an error rateat the demodulator output of worse than 10 -2.

10 What sort of code is needed to makethe 8-PSK system have a 10 -5 decoded BER? A t-error correcting code of block length n, with k information bits must satisfy theHamming bound [see Weldon and Peterson]--- which provides a lower bound on thecode block length Suppose t=2 and k/n = R= 2/3 [as per our example] we find that n > 24. With such a code we need a binary block length of 24 bits or eight 8-PSK symbols. Eachof the symbols has an error rate of 10 -2. With Gray coding [ie, a symbol error --->onebit error], the code will correct two symbol errors. An error will be made if 3 [or more] of the 8 symbols are in error, and the decoded BER Thus relatively complex codes [n=24] are required and this code did not provide gain.