TCM

Trellis-Coded-Modulation (TCM)
Discovered (Invented) by G. Ungerboeck
“Channel Coding with Multilevel/Phase Signals”
IEEE Trans. Info. Theory, Vol. IT 28, No. 1, Jan 1982, pp 55-67.
⇒
Regard channel coding and modulation as an entity together
-
as proposed first by Masseyseparately.
as opposed to Coding and Modulation
Classical View
Error Control Coding → Increase in spectrum bandwidth
Decrease in SNR
Due to the fact that the rate of
the encoder o/p is greater than
the rate of the encoder i/p
-
assuming identical alphabets – by 1/R
(Consider R = ½ convolutional encoder)
⇒
Coding could only provide gains in energy efficiency when the
possibility of bandwidth expansion is present.
Ungerboeck
-argued that the modulation symbol set could be enlarged when coding is used
relative to that needed for “uncoded” case.
If the signal set dimensionality per info bit is unchanged the power spectrum
remains unchanged. (no BW expansion)
* The signaling rate does not change.
i.e., Coding and modulation is performed with respect to Euclidean distance
between coded modulation o/p sequences.
⇒
MLD soft decision decoding.
Set Partitioning
Consider a constellation having M points in an N dimensional space. (1, 2 dim.
originally)
Example
M-ary PAM, M-ary QAM, PSK or subsets of N-dimensional lattices.
•
First partition the original set into p1 equal sized disjoint subset or
cosets. ⇒ Each of size M/p1
1
•
p1 ⇒ A1, A2, ..., A p1 subsets. So that within each subset the minimum
ED between signal points is maximal.
Next each of these subsets are further split into p2 subsets denoted by B0,
B1, ....
Proceeding recursively original constellation may be eventually
decomposed into single point subsets.
Typically, the splitting factors pi are equal pi = 2 usually (not essential.)
•
•
•
Example
d02
= 0.585 Es
= (2 sin π/8 )2 Es
(b1 b2 b3)
A0
b3= 0
1
A1
d12 = 2 Es
B0
b2= 0
0
1
B2
1
B1
B3
d22 = 4 Es
b1= 0
C0
1
C4
0
1
C2
C6
0
C1
1
C5
0
C3
Set partitioning of 8-PSK with associated bit labeling
2
1
C7
Example 2
Partitioning of the 2-dimensional Lattice Z2. (2a is the constellation spacing
along each signal-space axis.) – 16 QAM, 32-cross.
16 QAM Signal Constellation- Set Partitioning
3
*Trellis Coding for band limited channels
1) If m bits to be transmitted/modulation interval
~ < m bits expanded into m
~ +1 ( m
~ +r) coded bits by m
~ /( m
~ +1)
2) m
convolution encoder
~ +1 bits to select 2 m~ + 1 subsets of a 2m+1 signal set.
3) Use these m
~ uncoded bits determine which of the 2 m− m~ signals in the
4) Remaining m- m
subset is transmitted.
~
SIGNAL MAPPING
m- m
m
m
xn
Select
signal from
~+ 1
m
xn
subset
Signal
sequence
~+ r
zm
n
~
xm
n
Convolutional
Encoder
~ /( m
~ +1)
m
encoded
xn’
Select
subset
~ +r
zn’ m
Time interval
Modulation has 2m+r points in N dimensions. (r = 1 usually)
Hand Design of Codes
(*)
Selection of the trellis size – No. of states
S = 2v ,
v – memory
(*)
⇒
m bits/trellis level.
2m branches leaving and merging with each state.
m = 3 ⇒ 23 = 8
This can be divided as
i)
eight single branches
~ =3
m
ii)
four groups of two
~ =2
m
iii) two groups of 4
~ =1
m
4
which one is best is not obvious.
⇒
We assign constellation subsets of proper size to various state
transitions.
Ungerboeck’s Rules
1)
2)
Employ all subsets equally often m labeling the trellis.
For subset assignments that share a common splitting state or merging
state, choose subsets between which the minimum “intersect” distance is
largest.
Example
4 state code for m = 2, 8-PSK.
Throughput is m =2 bits/modulator symbol.
No. of branches/state = 22 = 4
~ =1 ⇒ 1 bit left
Assign branching as 2 sets of 2 as shown below, i.e., m
uncoded.
Trellis labeling for 4-state, 8-PSK code. Subsets have size 2.
Rule 1
Rule 2
(*)
There are 4 antipodal subsets. Trellis requires 8 subset
assignments ⇒
each subset used twice.
For branches leaving (merging) assign subsets that differ by 90°
rotation.
Presence of “parallel transitions” – TCM design only
Not in convolutional codes.
5
⇒
Single step error events are possible.
For ML decoding “free distance” – min ED between any two coded sequences,
is the figures of merit (at high SNR)
ED for parallel transition d12 = 4 Es
3 stage error
d32 = 2 Es + 0.585 Es + 2 Es
= 4.585 Es
⇒
df2 = 4 Es (four state code 8-PSK)
Each code symbol carries the energy of 2.
info bits
Es = 2 Eb
df2 = 8 Eb
Uncoded case
d f2u = 2 Es = 4 Eb
Coding gain = 10 log10
2
2

 d free( coded ) / d free( uncoded )


 Energy coded / Energy uncoded





