Fabio Montoro
T
re llis-Coded Modula lion (TCM ) has evol.ved over
lhe pa sl decade as a co mbm cd codlng and
moduladon tec hniq ue for digital transmission Q\'cr
band-Iímiled channels . -Its maio 31u3ction comes fTom
lhe faCl lhal ir all ows lhe achievcment af sign ifi ca nt
cod ing ga ins o ver co nvent io nal uncoded multilc\'cl
mod uladon wilh o ut co mpromising bandw idlh dfi eiene)'. The fim TCM sehemes. \Ve re proposed in 1976
[I ]. Foll ow ing a mo re de lail ed public3 1i o n [2 ] in 1982. a n
exp las ien af resea rc h and aClua l implemcmatlon s af
~CM lOok place. lO lhe pai nl where lOday lh ere is a good
understa ndin g af lhe lh eory and G1pa bil ities af TC~l ·
methods. In Part I af (hi s (\\Io-pa rt aniclc. an in troduc tion inlO TeM is g iven. The fca sons fo r lhedeve lop menl
of TCM are rev ie\Ved . a nd examples o f simpl e TC~ [
schemes " re d iscussed. Pan II [15] provides [unher
in sight inlO code design and performance. and ad dresses
Teeenl advances in TCM.
TCM sche m es e mplo y rcd und3 n1 nonbinar y modula tion in combinalion with a finlle-s(ale e ncoder wh ich
ggverns lhe selecti on af modulad o n sig nal s to generate
caded signal sequences. In lhe receiver, lhe no isy signa ls
are decoded by a sofl-decision maximum-likelihood
sequence decader. S imple fo ur-slate TCM . schemes ca n
improve lhe robusm css of digilal tran s mission aga insl
additive naise by 3 dB. compared lO conventional
uncoded modulalio n . \Vilh more co mplex T C:\I
schemes . lhe cad ing gai n ca n reac h 6 d B o r m ore. These
ga ins are ob lain ed wilh o Ul bandwidth ex pansion or
red uCliQn af lhe e ffective ~nformadan ra te as required by
lraditional erro r-correnion schemes. S han non 's in for malian lh eary predic ted lh e ex isle nce of coded modulation schemes with lhese c haraner istic5 :-nore lha n thre e
decades ago. The development of efleclive TCM lech n iq ues and lOday 's signal-processing technology no \\'
all ow lhese gai ns lO be o blained in practice.
S ignal waveforms represenling information sequences
are mOSl impervious lO noise-induced de tec tiol1 erTo rs if
lh ey are very d iffe ren[ fro m each olher. Mathematicall y.
(hi s lran slales in lO lhe rcqui rem en t [hal sig na l sequences
shou ld have large diSlance in Euclidea n signal space.
The essentia l new concep l of TCM Ihal led 10 lhe a[orementioned gains was lO use signa l-sc l ex pa nsion lO
provide redundancv fo r codin g . 3nd 10 design ·coding aird
signa l-map ping fu nctio n s jointh' 50 as lO max itn ize
direc Ll y lh e "free dis lance" (minimum Euclidean dislance) belwee n coded signa l sequences . Thi s 3 11ow ~d lh e
constru c ti on a f modularion codes whose frec disrance
signiricant ly exceeded lhe minimum d islan ce belw een
uncoded modularion sig nals. ar lh e sam e informarion
rale , bandwidlh, and signal power. The [erm "trelli s" is
used because 'lh ese sc hem es can be described by a s ra letra ns iti o n ( tre lli s) diagram similar to l he lrellis diagrams
a f binary convo luri o nal codes: The differcnce is tha t in
TCM schemes. lhe trellis branc hes ;] re labeled \dth
redundanl nonbinary modul3tio n signal s ra lh er lha n
Wilh binary code symbo ls.
The basic princ ipies of TCM were p ublished in 1982
[2]. Funher descri pl ions fo llOlved in 1984 [3- 6]. a nd
co in c ided witli a rapid lrdn siti o n of TeM from lhe resea rc h srage lO praClica l use. In 198·L a TCM sc he me
w ilh a cod ing ga in a f -l d B was adop ted hy lh e Inlernational T e legraph and Te lephone Consu lLat ive Commil-
5
February 1987-Vol. 25. No, 2
IEEE Communicotlon s Magazine
~,.:_:.::....... ~ ... _•
,<.~.~.:.~:;~;:~~~.... ~\: .:.~
.r·
.l . . . .
~:~~::~~~~~:',-
.. _ . . . . .:
.
.-_.~.~,
,~. '.' '. ~~~:-.. :~".~'~:'.><.,~:", ~'.'~~.q _..... ,,-:~i... ~
. ".\)' ',' .. '~'. ,~\.:~·;.. 4:_"':~_ _,~.
.
..,
'
:.... ,'. ~
"
.
.:~':' "-.f.:,~ . T~"'...
~ ,._~" ';~:"'.I:.
, ....
. -'
~.
.,
'.',
;~,
<o. '''',
,';'. ,;:. ':
;"'~;)-'>(.;~:.:.
; :.:...... _-.,
-
"
~~...~ ;~~ ~.,:~....:.
f;."
: ..: ...... ~,. :.'
~-~,~r.~
.....
•
-.l·
• __ .. l(~ ': '_:~-.,# '.
" : '• • "1- ":.~."-::.,,,'./: ..... 1 • .':,'
...-,'" lo .. :.
..
,1
'
."
.. ,
'.'
,
':··-:·#";
.,.-
" ,: . '" .. ~
'':.: '."
~":. ,:,.~~:"~'~"
..
'.
' . . . "t;
......
;
:.:..~
... ,. ...
~
.:.....'~.-.~
,.,.'
..
--="
r ..
"
- ...
. ..::
;
..
. : ... ,
~
~.,
.
.
'.'
.......
..
.......
• ~+"
-
. :".'
~:
-'
.... -"
'.~-
:'.
. 4'
... ..
-.~
"'-
•• -:,- ~~ _ ::".t...~ ..
........... .
..
-1.-'
.'':
.. - ~ . ,.' .. .
'. ·l····.·.···
";"".:
-'. '.
,
,"
o':::::..;.·.. :...
~
.
:.
,-~ ~ ,
'_.~:
'..
,.'~.'~
•
-~~
.•• 7"' • .
'.'
,~4
,
,
.
-'
'.#
'.
':
. ..
~; ~: -
#
•
~
.. ;
•• 1
-:
.
-
.' ."
',. : ,..,
,= :.~
--'....
. : "',: ,li::. r" ,.•
~.
}:',
~:
.
.... ','
,
'.~'
.;
:.. ,..
"'~:.
" :'
'.~"
::: .
';
. , ........'-
".
"-:-.'
.,;;~
~: ~~~~~~.~~ .~~:~::
.
:. ~ -. - , ' " ; . -
......
. ..:.:.~::~;;::::
•
- '
. . . . .' " . _ ; , . : .
,•.': .: ~..•~.' .,.,.,.~:•. :~;.•..~..~.:•.,~,. "."
:,..: • • , , : . ;
#
•
..
.' •....
. . .
..:'
~ 'p- •
,.
',-
:··...:~·" . \< . .~··.,·t
.
~.
•
'.
....
.
~
• -:. -.,r.,:.';' ....- '. ; .
-4
.~
;
,'.& .
.o -
"
.~
... ,o.
.
~:
.
;
: "';"'!-. . ,
:
. ..
....
..:..~...
~
~,.
.'- ...
""T •••
l'
•
•
•p
.... :
..
, • •:
•• _
:
••
1.
-,
..........-.
;/' '.~'..~.
.,
'.~
':. ..
'.'
":
..
"',
-'o , .
:'.~"": .
~'.;'
,.··\:i ".':: ~;~~: ,:;;~L??:::
~
.... :.:::\~~
... , --~".:
V
;.
.. ::_~.::.:...;:.. "" .".
"
>~5'
...... ".
.
.
'ee (CCITT) for use in new high-speed voieeband
modems [5 .7.8). Prior to TCM, un eoded lransmission
al 9,6 kbi tl s ovcr voiceband channels was arten con~
sidercd as a p racti ca l limit for data modems. Since
198~ , data mo dems have a ppeared o n lhe markel '
which employ TeM a lo ng wirh o lher improvemenls in
equalization, synchronization. ;)nd 50 ranho LO transmit
data relia bly Qvcr vo iceband cha nnels ,u rates af 14 .4
kbir / s and high er. Similar adv.a nces a re being achieved
in lransmission Qvcr ot her bandwi'dth·conslrained
channels. The com mon use af TeM techniques in such
ap plications . as sa lcllirc [9-11]. rcrres lria l microwave.
and mobile communi ca ti o ns. in ard er lO increase
rhroughpul rale a r to permit sa tisCactory opera don ar
lower signa l- to -noi se falias. ca n be safel y p red icted for
lhe near fULUre.
/.
ConvenLlonal encoders and decoders for error correction operale on binary, ar more generally Q-ary, code
sy mbols lransmiued over a discrete channel. Wiih acode
o [ rale k/ n < I , n - k redundam eheek sy mbols are
ap pended lO every k information symbols. Since lhe
decoder receives only discrete code symbols. Hamming
distance (lhe number of symbols in which IWO code
sequenees or bloeks differ, regardless of how lhese
sy mbols differ) is lhe appropriate measure of distance for
deeoding and henee for code design o A minimum
Hamming distance d~in, also called "[ree Hamming
di sta nce" in lhe case of convolulional codes, guarantees
lhal lhe decader ean carreel aI leasl [( d~;n -I )12) cadesy mbal errors. If low signal-to-noise ratios a r nons tationary signa l disLUrbance limit lhe performa nce af
lhe modulation syslem. lhe ability la correcl errors ca n
juslify rhe rate loss caused by se nding redundanr check
sy mbo ls . Similarly, long delays in error-reeo very
procedures ca n be a good reason for trading lransmission
rale for fo rward errar-correction capability.
Generally, lhere exist two possibilities to compensale
far th e rale loss: increasing lhe modularion rale if the
channel permils bandwidth expansion , or enlarging 'lhe
signal set of lhe modularion sys lem if lhe channel is
band-limited. The lauer necessarily leads to lhe use af
nonbinary modularion (M > 2). However, when
modulalion and error-carrection cading are performed
in lhe c1assical independent manner. disappo inling
results are obtained.
As an illustration , consider four-phase modul a lion
(4-PSK) wilhoUI coding, and eighl-phase modulation
(8-PSK) used with a binary error-eorreetion cade of rale
2/ 3. Both systems transmit two informatian bits per
modulation imerval (2 bit/see/Hz). ![ lhe 4-PSK syslem
operates at an error rate of 10-", at lhe same signal-tonoise ratio the " raw" erro r rate ar lhe 8-PSK demodulator
exeeed s 10-2 beca use o[ lhe smaller spaeing belween lhe
8-PSK signals. Patterns of at least lhree biterrors must be
corrected to reduce lhe error rate lO that of the uncoded
4-PSK sys lem. A rale-2/ 3 binary convolulional code wilh
eonslrainllenglh v = 5 has lhe required value of d~; .. = 7
[12). For decoding, a fairly eo mplex 54-slale bin a ry
Viterbi decoder is needed. However, after ali lhis effoTt.
erra r performance only breaks·even w ith that af un C:.:oded
4-PSK.
Two problems contribute to lhis unsatisfaclo ry
siLUarion .
Classical Error-Correction Coding
'-
In classical di gital co mmunicaLi o n sys lcm s. lhe funeLiolls af modulaLion a nd error- corrcCl io n coding a re
separa ted. ModulalOrs a nd d e mod ulaLOrs co nve n a n
a na log waveform channe l inlo a d iscrClC cha nnel .
wherc3s encoders a nd decoders co rrect errors lhal cceUf
011 lh e discrete channel.
In co nventional multi levei (amplitude a nd/ o r phase)
modulation syslcms. during cac h mod ulati o n inlcrvaI
lhe modulalOr maps m binary symbols (bits) inlO o ne Df
M = 2 m possible transmiL signa ls. a nd lhe demodulalOr
reCQvcrs lhe !TI bits by making an indepe nde nt M-a ry
nearest-neighbor decision 0 11 cach signa l received.
Figure I depicls co nsteIlations af rea l- or complexvalued modula Lion amplitudes. hencefonh called signal
selS. which are co mmonly employed for o ne- o r lWOdimensional M-ary linear modula rion . Two-dimensional carrier modulation requires a bandwidth of I/ T
Hz a round lhe ca rri er frequency to lransmil signals a l a
modula ti o n rale o[ I/ T signals/ see (bau d ) WilhoUI
intersymbol interfere nce. H ence. two- dimensional 2m _
ary modulalia n sys lem s ca n achieve a speClral effici ency
o[ a bo ul m bil/ see/ Hz. (The same speelral effieieney is
o btained with o ne-d imen sio nal 2m 2-ary baseband
mod ulari o n .)
Amplitude/Phase modulotion
Amplitude modulction
o
o
O
I
o
o
o
o
o
o
o
o
o
o 1 o
JO
~
8-A~
~::OOCCO
16-,4, '"
Phose modu lotion
04
+
o
•
o
"-PSK
o
o o
8 - PSK
o
o
o
o
o
o
o
o
o
o
o
o
o o o o
o o o o
o o o o
o o o o
o o o o
o 0+0 o
o o o o
o o o o
o o o io
o 0 :0 : 0
o io :o :o
o
o
o
o
o
o
o
o
o
o
o
o ~o j o : o o
, ,
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
00
0 0
6',,-oASK
1:2.8-CROSS
16- PSK
Fir:. /. S i grlfl l U (.~ f or oru~ ·d im i' ,uj01 I (l1 nmp/iIUi/e modu/nlÍ01I.
,, "d Iwo- d imOI.flO1I a/ p/UI.fi' flnti (wl pliIUdi' l p/uHe motJu/nlio 7l.
February 1987-Vol. 25. No. 2
IEEE Communicatlons Magazine
i
,/,
One problem in lhe caded 8-PSK sys lem jusl deseribed
arises from lhe independent "ha rd " signal decisions
m ade prior lO decoding which cause an irreversible loss
of information in lhe receiver. The remedy for lhis
problem is soft-decision decoding, which means lhat the
decoder operares directl y on unquanlized "soft " OUlput
samples of lhe channel. Let the samples be rn = a n + w n .
(real- or complex-valued. for one- or (wo-dimensional
m odul a lion, respectively), where th e a n are the discrete
sig nals senl by lhe modulalor. and lhe Wn represent
samples of ~ n additive white Gaussian noise processo
The decision rule of the optimum sequence decod er is to
32--GROSS
~o--l---o*o
; i
'. I
Soft-Decision Decoding and Motivation for
New Code Design
16-oASK
ooo l
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
1
6
.. - - - -_ ..
__.- .---
-"
__-
---- ... ---------------------------------_..
..
_...'
determine, among the set C of alI coded signal sequences .
which a cascaded encoder and modulator can produce,
the· sequence {ân} with minimum squared Euçlidean .
dislance (sum of ·squared errors) from {rn}' that is, the·
sequence 'fân} which salisfies
_
·lr,,-â I2 =
n
'~I
I
Min L
{â,,}EC _
necessary for coding-would have to come from expanding
the siggal set to avoid bàJidwidth expansion.
To understand the ,potentiaI improvemenls to· be
expecled by. this approach, he compuled the channel
capacilY of channels Wilh additive Gaussian noise for the '
case of discreie· multilevel modulation at lhe channel
input and unquanlized signal observation at the chan-nel
OUtput. The results of these calculations [2] allowed
making two observations: firstly, lhat in, principie
coding gains of about 7-8 dB over conventional uncoded
multilevel modulation should be achievable, and
secondly, that most of the achievable coding gain could
be obtained by expanding lhe signal sets used for
uncoded modulation onIy by the factor of two. The
author then concentrated his efforts on finding trellisbased signaling schemes that use signal sets of size 2m+1
for transmission of m bits per modulation interval. This
direction tumed OUI to be succesful and today's TCM
schemes still follow lhis approach.
The next two sections illustrate with two examples
how. TCM schemes work. Whenever dislances are
discussed, Euclidean distances are meant.
Ir"-a I2 •
tt
The Viterbi algorithm, originally proposed in 1967
[13] as an "asymptolically oplimum" decoding technique for convolulional codes; can be used 10 determine
lhe coded signal sequence {ân } closest to the received
unquantized signal sequence {rn } [12,14], provided thal
lhe generation of coded signal sequences {an}EC follows
lhe rules of a finile-stale machine. However, lhe nOlion
of"error-correction" is then no longerappropriale, since
lhere are no hard-demodulalor decisions to be corrected.
The decoder determines the most likely coded signal
sequence directly from the unquantized channel outputs.
The most probable errors made .by the oplimum
soft-decision decoder occur belween signals or signal
sequences fa n} and (bn ), one transmilled and the olher
decoded, that are closest together in terms of squared
Euclidean dislance. The minimum squared such distance is called the 'squared "free distance:"
di", ~
Min
{at/}~{bt/}
L Ia"-b,, I ,.
{a,,}, {b,,}
E
Four-State Trellis Code for 8-PSK Modulation
The coded 8-PSK scheme described in this section was
the first TCM scheme found by the author in 1975 with a
significant coding gain over uncoded modulation. It was
designed in a heuristic manner, like olher simple TCM
systems shortly thereafter. Figure 2 depicts signal sets
and state-transition (trellis) diagrams for a) uncoded
4-PSK modulation and b) coded 8-PSK modulation with
four trellis states. A trivial one-stale trellis diagram is
shown in Fig. 2a only to illustrale uncoded 4-PSK ,from
the viewpoint of TCM. Every connecled. path through a
trellis in Fig. 2 represents an allowed signal sequence. In
C.
When oplimum sequence decisions are made directly
in (erms of Euclidean distance, a second problem
becomes apparent. Mapping of code symbols of acode
optimized for Hammingdistance inlo nonbinary modulation signals does nOI guaranlee that a good Euclidean
distance structure is obtained. In fact, generally one
cannol even find a monolonic .. .relationship between
Hamming and Euclidean distances, no matter how code
symbols are mapped.
For a long time, lhis has been the main reason for the
lack of good codes for multilevel modulalion. Squared
Euclidean and Hamming distances are equivalent only
in the case of binary modulation or four-phase modulation, which merely corresponds to two orthogonal
binary modulalions of a carri~r. In contrast to coded
, multilevel systems,· binary modulation systems with
codes oplimized for Hamming distance and soft-decision
decoding have been well eSlablished since lhe late 1960s
for power-efficient transmission at spectral efficiencies
of less than 2 bitlsec/Hz.
The motivation of this author for developing TCM
initially carne from work on multilevel systems thal
employ the Viterbi algorithm to improve signal detection
in the presence of inlersymbol interference. This work
provided him with ample evidence of the importance of
Euclidean distance between signal sequences. Since
improvements over lhe established technique of ada ptive
equalization lO eliminate intersymbol interference and
then making independenl signal decisions in most cases
did not turn out to be very significant, he turned his
auenlion 10 using coding to improve performance. In
this connection, it was clear to him that codes should be
designed for maximum free Euclidean distance rather
than Hamming distance, and lhat the redundancy
4
30
~
2 .... ········ ..
.. ,
61=.ti
•••..•.•. 6 0
5°
\.
60
= 21ln (I'/a)
'o
°;............. =2"
62
d f, "
Redundont 8-PSK .Ignol .et
State
sl,~
o o
~
...
~~
~.~...~?>
2
•• 2 . ·
2
3
Fig.2.
7
·····3···..·
3
o
1
1
o
1
1
O"e-stote 'reln.
rour-sto•• t,ellla
(a)
(b)
(a)Uncoded/our-phasemodulalion(4.PSK),(b)Four-Slale
lrellis·coded eighl-phase modulalion (S·PSK).
February 1987-Vol. 25. No. 2
IEEE Communlcatfons MagazJne
both systems, starting from any state, four transitions can
occur, as required to encoae two information bits per
modulation interval (2 bitlsec/Hz). For the following
discussion, the specific encoding of information bits into
signals is not important.
- The four "parallel" transilions in the-one-slate trellis
diagram of Fig. 2a for uncoded 4-PSK do nOl restriét the
sequences of 4-PSK signals thal can be transmiued, that
is, there is no sequence coding. Hence, the oplimum
decoder can make independent nearest-signal decisions
for each noisy 4-PSK signal received. The smallesl
distance between lhe 4-PSK signals is .J2, denoled as AJ.
We caJl il lhe "free dislance" of uncoded 4-PSK
modulalion lO use common terminology with sequencecoded systems. Each 4-PSK signal has two nearestneighbor signals at lhis distance.
In the four-state trellis of Fig. 2b for the coded 8-PSK
scheme. the transitions occur in pairs of two parallel
transitions. (A four-state code with four distincl transitions from each state to alI successor stales was also
considered: however, lhe trellis as shown with parallel
transitions permiued the achievement of a Iarger free
distance.) Fig. 2b shows the numbering of the 8-PSK
signals and relevant distances between these signals:
Ao = 2 sin(1T/8), AI = V[, and 1.12 = 2. The 8-PSK signals are assigned to the transitions in the four-stale
trellis in accordance with the following rules:
through lhe code trellis with lhe. minimum sumof
squared distances from the sequence oi noisy channel
outputs received. Only the signals already thosen by
subset -decoding are considered.
_
Tutorial descriptions of the Viterbi algorithm can be
found in severa I textbooks, for example, [12]. The
. essenlial points are summarized hêre as follows: assume
that the optimum signal paths {rom the infinile past lO
alI trellis states at time n are known; the algorithm
eXlends these paths iteratively from lhe states at time n lO
lhe states at time n + 1 by cho<?sing one best palh to each
new Slale as a "survivor" and "forgetting" alI other paths
lhat cannot be eXlended as the best paths to the new
stales; looking bac1çwards in time. the"surviving" paths
tend to merge into lhe same "hislory path" at some time
n - d; with a sufficient decoding delay D (so lhat the
randomly changing value of d is highly Iikely to be
smaller lhan D), lhe informalion associaled with a
transition on the common history path at time n - D can
be selected for output.
Let the received signals be disturbed 1}y uncorrelaled
Gaussian noise samples with variance a2 in each signal
dimensiono The probability that at any given time the
decoder makes a wrong decision among the signals
associated with parallel transitions, or starts to make a
sequence af wrong decisions along some path diverging
for more than one transidon from lhe correct path, is
called lhe error-event probability. At high signal-lonoise ratios. this probability is generally well approximated by
a) Parallel transitions are associated with signals wilh
maximum distance A2(8-PSK) 2 between them,
the signals in the subsels (0,4), (1,5), (2,6), or (3,7).
b) Four transitions originating from or merging in
one state are labeled with signals wilh at leasl
distance AI (8-PSK) V2,between them, that is, lhe
signals in lhe subsets (0,4,2,6) or (1,5,3,7).
c) All 8-PSK signals are used in lhe trellis diagram
with equal frequency.
..
=
Pr(e)
=
N,r~~ e Q[d,r~~/(20)],
where Q(.) represents the Gaussian error integral
Q(x)
Any two signal paths in lhe trellis of Fig. 2(b) that
diverge in one state and remerge in anOlher after more
lhan one transition have at least squared distance
Ar + ~ + Ai = Ai + ~ between them. For·example, the
paths with signals 0-0-0 and 2-1-2 have this distance. The
distance between such paths is greater than the distance
between the signals assigned to parallel transitions,
A2 (8-PSK) = 2, which thus is found as the free distance
in the four-state 8-PSK code: drrt't' = 2. Expressed in
decibels, lhis amounts to an improvement of 3 dB over
the minimum distance V2 belween lhe signals of
uncoded 4-PSK modulation. For any state transition
along any coded 8-PSK sequence transmiued, lhere
exists only one nearest-neighbor signal at free distance,
which is the 180°.rotated version of the transmiued
signal. Hence, the code is invariant to a signal rotation
by 180°, but to no other rotations (cf., Part 11). Figure 3
illustrates one possible realization of an encoder-modulator for the four-state coded 8-P5K scheme.
50ft-decision decoding is accomplished in two steps:
In the first step, called "subset decoding", within each
subset of signals assigned to parallel transitions, the
signal closest to the received channel output is determined. These signals are stored logether with their
squared distances from the channel output. In the second
step, the Vilerbi algorilhm is used lO find the signal path
February 1987-Vol. 25. No. 2
IEEE Communlcatlons Magazine
=
1
= ..j21T
x
Jco
exp(--i/2)dy.
and NfrCT denotes lhe (average) number of neareSlneighbor signal sequences with distance dr~ that diverge
at any state from a transmitted signal sequence, and
remerge with it after one or more lransitions. The above
approximate formula expresses the fact that at high
DIFFERENTIAL ENCODER
8-PSK SIGNAL
rfil--,
MAPPING
x~~-J_------x~
X~
_ _ _ _~
_________~______________ Zl
~z;
4-STATE CONVOLUTIONAL
ENCODER
Fig. J.
Illuslrales an encodn lor
00001111
00110011
01010101
01234567
Signal No.
th~ lour·slal~
8·PSK
cod~.
8
"
....
_------------..._--_..._------_.------------------_ .. -_ ..
si ~nal-ICHlOi se r; lIios dito prohilhi lil y o f e rror l've nt s
associalcd w i[h a d isla llcl' 1a1'!.~"t'I" Ihen dI"," bccoml's
Il q~ lig" ihJco .
For 11IJ("od('tJ II-PSK . \\1(' ha v(' d h .. ,
anu N/H," = 2.
a nti for [OIII"·S I;)Il' ("(Hit'd H-PSK \\"(' fOllnd di"," = 2 :l II U N II .,..
= I . Si nn: in h(uh sysl<..'ms frel' dis l:lI1Ce! is fO llntl bt: [\\I('e! n
para l kllran s itioll s, . . . ill g'k s ig nal-deci sio n erro rs ilre! lh e
dominaling lTl'o r ('\' ( ' IH S .. In [ h(' s pccial ras(' of lhese!
.'I i 111 pl (' S)'S I(' II1 S. I IH ' 11' 1111 h(')"s ()f Ill';lI"CSI I1ci g h I)ors do 110l
d('fJl' luj 0 11 whidl pa ni c ul ar :, ig nal sequencl' is Iran s millC'd .
Figur(' ·1 s ho\\l s Ih (' n I"OI"- (' \'l'n l prnhahilil )' of lhe 1\\/0
syS I<' IllS as a fU Il("lio ll of si .l4"lla l-lo- noi sl' ralio . Fo r
lI11coded 'I-PS K, !lH' CITO!" -I'Velll pl"oha hil ity is eX lre m el)'
\\'(,11 appro xi m;lIed hy tIl(' las l IwO ('quõlli o n s abov(' . For
fo ur- s l<l I(' ("(){. lt-d H- PSK. [hese ('qu<ll io ns prov idt' a lower
bound l hal is asympLOlically achiev('d a i high s ig nal- to Tloi st· ralios . S imul a t ion rt's ult s are inclucl ed in Fit{ . . 1 fo r
111(' coded H- PSK s ySI('111 lO i llll sl rall' lhe ('(feri or l~r ror
l"\'(' lll S w i[h disl;lll(T larg'l'1" IlIal1 frcc distallce. \\I hosc
prohahility o I ()(T UlTl'I1 Ct' is 1101 nq~ligib l l' a i 10\\1 sig n a l10-n Ol Sl' ra tICJ . . . .
Figure S illu slrau:s a noi sy [o ul"-stol te coded 8 -PSK
sig n aJ as ohsl'n"l..'d a t co mpl ex basl'band bdore sal1lpling
= V2
\
f ig . 1..
w/lh
-2 '
10
>-
~
.o
'"o
.o
3
sig nal s are Joc(lled o n LI q uadratic g rid. al so know n as a
Jau ice o~ type "Z1 .... The code C<-In be useei wi lh a li of l he
sig na l se IS dep iCled in Fig . I fo r a m p lillldc/ phase
modu la li oll . To Irans mit!TI in formalio n bils per modulalion interva I. a sign;J) set w ith 2",..,. 1 signal s is needed .
H Cll cc . fo r IH = 3 lhe 16 -QAS K sig nal se i is 11 5('d. for m =
,,
,,
Q)
li
o
~
~
o
~
~
sta le
trel lis- c oded
4-
-I lhe 32-CROSS sig nal se l. " nd so[onh. For a n y ffi . a
cod in g g'd in of appro ximately -! el B is achieved over
\ 8 -PSK
\ (Simu lation)
-.
u ncooed modula li o n .
Figu re 6 ill u slrales a " ,el pa nitioning" of lhe !GQASK :lIl d 32-C ROSS sig n al seIs i nt o eig hl S110SC IS. The
pani li o ll i n g o f larger s ignal se iS is do n e in dw samt' way .
T IH' sig nal 5(' 1 c h osc n isdenoled by AO . and it s slIhsels hy
DO . DI.
07 . If lhe s mallesl d ist;lnc(' a lllong lh e
sigllals in AO is~ .. Ihen <llllo n g Lhc signal s in l he lInion
of dl t' SUOSt'LS DO.04.D2 . 06 or 01 . D5 . D:i . Di lhe mini11111111 dis l<.In ce is
à..,. in lh e unio n a f [h e SubSC1S
1)0.1)1: 1)2. 0 6: 01.05: o r 0~. 07 il is
;l o. :lf1d wilhi n
[lI l' individua l s ubscls it is
0. ... (:\ co nct'plu :dl y si mil a r
pa l"lili o ll in g n f l he H-P SK s i~llaJ SCI inlO s m ;dl{' r 'i igllal
.,l·I S \," ilh in (Tl':lsing inl r;l- sc l dis l:JIl ("t'S \lias illlplil'u illlh('
t·xall1 p lt . nf ("out·d 8- PSK . Tlw fll lldaI1H: llI;!I imj>OI"l ;IIH"l'
,,1
10
I~
I Channet
I capacity
101 8-PSK
I - 2 bit / sec / Hz
1
6
V2
7
8
1-:""'''''':'''1/( /lro/m/ohl \' ;·,· r . \ I / \
li /li
(lI rO ll/plt' \: {)(ut'lJ(lm/
The l' ighl -slaI C trelli s code dis(ussed in lh is sec li on
,
>
5
.\"I (!I/Il!
ui f. ,Nr, = 1'1 . (; !IH.
\\Ias dcs ign ed fo r lwo -dimens io n al sig nal se is whost"
o
0.5
Q)
w
Uncoded
4-PSK
3 de
1Õ
úgll(lI-/u-lwi. çt' rtllw
Eight-Slale Trellis Cod e fOF
A\mplílUde/ PnasfI Morlulalion
o
~
c
(I
in lhe recciver of a n ex p erim enta l 64 kbit/ s sa tdlilC
modem [9].. AI a sig n a l-lO-n oise ratio o, EJ N II = 12 . 6 dE.
( E.: s ig nal ene rgy . N n: a ne-s idcd s peclraJ noisc dcnsilY ).
l h e sig-nal is decoded t'ssc nli ally error- free . A I lh e sa m e
sig naJ-lO-nai se ratio. lhe e rrar rale Wilh uncoded II-PSK
m odulalion wo uld b~ a rou nd 10- " .
In TCM sc hemes w ith m o re nelli s Slales a nd Olh eI"
sig nal se IS. dI.". is n Ol nccessa ril y fO llnd be t \\l l~ C n parallcj
Ira n s ili o ns. a nd N Ir " . w ilI genera lI y be a n Jverage numbe r
la rge r Ihan ane, as wilI be s h ow n by lh e scco nd examplt',
-
a.
. Vo;. \-" fOflr-..~ /(llr ("IJ(/n/ N.. !'S }.,"
'''',·fi
I .. "S },,"
I llItI
9
10
11
12
dB
fi
\/l!llId-ln"f/ o/..\t' rfl//l1 (IIr
(ollr·\ I II I ,·
,,,,,,.tI .\... /... .,-11....
9
v:J
Februcry 1987-Vol.. 25. No . 2
IEEE Communicctlons Magazine
sequence and from any state along tbis sequence, lhere
are four sucb palhs, lWO of lengtb tbree and two oLlengtb
four. The most likely error evenlS wiU correspond to
tbese error palhs. and wiII result in bursls o( decisioR
errors of length three or four.
.
The coding gains asymplOlicalIy achieved al high
signal-ló-noise ratios are calculated in decibels by
Signal SOtl: t6-0ASK and 32-CROSS
AO
-
:~:~~:
: - 'ZZ"latt!Ce
:: ::.:: :
-00000
•
: :t~~~~': ;
Signallubsefs
G,. "
Fig. 6.
S~I
where dirlT.,· and dTnT.1I are lhe squared Cree distances, and
~". and Es.1I denote the average signal energies oC lhe coded
and uncoded scbemes. respectively. When lhe signal sels
have lhe same minimum signal spacing A .. drR't..J
dir",.1I = 5, and E,."./E...II ::::: 2 for ali relevant values oC m.
Hence. lhe coding gain is 10 )oglo(5/2) ::::: 4 dB.
The number of neareSl neighbors depends on lhe
sequence of signals lransmiued. lhal is Nrl'ft' represenls an
average number. This is easy lO see for uncoded
modulation, ivhere signals in lhe center of a signal sel
have more nearest neighbors lhan the outer ones. For
uncoded 16-QASK, Nrl'ft' equals 3. For eight-state coded
16-QASK. N rn,. is around 3.75. In the limit of large
"Z/' -type signal selS, tbese values increase toward 4 and
16 for uncoded and eight-state coded syslems, respeclively.
paTI;lion;ng of lhe /6-QAS/\ nnd J2-CROSS signal St'ts.
of lhis partitioning (or TeM codes wiII be explained in
Part 11.)
In lhe eighl-state trelIis depicted in Fig. 7, (our
transilions diverge (rom and merge into each state. To
each lransilion, one of lhe subsels DO, ... D7 is
assigned. If AO contains 2m+1 signals, each of ilS subsels
wiII comprise 2m- 2 signals. This means lhat lhe lransilions shown in Fig. 7 in (act represenl 21n - 2 parallel
lransitions in lhe same sense as there were lWO parallel
lransitions in lhe coded 8-PSK scheme. Hence, 2msignals
can be sent from each stale, as required to encode m bits
per modulalion interval.
The assignmenl of signal subsets lO lransitions
satisfies lhe same lhree rules as discussed for coded 8PSK, approprialely adapted to lhe present situation. The
four transitions from or lO lhe same slate are aIways
assigned either the subsets DO,D4,D2,D6 or D 1,D5,D3.D7.
This guarantees a squared signal dislance of atleasl2~
when sequences diverge and when they remerge. If palhs
remerge after two transitions. lhe squared signal distance
is at least 4~ between the diverging transitions, and
hence lhe total squared distance between such paths wilI
be at least 6A1. If paths remerge after three or more
transitions, al least one intermediale lransition contributes an additional squared signal distance ~, so lhe
squared distance between sequences 13 at.least
AJ.
Hence, lhe free distance of this code is
60. This is
smaller than lhe minimum signal'distance wilhin in lhe
subsels DO, ... D7, which is
60. For one particular
code sequence DO-DO-D3-D6. Fig. 6 illustrates four error
paths at distance V5 60 from lhat code sequence; all
starting al lhe same stale and remerging after lhree or
(our lransitions. It can be shown lhal for any code
.J5
Trellis Codes of Higher Complexity
Heuristic code design and checking of code properties
by hand, as was done during lhe early phases of lhe
development of TeM schemes. becomes infeasible for
codes with many lrellis states. Optimum codes must then
be (ound by computer search, using knowledge of lhe
general structure of TeM codes and an efficient method
lO determine free distance. The search technique should
also include rules to reject codes with improper or
equivalent distance properties without having to evaluate free distance.
In Parl n. lhe principIes of TeM code design are
outlined, and tables of optimum TeM codes given for
one-, lWO-, and higher-dimensional signal selS. TeM
encoder/modulators are shown to exhibitlhe following
general structure: (a) of the m bits lO be lransmiued per
encoder/modulator operation, f i S; m bits are expanded
into fi + 1 coded bits by a binary rale-m/(iõ+l)
convolutional encoder; (b) the + 1 coded bits select one
of 2m-+1 subselS of a redundanl 2In +l _ary signal set; (c) lhe
remaining m-m. bits delermine one of 2m- in signals
within the selected subset.
.J5
:;s
m
New Ground Covered by Trellis-Coded
Modulation
D2D401SDO
D1 01 D3 D5
DGDOD2D4
D4 De DO D2
0107
D2 DO OIS D4
D5 D3 0107
Fig. 7.
E;g"'-slal~. tr~llis cod~
for
nmpl;lud~1 plulS~
wilh "Z!"·lyp~ sig'lnl s~lS;
February 1987-Vol. 25, No. 2
IEEE Communicatlons Magazine
d",.,.
=
J5~I.
= 10 laglo [( d7r,.,..r·/ áj,,.,..u )/ E, ..!E.t.u )],
TeM schemes achieve significant coding gains al
values of spectraI efficiency for which efficienl codedmodulation schemes were not previously known, lhat is,
above and incl uding 2 bit!sec/Hz. Figure 8 shows lhe
free distances obtained by binary convolulional coding
with 4-PSK moduladon for spectral efficiencies smaller
than 2 bit/ sec/Hz, and by TeM schemes with lWOdimensional signal sets (or spectral eHiciencies equal lO
or larger than 2 bit/sec/Hz. The free dislances of
uncoded modulalion at lhe respeclive spectral effi-
os D3
modulalion
10
. --------. --_.. ---- .... -_..... __ .. -- -..... - .......... _.... -_... --- -- .. __ .__ ...
__._-------_
..... ..
61NARY CONVQlUTIOHAl
cooes
,
wrTH 4-PSI< MOOlA.A "OH
(4 - 2S6 11.'''1
A" 113
12 -
.,...
....,
~
:
~'6
u
0"-
-',
..
3 -
0 -
-
R"lI~
~'1'I.~
I '"
0'
o.
"
,
A
!
~i
t
':"
_
I'...
I
I
I
I
---
",,1112
.....
11 ..... •
......,
"
ut-tCOOEO MOOULATION
51.11111
2
L=
': ~lU~
I
3
I
,
,
.
", I
'DI
L
I
I1
.,
("t·O"'SK
...'. -- ,.
....,".
..
... '2S.~
". 16.»
I
\<'8.cRO
......
I6-0ASK
--L
I
s,..IH)
... ,•.u
,."" .........,
H-·
,
...'"
.
-l, ",~L. · _ _
" 1'-
li
14 - 2S5
... , l'I~
... I6-PSK
I
TR,I,us<oOEO MODULA"ON
1&.0"'$.1(
"i..
,
,,I
_
-
!,
II
I ....
141
••
-r-, ..:S~I ,'
-.
-12 -
...
Il"~
iLol'l
I .. J2
~
2.PSI(
-6 _ .
I
I
<li' ,.(a.psl(
- 3 -- - .
I
I ,,'/'
<lIll.... /
'-L.
...
I
I
I
mNI2•
9-
I,
I
II
I
OUI
§t A-1I2
ceding to nonb inary modulation wi th. signal sets o[
ar bitrary size. It a ll ows lhe achievement of cod ing gains
o[ 3- 6 dB a t spectral efficiericies equa l to or larger than 2
bit/ seci Hz. These are lhe va lues <.Il which one wan ls LO
operate on man y band-lim ited channels. Thus, a gap in
the theory a nd practice o[ chan·nel codin g has been
dosed.
.,
I
' 6-PSK
I
I
4
"
......~
"",'21
'
J........
01
:l2-CROSS
I
5
......
.....
,
",I
.
f...·......
,
6<1·0 ... $1(
Speclral etrlC,ency (biVseclHZ!
Fig. 8. Fru dislnna 01 binnry coPltlolUlionnl codt:J IIJ;llt -I-PSK
modulnliO'I. flnd TeM wilh a variely of lwo-dimensional modulatioll schenus. f 01 spUlro.l t:fficit:ncit:s !rom 21J lO 6 biUsf!c / H1..
,
.!
ciencies are also depicled. The average signal energy af
a li signal selS is normalized lO unity. Free disLances a re
expressed in decibels rela li ve lO lhe value dfrCT = 2 of
uncoded -I-PSK modulation. The binary convolutional
cedes o[ rates 1/3 , 1/2, and 3/4 with optimum Hamming
distances are taken [rom textbooks, such as, [12]. The
TeM codes and their properties are [ound in the code
tables presen ted in Part II (iargely rep roduced [rom [2]).
All coded syslems achieve significanl dis lance gains·
with as [ew as -I, 8, and 16 cede states. Rbughly speaking,
it is possible to gain 3 dB with -I states, -I dB with 8 states,
nearly 5 dB with 16 states, and up to 6 dB with 128 o r
more stales. The gains obtained with lwo~sta le codes
usually are very modesL Wiih higher numbers o f Slales.
lhe incremenral gains beco me smaller. Doubling the
number of states does nOl a lways yield acode wi th large r
free distance, Genera ll y, limiled distance growlh and
increasing numbers of neareSl neighbors. and neighbors
Wilh nexl-Iarger dislances. are lhe {wo mechanisms lhal
prevenl rea l codi ng gains from exceeding lhe ultimale
limil sel by channel capacity. This ' limü ca n be
cha raclerized by lhe signal-to-noise ratio al which lhe
channel capacity of a modulalion sys lem wiLh a 2'"+1_a ry
signal set equals m bit/ see/ H z [2] (see also Fig. 'I).
Conclusion
Trel l is-coded modu lario n was invented as a method to
impro ve lhe nbise immunily a f digital transmission
syslems withoul bandwidlh expans ion a r reduclion of
data rale. TeM eXlended the p rin cipies of convolulional
11
References
[ I) G. Ungerboeck and 1. Csajka. "On improv ing da ta-link
performance by increas ing lhe channel alpha bet and
imroducing seq uence cod ing. " 1976 Im. Sy mp. Inform .
Theory , ROl1 ll cby, Sweden. JUlle 1976,
[21 G. Ungerboeck, "Channel cod ing Wilh ITIlIhilc\'el / phase
signals." IEEE Tralls. l11fo rmalion Tht!ory, vol. IT-28,
pp. 55-67. jan. 1982.
[3J G. D. Forne\,. Jr.. R. G. Ga llager. G. R. Lang, F. M .
Longstaff, and S. U. QlIrcshi. "EfficicnI modularion for
band- limited channel s," IEEE Trans. Seiected A.reas in
Comm .. vaI. SAC-2. pp. 632- 647. Sepl. 19R4 .
[4 ) L. F. Wei. "Rotalionall y in\'arianl convolutional channel
codi ng Wil h expanded signal space-Part I: 180 degrees,"
IEEE Trans. Seiecled A.reas in Comm., vol. SAC-2, pp.
659- 672. Sepl. 1984.
[5 J L. F. Wei, "ROlal ional ly invaria m convo luli o nal channe l
coding with expanded signal space- Part 11 : nonl in ear
codes," IEEE Trans. Sdecud Areas in Comm., vaI. SAC-2,
pp. 672- 686. Se pl. 1984.
[61 A. R. Calderbank and J. E. Mazo. "A new description of
lrellis codes," IEEE Tran s. lnformatio71 Theory, vol. IT·
3D, pp. 784-791. Nov. 1984 .
[7J CCITT Sludy Group XV II , " Recommendalion V.32lora
family of2·wire. dup lex modems opera lin gon lhe general
sw itched lelephane nelwork and on leased lel epho ne-lyp e
circuits." Oocument AP VIII·4~-E. May 1984.
[8J CCITT Sludy Group XV II , " Drall recommendalion V.33
for 11400 bits per seco nd modem sta ndardized for use on
poim-tO-poim 4-wire leased telephone-lype circuils,"
Circular No. 12, COM XVII/ YS, Geneva, Mar 17. 1985.
[9J G. Ungerboeck . J. Hagenauer. and T. Abdel Nabi .
"Coded 8-PSK experimental modem for lhe INTELSAT
SCPC systcm.·' Proc. 7[h Im, Conf. on Digital Salell ile
Communicalions (ICOS-7), pp. 299-304. Munich. May
12-16. 1986.
[ IO J R. j. F. tang, ·'A coded 8-PSK sySlem lo r 140-Mbil/ s
informal ia n rale rransmission over 80-MHz nonlinear
lranspo nders." Proc. 7th Im. Conf. on Digital Salellile
Cammu ni catio ns (lCOS-7 ). pp. 305- 313, Munich. May
12-16. 1986.
[lI}. T. Fujino. Y. Moritani. ' M. Miyake, K. Murakam i. Y.
Sakato. a nd H . Shiino. "A 120 Mbit/ s 8PSK modem with
sofl-Vilerbi decoding ," Prac, 7th Im. Conf. on Digilal
Sa lelli lc Co mmUniC;)li ons (lCOS-7 ). pp. 315-32 1. Munich o May 12-16. 1986.
(l2) G. C. Cla rk a nd J. B. Cain . Error-Correclioll Coding for
Digital Communications, Plenum Press. Ncw York a nd
Londan. \981.
[l3} A. J. Vilcrbi. "Errar bounds fo r ca n volulional codes and
an asymplolically opli mum decoding algorithm." IEEE
Trans. lnformation Theory. vol. IT-13. pp. 260- 269, Apri1
1967.
[I'IJ G. D. Forney, Jr .. "The Vilerbi algorithm." Proc. of lhe
IEEE, vol. 61. pp. 268-278. March 1973.
r15} G. Ungerbot'ck. "Trellis-coded modulation wir il redun·
dan l signal seiS, Pan Il : Slalc of lh~ an ." IEEE
Commllnicutiol1S Magazine. vo l. 25, no. 2, Ft:'b. 1987.
February 1987- Vol. 25, No. 2
IEEE Communlcatlons Magazine
I
I n [his seco nu parl (lJ. a sy nopsis af lhe presenL slatc af
lhean in lrellis-coded modulation (TCM ) isgiven for
lhe more inlc reslcd readcr. Firsl. lhe general SlrUCLUre af
T eM sc hemes a nd lhe princ ipies af code co nslruc ü o n
are rev iewed. Nexl. lhe effcCls af ca rri er- p hasc orescI in
ca rrier-modula lcd TeM SYSlcm s are d iscussed . The topic
is impo n a nl , s ince TeM sc hemes LUfO QU l lO be more
sensi li ve lO phasc OffSC l than u ncodcd modula ri on
sys lcms. Also. TeM schemes a re genera ll y nOl p hase
invarianllO lhe sa me cx lent as lhei r sig nal se lS. Fina lly,
recenl adva nces in TeM schemes lha r use signal scts
defined in more lh an {\vo di m en sion s a re described . a nd
olher wo rk rclareel lO lrelli s-codcd moduladon is mention ed. T he besl codes c urrend y know n for one-, (\\10·.
four-, a nd eig hl-d imensional sig nal selS a re given in a n
Appendix.
Design of Trellis-Coded
Modulation Schemes
The lrellis SlrUClure of lhe ea rl y hand -desig ned TCM
schemes a nd lhe heuristic rul es used to ass ig n s i gn~ l s to
rrellis lransitio n s sugges ted that TeM schemes sho uld
ha ve a n intcrpretation in (erms of co nvo lutional codes
Wi lh a specia l signal m app ing_ This mapping should be
based 0 11 g rouping sig nals into suhsels Wilh large
dis lance between the subset signa ls. Auempls lO ex plain
TCM schemes in lhis manner led LO lhe ge neral struClure
ofTCM encoders/ modula lors depicled in Fig_ I. According to lhis figure , TeM signal s a re genera ted as fo llows:
When m bits a re to be tra n smitted per encoder/ m od ularor
operation_ m:S m bilS a re expa nd ed by a ra le-m / (In + I )
bi nary co n vo lutiona l encader into rii + I ~Od éd bils.
These bits are used to seleCl o ne of 2';1 .... I subsets af a
redundant 2m + ' -ary signal set. The remaining !TI - rii.
uncoded bits determine which of lhe 2",- ,i1 signal s in lh is
subset is lO be transmiued.
Set Partitioning
The co nceptof set partitioning isof ce ntral signi fica nce
for TCM schemes. Figure 2 shows lhis co nct' pt fo r a
32-CROSS signa l sel (I ], a signal sel of lallice lvpe "Z; '.
Generall y, thenotation ·' Z~" . is used toden o tea n in finile
"Ia uice " o f points in k-dimen sio na l space w ith integer
coordinates. Lauice-type sig na l selS a re fin ite subsets of
lauice points. which a re centered arou nd lhe o rigin a nd
ha ve a minimum spaci ng of d().
Set panitioning divides a sig nal sel successively into
smaller subselS with maximally increasing smalles t
intra-set dislances Â;, i
0.1. .. . Each panilio n is
lwo-way. The panitioning is repealed rn + I limes u ntil
.ó. ,il+1 is equalLO or g rea ler tha n lhe des ired free dislance of
lhe TCM sc heme lO be desig ned. The fi na ll y ob lained
subselS. labeled DO, DI, .. _ D7 in lhe case of Fig. 2. \V iII
hen cefo nh be referred lO as lhe " subselS." The labeling of
bra nches in the pa rtiri o n lree by lhe m+ I coded bits z::' .
z:~ , in lhe o rder as show n in Fig. 2. resuhs in a label l"
=
for each subset. The la bel refleCls lhe positio n
of lhe subset in Lhe tree.
Thi s labe ling leads lO on imponanl propen y. If lhe
labe ls af lWO subsets agree in lhe las t q positioll s. but no t
in lhe bit z:~. then the sig nal s of th e t\\lO subsets are
=
... .
[z::', ... z::l
12
016:l-681J4/87/0002-OO12 S01 .00 ' '1987 IEEE
-
_x;:
~
rtt~iii
-~.,;....----------"";';'::"*'
::I,
. ::,I
"
-X:·I,_-!-'::--_________
I.
CONVOLurlONAL
ENCODER
Fig. J.
Selec. signa'
from subsat
'1
-"+".-.tJ
"
x'n
where {~II} den~tes -lhe error sequence b~ which these
sequences differ. Since lhe convolution.al code 15 linear.
klll is also acode sequence.- It folIows from lhe "setpartitioning Iemma" menlioned in lhe preceding sub5eclion and the· "rale-m/(m + 1) code lemma" that lhe
squared free disrance betweeil non-parallel paths in the
TeM Lrellis is bounded by [2]
SIGNAL
MAPPING
dj,,.,.(m) ~
Salec. subset
Rata m/(iii+1)
L:"
Min
k"I;06IOI
Here q(~n) is lhe number of trailing zeros in ~," lhal is.
lhe number of trailing positions in which lWO subset
labels ~II and ~{. =~II EB ~II agree. For example. q(~1I j= 2. if
~u =[e::
~,I,O.O] ..The "set-partitioning lemma" states
lhal the distance between signals in lhe subsets selected
by ~n and ~:. is lower-bounded by ~flCCnl' One must take
A cUI = O, nOl d,il+I. Minimization has to be carried out
over ali non-zero code (error) sequences {~II} thal deviale
alo say. lime O from the alI-zero sequence {m and remerge
Wilh ilala later lime. The "rate-m/(m + I )code lemma"
assures lhal for any given sequence {~II} lhere exist lWO
coded signal sequences whose signals have at any lime n
lhe smallest possible distance between lhe signals of
subsets whose labels differ by til' UsualIy, lhis smalIest
distanceequaIs Aq(tul forall ~II' If this is thecase, lheabove
bound on drn"\.(m) becomes an equation. (OnIy when the
signal subsels contain very few signals may lhe bound
nOl be satisfied with equality. A similar always true
equation can then be used to compute drm.(m) [2].)
This equalion is of key importance in the search for
optimum TeM codes. It states' lhat free Euclidean
distance can be determined in much the same way as free
Hamming distance is found in linear binary codes, even
lhough Iinearity does nOl hold for TCM signàl seq uences.
It is only necessary lO replace the Hamming weighls of
the ell (number of 1's in ~II) by the Euclidean weights
A~(tlll' It is not necessary (as some authors seem to think)
to compute distance between every pair of TCM signal
sequences.
G~ntmd slruelur~ of meoderl modulalor for lr~ili.f·eoded
modulalion.
I
.... ,
elemen ts of the same subset a t leveI q in the parti tion tree;
thus they have at least dislance Arl' This dislance bound
can be staled in a "set-partitioning lemma" and will be
used in the next subseclion.
The m - m uncoded bits X::I, ...• X::I+I are used lO choose
a signaI from lhe selected subsel. The specific labeling of
subset signals by these bits is not particu~arly important
at this point of the discussion. In the code trellis, the
signaIs of lhe subsets become associated with 2m - lil
parallel transitions.
The free Euclidean distance of a TeM code can now be
expressed as
d",.,.
.
I/
= Min[A';,+I, d,,"(m) l,
where Am+l' is the minimum distance between parallel
transitions and drm-(m) denotes the minimum distance
between nonparaIlel paths in the TeM treIlis diagramo
In the speciaI case of m = m, the subsets contain onIy one
signal, and hence lhere are no parallel transilions.
,
t
Convolutional Codes for Trellis-Coded
Modulation
Al every time n, lhe rate-m/(m'+ 1) convolutional
encoder depicted in Fig. 1 receives m input bits. and
generates m + 1 coded bits which serve as the subset
labels ~n = [z::" Z~]. The set of alI possible sequences
{~II}' which lhe encoder can generale, forms a convolutional code. A linear convolutional code of rate rol
(m + I) is mOSl compactly defined by a parity-check
equation which pU1S a constraint on lhe code bits in a
sliding time window of length v + 1:
Search for Optimum TCM Codes
o ••
t(h:.z;~,-l' E9 h:..... ,Z;!,,·~,
E9 ...
For lhe one- and lwo-dimensional signal sets depicted
in Fig. 1 of Part I [1], lhe minimum inlra-set distances are
AO'
.........
··~z;
•• 0 0 0 0 ' •
h~z;!,) = O.
In lhis ~q(~ation. E9 denotes modulo-2 addition. The
quantity li is called the conslraint length. The quantities
h~, " ~ 2 ~ O; O S i S m, are lhe binary parity-check
coefficienls of lhe code. Valid code sequences salisfy lhis
equalion at alI limes n. The equalion defines only lhe
c~e sequences, nOl lhe inputloulput relation of an
encoder. A laler subsection deals with minimal encoder
realizations with " binary storage eIements, which is
equivalent lO saying that the code has 2" trelIis states.
From lhe parity-check equation, one can observe lhat
code sequences {~II} can have arbitrary vaIues for each
I, ..• Z:I] with an appropriate choice of lhe
m-luple
sequence {z?} 50! lhal lhe parity-check equalion is
satisfied. This property can be expressed in a "rate·m/
(m + 1) code lemma."
Let now {zu) and {~I} = {~II EB ~n} be two code sequences,
·000000·
'000000'
"0000"
.:~=I
.. ~~ ... ;..- ........ ~ ... ~~ .. .
zO=o
:
~~~~~
: :
: :
: ~ ~ ~..~ ~ ~ :
. '0'0'0'
. . o· o· ..
~
z~
I
I?
',z~
~
=I
C3
'0'1
••••.•..•• 6 2 "",_4
IT 0
~: ~+:
. o· o· o
~ 06
.. o· . . • . . o·
, . ~: : : .
: ~ :.: : ~ :: :..~ ::
•. o·. ... :: ~.: : : .....
. . ..... . • . . . •
'"
z~=OI \Z~;I
oI
~ 05
'. ~.' :"'0:">"
'"
.•.•.. o
........
.. o·
.:
o· o· o·
0·0'
z~=OI \Z~=1
z~=OI \Z~=1
03
'"
~.'.:.'~.
~
07
~ ~.'~.::.- 4s=~Ao
õ. '.:
'.' '.' '.: .•
. . o· ........ o·
co
S~l parlÍlümill.l{ o{ lhl' n·CROSS sigllal .~I'l fof [lluia Iyp~
··Z!" ).
90":
Fig. 2.
=0/'
CI
C2
: ~ :+~: ~
02
=fi Ao
'0'0'0"
,z~;
o· o· o.
~: ~+: ~:
~ ~ ~ ~.: •• 6,
: ~ ~ ~.~ ~ ~ :
. . . o· o· .
tz::
\ ...
loltlce
: :: :.:: X·;---- Ao
CO -
Cl
-
C2 -
C3
_
-I
I
I
1
l
;
13
February 1987-Vol. 25, No. 2
IEEE
Communlcatlons Magazine
dS
li)
'o
lracking. In these loops, IlTe phase offset is estimated
fr9m the received signal and lhe decoder decisions. The
eSlimaled phase offsel controls lhe demodulating E:arrier phase. In a TCM receiver, if lhe phase oifsel exceeds a, criticai value, for example,_22.5° in lhe case of coded
8-PSK, lhe decoderdedsions become essenlially uncorreIaled with the received signal and lhe mean value of lhe
phase estimale drops 10 zero. Figure 5' ilIustrat~s, for
4-s1ale coded 8-PSK [2], the mean estimale oJ /l'c/> ("Scurve") and i IS variance as a f unction of the aClual vai ue
of lhe phase offset. A val)ishing mean estima te, as occurs
for /lq, belween 22.5° and 157.5°,leaves lhe carrier-phase
tracking loop in an undriven random-walk situalion
which can lasl for long periods. Evenlually, lhe system
resynchronizes when the randomly-fluctuating demodulating carrier phase approaches a value for which the
received signal again resembles a valid TCM sequence.
This behavior is in significant contrast to the short phase
skips and rapid recovery observed in uncoded 4-PSK or
8-PSK systems. It suggests that in some cases TCM
syslems may require special methods to force rapid
resynchronization.
18
~
11
co
'-'
0..... 16
l
co
>
co
:c
..:1 ,
~ 14
~
-
o
-c
co
':; 12
eco
'-
~o
10
(I)
w
a:
'-'
z
cn
!.
00
•
l
...,
'~
Fig. -I.
22.5°
Carrier- phase offset â4)
45 0
lnvariance of Two-Dimensional TCM Codes
under P hase Rolation
Error pnlormanc~ 01 coded 8-PSK and uncod~d 4-PSK in
lh~ presmce 01 carrier-phase ollsel Il.q, •
..
~.
TCM codes are nOl usually invariant (O ali phase
rotations under which the signal set is phase invariante
Figure 5 indicates a phase symmetry of 4-s1ate coded
8-PSK only at llq, 180°, but not aI other multiples of
45°. This symmelry can be verified by inspection of the
code trellis presented in Fig. 2b of Part I [1]. Coded 8-PSK
schemes which are invarianl to phase shifts of ali
multiples of 45° have been found [4], bUl these schemes
require more than four SlaleS to achieve a coding gain of
3 dB.
In general, it isdesirable thal TCM codes haveas many
phase symmetries as possible 10 ensure rapid carrierphase resynchronization after temporary 10ss of synchronization. On lhe other hand, such phase invariances
must be made lransparent to lhe lransmiued user
Performance Degradation
t
Jr'
~~
.\.'---
~
.:/
=
The error performance of 4-stale and 8-stale coded
8-PSK syslems in lhe presence of phase offsel (based on
unpublished work) is ilIuslraled in Fig. 4. The figure
shows lhe signal-lo-noise ratio needed lO susta in an
error-evenl probabililY of 10-3 as a function of Aq,. For
lhe coded 8-PSK syslems, lhe required signal-lo-noise
ratio increases with increasing values of Aq, unlil bOlh
syslems fail alllq, = 22.5°, even in the'absence of noise. In
conlraSl, uncoded 4-PSK requires a higher signal-tonoise ralio aI small phase offsels. bUl has an operaling
range up to /lq,
45° in the absence of noise. These
results are lypical for TCM schemes.
The grealer susceplibilily of TCM schemes 10 phase
offsel can be explained as follows. In the trellis diagrams
of TCM schemes, there exist long distinct paths with low
growlh of signal distance between them, that is, paths
which have either the samé signals or signals with
smallest distance /lo assigned to concurrenl transilions.
In lhe absence of phase offset. the non-zero squared
distances llÕ and the squared larger distances of diverging
or merging transitions add up loat leaslthe squared free
dislance. However, if phase offsel rOlales the received
signals such that received signals become located
halfway belween the signals of the original signal set, lhe
difference in dislance between received signals and lhe
signals on dislincl lransitions thal are llo apart may be
reduced 10 zero. There may lhen be no difference in
distance between a long segment of received signals and
two distinct trellis paths, jusl as though the code were
calastrophic. At this poinl. the decoder begins to Cail.
=
~
t-\
.""
./"',
,r',....../..-''''''_/-',
\
'.I
200~,-/ \
,
.
\
\
10° '00 I
-c"..
lir
'-'
/-.
i
Standard
deviation
\.-
!"",
!
\_
c'"•
•C
•,
.c
rol
-10 0
Mean estimate of
(S- curve)
A~
-20°
-45°
0°
45 0
90°
135 0
180 0
225 0 âcl)
Mean ("S-curoe") and varianu o/lhe eslimal~d phas~ ollsel
decision·diTeCI~d carrier-plul.'ie lracking loop lar 4-slal~
coded 8-PSK versus lhe aclual pha.f(! oll.'iel tlq" ai a signal-lo-noise
ralio 01 JJ dB (lenlal;ve deci.'iions used wilh zero d~lay).
Fig. 5.
Behavior of Carrier-Phase Tracking Loops
tJ.4> in a
Nowadays, in most digital carrier-modulation syslems,
decision-direcled loops are employed for carrier-phase
15
February 1987-Vol. 25, No. 2
IEEE Communlcatlons Magazine
I.
~
the CCITT V.33 Draft Recommendation [8. Part I), but
with 64-QASK and 128-CROSS signal sets (m = 5,6). In.
the limit of large signal sets. lhe number of nearest
neighborsin lhe 8-Slale linear and lhe CCITT nonlinear
code is 16.
.
In a late contribution to lhe CCITT [7], illuslraled in
Fig.. 7. an alternalive 8-stale nbnlinear encoder Wilh the
differenlial-encoding function integrated into the encoder was proposcd. The coding gain and the number of
nearest neighbors are identical to those af the other 8state schemes. Thc lrell~s diagram of lhe alternative
nonlinear code was shown in Fig. 6 of Part I [I].
Differential dccoding requires that the receivcrcompule
x:, z~! EB z~:+I' Subsels are I&lbeled as indicélled in Fig. 2.
The selection of signals within the subsets by the
uncoded bits x,~, x~ is worth mentioning. If X,I, = O. ollly
signals of the inner 16-QASK set are transmiued (m = 3).
With non-zero values of x,~. outer signals of lhe larger
32-CROSS sel arealso selecled (m =4). Extension of this
concept lO larger sigmll sets resulted in one geneml
signal.mapping for ali data rates. e.g., for 3:5 m :5 7 [7].
The mapping has the addilional. property lhal il can just
as wellbe used for uncoded modulation with módulo-4
differential encoding of lhe bits z:" z!!.
The nonlinear 8-state TCM codes appear lO be special
cases. Similar nonlinear phase-invariant codes wilh 16
and more states can be constructed. However. at least for
16 stales. itdoes not seem possible to find acode with lhe
same 4.8 dB coding gain as can be obtained with a linear
code.
X~
,----------------------~
...
zA
zJ.
32-CR
SGIAL
MAPPING
8n
~~+---~~----~~~----~
~,
(S80
below) .
HUMSER 8EHEATH SIGNAL:
=
.:.:Z!Z!Z:
Fig. 6. NonlineaT 8-slale eneodeTI modulaloT wilh J2-CROSS signal
sei and dif/eTenlial eneoding. as in CCITT Recommendalion V.J2.
information by some form of differential encoding and
decoding. If loss of phase synchronization is very
unlikely, one may argue that TCM codes without phase
invariances may have theadvantage that the receivercan
establish absolute phase from the received signal. so that
no differential encoding/decoding is required.
The problems of phase invariance and differential
encoding/decoding auracted considerable auention in
work taward a TCM code for use in CCITT Recommendations for voice-band modems operating full-duplex at
up to 9.6 kbit/s over two-wire telephone circuits. and at
up ta 14.4 kbit/s over four-wire circuits. There was
considenlble interest in a two-dimensional 8-state code
that can achieve. with 90 0 -symmelric QASK and CROSS
signal sets. a coding gain of about 4 dB over uncoded
modulation. With the known linearcode (cf. Table 111 in
lhe Appendix. li 3), ir was only possible (by adding
parity-check coefficients in a way which does not change
free distance. as mentioned in lhe subsection on
optimum-code search) ta have either no phase symmetry
ora symmelryal180° [51, [4, Part I]. A breakthrough was
finalIy accomplished by L.F. \-Vei. who intraduced
nonlinearelements inta the convolutional encoderof lhe
8-state code. This made the code invariant to 90°
rotations while maintaining its cading gain of 4 dB [6],
[5. Part I]. Figure 6 shows the resulting encoder/modulator with its differential encoder, nonlinear convolutio·nal encoder, and signal mapping for a 32-CROSS
signal set (m = 4). as finally adopled in lhe CCITT V.32
Recommendalion [7, Part I]. The labeling of subsels
dicrers slighlly from lhat indicated in Fig. 2, bUl lhe
subsets are lhe same. The same code was also chosen for
X
4
~n~
x~
____________________________________________________ X~ r---------,
~
r----------------------------------:
SlGNAL
Xl
:OFF. ENCOOER
z~ MAPP1NG
~n~--!-*~~--t'i------r------t---t(seo below)
8n )(
GAIN
··
'-----......----------.......··
'-' •••• ______ •• ___________________________ J
NONLINEAR CONVOLUTIONAL ENCODER
NUM8ER BENEATH SIGNA!.:
=
February 1987-Vol. 25. No. 2
IEEE Communlcattons Magazine
z~
.:-.!Z!Z!Z:
o
o
o
o
11010
11111
10110
10011
r---
o
o
o
o
o
o
10000
01001
01100
00101
01000
11001
o
o
o
o
o
o
10111
00110
00011
00010
01111
11110
o
o
o
o
o
o
11100
01101
00000
00001
00100
10101
o
o
o
o
o
o
11011
01010
00111
01110
01011
10010
o
o
o
o
·10001
10100
11101
11000
Fig. 7. Allnnali.,t' nonliut'(lr R-slalt' t'"eodt'Tlmodultllnr w;lh inlt'grait'd dil/t'Tt'nlial tmC"oding nud ,l{ePlt'rnl sigrral mnt)pirrg fOT /6QASK. J2-CROSS, ele., s;gllnl st'I....
16
.1
Multi·:DimensionaI Trellis Codes
xl:"·...-----,
x~·
~------------------------~------------~
Recently. lhere have been a number of investigalions_
into trellis coding with signal sets defined in more lhan·
two dimensions (3. Part I]. [8-11]. In practical syslems.
multi-dimensional signals ·can
lransmiued as se-:
quences of constÍluenl one- or two-dimensional (1-0 ar
2-D) sigmlls. In lhis.. sectioll-.. 2K-D TCM schemes are
considered which lrdnsmÍl m bits per constituent 2-D;
signal. and hence mK bits per2K-D signal. The principie
of usinga redulluant signal set.of lwice lhe size needed for
uncoded modulation is mainiained. Thus, 2K-D TeM
schemt·s use 2~1II+I-ary sets of 2K-D sigmlls. Compared lO
2-0 TCM schemes. this results in less signal redundancy
in lhe constituent 2-D signal sets.
For 2-D TCM schemes with "Z2"-type signal seiS. lhe
minimum sigllal spacing à" mUSl be reduced by
approximately lhe faclor ;:;2(- 3 dB) lO have lhe Sélme
average signal power as for uncoded modulation. This
loss in signal spacing needs lO be more lhan compensaled
for by codillg lO obtain an overdll improvemenl in free
dislance. The lower signal redundancy of multi-dimensional TCM schemes with "Z2K" -type signal seis resuhs
onl)' in a reduclion of lhe minimum signal spacing by
lhe 2K-lh rOOl of 2 (.-:-1.5 dB for K 2; and - 0.75 dB for K
= 4). so coding has to contribule less lhan in lhe case of
2-D TCM to obtain the same gain in free distance. The
larger sigilal spacing should also make multi-dimensionaI TCM syslems less sensitive lO phase offsel.
FinalIy. it has been found lhat multi-dimensional TCM
schemes with 90° phase invariance can be obtained with
linear codes.
be
z~
hM~----r---,----+----~
'--.....---......
=
=
=
=
N:
.r4G"
F
=
The 4-0 TCM schemes (K
2) described in lhis
subsection employ compacl sets of22ni+1 signals chosen
from a lauice of type "ZI" with minimum signal spacing
~". Figure 8 illuslrales lhe sel partitioning of a signal set
of lype "ZI". The general idea is lO derive lhe sel
partitioning of a higher-dimensional signal set from lhe
set partitioningof constituenllower-dimensional signal
sets. In the present case, A': and ilS subsets are characterized by two constiluent "Z2 ,. -lype signal sets AO and their
'O.....
l
(- o~... 7
zg
subsets. such as inlroduced in Fig. 2. This leads (O a
partilian rree wirh signal seis of types "ZI" - "DI" "ZI" - "DI" - "ZI", etc.. wilh minimum intrd-set
lln. elc. The
dislances ~(I.lll =~:! ~ .!lllt ll'l =!ll =
next pardgfaph describes lhe details of lhe partitioning
process (and may be skipped by readers without specific
interesl in lhis process).
Sel partitioning begins by writing A':
AO ~ AO (X
denotes set-product operatian: lhe producl ser consisls of
ali concalenations af elements of the first set with lhe
elemenls af the second set). Substitution of AO BO U BI
(U denotes sel union) yields AC
: = (BOUBI )X(BOUBI) =
(BOXBO)U( BOXB I )U( B I XBO)U( B I XB I). The first partition divides AI: inlO lhe two subsets BCl
(BOXBO)U
(BIXBI) and B.I (BOXBI )U(BIXBO). These subsets are
af type "DI". where "D I" denotes lhe densest lauice
known in 4-D space Pg}. The minimum intra-set
distance in B': and B.I is V2 ~(I, which is the minimum
distance between constüuent2-0 signals in BO or B I, and
also between one 4-D signal in BOXBO and anolher in
BIXBl. On lhe next binary partition, e.g., when B': is
partitioned into subsets BOXBO and BIXBI. no dislance
increase is obtained. These subsets are of type "Z.I". like
At (rom which they differ only in lheir orientalion.
position with respect lO the origin, and scaling. Hence.
lheir partitioning is conceptually similar to lhat of A':.
The minimum intra-set distance increases to
llo
when, e.g., BOXBO is split inlO subsets CI: (COXCO)U
(C2XC2).and
(COXC2)U(C2XCO), which are now
again af type "DI".
Oplimum convolulional codes are found by using lhe
obtained sequence o( minimum inlra-set dislances in lhe
code-search pragrdm mentioned earlier. The codes and
their asymplOtic coding gains over uncoded modulation
with "Z2" -type signals are given in Table IV in lhe
Appendix. The g"dins are \'alid for large signal sets which
fiH thesame volume in signal spaceas lhe signal selS used
for uncoded modulalion. Thus. lhe comparison is made
for the same averdge signal power and lhe same peak
power af 2-D signals.
It may be helpfulla discuss lhe 16-stClte code of Table
IV. which achieves an asymptolic coding gai n of 4.52 dB.
in more delail. The code uses lhe eigh( 4-0 subsets
C~ shown in Fig. 8. and has 64 dislinct transitions in its
lrellis diagramo "The. onJy nearest-neighbor signals are
lhase associated with pardllel trdnsilions. and their
number ai anv lransition is 24 (lhe number of neareSl
neighbors in a '''OI''lmtice). Figure9depicls one possible
realizalion of an el1coder/modulalor Wilh d ifferen tia I
Four-Dimensional Trellis-Coded Modulation
J!Go
I Selecl
c
Fig. 9. S;xlun-slfllr t'lIc(}(lrr! d,.nwdulalor lor /our-tiim,.".fiorral
"Z/"-h'IJr Ir,.lIis-oulrd modlllal;m, willr dif/nn'lial ,.,u·odill.f{.
=
'Z" ...
SIGNAL
MAPPING
c: =
=
=
F
C:....
'O: ...
Fi!{. 8.
JIao
S,.t parlilion;n.f{ oI I(mr-dim,.n.úmlfll .f;!{"al s,.ls oI "wic,.
1)'P" ··Z/·. al.m .fh()wi,,~ Ih,. "(fUI oI fi 9(JO mlal;orr.
17
February 1987-Vol. 25. No. 2
IEEE Communicaflons Magazine
,
~
.
.:-/I.~.Z,' ~
0:-7'\,
-7\, l\, -i\, ~.'O".. ~
~-~i'\,
~··7\,
~
.~,._~
i\' i\ i\ i\' i\ ~, i\' ~. . . ~
~'i\
....,"'1
c: c:
Co·
~
<l Co· "'I Co· cl cl cl c:'
~x~ucixc~uc:xc:u~xc!
-
asymptotic coding gain of 5.27 dB ove!: uncoded "Z2 "lype modulation. If co de complexity is increased to 64
stales, theonly nearest neighbors are· those associated
wilh parallel transitions. and their number is 240, whích
is lhe numberof nearest-neighbors in an UEH"lattice. The
"E/'-lype subsets Cdn be funher partitioned into lwo
subsets with 90° symmetries as indicaled in Fig. lO. This
properly can be verified by observing lhe 90° symmelries
among the constituent 4-0 signals as shown in Fig.8.
Hence, 8-0 codes are inherenlly 90° phase invariant,
beca use lheir subsets have lhis property. OiCCerential
encoding/decodingcan be performed entirely within lhe
subsels. decoupled from lhe convolutional encoding
funClion.
Other 8-0 TCM schemes are oblained by choosing lhe
2.1111 + 1 signals from anolher lauice lype lhan "Z"" in lhe
chain of lypes encounlered in Fig. lO, and ·performing
lhe code search for lhe sequence of minimum inlrd-Ser
dislances lhat originales from lhis lype. Codes with
signals from "OEII " or "EH " are of some inleresl [9]-(11),
although il does not seem that lhese codes exhibit
significdnl advantages over lhe "ZII"-type codes, if code
complexities, asymptotic coding gains, and numbers of
nearest neighbors are compared. This is also lrue for 4-0
codes with "D I " signals, as compared tO codes wi lh "z.,"
signals.
cI'
c: <I'
.... ... .r..,
00
A
1\
00
00
A
00
Fig. 10.
·DE..... .r~
·e," ... J8Ao
St'l paTlilion;ng of t';gltl-dimms;onnl signnl .f(!iS of InUiu
typt' "z,t·. nlso slrowing t/,t' t'f1UI 01 n 900 Totnlion.
encoding. The code erom Table IV was firsl made
invarianl to inversion of lhe bit Z:l by interchanging lhe
parity-check coefficient vectors 111 and h:!. Invariance lO
90° rOlalÍons and lhe required differential encoding
follow from the 90° symmetries indicated in Fig. 8, which
in turn are based on lhe 90° symmetries in the. constúuent
2-0 signal subsets. The subsets C~ •... Clt each.composed
of two subsets CiXCk. must be chosen individuaIly for
each value of m. The subset COXCO contains 22m - S
signals, and may be constructed first. The other subsets
CiXCk are then obtained by 90° rotations of the two
constituent subsels CO in COXCO. For-the specific case of
m = 4.5, COXCO contains 8X8 signals, and hence lhe
8-ary subset CO of Fig. 2 can be used. This conslruction of
lhe 4-0 subsets also suggests an efficienl subset-decoding
method that begins with signal decisions within the
conslituent 2-D subsets CO, ... C3. In general, the design
of signal sets can be more complicated. References [3.
Part I] and [11] discuss mapping techniques for cases
where signal-set sizes are not powers of 2.
Discussion
The number of distinct lranSlllons in lhe trellis
diagrams of TCM codes is 211+1il. This so..called "lreIlis
complexilY" represents a measure of code (decoding)
complexilY. A fair comparison of TCM schemes with
different signal dimensionalities requires normalization
of lrellis complexities and numbers of nearest neighbors
to lhe same number of signal dimensions. In the
following", normalizalÍon to lWO dimensions is assumed.
Hence. normalized trellis complexity specifies the number of dislincl trellis transitions lO be dealt with bv lhe
decoder per 2-0 signal or two l-O signals received.
Similarly, a normalized number of nearest neighbors
indicales the number of error evenlS Wilh free distance
lhal could 51art (on average) during lhe same lime
inlerval.
In Fig. 11, asymptolic coding gains of TCM schemes
with large I-O (K = 0.5) tO 8-0 (K = 4) signal sets are
plotted versus normalized trellis complexilY, 2"1"lil/K.
Normalized numbers of nearesl neighbors, Nh,"C./K, are
given in parenlheses. At a norm~tlized lrellis complexilY
of 8. lhe "Z2" -type 4-Slale code is Wilhout compelilion.
The "Z,"-type 16-slate code, whose encoder/modulator
was illustrated in Fig. 9. shows a 0.5 dB advanlage over a
"Z2"-lype 8-statecode. e.g., lhe nonlinear CC ITr code,
and alsoa slightly reduced numberof nearest neighbors.
at lhe same normalized complexily of 32. Next in lhe
order of increasing complexities. lhe "Z2"-type 16-slale
code mav be of inleresl. bUl it cannot be madc invariant
lO 90° rolalions. Al a normalized complexity af 128, i.e.,
four times lhe complexilY of lhe CCITT code. lhe "Z/'and "E/'-lype 64-smle codes are found as attractive 90°
phase-invariant codes. Finally, al a 32 times higher
complexilY lhan lhe CCITT code. lhe "Z," -lype 256-state
code stands out for its élsymplolic coding g'din and low
number of neareSI neighbors.
Eighl-Dimensional Trellis-Coded M odulalion
The technique of set partitioning of a higherdimensional signal set based on lhe known partitioning
of lower-dimensional sels is now applied ta 8-0 signal
sels (K=4) of type "ZH" = "Z., X Z, ". Figure I O iH ustrates
the delails. The sequence of minimum intrd-sel dist«tnces
ao,  1  2 = a 1 = fi  o•  1 ar, = â,; = Â; = .J4 ali,
etc., is oblained, corresponding loa chain of lauice lypes
=
=
"ZK" --- "OM" -- "O., X 0.1" - ·'DE.. " - "EM" - "OK·',etc.,
;~
\
where" EH " denoles the famous Cosset lattice, lhe densesl
lauice known in 8-0 space [12]. (The nomenc1alure
"DE M" was introduced in [91; [11] uses "OJ."·'.)
Codes oblained by lhe code-search program are given
in Table V in the Appendix. The codes use 21111+1 8-0
signals parlilioned into 16 subsels C~, ... cr' of lype .. EH " .
In lhe limil of large sigmll seIs. lhe codes achieve an
February 1987-Vol. 25. No. 2
IEEE Communlcatfons Magazine
18
:~,
.:
Other Recent Work
.~(128)
(132) .:t4)
f6 0
0
344):'
, !r
o
0-----00-----00-----00--(380)
(124)
(60
(764)
5.0
.
i
24
----~o-----........ (23)
.....
(16~•••••··....
C
o
Trellis codes have also been designed for l-O and
2-D signal sets with nonequally-spaced ("asymmetric")
signals [6, Part I], [13]. Some modest coding gains
compared lO schemes with equally-spaced signals.. are
achieved when the codes have few -states and small signal sets. These gains disappear for larger signal sets
and higher code complexity. There are opcn questions
about lhe number of nearest neighbors and sensitivity
to carrier phase offsct when signals are l10nequally
spaC('do
While TCM schemes have been designed for linear
modulmion channels. similar developments look place
in tlu- field 01' conlinuous phase modulation (CPM) for
channe1s requiring conSlanl envelope signals, A summary 011 CPM schemcs is gi,tcn in [HJ.
(4)
.i~72)
(56)0
(72)
CI
CI
~
.
:'
S
'Cú
(44)
::;
Ao .. •• ...... 6· .................. ..:1<.
4.5
(44)
u
(12)
(4)
.~
Õ
Ci 4.0
:.-._- .~~ lK:4
E
0--- ''ZéZ:
>-
11)
4(
3.5
0-
30
1 .
~
6 ......
K02
K:l
'Zi
v - 'Z1
K.0.5
(4)
.
8
16
,
:32
,
64
'
128
,
256
,
512
,
1024
,
2048
t
Conclusion
Trellis complexity per 2-0 signal (2,,·ii'l/Kl
It is probably fair lO stale thal in recenl years the
theory of lrellis-coded modulation has matured 10 the
point where the achievement of further major gains
seem less likely. However. lhere are still open ques(ions concerning real coding gains. performance under
channel impélirments other than Gaussian noise. and
actual implemenlalion complexities.
The 8-state CCITT scheme was established only two
years ago (1984). In lhe meanwhiJe, many manufacturers of voice-band modems and other transmission
equipmenthave adopted lhe 'new combined coding
and modulation technique. At Ieast one manufacturer
has already realized the sophisticated "Z/I'.'-lype 6-1-state
TCM scheme in a commercial product. In the struggIe
toward higher coding gains, application of more complexity is mel with diminishing relurns. For channels
wilh Gaussian noisc. lhe so-called "cul-off rale" Ro'
which is smaller than channel capacity by lhe equivalenl of about 3 dB, has been suggested as a more realistic limit [15]. TCM schemes have reached this barrier.
Fig. J J. A.rymplolic coding gains t'~rsus lr~llis compl~x;ly p(!r 2-D
signnl f21rl'"i! K) lor large 2K-D signal sels 01 lype "Zul' for K
0.5. J. 2, -I: .. E,rt": and" DE..,". Numbers of l1earesl ne;glabors per 2-D.
s;gnal (N fr,.,.,' K) ar,. g;l,,.n in par,.ntheses.
=
The asymptotic coding gain of lhe "DE II " codes
exceeds thatof the "Z/I" and "E/I" codes byO.75 dB, but the
"DE,," codes also have many more neareSl neighbors.
Hence, one may question their usefulness. Similarly, the
"ZI" -type I 28-state code with the highest asymptotic coding gain of 6.28 dB shown in Fig. 11 may not be of practical interest, because of its large number of nearest
neighbors,
'
Figure 11 gives important information about the
ranking of TCM codes. However, the picture also
remains somewhat incomplete. Real coding gains at
given error probabiIities, considering nearest and nextnearest neighbors and the boundary effect of fini te signal
sets, are nOl incIuded. In firsl approximation, one may
use the rule lhat for error rales around 10-:; lhe real
coding gain is reduced by 0.2 dB for every increase in lhe
number of nearest neighbors by the factor of 2. There is
also very liule published information aboul lhe carrierphase sensitivity (a possible advantage of the multidimensional TCM schemes) of lhe TCM schemes under
discussion, The complexity of subset decoding and
decoder-memory requireme'nts are further important
aspecls that need to be considered.
In general, one can make the following observalions.
At low complexity. higher-dimensional TCM schemes
exhibit larger asymptolic coding gains than the lowerdimensional schemes. however. lhese coding gains are
compromised by large numbers of nearest neighbors. In
the mid-range, 4-0 and 8-0 TCM schemes achieve
slightly larger real coding gains than the l-O and 2-D
schemes. Finally. cU high trellis complexities lowerdimensional TCM schemes wiII eventually prevail in
performance. This can be explained by lhe fact that these
schemes have more signal redundancy available for
coding than higher-dimensional TCM schemes. Overall,
the differences in real coding gains are not very large,
that is. they are smaller than 1 dB for the range of complexilies considered.
Acknow ledgments
The author expresses his sincere appreciation for lhe
many helpful comments and suggestions he obtained
from colleagues and reviewers while writing this twopart article. Dr. GoD. Forney deserves spccial thanks for
his many excellent technical comments and many detailed suggestions about the presentation of the materiaL
By sendingearly versions of [9] and [11] to the author, Dr.
L.F. Wei and Dr. DoGo Forney contributed significantly
to thediscussion of multi-dimensional TCM. as present.ed this part of the paper. Dr.- V.M. Eyuboglu helped
generously by verifying the correctness of lhe codes
presented and providing stilI missing numbers of neareSl
neighbors.
Appendix: Code Tables
Tables I-IIl are largely reproduced from [2]. Tables
IV and V have not been published previously; however,
similar codes with up lO 64 states were found by L.F.
Wei [91. In lhe lables, an aSlerisk (.) indicates that free
distance occurs only among parallel transitions, i.eo,
d'u't.(m)
19
_O'
> .:l,il"'"
Februarv 1987-Vol. 25. No. 2
IEEE Communlcallons Magazine
·
Ü
:;. J
\
.
.1.·
COnES F \
-
A
2"
Parity check
coefficients
. -m
4
8
16
32
64
128
256
256
TABLEI
.
PUTV:~ ~On-:.~nON WITH "li" SICNALS,
{~.
No. of .
SI~ltes .
-
O_
1 _
~.
2) -
2Al, 4ÂQ.
Asympt. coding gain [dB]
hl
hO
~Ift/~
2
04
04
10
024
126
362
362
5
13
23
45
103
235
515
515
9.0
10.0
11.0
13.0
14.0
16.0
16.0·
17.0
GU .MI2AM
(m = I)
GsAM/4AM
(m =2)
Gcl"
(m-co)
2.55
3.01
3.42
4.15
4.47
5.05
3.31
3.77
4.18
4.91
5.23
5.81
5.81
3.52
3.97
4.39
5.ll
5.44
6.02
6.02
Nflft
(m-co)
-4
4
8
I~
36
66
2
5.30
TABLE 11
COnES FOR PRASE MODULATION
J2.
8-PSK: {âit O ~ i ~ 2) = 2 sin(7T/8).
2;
16-PSK: {.6 j • O ~ i ~ 3} = 2 sin(7T/16). 2 sin(7T/8).
/
.-
v'2. 2.
Âsympt. coding gaio [dB]
No.of
Slates
Parity-check coefficieots
2'
rii
4
8
16
32
64
128
256
1
2
2
2
2
2
2
4
8
16
32
64
128
256
hO
df~.6!
(m=2)
122
130
2
02
04
16
030'
054
072
5
II
23
45
103
277
435
4.000·
4.586
5.172
5.758
6.343
6.586
7.515
3.01
3.60
4.13
4.59
5.01
5.17
5.75
374.
2
04
04
10
024
024
176
5
13
23
45
103
203
427
1.324
1.476
1.628
1.910
2,000·
2,000·
2.085
04
16
34
066
1
2
GSPSKl4PSK G I6PSKlSPSK
!lI
h.2
(m=3)
Nflft
(m-oo)
1
2
=2.3
-I
~5.3
=0.5
~1.5
3.54
4.01
4.44
5.13
5.33
5.33
5.51
-1
-1
8
8
2
2
~8.0
TABLE lU
COOES FOR Two-DIMENSIONAL MOOULAnON WITH "12" SIGNALS,
{âj. O ~ i ::; 3) = .60.
Asympt. coding gain [dB]
No.of
slates
2'
V2 âo. fi .60. fi .60.
G I6Q,v8PSK
Parity-check coefficients
rii
4
1
8
16
32
64
128
256
512
2
2
2
2
2
2
2
J!2
.h.
.h.
dfrui.6ã
04
16
10
064
042
304
0510
2
02
04
06
016
014
056
0346
5
11
23
41
101
203
401
1001
4.0·
5.0
6.0
6.0
7.0
8.0
8.0
8.0·
1
FebNOry 1987-Vol. 25, No. 2
IEEE Communlcatlons Magazine
0
(m=3) .
4.36
5.33
6.12
6.12
6.79
7.37
7.37
7.37
20
GttCRII6QA
G 64Q,v.!2CR
(m=4)
(m=5)
GC/v
(m-CO)
(m-oo)
2.80
3.77
4.56
4.56
5.23
5.81
5.81
5.81
3.01
3.98
4.77
4.77
5.44
6.02
6.02
6.02
4
16
56
16
56
344
44
4
3.01
3.98
4.77
4.77
5.44
6.02" :
6.02
6.02
N'1ft
_TABLE IV
Coors FOR FQUR-DIMENSIONAL MOOULATlON WITH "Z4" SIGNAU,- {~i. O S i S 5} = Ao • .j2 ~o, V2~
~. J4~. Jã~.
. .J4
No.of
- states-
-
2'
m
8
16
32
64
128
2
2
3
4
..
h4
050
120
.
Parity-check coefficienas
!l'
11%
!lI
nO
dr~~
Asympl. coding
gain (dB]
(m-OO)
30
030
050
04
14
11
014
022
02
02
02
002
006
1I
21
41
4.0
4.0·
4.0·
5.0
6.0
1.52
4.52
4.52
5.48
6.28
101
203
N flft
(m-oo)
88
24
8
144
TABLE V
Coor.s FOR ErGHT-DIMENSIONAL MODULATION WITH "ZR" SIGNALS.
{~i. o S i S 5} ~" .j2 ~" .J2 ~, fi Ao, J4 ~,
Ao.
v.r
=
No.of
states
,1:
Pari ty-check coefficienls
2'
m
16
32
64
128
3
3
4
h"
3
11'
10
10
120
044
044
11%
hl
!lo
dr~~
Asympl. coding
gain [dB]
(m-oo)
04
04
014
014
02
02
002
002
21
41
4.0
4.0
4.0·
4.0·
5.27
5.27
5.27
5.27
101
201
Nfree
(m-oo )
496
240
112
[6] AT8cT Informalion Syslems, liA lrellis coded moduladon
scheme lhat includes diCCeren tia I encod~ng for 9600
bit/sec, full-duplex, lwo-wire modems," CCITr se XVII
Comribution COM XVII. No. D159, August 1983.
[7] IBM Europe, "Trellis-coded moduladon schemes wilh
8-stale syslemalic encoder and 90° symmetry Cor use in data
modems transmilling 3-7 bits per moduladon interval,"
ccrrr SG XVII Contribution COM XVII, No. 0180.
October 1983.
[8] A. R. Calderbankand N. J. A. Sloane. "Four-dimensional
modulation with an eighl-slate trellis code," A TÓ'T Tech.
JOUT., vol. 64. pp. 1005-1017, May-June 1985.
[9] L. F. \Vei, "Trellis-coded modulation with multidimensional conslellations." submitted lO IEEE TTans.
Informalion TheoT)', Aug. 1985.
[10] A. R. Calderbank and N. J. A. Sloane. "An eighldimensionaltrellis code," Proc. of lhe IEEE, vol. 74. pp.
757-759, May 1986.
[11] G. D. Fomey, Jr .• Coset Codes I: Geometryand Classification. Aug. 25. 1986.
[121 N. J. A. Sloane, "The packing of spheres," Scientific
American, vol. 250, pp. 116-125, jan. 1984.
[13] M. K. Simon and D. Divsalar. "Combined trellis coding
with asymmelric MPSK modulalion," JPL Publicatio'J
85-24, Mav I, 1985.
(14] C. E. Sundberg, "Cominuous phase modulation," IEEE
CommunicationsMagazine, \'01.24, no..1. pp. 25-38, April
1986.
[151 J. L. Massey, "Coding and moduladon in digital
communicalions," Proc. 1974 Int. Zurich SeminaT on
Digital Commun;calions, Zurich. Switzerland. pp. E2( 1)(4), March 1974.
[16] V. M. Eyuboglu and G. D. Forney, jr., private communicarions, Sept. 1984 and Sept. 1986.
V.M. Eyuboglu and G.D. Forney [16] discovered typographical errors in the earlier published "ZI" - and
"Z2tt-type 256-state codes [2], which have now been corrected in Tables I and IH.
Some of the 8-PSK codes of Table lI, were improved,
compared to those published in [2], by using the exact
expression for d'nT(m) in lhe code search. The 16-PSK
codes of Table 11 are new.
The exact numbers of nearest neighbors. N 'n'l" given in
the lables were taken from various sources, in particular
[I I] and [17]. The approximate values af Nrrc'l" given for
some codes in Table lI. are average values recently
determined by lhe author.
References
[1] G. Ungerboeck. "Trellis-coded modulalion Wilh redundant signal sets-Partl: Introduction."·IEEE Commrmicalions Magaú'le. vol. 25. no. 2. Feb. 1987.
[2] G. Ungerborck. "Channel coding with multilevel/phasc.·
signals," IEEE Trans. Information Theory, vol. IT-28.
pp. 55-67, Jan. 1982.
[3] G. D. Forney, jr.. "Con\'olulional codes I: Algebraic
slructure," IEEE Tran .... /llformation Theory, vol. IT-16,
pp. 720-738. Nov. 1970.
(4) M. Oerder, "Rotationally in\'ariant lrellis codes for mPSK
modulation," 1985lnlemat. Commun. Conf. RecoTd, pp.
552-556. Chicago, June 23-26, 1985.
(51 IBM Europe. "Trellis-coded modulation schemes for use
in data modems transmilling 3-7 bits per moduléltion
interval," CCITT SG XVII Contriburion COM XVII. No.
DI 1-1, April 1983.
21
February 1987-Vol. 25, No. 2
IEEE Communlcatlons Magazine