Trellis Coded Modulation Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Sketch the (industry standard) STM-1 frame that will be carried over the optical link and explain in detail the component sections of the frame. Explain how the multiplexors could be synchronised together within the network shown. 21

Task: In order to improve link performance, radio systems often use TCM (trellis coded modulation) techniques. Explain the operation of TCM and show how link performance can be improved by using TCM


In simple wording TCM can be explained as a combination of coding and modulation scheme that provides a large coding gain. It is called 'Trellis Coding' because the sequence of states in the finite state machine which encodes the signal levels follows a trajectory like a trellis lattice used in gardens. The following figure depicts the key elements of TCM. The elements consists of Trellis code nad constellation mapper. TCM combines the functions of convulational coder of rate R = k / k + 1 and an M-ary signal mapper that maps M= 2k input points into a larger constellation of M=2k+1 constellation points.

Figure 1: Trellis Coded Modulation

TCM is a channel coding with multilevel or phase level signals. It increases the free Euclidian distance by means of channel coding with multilevel or phase level signals. TCM is a bandwidth efficient modulation scheme, as it uses convolutional coding of rates(r, r+1). TCM applies the parity check on a per symbol basis. This idea is termed as Mapping by Set Partitions. TCM improves error performance of synchronous data links without sacrificing data rate or requiring more bandwidth...

It was invented by Gottfried Ungerboeck. The following figure depicts the history of TCM:

Figure 2: History of TCM

Let us try to understand the TCM scheme with the aid of an example.

Figure 3: Example of TCM, code rate 2/3

The above figure demonstrates TCM system with uncoded 4-PSK and rate of 2/3, coded 8-PSK, Demod BER=10-2, Decoded BER 10-5. The following figure depicts four point (uncoded) signal constellation.

Figure 4: Four point (uncoded) signal constellation

The following figure depicts eight point (coded) signal constellation.

Figure 5: Eight point (coded) signal constellation

For both the above signal constellation, radius is one, thus the signal power is of unity.

The following figure depicts the Trellis Coding. The Convolutional encoder rate is 2/3 codes and it is mapped into bits that defines a signal point (y2, y1, y0) - (1, 0, 0). Once the state is determined, Euclidian distance is used for finding uncoded bits. The remaining bits determine the choice of the subset. Mainly the allowed sequences correspond to a simple convolutional code. For having maximum distance separation, choose subsets that correspond to branching in and out of each state to have maximum distance separation.

Figure 6: Trellis coding

Following figure shows the Encoder states of the Trellis. Receiver tries to generate the estimate path through Trellis. The new state is a function of the current state and the input provided. Each parallel pair represents a pair of points with Euclidian distance =2. At each node the four arms entering have Euclidian distance of √2 and the minimum distance separation at the same node is 0.38 (2 sin (π/8)).

Figure 7: Encoder States

The Viterbi Decoder at the receiver is responsible for copying the transmitter trellis and estimating the received path through the trellis whose distance is closest to the received signal. The performance for the same by using following:

d2 = (leaving same node) 2 + (entering different nodes) 2 + (entering same nodes) 2

The following figure shows the mathematical calculation:

Figure 8: Mathematical aspects

TCM also conserves bandwidth by doubling the number of constellation points of the signal. Even this property helps in increasing bit rates keeping the symbol rate same. Let us understand the constellation doubling in TCM.

Figure 9: Constellation doubling in TCM

For k=2, we have a code rate of 2/3, QPSK signal (M = 4) and get 8-PSK signal (M =8). Thus TCM doubles the constellation points.

By varying k, we can create higher level signals, as depicted by the following figure:

Figure 10: Different types of TCM

How link performance is increased by using TCM

Let us first understand the key points of TCM and then will look into

Details how the performance is increased:

The bandwidth is not expanded, power spectrum remains same

Error probability is decreased

Coding gain is used to measure the performance improvement

Euclidian distance is increased between signal sequences

Convolutional Coding constraints allows symbol transitions creating sequence coding

The decoding metric is not Hamming distance, but Euclidian distance

Now let us understand, how the above points actually add to performance:

For different outputs of TCM, actually symbol bit size is changed by one, i.e., k = k + 1 bits. Since the bit rate increases we need to double the constellation size, as follows:

2L+1 = 2 x 2L

So if original signal is BPSK, then a TCM encoder will generate QPSK and so forth. Now let us see how bandwidth is affected. Consider bandwidth B. We also need to calculate the size of the alphabet that can convey the needed signal BER at the given available power. Let us assume we need to transmit QPSK signal. The following figure depicts the constellation of QPSK signal of amplitude 1 and as well as trellis. The minimum Euclidian distance is dmin = √2.

Figure 11: Constellation and Trellis for QPSK