Feedforward encoder realization of best 4-state code for 8-PSK.
(*) For – four sets of one branching we can show that
df2 = d22 = 2.585 Es – suboptimal trellis structure.
No parallel transitions.
Note : This trellis structure is identical to the best binary Hamming distance
code with R = 2/3. Even with best assignment of 8 PSK to o/p 3 tuples we
produce an inferior code for AWGN channel.
6
Example
16 QAM – TCM with m =3 bits/symbol.
~ =3 coded bit
4 state trellis with m
Trellis labeling for 4-state, 16 QAM code. Note similarity with 4-state, 8-PSK
design. Subsets have size 4.
•
Single step error events are dominant.
df2 = 16 a2 where 2a is the along axis spacing in the constellation.
Es = Average energy per symbol = 10 a2
∴ df2 = 1.6 Es = 1.6 (3Eb) = 4.8 Eb
3 info. bits
For the uncoded 8-PSK
d f2u = 0.585 Es = 0.585 (3Eb) = 1.755 Eb
∴ Coding gain = 4.8/1.755 ~ 4.4 dB
Referring to the Trellis encoder given the design questions are, for a given m
and S (=2v, v = no. of binary memory elements)
1)
2)
3)
What constellation should be used ?
What is the proper (or what form of trellis branching should be used)?
What is the best subset labeling pattern or, equivalently, the best
encoder?
Rearranging the constellation issue
7
(*)
(*)
Codes with constant energy per transmitted symbol may be important –
M-PSK.
Constellation Size : Ungerboeck argued that expansion by a factor 2 is
adequate for 2-D constellations e.g. uncoded M QAM ⇒ coded 2M –
QAM.
⇒
dimensionality per info. bit remains unchanged
⇒
to first order, so is the power spectrum i.e Bandwidth
(*)
8 points constellations
for R = 2 bits/symbol
16 point ⇒ 3 bits/symbol.
(*)
Large complexity codes by computer search.
combining CC’s with set partitioning, i.e., we can use the labeling
implied by the set partioning powers and the search over the class of
binary CC’s with S states, determining the free distance for each such
code.
(*)
Use systematic encoders with o/p feedback.
(Any feedforward nonsystematic CC can be realized as one.) ⇒
Noncatastrophic.
Systematic encoders with feedback are specified by listing the parity check
polynomials.
hi(D) = h0i + h0i D + ... + hvi Dv for i = 0, 1, ..., m.
For encoders with only coded bits
~ < i < m which says that the uncoded bits need not obey any
hi(D) = 0, m
parity constraints.
~ =~
m = k, m
k
8
Generic 2v – state encoder in systematic form with feedback.
(*)
~ - inputs (coded bits)
The figure illustrates the case where only m
influence the state vector.
h0(D) provides the feed back connections.
Usually hi(D) are specified in octal notation.
Example
For 8-PSK, 4-state encoder
h0(D) = 1 + D2 ; h1(D) = D ; h2(D) = 0
Four-state encoder for 8-PSK in systematic form with feedback.
h0(D) = 1 + D2 ; h1(D) = D ; h2(D) = 0
9
Sixteen-state encoder for QAM constellations. h0(D) = 238;
h1 = 48 ; h2 = 168 , other hi = 0.
•
Bigalieri has shown that for Ungerboeck-style TCM, i.e., set partitioned
constellations proceeded by CC’s, the power spectrum is in fact
unaltered. (symmetries of the signaling process – mostly due to)
“Ungerboeck Codes Do Not Shape Power Spectrum”
IEEE Trans. Info Theory Vol. IT-32, pp-595-596, July 1986.
Example
Note that parallel transitions imply that single signal error events can occur.
This limits achievable free Euclidean distance to the minimum distance in the
subsets of signals assigned to parallel transitions.
On the other hand, parallel transitions reduce the “connectivity” in the trellis
and allow extension of the minimum length of the multiple signal error events.
(*)
4 state – 8 PSK – with parallel transitions- best solution-3 dB gain
But with 8 and more states, only trellis structures with distinct transitions can
be of interest, otherwise free ED gain would remain limited to 3 dB.
10
8 PSK
0426
1537
2
3
6
0
4
2
1
4062
4
0
5173
5
7
2604
6
3715
6240
7351
3.6 dB gain over 4-PSK
(*)
Transitions originating from the same state or merging into same state
assigned signals from either subset A0 or A1
Decode the received signal in 2 steps:
(a) Subset decoding – within the signal subset assigned to the parallel
transitions, choose the signal closet to the received channel o/p. Store
these signals together with their squared distances.
(b) Use the VA to find the signal path that is cloest to the received signal
using these subset winners and their ML metrics.
Example
8-State, 16 QAM
0246
1753
6420
7135
4602
5317
2064
3571
11
6
0
2
4
Examples (TCM)
Encoder configurations:
~ =2
m
m =3
v =3
(0)
h = 11
h(1) = 02
h(2) = 04
Octal
001001
000010
000100
→
→
→
→
→
→
Binary
1001
0010
0100
Select one of 2
signals in a
partition
h(2) = 0100
h(1) = 0010
h3(0) = 1
Select
partition of 16
QAM
h0(0) = 1
h(0) = 1001
It is shown that the number of coded bits, 2, remains unchanged for most of
MPSK, MQAM schemes regardless of the memory and signal points. This is
for best TCM codes in AWGN channel.
[Ref: Ungerboeck 1982, 1987.]
Decoding TCM over AWGN Channels
In the previous sections the minimum Euclidean distance (dfree) was
always used as a guideline to design good codes. Actually this result comes
from the analytical upper bound on Bit Error Rate (BI/LR) of TCM for thc
AWGN channels.
In general the TCM trellis assigns a sub-constellation of signals to each
branch in the trellis. Viterbi decoding is performed m the two steps:
1. At each branch in the trellis the receiver compares the received signal
to each signal allowed for that branch. The identity of the allowed
signal closest to the received signal is saved in the memory and the
branch is labeled with a metric proportional to the distance between
the two signals.
12
2. The Viterbi Algorithm is then applied to the trellis with surviving
partial paths corresponding to partial signal sequences that are closest
to the received sequence. The maximum likelihood path is then the
complete signal sequence closest in Euclidean distance to the
received sequence.
When the Viterbi decoder is used, the performance analysis for TCM system is similar to
that for convolutional codes. Following the derivation, the upper bound on the node error
rate (i.e. the rate whenever a nonzero path leaves a given node and reemerges with the
correct path at a later node) is given by:
 d2 E
