Trellis-Coded
`
`Modulation with
`
`Redundant
`Signal Sets,
`Part I: Introduction
`
`
`
`Gottfried Ungerboeck
`
`Simple four-state trellis-coded modulation
`(TCM) schemes improve the robustness of
`digital transmission against additive noise
`by 3 dB without reducing data rate or
`requiring more bandwidth than
`conventional uncoded modulation
`
`schemes. \Mth more complex schemes,
`coding gains up to 6 dB can be achieved.
`This article describes how TCM works
`
`0163—6804/87/0002—0005 $01.00 © 1987 IEEE
`
`
`
`T rellis—Coded Modulation (TCM) has evolved over
`the past decade as a combined coding and
`modulation technique for digital
`transmission over
`band-limited channels. Its main attraction comes from
`the fact that it allows the achievement of significant
`coding gains over conventional uncoded multilevel
`modulation without compromising bandwidth effi-
`ciency. The first TCM schemes were proposed in I976
`[1]. Following a more detailed publication [2] in 1982, an
`explosion of research and actual implementations of
`TCM took place, to the point where lotlay there is a good
`understanding of the theory and capabilities of TCM
`methods. In Part I of this two-part article, an introduc-
`tion into TCM is given. The reasons for the development
`of TCM are reviewed, and examples of simple TCM
`schemes are discussed. Part
`II
`[15] provides further
`insight into code design and performance, and addresses
`recent advances in TCM,
`
`TCM schemes employ redundant nonbinary modula-
`tion in combination with a finite-state encoder which
`governs the selection of modulation signals to generate
`coded signal sequences. In the receiver, the noisy signals
`are decoded by a soft-decision maximum-likelihood
`sequence decoder. Simple four—state TCM schemes can
`improve the robustness of digital transmission against
`additive noise by 3 dB, compared to conventional
`uncoded modulation. With more complex TCM
`schemes, the coding gain can reach 6 dB or more. These
`gains are obtained without bandwidth expansion or
`reduction of the effective information rate as required by
`traditional error-correction schemes. Shannon‘s infor-
`
`mation theory predicted the existence of coded modula—
`tion schemes with these characteristics more than three
`
`decades ago. The development of effective TCM tech—
`niques and today’s signal—processing technology now
`allow these gains to be obtained in practice.
`Signal waveforms representing information sequences
`are most impervious to noise-induced detection errors if
`they are very different from each other. Mathematically,
`this translates into the requirement that signal sequences
`should have large distance in Euclidean signal space.
`The essential new concept of TCM that led to the afore»
`mentioned gains was to use signal—set expansion to
`provide redundancy for coding, and to design coding and
`signal—mapping functions jointly so as to maximize
`directly the “free distance” (minimum Euclidean dis-
`tance) between coded signal sequences. This allowed the
`construction of modulation codes whose free distance
`
`significantly exceeded the minimum distance between
`uncoded modulation signals, at the same information
`rate, bandwidth, and signal power. The term ”trellis" is
`used because'these schemes can be described by a state-
`transition(trellis)diagram similartothetrellisdiagrams
`of binary convolutional codes. The difference is that in
`TCM schemes,
`the trellis branches are labeled with
`redundant nonbinary modulation signals rather than
`with binary code symbols.
`The basic principles of TCM were published in 1982
`[2]. Further descriptions followed in 198-1 [3—6], and
`coincided with a rapid transition of TCM from the re
`search stage to practical use, In 1984, a TCM scheme
`with a coding gain of 4 dB was adopted by the Interna-
`tional 'I‘elegraph and Telephone Consultative Commit-
`
`February 1987—Vol. 25, No. 2
`IEEE Communications Magazine
`
`ERICSSON EXHIBIT 1007
`
`

`

`tee (CCITT) for use in new highspeed voiceband
`modems [5,7,8]. Prior to TCM, uncoded transmission
`at 9.6 kbit/s over voiceband channels was often corr—
`sidered as a practical
`limit for data modems. Since
`1984, data modems have appeared on the market
`which employ TCM along with other improvements in
`equalization, synchronization, and so forth, to transmit
`data reliably over voiceband channels at rates of 14.4
`kbit/s and higher. Similar advances are being achieved
`in transmission over other bandwidth-constrained
`channels. The common use of TCM techniques in such
`applications, as satellite [9-11],
`terrestrial microwave,
`and mobile communications,
`in order
`to increase
`throughput rate or to permit satisfactory operation at
`lower signal-to-noise ratios, can be safely predicted for
`the near future.
`
`Classical Error-Correction Coding
`
`In classical digital communication systems, the func»
`tions of modulation and error-correction coding are
`separated. Modulators and demodulators convert an
`analog waveform channel
`into a discrete channel,
`whereas encoders and decoders correct errors that occur
`on the discrete channel.
`In conventional multilevel (amplitude and/or phase)
`modulation systems, during each modulation interval
`the modulator maps m binary symbols (bits) into one of
`M : 2'“ possible transmit signals, and the demodulator
`recovers the m bits by making an independent Mvary
`nearest—neighbor decision on each signal
`received.
`Figure 1 depicts constellations of real- or complex-
`valued modulation amplitudes, henceforth called signal
`sets, which are commonly employed for one- or two-
`dimensional M-ary linear modulation. Two—dimen-
`sional carrier modulation requires a bandwidth of l/T
`Hz around the carrier frequency to transmit signals at a
`modulation rate of l/T signals/sec (baud) without
`intersymbol
`interference. Hence,
`two«dimensiorral 2'”-
`ary modulation systems can achieve a spectral efficiency
`of about in bit/sec/Hz. (The same spectral efficiency is
`obtained with one-dimensional
`2'“ 2-ary baseband
`modulation.)
`
`Amplitude modulation
`C>'--i---O
`2—AM
`
`
`Amplitude/Phase modulation
`‘
`.
`
`()——-—()-4-<)——-—C
`A—AM
`
`o—o—o—o-t-o—o—o—o
`B—AM
`
`OOOOOOOGOOOOOOOO
`16—AM
`
`Phase modulation
`
`
`
`
`OO00O0OO0OO0
`'O000OO00'0OOOOOOO0OOO
`
`.OO0OOOO0‘
`
`
`-O0OOOOOO'
`
`
`'O0O0OOOO0
`
`
`
`4-PSK
`
`°
`
`°
`
`o
`
`O O
`8—PSK
`
`slz—csoss
`
`64—OASK
`5.
`128-CROSS
`
`Fig. 1. Signal sets for oneedzmensional amplitude modulation,
`and trun-dr'mmr.tional phase and arrtpliludet’phase modulation.
`
`February 1987—Vol. 25, No. 2
`IEEE Communications Magazine
`
`Conventional encoders and decoders for error correc—
`
`tion operate on binary, or more generally Q-ary, code
`symbols transmitted over a discrete channel. With a code
`of rate k/n < l, n — k redundant check symbols are
`appended to every k information symbols. Since the
`decoder receives only discrete code symbols, Hamming
`distance (the number of symbols in which two code
`sequences or blocks differ,
`regardless of how these
`symbols differ) is the appropriate measure of distance for
`decoding and hence for code design. A minimum
`Hamming distance dflw also called ”free Hamming
`distance" in the case of convolutional codes, guarantees
`that the decoder can correct at least [(d,’,‘,,,1 -l)/2] rode-
`syrnbol errors.
`If low signal-to-noise ratios or non-
`stationary signal disturbance limit the performance of
`the modulation system, the ability to correct errors can
`justify the rate loss caused by sending redundant check
`symbols. Similarly,
`long delays
`in error—recovery
`procedures can be a good reason for trading transmission
`rate for forward error-correction capability.
`Generally, there exist two possibilities to compensate
`for the rate loss: increasing the modulation rate if the
`channel permits bandwidth expansion, or enlarging the
`signal set of the modulation system if the channel
`is
`band-limited. The latter necessarily leads to the use of
`nonbinary modulation (M > 2). However, when
`modulation and error-correction coding are performed
`in the classical
`independent manner, disappointing
`results are obtained.
`As an illustration, consider four-phase modulation
`(4—PSK) without coding, and eight-phase modulation
`(8-PSK) used with a binary error-correction code of rate
`2/3. Both systems transmit
`two information bits per
`modulation interval (2 bit/sec/Hz). If the 4-PSK system
`operates at an error rate of If)“, at the same signal-to-
`noise ratio the “raw" error rate at the 8-PSK demodulator
`exceeds 10"2 because of the smaller spacing between the
`8-PSK signals. Patterns of at least three bit errors must be
`corrected to reduce the error late to that of the uncoded
`4-PSK system. A rate—2/3 binary convolutional code with
`constraint length 12 = 6 has the required value of d,',l,,, = 7
`[12]. For decoding, a fairly complex fi4-state binary
`Viterbi decoder is needed. However, after all this effort,
`error performance only breaks even with that of uncoded
`4-PSK.
`
`Two problems contribute to this unsatisfactory
`situation.
`
`Soft-Decision Decoding and Motivation for
`New Code Design
`
`One problem in the coded 8-PSK system just described
`arises from the independent “hard” signal decisions
`made prior to decoding which cause an irreversible loss
`of information in the receiver. The remedy for this
`problem is soft—decision decoding, which means that the
`decoder operates directly on unquantized “soft" output
`samples of the channel. Let the samples be rH 2 a" + wn
`(real- or complex-valued, for one- or two-dimensional
`modulation, respectively), where the a,, are the discrete
`signals sent by the modulator, and the w,. represent
`samples of an additive white Gaussian noise process.
`The decision mile of the optimum sequence decoder is to
`
`

`