The decoder on the receiver side deciphers which symbols were sent based one which decision region the signal falls in sort. The error performance is the function of the Minimum Squared Euclidean Distance, MSED. Let us suppose that we want to transmit a QPSK signal, uncoded with a BER of 10-5. It requires 9.6 dB of energy according to ideal Eb/No vs. BER relationship. But if this much power is not available because of the capabilities of the transmitter, then we need to add a code rate of 2/3 to reduce BER. But then the bandwidth increases by 1/R, in our case 3/2. To keep it constant we have to decrease information rate by same proportion.

Coding gain

The coding gain of coded signal over an uncoded signal is given by:

γ = d2 free/coded Es/coded ….Equation (1)

d2 min/uncoded Es/uncoded


dfree/coded is coded sequence Euclidian Distance

dmin/uncoded is minimum distance between the signals in uncoded constellation

dfree is Euclidian distance of coded signal in terms of the smallest possible distance between all allowed sequences

Let us assume we transmit an all zero message and during decoding an error occurs i.e. wrong trellis path is deciphered. So the only way to get the correct path is by means of diverging and remerging alternate paths, as shown below:

Figure 12: Alternate paths

So in our case, it requires only two segments to diverge to correct sequence. So,

d2 free/coded = d2 min + d2min

= 2 + 2 = 4

Now let us compute dfree and the coding gain of rate 2/3.

Figure 13: Rate 2/3 Convulational Encoder

The following figure shows different bits to symbol mapping. First part shows 8PSK symbol, second part shows natural mapping and third part shows gray coding.

Figure 14: Bits to symbol mapping

d2 min for QPSK is 2.0, but for 8PSK it is 0.586 (nearly 75% smaller) . The trellis of the 2/3 code is depicted in following figure using convolution coding:

Figure 15: Trellis for code 2/3

MSED for the above sequence is = 2.0 + 2.0 + 0.586 = 4.586

So by using Equation (1), coding gain is:

10 log (4.586/2) = 3.58 dB

Now let us check the coding gain with gray code:

MSED = .586 + .586 + .586 = 1.758

So by using Equation (1), coding gain is:

10 log (1.758/2) = 0.5 dB

So we can say that mapping play important role. Gray coding is not useful here. Now let us see how set partitioning helps here. The basic idea is to map k information bits to 2k+1 constellation points. The figure depicts the partitioning:

Figure 16: Set partitioning for 8PSK

Thus the 8 points are in turn partitioned into disjoint cosets such that SED is increasing at each level. Since the top two levels have smaller distances, error is more likely here. So we will use coded bits to traverse through this part; b3 to b2 which are coded are used to decide which partition or coset to pick. And then we traverse to the last level to pick the signal that was transmitted.

Thus most significant bit is left uncoded, and it takes care by large Euclidian distance.

Thus we can conclude that TCM with its key features increases the performance.

The following figure shows, the performance of 9600 bps transmission:

Figure 17: Performance graph

The following figure shows the code comparisons:

Figure 18: Code Comparison

Thus we can conclude that TCM is power efficient and bandwidth efficient modulation technique for fading channels.

Viterbi Equalization application to GSM

Task: with the aid of diagrams, explain how, and why, Viterbi equalization is applied to GSM radio links

First let us discuss Viterbi Equalization in brief.

Viterbi algorithm is used for decoding of convolutional codes, as used in GSM.

Convolutional codes are used to correct errors in noisy channels. Convolutional coding is a method of transmitting code word consisting of 1/R symbols affected by data bits instead of transmitting the data bits themselves. The following diagram depicts Convolutional Encoder:

Figure 19: Convolutional Encoder

Viterbi Algorithm

Let us define some basic terms:

Soft decision decoder - it receives bits from the channel with some kind of reliability estimate. Generally three bits are used. Actually increasing soft decision width will increase performance only slightly while considerably increasing computational difficulty? For example, if we use a 3-bit soft decision, then'000' is the strongest zero,'001' is a weakest zero, '100' is a weakest one and '111' is a strongest one. Mainly Euclidian distance is used.

Hard decision decoder - it receives bits only from the channel with no reliability estimate. Mainly Hamming distance is used.

Branch metric - a distance between the received pair of bits and ideal pairs.

Path metric - sum of metrics of all branches in a path

Now let us see the steps for Viterbi algorithm, depicted by the following figure:

Figure 20: Viterbi Algorithm

Branch Metric Calculation : Calculation of a distance between the input pair of bits and the four possible ideal pairs, depicted by BM

Path Metric Calculation: Calculation of metric with minimum path ending in the state, called survivor path. It uses Add compare and select mechanism (ACS). Path metric is represented as PM.

Traceback : Storing one bit information about survivor path, so that hardware is not loaded

Figure 21: Add Compare and Select