free s
Pe ≤Q

 2 N0

 d 2 E 
.exp free s .T (D )
D = exp ( E s / 4 N 0 )

4 N0 
 

 
(1)
And the upper bound on BER is:
d 2free E s
1 

Pb ≤ .Q
m  2 N0

 d 2 E  ∂T (D, I )
.exp free s .
D = exp ( E s / 4 N 0 ), I =1 (2)

4 N 0  ∂I
 

 
Where T(D) is the generating function of the directed graph which is related to the state
diagram of the trellis code. T(D,I) is the augmented version of T(D) with components of the
I terms denote the number of information bit errors associated with each error event. N0 is
the one-sided noise spectral density of AWGN, Es. is the average energy of the signal
constellation and m is the number of information bits carried by each symbol.
The derivation of generating function can be quite complicated and becomes
intractable as the number of states in the TCM increases. However at high Signal-to-Noise
Ratio (SNR) (1), (2) can be approximated quite accurately without the use of T(D,I) :
 d2 E
free s
Pe ≈N d free Q

 2 N0

d free 
d 2free E s 


Pb ≈
Q
m  2 N0 



(
)





(4)
(5)
Here N(dfree) is the average number of sequences that are distance dfree from the transmitted
sequence and bd free is the total number of the information bit errors associated with
erroneous paths that are distance dfree from the transmitted path, averaged over all possible
transmitted path. Equations (4) and (5) justify the importance of minimum Euclidean
distance to the asymptotic coding gain.
13
Some Applications of Trellis-Coded Modulation in CCITT
Recommendations
V.32 is intended for 9.6 Kbps traffic over two-wire telephone lines and 14.4
Kbps traffic over over-wire circuit. The TCM code is used in V.32 modem in
order to obtain higher noise immunity over uncoded transmission at the same
data rate, transmission power and bandwidth limit.
(m+l)
The V.32 TCM code uses m = 4 binary input symbols, signal set has 2
= 32
signal vectors in the 32-CROSS constellation. A convolulional encoder with k
2 input, n=3 output, and memory M = 3 is implemented. This is a non-linear
encoder. With this implementation a asymptotic coding gain of 4dB is
obtained.
The same nonlinear encoder was later adopted for use with 64-QAM and 128CROSS in V. 17 (14.4 Kbps FAX traffic over standard phone lines) and V.33.
TCM technique is relatively young. Several questions concerning real coding
gains, performance under channel impairments other than AWGN channels
(especially for mobile radio channels) and implementation complexities are
actively being studied.
14
MTCM
0011
2
1
1
0101
0123
3
0
dfree2 = d2(0, 2) + d2(0, 1) = 4 + 2 = 6
TCM Trellis:
3
s1
1
1
2
s0
0
0
s0 → {0, 2} , s1 → {1, 3}
Now allow the encoder to select r = 2 signals (with replacement) from these
respective partitions for each trellis branch.
Thus for s0 → {0,0 ; 0,2 ; 2,0 ; 2,2}
These can be viewed as the vertices of a square.
0, 2
2, 2
d2 = 8
0, 0
2, 0
Since these are four possible two-signal sequences but only two successor
states for s0 – i.e s0, s1 there will be parallel transitions. The two signal
sequences are partitioned into pairs such that the inter-sequence distance in
each pair is maximized.
s1
{1,1;3,3}
{1,3;3,1}
{1,3;3,1}
{0,2;2,0}
s0
{0,0;2,2}
{0,0;2,2}
15
2 state MTCM
Trellis with r = 2
d2free, parallel = d2(0, 2) + d2(0, 2) = 4 + 4 =8
d2free, nonparallel = d2(0, 0) + d2(0, 2) + d2(0,1) + d2(0,3)
=0+4+2+2
=8
Coding gain over TCM = 8/6 = 1.33 (1.25 dB)
Coding gain over BPSK = 8/4 = 2 (3.01 dB)
This further development of TCM technique was made by Divsalar and Simon
where the authors demonstrated a trellis coded-modulation technique referred to as multiple
trellis coded - modulation (MTCM). It was shown that MTCM can achieve a significant
increase in coding gain relative to conventional TCM by increasing the number of signals
transmitted per each trellis branch.
The principle behind MTCM is to design a rate nk/(n+I)k encoder and combine it
(again through a suitable mapping) with 2n+1 - point signal constellation and to output k of
these signal points in each transmission interval. Since in each transmission interval, /or bits
enter the encoder and k symbols leave the modulator it is guaranteed to have unity
bandwidth expansion relative to a 2n - point uncoded system.
A multiple trellis encoder has m binary input bits and u binary output bits which are
mapped into k M-ary symbols in each transmission symbol. Such a system has throughput
m/k bits/s/Hz which has the same bandwidth with 2m/k - point signal constellation. In the
considered system the partition is carried out as follows: u binary encoder output bits are
partitioned into k group of m = log2 M bits each. Each of these groups results in an MPSK
output symbol. Clearly, to achieve this result the parameters u, k, M have to be chosen so
that u = k . log2 M ( here m1=m2=… =mk).
Multiple Trellis Encoded M PSK Transmitter
To illustrate the principle of MTCM, an example of 2-state MTCM was discussed.
Figure given earlier is the 2- state trellis diagram for rate 1/2 conventional trellis coded
QPSK and the corresponding multiple trellis diagram for the same coded modulation was
nk
given next. In MTCM case m = 1 and k = 2 and thus there are 2 =4 branches going from
each state. With 2-state trellis this means that there must be two parallel branches between
each pair of states. Also since k = 2 then there are two output QPSK symbols assigned to
each branch.
16
Asymmetric Constellations –MTCM
Partition the original signal point constellation into two sub-constellations each
with maximum distance among its signal points. Signals in partition 1 are
assigned to transitions.
δ
3
2
3
δ
2
4
1
5
0
6
δ
1
7
3
2
1
4
0
5
7
6
δ12 = 4 sin 2
φ
= 2(1 − cos φ)
2
δ22 = 2
π φ
δ32 = 4 sin 2  +  = 2(1 + sin φ)
4 2 
π φ
δ52 = 4 sin 2  −  = 2(1 + cos φ)
2 2 
δ62 = 2
π φ
δ72 = 4 sin 2  −  = 2(1 − sin φ)
4 2 
δ42 = 4
Two state trellises for multiplicity 2 and 3 are shown below.
17
0,0
0,4