`deter mine, among the set C of all coded signal sequences
`which a cascaded encoder and modulator can produce,
`the sequence {5,} with minimum squared Euclidean
`A
`distance (sum of squared errors) from {r,,}, that is, the
`sequence {a.,} which satisfies
`
`Ir,,- a,
`
`'-’= Min 2 Ir..— a.
`{6..16C
`
`2.
`
`The Viterbi algorithm, originally proposed in 1967
`[13] as an “asymptotically optimum" decoding tech-
`nique for convolutional codes, can be used to determine
`the coded signal sequence {5,} closest
`to the received
`unquantized signal sequence {rm} [12,14], provided that
`the generation of coded signal sequences {a.,}eC follows
`the rules 01a finite-state machine. However, the notion
`of “error-correction” is then no longer appropriate, since
`there are no hard-demodulator decisions to be corrected.
`
`likely coded signal
`The decoder determines the most
`sequence directly from the unquantized channel outputs.
`The most probable errors made by the optimum
`soft-decision decoder occur between signals or signal
`sequences {a,,} and {b.,}, one transmitted and the other
`decoded, that are closest together in terms of squared
`Euclidean distance. The minimum squared such dis—
`tance is called the squared “free distancez”
`
`dim, 2 Min 2 [anvbnl
`{ar117é1bnl
`
`;
`
`{an}; {bu} f C-
`
`When optimum sequence decisions are made directly
`in terms of Euclidean distance, a second problem
`becomes apparent. Mapping of code symbols of a code
`optimized for Hamming distance into nonbinary modu-
`lation signals does not guarantee that a good Euclidean
`distance structure is obtained. In fact, generally one
`cannot even find a monotonic relationship between
`Hamming and Euclidean distances, no matter how code
`symbols are mapped.
`For a long time, this has been the main reason for the
`lack of good codes for multilevel modulation. Squared
`Euclidean and Hamming distances are equivalent only
`in the case of binary modulation or four-phase modula-
`tion, which merely corresponds to two orthogonal
`binary modulations of a carrier. In contrast to coded
`multilevel systems, binary modulation systems with
`codes optimized for Hamming distance and soft-decision
`decoding have been well established since the late 19605
`for power-efficient transmission at spectral efficiencies
`of less than 2 bit/sec/Hz.
`
`The motivation of this author for developing TCM
`initially came from work on multilevel systems that
`employ the Viterbi algorithm to improve signal detection
`in the presence of intersymbol interference. This work
`provided him with ample evidence of the importance of
`Euclidean distance between signal sequences. Since
`improvements over the established technique of adaptive
`equalization to eliminate intersymbol interference and
`then making independent signal decisions in most cases
`did not turn out to be very significant, he turned his
`attention to using coding to improve performance. In
`this connection, it was clear to him that codes should be
`designed for maximum tree Euclidean‘glistance rather
`than Hamming distance, and that
`t e redundancy
`
`necessary for coding would have to come from expanding
`the signal set to avoid bandwidth expansion.
`To understand the potential
`improvements to be
`expected by this approach, he computed the channel
`capacity of channels with additive Gaussian noise for the
`case of discrete multilevel modulation at
`the channel
`input and unquantized signal observation at the channel
`output. The results of these calculations [2] allowed
`making two observations:
`firstly,
`that
`in principle
`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 the signal sets used for
`uncoded modulation only by the factor of two. The
`author then concentrated his efforts on finding trellis»
`based signaling schemes that use signal sets of size 2"‘*'
`for transmission of m bits per modulation interval. This
`direction turned out to be succesful and today's TCM
`schemes still follow this approach.
`The next two sections illustrate with two examples
`how TCM schemes work. Whenever distances are
`discussed, Euclidean distances are meant.
`
`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 other 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—state trellis diagram is
`shown in Fig. 2a only to illustrate uncoded 4-PSK from
`the viewpoint of TCM. Every connected path through a
`trellis in Fig. 2 represents an allowed signal sequence. In
`
`
`
`A—PSK signal sat
`
`
`
`Redundant B—PSK slgnul set
`
`
`
`Stale
`sr‘.
`5?.
`0 0
`
`0
`
`1
`
`l
`
`1
`
`0
`
`1
`
`
`
`One-slate trellis
`
`Four—stale trellis
`
`(a)
`
`(b)
`
`Fig. 2.
`
`(a) Unroded four-phase modulation (4»PSK), (b) Four-suite
`trellis-coded eight-phase modulation (8~PSK).
`
`February 1987—Vol. 25, No. 2
`lEEE Communlcatlons Magazlne
`
`

`

`both systems, starting from any state, four transitions can
`occur, as required to encode two information bits per
`modulation interval (2 bit/sec/Hz). For the following
`discussion, the specific encoding of information bits into
`signals is not important.
`The four “parallel” transitions in tlte one-state trellis
`diagram of Fig. 2a for uncoded 4—PSK do not restrict the
`sequences of 4-PSK signals that can be transmitted, that
`is,
`there is no sequence coding. Hence,
`the optimum
`decoder can tnake independent nearest-signal decisions
`for each noisy 4-PSK signal
`received. The smallest
`distance between the 4-PSK signals is fl, denoted as A0.
`We call
`it
`the “free distance" of uncoded 4—PSK
`
`modulation to use comtnon terminology with sequence-
`coded systems. Each 4—PSK signal has two nearest—
`neighbor signals at this distance.
`In the fourstate trellis of Fig. 2b for the coded 8—PSK
`scheme, the transitions occur in pairs of two parallel
`transitions. (A fourestate code with four distinct transiv
`tions from each state to all successor states was also
`
`considered; however, the trellis as shown with parallel
`transitions permitted the achievement of a larger free
`distance.) Fig. 2b shows the numbering of the 8—PSK
`signals and relevant distances between these signals:
`A0 = 2 sin(7r/8), A, = «E, and A. = 2. The 8—PSK sig—
`nals are assigned to the transitions in the four-state
`trellis in accordance with the following rules:
`
`a) Parallel transitions are associated with signals with
`maximum distance A2(8'PSK) = 2 between them,
`the signals in the subsets (0,4), (1,5), (2,6). or (3,7).
`b) Four transitions originating from or merging in
`one state are labeled with signals with at
`least
`distance A,(8—PSK) I fibetween them, that is, the
`signals in the subsets (042,6) or (l,5,3,7).
`c) All 8-PSK signals are used in the trellis diagram
`with equal frequency.
`
`Any two signal paths in the trellis of Fig. 2(b) that
`diverge in one state and remerge in another after more
`than one transition have at
`least sqttared distance
`A}: + A}; + Af = Afi + A}; between them. For example, the
`paths with signals 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,
`AJR-PSK) = 2, which thus is found as the free distance
`in the four—state 8~PSK code: dm, 2 2. Expressed in
`decibels, this amounts to an improvement of 3 dB over
`the minimum distance \/2 between the signals of
`uncoded 4-PSK modulation. For any state transition
`along any coded 8-PSK sequence transmitted,
`there
`exists only one nearest—neighbor signal at free distance,
`which is the 180° rotated version of the transmitted
`
`signal. Hence, the code is invariant to a signal rotation
`by 180°, btrt to no other rotations (cf., Part 11). Figure 3
`illustrates one possible realization of an encoder-modu-
`lator [or the four-state coded BAPSK scheme.
`
`Soft-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 deter—
`mined. These signals are stored together with their
`squared distances frotn the channel output. In the second
`step, the Viterbi algorithm is used to find the signal path
`
`February 19B7—Vol. 25. No. 2
`IEEE Communications Magazine
`
`
`
`through the code trellis with the minimum sum of
`squared distances from the sequence of noisy channel
`outputs receiver]. Only the signals already chosen by
`subset decoding are considered.
`Tutorial descriptions of the Viterbi algorithm can be
`found in several
`textbooks,
`for example,
`[12]. The
`essential points are summarized here as follows: assurrre
`that the optimum signal paths from the infinite past to
`all
`trellis states at
`time n are known;
`the algorithm
`extends these paths iteratively from the statesat time n to
`the states at time n +1 by choosing one best path to each
`new state asa “survivor"and “forgetting" allotherpaths
`that cannot be extended as the best paths to the new
`states; looking backwards in time, the “surviving” paths
`tend to merge into the same “history path” at sortie time
`n — d; with a sufficient decoding delay I) (so that the
`randomly changing value of d is highly likely to be
`smaller than D),
`the information associated with a
`transition on the common history path at time n i D can
`be selected for output.
`Let the received signals be disturbed by uncorrelated
`Gaussian noise samples with variance of in each signal
`dimension. 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 of wrong decisions along some path diverging
`for more than one transition from the correct path, is
`called the error-event probability. At high signal-t0-
`noise ratios, this probability is generally well approxi-
`mated by
`
`137(6)2 NM. - Q[d,,,,/(2o)],
`
`where Q(.) represents the Gaussian error integral
`
`1
`
`th) =E,fexp('yi/2ldy'
`
`°°
`
`.,
`
`and Ni”... denotes the (average) number of nearest-
`neighbor signal sequences with distance d.,,... that diverge
`at any state from a transmitted signal sequence, and
`remerge with it after one or more transitions. The above
`approximate formula expresses the fact
`that at high
`
`DlFFERENTIAL ENCODER
`
`$PSK SIGNAL
`MAPPING
` 00001111
`
`
`00110011
`
`
`
`01010101
`
`
`
`01234567 —-
`4~STATE CONVOLUTIONAL
`Signal No.
`ENCODER
`
`an
`
`Fig. .3.
`
`Illustrates an encoder for [he {our-slate 8-I’SK code,
`
`

`

`
`
`Fig. 5. Nozsv foursmte (oded Y-I’SK signal «1/ romp/m- [)(ltr'fmnd
`with (I .S'I‘L’”(lfrhrntflfl’ mtio (1/ AN“ 2 12.6 dB.
`
`in the receiver of an experimental 64 kbit/s satellite
`modem [9]. At a signal-to-noise ratio of lid/N“ = 12.6 dB
`(13,: signal energy, N“: oneesided spectral noise density),
`the signal is decoded essentially error-free. At the same
`signal-to-noise ratio, the error rate with uncoded 4—PSK
`modulation would be around 10’“.
`In TCM schemes with more trellis states and other
`signal sets. rim. is not necessarily found between parallel
`transitions, and NI,“ will generally be an average number
`larger than one, as will be shown by the second example.
`
`Eight-State Trellis Code for
`Amplitude/Phase Modulation
`
`The eight—state trellis code discussed in this section
`was designed for two-dimensional signal sets whose
`signals are located on a quadratic grid, also known as a
`lattice of type 22". The code can be used with all of the
`signal sets depicted in Fig.
`l
`for amplittide/phase
`modulation. To transmit or information bits per modula—
`tion interval. a signal set with 2‘”+1 signals is needed.
`Hence, for m I 3 the lfi—QASK signal set is used. form I
`4 the 32-CROSS signal set, and soforth. For any at, a
`coding gain of approximately 4 dB is achieved over
`uncoded modulation.
`Figure 6 illustrates a “set partitioning” of the lb?
`QASK and 32—CROSS signal sets into eight subsets. The
`partitioning of larger signal sets is done in the same way.
`The signal set chosen is denoted by AU, and its subsets by
`D0, D1,. .
`. D7.
`If
`the smallest distance among the
`signals in A0 is A“, then among the signals in the union
`of the subsets DO,D4,D2,DG or Dl,l)5,l)3,D7 the mini-
`mum distance is \/§ A“,
`in the unioti of the subsets
`D0,D4; 132,136; D1,l)5; or D3,D7 it is fill“, and within
`the individual subsets it is fiA,. (A conceptually similar
`partitioning of the 8—I‘SK signal set into smaller signal
`sets with increasing intra~set distances was implied in the
`example of coded 8—PSK. The fundamental importance
`
`February 1987—Vol. 25, No. 2
`EH Communications Magazine
`
`signalao-noise ratios the probability of error events
`associated with a distance larger
`then dim. becomes
`negligible.
`For uncoded 4—PSK, we have dim. I fland NW. 2 2,
`and for four»state coded 8—PSK we found d4”... : 2 and NIH,
`: 1. Since in both systems free distance is found between
`parallel transitions, single signal-decision errors are the
`dominating error events. In the special case of these
`simple systems, the numbers of nearest neighbors do not
`depend on which particular signal sequence is trans-
`mitted.
`
`Figure 1 shows the error-event probability of the two
`systems as a
`function of
`signal—to—noise ratio. For
`uncoded 4-PSK, the error—event probability is extremely
`well approximated by the last two equations above. For
`four—state coded 8-PSK, these equations provide a lower
`bound that is asymptotically achieved at high signal‘to-
`noise ratios. Simulation results are included in Fig. 4 for
`the coded 8—I’SK system to illustrate the effect of error
`events with distance larger than free distance, whose
`probability of occurrence is not negligible at low signal—
`to-noise ratios.
`
`Figure 5 illustrates a noisy four-state coded 8-PSK
`signal as observed at complex baseband before sampling
`
`t
`
`‘\
`
`
`
`—i
`
`Uncoded
`4~ PSK
`
`t
`
`i
`l
`t
`t
`I
`|
`|
`|
`I 05
`l
`|
`l
`|
`l
`:
`i
`!(\\
`| Channel
`t capacity
`| of 8-PSK
`
`l -2 bit/sec/Hz
`|
`
`-2
`10
`
`-3
`10
`
`10—4
`
`.3
`g
`n
`9
`O.
`._.
`
`c 0
`
`> 0
`
`’
`L
`L
`o
`‘-
`LU
`
`an...“A
`
`__....n~_a--r_e
`
`
`
`
`
`
`
`
`
`
`4-state
`\
`
`trellis— coded
`\ 8~PSK
`
`‘\‘ (Simulation)
`‘l
`
`‘
`
`
`
`
`
`.
`
`
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`n
`
`12
`
`dB
`
`SNRfESUQ)
`
`Fit
`
`Fig. 4.
`
`Iirrorw'rten/ probability versus .szgnrtl-tomoise ratio for
`Intruder] ‘I-I’SK nml tour-slate coder] X-I’SK.
`
`

`

`Slgnal sets tE-QASK and 32»CROSS
`A0
`
`
`
`---:; -. .toe‘toou~ M—“ZQ'Iatttce
`’COOOOV -
`.moooa.
`‘ooo'ooZ‘fiO
`womo‘
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig. (7.
`
`Sci pttrltlmrulrg of the Ionz-lSK (1nd32»CROSS “grill/sets.
`
`of this partitioning for TCM codes will be explained in
`Part II.)
`four
`In the eight—state trellis depicted in Fig. 7,
`transitions diverge from and merge into each state. To
`each transition, one of
`the subsets DU,
`.
`.
`. D7 is
`assigned. If A0 contains 2‘“ H signals, each of its subsets
`will comprise 2”": signals. This means that the transi-
`tions shown in Fig. 7 in fact represent 2””2 parallel
`transitions in the same sense as there were two parallel
`transitions in the coded 8—PSK scheme. Hence, 2'“ signals
`can be sent from each state, as required to encode m bits
`per modulation interval.
`to transitions
`subsets
`The assignment of signal
`satisfies the same three rules as discussed for coded 8—
`PSK, appropriately adapted to the present situation. The
`four transitions frorn or to the same state are always
`assigned either the subsets D0,I)4,D2,D6 or [)1 ,D5,D3,D7.
`This guarantees a squared signal distance of at least 2A5
`when sequences diverge and when they remerge. If paths
`remerge after two transitions, the squared signal distance
`is at
`least 4A5 between the diverging transitions, and
`hence the total squared distance between such paths will
`be at
`least 6A5.
`If paths remerge after three or more
`transitions, at
`least one intermediate transition con-
`tributes an additional squared signal distance A5,, so the
`squared distance between sequences is at least J? A“.
`Hence, the free distance of this code is fl A“. This is
`smaller than the minimum signal distance within in the
`subsets DO,
`.
`.
`. D7, which is fiAU. I501“ one particular
`code sequence I)()-I)0—D3—I)fi, Fig. 6 illustrates four error
`paths at distance \/3 A“ from that code sequence; all
`starting at the same state and rerner'ging after three or
`four transitions.
`It can be shown that for any code
`
`
`
` // \\‘ — J“
`
`no 02 04 DG\ '—\ \
`\ N\
`_\
`. 000692
`/
`mmosm.
`\
`/\
`02040500
`t-
`,w‘ A
`a ‘ o
`DG 04 02 Do
`'€§{\v‘vl;'<‘k‘
`04 D2 on 06
`Av
`D7 BI 03 05
`- ’Q'.’-
`i, 06 DO D2 04
`Roé-.~‘( \‘wfii. -(
`7
`zfié’vi-Q x1. {49
`D4 05 no 02
`. o‘v ‘& 01 D7 05 D3
`‘5 “
`I’ ‘
`as. m or D7
`‘7' (’A‘Xg- ’/ (VQ‘V D7 01 as 05
`05 03 Dt D7
`9
`' ‘\ ' A‘\
`. D3 05 D7 D1
`
`\ /
`
`,
`
`'
`
`'
`
`Fig. 7. Eight-stale (7(‘ffl,\' code [or (rnrfifltudcfphase modulation
`zurllr “13”»typc signal .relr; (I,W I firm.
`
`February 1987—Vol. 25, No. 2
`IEEE Communications Magazine
`
`10
`
`sequence and from any state along this sequent e, there
`are four such paths. two of length three and two oflength
`four. The most
`likely error events will correspond to
`these error paths, and will result in bursts of decision
`errors of length three or four.
`The coding gains asymptotically achieved at high
`signal—to—noise ratios are calculated in decibels by
`
`G.
`
`,, 3 10 log”; [(df,,.,_,/a’§,,., ,,)/I:‘,,/I;‘,.,,)].
`
`where dim and dim“ are the squared free distances, and
`E,_. and EU, denote the average signal energies of the coded
`and uncoded schemes, respectively. When the signal sets
`have the same minimum signal spacing A“, cl?,,.,.,/
`dim, = 5, and li..,/E..,, 2 2 for all relevant values of m.
`Hence, the coding gain is 10 l()g|tr(5/2) Z 4 dB.
`The number of nearest neighbors depends on the
`sequence ofsignals transmitted, that is N,,,.,. represents an
`average number. This is easy to see for uncoded
`modulation, where signals in the center of a signal set
`have more nearest neighbors than the outer ones. For
`uncoded lfi-QASK, NM. equals 3. For eightvstate coded
`l6-QASK, Ntw is around 3.75. In the limit of large
`“Zfetype signal sets. these values increase toward 4 and
`16
`for uncoded and eight-state coded systems,
`re-
`spectively.
`
`Trellis Codes of Higher Complexity
`
`Heuristic code design and checking of code properties
`by hand, as was done during the early phases of the
`development of TCM schemes, becomes infeasible for
`codes with many trellis states. Optimum codes must then
`be found by cornptiter search, using knowledge of the
`general structure of TCM codes and an efficient method
`to determine free distance. The search technique should
`also include rules to reject codes with improper or
`equivalent distance properties without having to evalu—
`ate free distance.
`
`the principles of TCM code design are
`In Part II,
`outlined, and tables of optimum TCM codes given for
`one-,
`two—, and higher-dimensional signal sets. TCM
`encoder/ modulators are shown to exhibit the following
`general structure: (a) of the m bits to be transmitted per
`em oder/ modulator operation. in E m bits are expanded
`into at + I coded bits by a binary r‘ateArii/(rh-l-l)
`convolutional encoder; (b) the m + l coded bits select one
`of 2'"+l subsets of a redundant 2”"'-ary signal set; (c) the
`remaining rncm bits determine one of 2”""7‘ signals
`within the selected subset.
`
`New Ground Covered by Trellis-Coded
`Modulation
`
`TCM schemes achieve significant coding gains at
`values of spectral efficiency for which efficient coded-
`rnodulation schemes were not previously known, that is,
`above and including 2 l)l[/S(‘C/III.. Figure 8 shows the
`free distances obtained by binary convolutiona] coding
`with 4-PSK modulation for spectral efficiencies smaller
`than 2 bit/sec/Hz, and by TCM schemes with two—
`dirnensional signal sets for spectral efficiencies equal to
`or
`larger
`than 2 bit/sec/Hz. The.
`free distances of
`uncoded modulation at
`the respective spectral effi-
`
`

`

`12 .
`
`‘\
`
`6
`
`3
`
`. 0
`
`,3 7
`
`i 1
`]
`
`‘
`.
`
`’6
`
`
`
`
`16 OASK
`A 128 255
`A 6‘
`\[\‘\
`\ ‘G'PSK A16 32
`CH
`I
`2508
`”SK 1' 6‘ ‘g’; a“ a 7'
`.
`15 AA a
`]
`\\
`j 2
`\\
`]
`7+
`2.
`.7),
`
`\
`
`.
`\\
`
`. 7..
`\\
`
`TRELLISCODED MODULATION
`(4 . 256 states)
`
`.
`
`i
`1
`‘
`’ ' ""’
`
`’ sarcaoss 7”;
`a 123 255
`,
`A an
`1
`misaz
`a a
`A a
`
`"" "
`
`.2
`’ 'i "t '*
`64 QASK
`]
`m 128 256
`16 32
`A 5..
`A
`2
`A B
`A 4
`
`x
`
`\\
`
`\\
`
`”‘1
`.
`2
`mesoss
`
`'
`D ‘
`BPSK
`A . 2.7.,
`UNCODFD MODJLATION
`(1 state]
`
`‘
`..i,.
`[
`1
`
`
`\
`\\
`.._.,.lx
`\
`‘
`‘3 “ \
`tErQASK ‘\
`
`.,
`
`i2BrCROSS
`m 128 256
`A 6‘
`m i532
`]
`“ ‘
`\\
`16-PSK
`
`\
`2
`.
`.2 .
`.
`\\ ]
`u \
`]
`,
`is.
`1
`]
`1
`i
`U‘
`‘
`.
`t
`]
`6470ASK
`1‘
`2‘
`3
`4
`r
`
`l
`‘__r
`.
`T————_—_;
`Spectral effictency [brt/sec/Hz]
`Free (Int/rm e of binary ronziolurzotrrtl codes with {APSK
`.‘x'.
`Hg.
`modulation, and TCM arr/Ii (I Nitric/yof[11107111mem‘rormlmodulm
`Iron schemes, for rpm/ml ('fjlrtencres from 2 3 lo 6 bit
`.ter' 11:.
`
`-12 7.
`
`.
`
`‘
`
`.
`
`ciencies are also depicted. The average signal energy of
`all signal sets is normalized to unity. Free distances are
`expressed in decibels relative to the value dim. : 2 of
`trncoded ~i-PSK modulation. The binary convolutional
`codes of rates 1/3, 1/2, and 3/31 with optimum Hamming
`distances are taken from textbooks, such as, [12]. The
`TCM codes and their properties are found in the code
`tables presented in Part 11 (largely reproduced front [2]).
`All coded systems achieve significant distance gains
`with as few as l, 8, and 16 (ode states. Roughly speaking,
`it is possible to gain 3 dB with >1 states, 4 dB with 8 states,
`nearly 5 (18 with 16 states, and up to 6 (1B with 128 or
`tnore states. The gains obtained with twovstate codes
`usually are very modest. With higher numbers of states,
`the incremental gains betome smaller. Doubling the
`number of states does not always yield a code with larger
`free distance. Generally,
`limited distance growth and
`increasing numbers of nearest neighbors, and neighbors
`with next-larger distances. are the two rnecharrisnts tltat
`prevent real coding gains irom excet’mlingr the ultimate
`limit
`set by channel capacity. This limit can be
`charatteri/ed by the signal-to-uoise ratio at which the
`channel capacity of a modulation system with a 2”“'«ary
`signal set equals tn bit/sec/l-lz [2] (see also Fig. ’1).
`
`Conclusion
`
`'I‘rellis—coded modulation was invented as a method to
`improve the noise irmnunity of digital
`transmission
`systems without bandwidth expansion or redttction of
`data rate. TCM extended the principles of convolutional
`
`BINARY CONVOI lJTIONAl CODES
`WITH 4PSK MOUULAHON
`(4 2 256 states)
`
`I
`
`
`
`,7
`
`.2
`
`]'
`
`.
`
`
`2.
`~—
`
`’
`1
`
`7777*" i7. “*7 ‘ ._
`r
`T
`1
`
`'7 7 "_"""""' ¥ 7
`
`1
`
`
`
`
`
`]r
`R :1/3 ‘
`'
`]
`o 125
`i .7 774 7]» ~ ~ ,7
`03; Rsiiz
`]
`]
`]
`IE
`0 256
`I
`on man I28
`]
`]
`9 i 04
`o 32
`rs
`7] 7+ 777]
`o 15
`R . 3/4
`“‘3
`,1
`“" \\
`o a
`a: ‘23 2‘56] /
`‘3!
`o 4
`©3254 ,’
`N _
`‘\ .2, 2-.
`8 w I’a-PSK
`or
`I a '28
`g
`4‘\\
`l A256 7
`c”
`g
`I xiii
`0‘
`1‘\
`\\
`o
`l A16
`]
`_
`m if“ 1 :2 ,,
`x'
`2795K
`\L
`g)
`{r
`U
`1’
`8
`g
`:i
`g
`1)
`2
`1;,
`B
`i;
`g
`a
`‘1’
`fi
`3))
`i
`
`
`
`coding to nonbinary modulation with signal sets of
`arbitrary size. It allows the achievement of coding gains
`of 3—6 dB at spectral efficiencies equal to or larger than 2
`bit/sec/Hz. These are the values at which one wants to
`
`operate on many band—limited channels. Thus, a gap in
`the theory and practice of channel codirtg has been
`closed.
`
`References
`
`[1] G. lingerboeck and