Viterbi Equalization in GMS

The following figure depicts GSM Communication model:

Figure 22: GSM Communication System

The channels of GSM introduce multi-path interference. In GSM, every transmitted slot includes the data bits and a training sequence, str(t), that is also known to the receiver. This training sequence enables the receiver to perform channel estimation and equalization. The received training sequence, rtr(t), is a convolution of the transmitted training sequence, str(t), and the channel's impulse response, hc(t):

rtrt(t) = str(t) -h(t)

The received training sequence in the digital domain, rtr[k], is fed into a digital matched filter with an impulse response, hmf[k], that is matched to str[k]. The matched filter output, he[k], can be written as shown in

he[k] = rtr[k] - hmf[k] = str[k] - hc[k] - hmf[k] =Rs[k]hc[k]

where Rs[k] is the auto-correlation function of Str[k]. In GSM, the sequences are engineered so that Rs[k] is a highly peaked real function. Therefore, he[k] is a good estimation of the complex value hc[k]. Let L denote the channel memory. x[k] is the complex valued sample of the received signal at time k. The Viterbi equalizer finds the sequence a[k]∈{-1,+1} that minimizes the Euclidian metric. The Euclidian metric can be mathematically approximated to another metric called the matched filter metric, M[k]. Due to a change in sign, we now maximize M[k] as


is the output of x[k] applied to a matched filter with an impulse response he[k] and

is the k-th tap of the autocorrelation of the channel impulse response estimation. The real part of the Sk series is called S-Parameters and can take only one 2L value. These values are denoted as Viterbi parameters (VP). To maximize the matched filter metric M[k], we must try all the possible a[k] sequences. The Viterbi algorithm does exactly this very efficiently using 2L states. In each stage all the possible VP values are calculated , one per state. Also, in each stage two branch metrics are calculated: the first is +(y - VP) and the second is -(y - VP). Those path metrics are also called Ungerboeck metrics. Each path in the trellis denotes the value of M[k] using different a[k].

Mainly soft decision Viterbi decoder is used. In Equalization mode, the branch metric for each transition within a Viterbi butterfly is a function of the matched filter output (MF) and the Viterbi parameters (VP). The VP values come from the channel autocorrelation. After the channel impulse response coefficients are extracted via a cross correlation process, the VP value for a particular state, uvwxyz, is calculated as follow:

VP(u,v,w,x,y,z) = (-1)u 2S6 + (-1)v 2S 5 +(-1) w 2 S4 + (-1) x 2 S3 (-1) y 2S2 + (-1)z 2S1

The following figure depicts Viterbi Equalizer used for GSM. The equalizer extracts the sequence, rtr[k], from the received signal and filters it using a matched filter with impulse response hmf[k]. The output of the matched filter, the channel estimation, he[k], is autocorrelated to obtain the S-parameters. The S-parameters are then correlated with all the possible 2L waveforms to generate the VP. The branch metric calculator calculates the Ungerboeck metric, which the Viterbi Algorithm uses to find the Maximim likelihood sequence estimation (MLSL). The equalized signal is the MLSE represented as hard decisions (±1).

Figure 23: Viterbi Equalizer

Design of TCM modulator

Task: Design a TCM modulator with a rectangular lattice where there is one coded bit (to choose one of two cosets) and four uncoded bits (to choose a signal point within a coset).

Now let us discuss the design of a TCM modulator with a rectangular lattice where there is one coded bit (to choose one of two cosets) and four uncoded bits (to choose a signal point within a coset).

Lattice is easier to visualize and convienent for discussion on multidimensional trellis code. A Lattice is represented by the notation ZN, where N is the dimension. Scaled lattice is represented as 2ZN. The other concept related with Lattice is the generator matrix- the smallest unit of points that can be rotated or translated to produce all other points in the lattice. Coset is defined as a translation of a sub-lattice by an element of the original lattice.

Let us consider the partitioning of 8PSK lattice into cosets. Here we have two unique cosets at each level so the total partition order is 8. The following figure shows the lattice for the same:

Figure 24: Lattice

The following figure shows the partitioning of 8PSKlattice into cosets:

Figure 25:Partition of 8PSK lattice into coset

Chapter 2

STM-1 Frame

Task: Sketch the (industry standard) STM-1 frame that will be carried over the optical link and explain in detail the component sections of the frame. Explain how the multiplexors could be synchronised together within the network shown.

STM is an acronym for synchronous transport module. STM-1 Frame is the transmission format for SDH (Synchronous Digital Hierarchy). It is at the first level of the SDH at 155.52 Mbps. The following figure depicts the SDH hieracrchy, and shows the position of STM:

Figure 26: SDH Hierarchy