2,2

2,6

4,0
4,4

6,2
6,6

0,2
0,6 

2,0

2,4

4,2
4,6

6,0 
6,4

0
0
1
1
0
1,1
1,5

3,3

3,7

5,5
5,1

7 ,7
7 ,3

18
1,3
1,7

3,1

3,5

5,3
5,7

7 ,1
7 ,5

0,0 ,0
0,0 ,4

0,2,2

0,2,6

0,4,0
0,4,4

0,6 ,2
0,6 ,6

2,2,2
2,2,6
2,4,4
2,4,0
2,6,2
2,6,6
2,0,4
2,0,0
6,6,6
6,6 ,2
6,0,0
6,0 ,4
6,2,6
6 ,2 ,2
6,4,0
6 ,4 ,4
4 ,0 ,2
4 ,0 ,6
4 ,2 ,0
4 ,2 ,4
4 ,4 ,2
4 ,4 ,6
4 ,6 ,0
4 ,6 ,4
0 ,4 ,6
0,4,2

0 ,6,4

0 ,6 ,0

0 ,0 ,6
0 ,0,2

0,2,4
0 ,2 ,0

0
1
4 ,4 ,4
4 ,4,0
4,6,6
4 ,6 ,2
4 ,0 ,4
4,0,0
4 ,2,6
4 ,2 ,2
2 ,0 ,2
2 ,0 ,6
2 ,2 ,0
2 ,2 ,4
2 ,4 ,2
2 ,4 ,6
2 ,6 ,0
2 ,6 ,4
3,3,3 7 ,7 ,7 5,1,3 1,5,7
0 
3,3,7 7 ,7 ,3 5,1,7 1,5,3
0
3,5,5

3,5,1

3,7 ,3
3,7 ,7

3,1,5
3,1,1

1
1,1,1
1,1,5

1,3,3

1,3,7

1,5,1
1,5,5

1,7 ,3
1,7 ,7

19
6 ,4 ,6
6,4,2
6 ,6,4
6 ,6 ,0
6 ,0 ,6
6 ,0,2
6,2,4
6 ,2 ,0
5,5,5
5,5,1
5,7 ,7
5,7 ,3
5,1,5
5,1,1
5,3,7
5,3,3
3,1,3
3,1,7
3,3,1
3,3,5
3,5,3
3,5,7
3,7 ,1
3,7 ,5
7 ,5,7
7 ,5,3
7 ,7 ,5
7 ,7 ,1
7 ,1,7
7 ,1,3
7 ,3,5
7 ,3,1
7 ,1,1
7 ,1,5
7 ,3,7
7 ,3,3
7 ,5,1
7 ,5,5
5,3,1 1,7 ,1
5,3,5 1,7 ,5
5,5,3 1,1,7
5,5,7 1,1,3
5,7 ,1 1,3,1
5,7 ,5 1,3,5