STM-1 comprises of AUG (Administrative Unit group) and the SOH (Section overhead) information. The STM-1 frame structure consists of an array of 270 columns by 9 rows of 8-bit bytes.

Figure 27: STM-1 Frame Structure

The first nine columns of each frame is the SOH and last 261 columns is Virtual Carrier (VC). The VC plus pointers H1, H2, H3 is called AU. VC carries Path overhead and container.

Figure 28: Virtual container

The following figure depicts the SOH:

Figure 29: SOH Structure

Regenerator Section Overhead (RSOH) contains:

A1, A2: indicates beginning of STM-1 frame

J0: Regenerator section trace. It is used to transmit a section access point identifier so that a section receiver can verify its continued connection to the Intended transmitter.

Z0: Spare

B1: Regenrator section error monitoring.

E1: Provides orderwire channels for voice communication between regenerators.

F1: Reserved for user

D1-D3: Data communication cahnnels

Let us understand how the multiplexers can be synchronized together within the shown network.








Optical SDH

Mux STM 1







2M PDH x8


SM Optical

Figure 1

















Since SDH is a synchronous network it uses synchronous multiplexing, i.e. data from multiple tributary source is byte interleaved. STM-1 frame works even with different clocks in the network (asynchronous), with the help of H1, H2 and H3 pointers. Even Synchronization status marker byte in SOH helps in synching since it contains the information about quality of embedded timing. STM-1 ring has termination points, through which 140 Mbps path passes unaltered through the multiplex section. So different STM-1 ring are time synchronized, to avoid errors.

Figure 30: STM-1 ring

KLM Numbering

Task: The Nortel TN1X SDH multiplexor uses the KLM numbering scheme to correctly allocate the individual 2Mb/s PDH streams into the SDH frame. Explain the operation of the KLM numbering scheme.

The KLM channel numbering is used to identify aggregate payload instances. It indicates the level of multiplexing. It uses vector (K, L, M) to represent channels within the virtual container (VC) payload structure:

K = TUG-3 (1 to 3)

L = TUG-2 (1 to 7)

M = TU-12 (1 to 3)

It allows a TUG-3 containing a single TU-3 to be distinguished from a TUG-3 containing seven TUG-2s. This allows, for example, differentiation of a VC-3 (34/45 Mbit/s) signal from a VC-12 (2 Mbit/s) signal:

'1,2,3' - indicates TUG-3 '1', TUG-2 '2', TU-1 '3' (i.e. a 2 Mbit/s VC-12 signal)

'2,0,0' - indicates TUG-3 '2' (i.e. a 34/45 Mbit/s VC-3 signal)

Siae microwave radio link

Task: The Siae microwave radio link, illustrated at the top of fig 1, is restricted to STM-1. Suggest reasons for this.

The Siae microwave radio link is restricted to STM-1 mainly because:

Redundant backup channel

Disaster recovery

Microwave radio link must be placed near to the attenas for system performance, and STM-1 is at first level in the SDH hierarchy

The path trace identifier can be provisioned by the user for each STM-1 link and for each direction seperatly.

STM-1 local, remote and simultaneous loopback is possible

Ugrading of given network

Task: The network is due to be upgraded, extra bandwidth is required. Link B (fig1) is a single mode fiber optic link carrying a single STM-1. Explain, with the aid of diagrams, how the capacity of this link may be increased by at least an order of magnitude

The capacity of this link may be increased by:

Synchronizing the SPEs (Synchronous payload envelope) by adjusting the payload pointers

The tributary STS-1 frames are byte interleaved with each other

References KLM Numbering

[1] Best Western Sterling Inn (2009) Safety and Security [online]. Available from: [Accessed 20/01/2010]

[2] Bonvin, Jacques Levy (2003) Hotels | A Brief History [online]. Available from: [Accessed 21/01/2010]

[3] Gibson, R. Sebastian (2008) The Risks of Serving Alcohol to a Minor in Hotels, Restaurants, Nightclubs and Bars in California [online]. Available from: [Accessed 20/01/2010]

[4] Kamanth, Vani, Bhosale, Shweta and Manjreakar, Pradip (2008) Revenue Management techniques in hospitality industry - A comparison with reference to star and Economy Hotels [online] Available from:

[5] MEAS (2003) Responsible Serving of Alcohol Programme [online]. Available from: [Accessed 20/01/2010]

[6] Net Resources International (2005) Enhancing the Guest Experience [online]. Available from: [Accessed 19/01/2010]

[7] Nikolis Nick (2009) The Effect of Yield Management on Hotel Chains [online]. Available from: [Accessed: 19/01/2010]

[8] Woody, Carol (2004) Security and Safety in the System Development Life Cycle - Introduction [online]. Available from:;jsessionid=6074e57f0ce3e0bcb8e8d0f37402 [Accessed 20/01/2010]