A Pragmatic Approach to Trellis-Coded
`Modulation
`
`Andrew J. Viterbi
`
`Jack K. Wolf
`Ephraim Zehavi
`Roberto Padovani
`
`IT IS CURRENTLY WIDELY ACCEPTED THAT
`
`Forward Error Correcting (FEC) coding is a practical tech-
`nique for increasing the transmission efficiency of virtually all
`digital communication channels. whatever their power or
`bandwidth limitations. Efficiency then applies to both tlte
`power and the bandwidth required to support a given informa-
`tion rate. or conversely to increase the information rate to be
`transmitted with a given power and bandwidth. This realiza-
`tion ofthe universal merits of FEC‘ coding is relatively recent.
`When practical coding techniques were lirst proposed in the
`late sixties. I it was generally believed that coding would benefit
`only power-limited channels where bandwidth was plentiful.
`Thus.
`the first applications were to space applications for
`which data rates, limited by low on-board transmitter power
`and large range losses. were much smaller than the available
`bandwidth. The first practical codes employed code rates of
`1/2 or even l/3, which equated to less than 1 b/s/l-lz with
`Quadrature Phase Shift Keying (QPSK).
`With the growth of digital
`satellite communication,
`transponder power grew but information rate requirements
`grew even faster, so that bandwidth limitations began to be felt.
`In response. code rates rose from 1/2 to 3/4 and even 7/8. but
`with QPSK modulation. even with code rates approaching l.
`bandwidth efficiency is limited to less than 2 b/s/Hz. Inciden-
`tally. whereas for a given coding Complexity‘ a different code is
`optimum for each rate. a technique known as “puncturing"
`permits the use ofa modified version ofthe basic rate 1/2 code
`for any rate (ii
`I)/ri that is only moderately less efficient than
`the optimum code for that rate. This technique——first em-
`ployed by Linkabit Corporation but first published by Clark.
`
`This work was supported in part under National Science Foundation
`Grant lSI—880l254.
`
`‘Throughout this paper. only convolutionzil and/or trellis codes are
`considered. Whereas some practical block codes have been used in
`communications systems. for any block code ofgiven complexity there
`\ irtually always is a eonvolutional code which exceeds it in perform-
`ance. except for those limited applications where messages are con-
`strained to be very short and code length is thereby limited.
`
`Cain. and Geist [1] for code rates 2/3 and 3/4 and later extend-
`ed to all rates (rt — 1)/n by Yasuda vi a/. [2]
`deletesa fraction
`ofthe symbols generated by the rate l/2 code. but utilizes the
`same decoder as the latter. with the deleted symbols replaced
`by erasures. This represents an earlier example ofthe pragmat-
`ie approach which, as will be further shown here. permits a sin-
`gle basic code to be used for both power-limited and
`bandwidth-limited channels.
`
`With the growth of digital Satellite
`communication, transponder power
`grew but information rate requirements
`grew even faster, so that bandwidth
`limitations began to be felt.
`
`To attain bandwidth efficiencies in excess of 2 b/s/H2. it is
`necessary to couple coding with symbols ofa higher level than
`the four (phase) levels provided by QPSK.3 Thus, if constant
`envelope (amplitude) signals are required (as for operation
`
`3The applications assumed throughout are to radio communication
`where two—dimensional signal constellations apply. Terminology for
`the constellations is more or less standard. Constant amplitude con-
`stellations where M signals are placed at equally spaced phase angles
`are called MPSK . For M : Sand M : I6. .1115 replaced by the specific
`integer. while for M : 2 and M = 4. the more common B (for binary)
`and Q (for quaternary) replaces M. The other commonly used constel-
`lation is the equally spaced grid of points. This is commonly called
`Q.-\M (for quadrature amplitude modulation) or QASK (for
`quadrature amplitude shift keying). The one-dimensional version 01
`equally spaced points on the line is simply called ASK. Graphs ofthese
`various constellations are given in [3]. Later in this paper. we precede
`this nomenclature by M or M3 to indicate the number of signals in-
`volvcd,
`
`0163-6804/89/0007-OOH $01.00 ‘ 1989 IEEE
`
`July 1989 - IEEE Comnitinicatioris l\/lagtizine
`
`'
`
`ll
`
`ERICSSON EXHIBIT 10 l 6
`
`

`
`
`
`k
`Parallel Blts
`
`
`
`Flb/sllnpul line
` Convolutlonal
`
`
`
`
`Encoder
`
`
`
`Rate (k-1)/k
`
`Parallel
`Bits
`
`Carrier
`
`Fig. 1. Generic encoder/modulatorfor zre/[ins-coded modularirm.
`
`over a nonlinear channel), the choice must be Multiple Phase
`Shift Keying (MPSK) with 8, 16, or even more levels. If the
`channels and power amplifier are linear. and non-constant en-
`velope signals are acceptable. multiple constellations in two di-
`mensions may be employed, such as l6, 64, or 256-point
`Quadrature Amplitude Shift Keying (QASK). In both cases,
`optimum trellis codes for a given complexity (constraint length
`or number of states) were found by Ungerboeck [3]. who pro-
`vided the impetus for coding of bandwidth-limited channels
`through a technique called “set partitioning." While he also
`showed that all such codes can be implemented using a binary
`convolutional encoder coupled with appropriate mapping of
`the binary code symbols onto the signal constellation, the re-
`sulting best codes for a given complexity (constraint length)
`were quite different from the classical binary convolutional
`codes used with BPSK and QPSK.
`Since the early seventies [4], for power-limited applications,
`the convolutional code of constraint length K = 7and rate 1/2,
`optimum in the sense ofmaximum free distance and minimum
`number of bit errors caused by remerging paths at the free dis-
`tance, has become the defaclo standard for coded digital com-
`munication. This was reinforced when punctured versions of
`this code also became the standard for rate 3/4 and 7/8 codes
`for moderately bandlimited channels. A major advantage of
`puncturing is that the same decoder can be employed, virtually
`unchanged other than in its branch metric generation, which
`inserts erasures for the punctured symbols.
`The remainder ofthis paper deals with methods for employ-
`ing this very same K = 7, rate l/2 convolutional code with sig-
`nal phase constellations of 8-PSK and 16-PSK and quadrature
`amplitude constellations of l6-QASK, 64-QASK, and 256-
`QASK to achieve, respectively, 2 and 3. and 2, 4, and 6 b/s/Hz
`bandwidth efficiencies while providing power efficiency that
`in most cases is virtually equivalent
`to that of the best
`Ungerboeck codes for constraint length 7 or 64 states. This
`pragmatic approach to all coding applications permits the use
`of a single basic coder and decoder to achieve respectable cod-
`ing (power) gains for bandwidth efficiencies from 1 b/s/Hz to 6
`b/s/Hz. It may well become the universal coding standard.
`
`A Comparative Summary of Ungerboeck
`Code Performance
`In his definitive paper on trellis-coded modulation,
`Ungerboeck [3]
`showed that with the generic encoder-
`modulator of Figure l for any integer number of bits per sec-
`ond pcr Hertz, it was possible to achieve Asymptotic Coding
`Gains (ACGS) ofas much as 6 dB in Eh/N0 within precisely the
`same signal spectral bandwidth. by doubling the signal con-
`
`l2 '
`
`July 1989 - IEEE Communications Magazine
`
`stellation set from M = 2*‘ ’ to M = 2"’ and employing a rate
`(It ~ 1)/It convolutional code. The signal selection or mapping
`process was based on a technique which he called set partition-
`ing. Code scarches were performed to obtain the rate (k — I)/k
`convolutional code with the highest ACG for a given signal
`configuration, of which three types were considered: MPSK,
`Amplitude Shift Keying (ASK) in one dimension, and QASK
`in two dimensions. A number of extensions of this work have
`since appeared in the literature, both to formalize the theory in
`terms of lattices [5] [6] and to find good codes for new signal
`constellations [7—9]. Probably the most significant ofthe latter
`was the extension to two-dimensional or more coding, which
`provided both improvements and more flexibility in accom-
`modating other than integer data-rate-to-bandwidth ratios,
`The major drawbacks of most of this work were that:
`- Each signal configuration seemed to require a different
`code, so that unlike the class of punctured binary codes, no
`single encoder—decoder could be used for a wide set of pa-
`rameters (e.g., 2, 3, and 4 b/s/Hz all with a single decoder).
`- From a practical implementation perspective, the number
`oftrellis code states used in most applications has been very
`low (typically 4 and 8, occasionally 16, but rarely more).
`- Performance was almost always measured by ACG, which
`is just a function of free Euclidean distance. This can give
`misleading results because not only may there be a large
`number of paths at this distance, but also the next higher
`Euclidean distance between unmerged paths may be a very
`small amount larger than the free distance (unlike the case
`for binary Hamming distances. which must be separated by
`integers).
`In this paper, we shall propose a remedy for each of these
`drawbacks. The next section treats the first and second of the
`above points, but first we note that the limitation of the third
`point has been removed by the work of Zehavi and Wolf[l 1],
`which showed that very tight union bounds on Bit Error Rates
`(BER), for all but very low Eb/N0, can be obtained based on the
`classical generating function technique used for binary
`convolutional codes [12]. To achieve this, the authors exploit-
`ed thc symmetry of the signal constellation to show that rela-
`tive distances, rather than all distance pairs, sufficed, as they
`do for binary codes. We have employed this technique to pro-
`duce complete curves of BER as a function of Eb/N0 for five
`classes of signal constellations} which we shall require for
`comparisons in the next section—namcly, the 8-PSK, 16-PSK,
`
`3While we might have also considered codes for QASK configura-
`tions, the pragmatic approach to be presented treats QASK configura-
`tions by pairs ofcodes, one on each ASK dimension.
`
` MPSK or MASK
`
` ""°““'3‘°’
`
`MPSK or MASK
`Coded S mbols
`
`Rsymbols/s
`
`

`
`
`
`Eb/No (dB)
`
`Slates:
`—o—QPSK
`‘H 1 -0- 4
`16
`+32
`
`+ 3
`—A.— 64
`
`Eb/NO (dB)
`
`+2-ASK
`”7"7
`~16
`
`States:
`-0- 4
`+32
`
`+ 3
`fl-64
`
`I-Yg. 2. BER for best Ungerbopck codesfm 8-PSK.
`
`Fig. 4. BER for best Ungerboeck codex/or 4—.~1SK.
`
` 8
`
`12
`
`13
`
`9
`
`10
`
`11
`
`ED/No (dB)
`
`States:
`-0- 4
`+32
`
`+8-PSK
`
`—_1—16
`
`‘
`‘
`
`+ 8
`70:64
`
`—o—4.AsK
`
`43-16
`
`States:
`—<>— 4
`+32
`
`+ 3
`-3- 54
`
`Fig. 3. BER‘/or best Ungerboeck codes./br 16-PSK.
`
`Fig. 5. BERf0r best Ungerboeck vodesjor 8-ASK.
`
`Jul} 1989 - IEEE Communications Magazmc
`
`' 13
`
`

`
`Pb
`1.0E-O2
`
`1.0E-03 ,
`
`.
`
`1.0E-O4
`
`1.0E-05
`
`1.0E-06
`
`1.0E-07
`
`1.0E-O8
`
`
`
`14
`
`15
`
`16
`
`18
`
`19
`
`.
`17
`
`(VLSI) implementations abound [l5—l7] (and which is also
`often convened, through puncturing, into a rate 3/4, 7/8, or
`generally (11 — I)/n code). The pragmatism refers to using the
`“industry standard,” which provides reasonably high coding
`gain, through a moderately high constraint length and a conse-
`quently large number of states, to generate trellis codes for a
`number of MPSK constellations. What remains to be shown is
`the degree of sub-optimality thus introduced relative to the
`best 64-state trellis code for each value of M considered.
`
`Before considering this comparison, we explore the maxi-
`mum ACG achievable with the configuration of Figure 7. The
`trellis form generated by this encoder/modulator is shown for
`M = 4, 8, and 16 in Figures 8a, 8b, and Sc (vector X varies over
`all 32 5-dimensionalvectors). ForM = 4 (Figure 8a), of course,
`it is the conventional trellis ofa binary convolutional code with
`64 states connected such that each state has two inputs and two
`outputs, each from two disjoint preceding and to two disjoint
`succeeding states. The trellis for M = 8 (Figure 8b) has twice as
`many branches, with basically the same connectivity but with
`all branches paired, since the input bit, which does not enter
`the rate l/2 encoder (Figure 7—based on single rate l/2
`convolutional code: G/D) = 1+ D2+ D3+ D“+ D5, G2(D) =
`1 + D + D2 + D3 + D5), produces two branches with identical
`connectivity, so that all branches of Figure 8a now become
`branch pairs with branch metrics identical except for opposite
`signs (i.e., the corresponding signal points are antipodal). Simi-
`larly, for M = 16 (Figure 8c), all pairs of states connected in
`Figure 8a by a single branch are now connected by four branch-
`es, each corresponding to one of four values of the two inputs,
`which do not enter the encoder. The squared Euclidean
`distance between nearest neighbors among these four “bun-
`dled” branches is proportional to sin2 (rt/4). Similarly, for any
`M = 2", for which the modulator of Figure 7 is modified only
`by having k — 2 uncoded input bits, the bundle size increases
`to M/4 : 2k‘ 2 branches, which correspond to neighboring sig-
`nal points separated by squared Euclidean distance propor-
`tional to sin2(47r/M). Now the ACG is defined, in the limit of
`asymptotically low error rates, to be the bit energy-to-noise Eb/
`No required for coded operation with M : 2* signal points rel-
`ativc to that required for uncoded operation with M/2 : 2*‘ 1
`signal points (note that both cases provide the same informa-
`tion throughput, k — 1 b/s/Hz). Bit errors can occur only be-
`cause of an incorrect choice of path at any state. For M = 4, all
`pairs of paths are disjoint over at least one constraint length
`(K = 7) branches, but for M 2 8, minimum length disjoint
`paths are only one branch long, because of the bundling of
`paths. Hence, the minimum Euclidean distance for an error
`event can be no greater than the single branch errors (although,
`under some circumstances,
`the 7-branch unmerged error
`events can accumulate less distance than the single branch
`error event—see the Appendix). Hence, while for an uncoded
`operation with M/2 signals, the BER PM is bounded by:
`
`Q i/(ZES/N0)sin2(2/t/M) < Pb“
`
`(1)
`
`< 2Q V(2ES/NO) sin2(2rt/M)
`the coded BER Pbc with an M-signal constellation is lower
`bounded by considering only the minimum Euclidean distance
`among the bundled branches,
`
`Pbc > KQ V(2ES/NO)sin2 (41;/M)
`
`(2)
`
`+3-A5K
`
`-13- 16
`
`Eb/No (dB)
`
`States:
`-0- 4
`+ 32
`
`—I— 3
`—A- 64
`
`Fig. 6. BER for best Ungerbaeck codes for 16—ASK.
`
`and 4-ASK, 8-ASK, and l6-ASK configurations. These are
`given in Figures 2 through 6. In addition, Tables I and II give
`the ACG associated with each code. In each case, performance
`of the best binary convolutional code found by Ungerboeck [3]
`and others [13] is given and all possible code state values be-
`tween 4 and 64 are included.
`It is worth noting, from Figures 2 through 6 and Tables I
`and II, that ACG can often be optimistically misleading. For
`example, while the 64-state code for 8-PSK provides an ACG
`over QPSK of 5.0 dB, the coding gain at a BER of 10” 5 is only
`3.6 dB; worse still, for 16-PSK, the corresponding difference is
`1.8 dB.
`
`The Pragmatic View for MPSK: A Sin le
`Coder-Decoder for All Values ofM = 2
`
`Figure 7 illustrates the pragmatic coded modulation system
`for M = 4, 8, and I6. Generalization to the kth power of 2 is
`immediate; k H 1 bits are input, with only the lowest order bit
`going to the binary convolutional encoder, while the remaining
`k — 2 bits select one of 2"‘ 2 sectors. The two bits output by the
`convolutional encoder select one of four phases according to
`the following Gray code:
`
`00
`01
`1 1
`10
`
`—>
`—>
`—-
`—>
`
`0 rad.
`7r/2*" rad.
`27:/2k‘ I rad.
`37:/2"” rad.
`
`the sector
`The remaining (uncoded) k — 2 bits select
`lexicographically (i.e., the binary vector whose decimal equiva-
`lent isj (0 S j 5 2"” — 1) selects the (j + 1)st sector).4
`The code chosen is the optimum rate 1/2, 64-state, binary
`convolutional code for which Very Large Scale Integration
`
`4This mapping was first used by Clark and Cain [14] and also in [18]
`to demonstrate that the 4-state rate l/2 code can achieve a 3 dB ACG as
`discussed below.
`
`where, as we Shall Show, K may be less than unity. Asymptoti-
`cally, only the argument of the error function Q comes into
`P1aY- HCHCC, in terms of decibels, the ACG is:
`
`14 '
`
`July 1989 - IEEE Communications Magazine
`
`

`
`Select
`Quadrant
`\
`
`3‘
`
`select
`Half-Plane
`
`input
`Information Bits
`
`Generalized M-ary PSK
`Modulator
`_m___.__..._..__j
`
`0101
`01110 O
`
`0100
`
`15-PSK
`Modulator
`
`0010
`0 O 001,
`o 0001
`0000
`O 1110
`O 1111
`
`
`
`
`
`3''’3K
`Modulator
`
`
`
`M-ary PSK
`Channel
`Symbol
`
`
`Output
`Selector
`
`4-PSK
`Modulator
`
`
`
`011
`
`0 001
`
`00°
`
`O 110
`
`O 00
`
`111
`
`n1
`
`Fig. 7. Pragmatic encoder/modulator for QPSK, 8—PSK, and I6PSK.
`
`10
`
`. 2
`sin (411/M)
`Acaslologlolfil
`Sm 262”/M)
`M28
`:10l()g10l4 COS
`It is shown in the Appendix that the true ACG is lower
`bounded by the minimum of Equation (3) and a term that de-
`pends on an unmergecl path which is at least one constraint
`length long; more precisely,
`
`(3)
`
`3
`I
`2/1
`ACG ‘=10log‘m(4 Minlcos2(—l - + -—-jl)
`M 2
`2 1
`8 cos (M)
`
`M 28
`
`(4)
`
`with equality if the minimum is achieved by the first term.
`
`Thus, for M = 8 and I6, the bound given by Equation (3)
`becomes an equality, and for these cases:
`
`ACG : 3.0dl3,
`ACG : 5.3 dB,
`
`M28
`M216
`
`(5)
`
`Table I summarizes these results and compares them with
`the ACG values for the best Ungerboeck codes ofthe previous
`section. It also provides Coding Gains (CGs) at BER values of
`10 ‘ 5. Note the apparent anomaly for M = 8, for which the CG
`at IOT5 is 3.2 dB, while the ACG for this code is only 3.0 dB.
`This can be explained as follows: The BER for this code is
`upper bounded by;
`
`1
`_ Tm.
`Pb<2Q(
`terms due to errors over
`unmergedpat/ls
`
`In ulti — bra nch
`
`Table |- Trellis-Coded MP5KPe”0"'"3"C9 ((13)
`Modulation
`b/s/Hz
`ACG
`CG at ~10'5
`
`
`
`7-0
`1
`4'PSK
`3.0‘
`2
`8—PSK
`5.3
`3
`16—PSK
`‘ Best Ungerboeck 64—state code (rate 2/3)
`provides ACG = 5.0 dB.
`" Best Ungerboeck 64—state code (rate 2/3)
`provides CG al ~ 10 ’5= 3.6 dB.
`
`5-3
`3.2“
`3.5
`
`Table II. Trellis-Coded QASK Performance (dB)
`
`Modumion
`4.AsK —) 16.QA$K
`3.AsK _) 64-QA3K
`16-ASK-9 256-QASK
`
`b‘/9/Hz ACG
`2
`4,5
`4
`52
`6
`5.4
`
`
`
`CG at “ 10'5
`
`'Ungerboeck codes slightly less (see Figure 10)
`
`July 1989 — IEEE Communications Magazine
`
`° 15
`
`

`
`Figure 9 compares the best M = 8 and M = 16, 64-state
`codes as found by Ungerboeck with those generated by the
`pragmatic encoder of Figure 7. Our conclusion is that, for al-
`most all purposes, the two sets of performance are equivalent,
`but the implementation of the latter is far simpler and more
`flexible.
`One more observation is important regarding MPSK modu-
`lation. In any phase modulation system, a stable phase refer-
`ence is required for coherent demodulation at the receiver. In
`particular, in a PSK system with M signals, phase ambiguities
`of the form 27:/M, 47¢’/.M, .. ., (M — I)(27t/M) must be resolved. A
`method was found for resolving all phase ambiguities for our
`pragmatic approach to coding. This method is such that all in-
`teger multiples of 47:/M phase shifts are resolved using a fon-n
`of differential encoding/decoding, while the remaining ambi-
`guities are resolved by monitoring the growth of the state
`metrics in the convolutional decoder. The details of this
`scheme are beyond the scope of this paper.
`
`The Pragmatic Approach for Linear
`MASK and M2-QASK Modulation
`
`The simplest extension of the above technique to linear
`channels and power amplifiers is to use the classical two-
`dimensional square grid of equally spaced points, and to code
`each dimension separately. Viewed as one-dimensional modu-
`lation,'this produces the same performance as the best
`Ungerboeck codes for MASK. Surprisingly, even compared to
`the more elaborate two-dimensional Ungerboeck codes, per-
`formance is roughly similar (as is also suggested in [13]).
`The approach for MASK is to stretch the circular mapping
`into a mapping on the real line. The modulator is similar to
`that of Figure 7, but now the k — 2 uncoded symbols select one
`of 2"”2 = M/4 line segments of length A, numbered
`lexicographically (i.e., from 0...O to l...l) from left to right
`spanning a range of length M/4 A centered about the origin.
`The two coded bits select one of 4 points within this segment,
`equally spaced at distance A/4 with O0, 01, l 1, 10 selecting the
`first, second, third, and fourth points, respectively, from left to
`right. This results in M points equally spaced at 41/4 extending
`from —(M/2 — 1) AM — 4/8 to + (M/2 — I) AM + A/8. All
`distances are finally scaled according to the average energy to
`be transmitted.
`'
`This mapping is the same as that for MPSK on the unit cir-
`cle, with a conformal mapping of the circle onto the line seg-
`ment of length A/4 (it is also that proposed by Clark and Cain
`[14]). Hence,
`the minimum separation between bundled
`branches is A. For comparison with the uncoded case, use
`M/2 = 2*‘ 1 points, equally spaced at distance A ’. If the aver-
`age symbol energies for the coded and uncoded cases are made
`equal by normalizing both to unity, then, as shown in the Ap-
`pendix,
`
`2 M2—1
`1=(A/4)(
`
`2 (M/2)2—1
`)=<A')1T1
`
`whence
`
`48
`.
`192
`42: T (5)3: ._T.
`(M -1)
`(M -4)
`
`Consequently, based only on the single branch errors, the
`ACG is upper bounded by:
`
`A2
`ACG S10l0gwI(£T)2I=101ogwl4-
`
`M2—4
`2
`M -1
`
`|
`
`(6)
`
`(b) 8-PSK
`
`(c) 16-PSK
`
`Fig. 8. Trellis structure for pragmatic encoder/modulator.
`
`The first term is the BPSK bit error probability, with energy
`doubled since two bits are sent per symbol, and multiplied by a
`factor of 1/2 because only half the input bits are involved in
`such potential (single branch) decision errors. The second term
`is negligible for M = 8, as shown in the Appendix and Equa-
`tion (4). Hence, the CG over QPSK is 3 dB plus the effect of
`the multiplication factor of 1/2. At values of E,,/NO for which
`Pb = 10' 5, the effect ofthe latter is an additional 0.2 dB, while
`as Pb approaches 0, the effect disappears; hence the ACG is
`only 3.0 dB.
`On the other hand, we note from Table I that for the corre-
`sponding Ungerboeck code for M = 8 and 64-states, ACG =
`5.0 dB while at Pb = 10‘ 5, CG = 3.6 dB, a difference of only
`0.4 dB relative to the pragmatic code. Note also, from Table I
`and Figure 3, that for the M = 16, 64-state code, ACG and CG
`are the same for both the Ungerboeck code and the pragmatic
`code. The explanation of this equality (see also the compan-
`sons shown in Figure 9) for M = 16, as contrasted to the differ-
`ence at M = 8, is that the optimal 64-state code at M = 16 is
`one for which the underlying binary convolutional code uses
`rate 1/2 and the pragmatic code performs essentially as well as
`that selected in Ungerboecl(’s search [3]. At M = 8, on the
`other hand, the best underlying 64-state binary convolutional
`code uses rate 2/ 3; thus, each state has four distinct input
`branches and four distinct output branches with no bundling.
`By limiting the pragmatic code to using a rate 1/2 binary
`convolutional code, sub-optimality is thus introduced.
`
`16 I
`
`July l989 - IEEE Communications Magazine
`
`

`
`1 .E-02 >
`
`1.E-03
`
`1.E-04
`
`1.E-05
`
`1.E-06
`
`....W
`
`1.E-O7 1.E-I18
`
`4.0
`
`5.0
`
`6.0
`
`7.0
`
`'9.o
`
`10.0
`
`11.0
`
`.
`12.0
`
`3.0
`E,/N, (dB)
`ri 8-PSK
`-0- opsx (Uneoded)
`-0- opsx (n=1/2)
`Ungerboeek
`
`—l}16-PsK
`-if 8-PSK Pragmatic —A—16-PSK Pragmatic
`
`Ungerboeck
`
`
`Fig. 9. BER vs. Eb/No for the pragmatic coder/modulator (PSK
`modulation).
`
`which approaches 6 dB asM becomes large. Note the similarity
`between Equations (6) and (3) for large M. Including the effect
`of multi-branch unmerged paths, it is shown in the Appendix
`that for the K = 7 rate 1/2 code
`
`Act:
`V12
`
`101
`
`14 M24 7)
`0% ,
`2
`,_
`M—1
`8
`
`4.5dB,
`
`M24
`
`25.2dB,
`
`M28
`
`(7)
`
`M216
`5.-1dB,
`Again for large M, Equations (7) and (4) approach the same
`limit. The cases of 4-ASK, 8-ASK, and 16-ASK are shown in
`Figure 10 and compared with the 64-state Ungerboeck code in
`each case. Performance is almost identical. CGs are summa-
`rized in Table II.
`It is also shown in the Appendix that, if the free Hamming
`distance ofthe rate 1/2 binary fionvolutional code d,2 12, then
`Equation (6) is satisfied as an equality and ACG =’ 6 dB. This,
`however. requires K 2 9 or 256 states [14]. From the practical
`viewpoint of CG at small, but not vanishing, Pb (such as 10” 5),
`the advantage of the higher constraint length and higher free
`Euclidean distance may be lost because of the large number of
`unmerged paths at that distance.
`For efficient use of bandwidth, both dimensions (1 and Q)
`must be coded, each with its own MASK coded modulation, re-
`sulting in a coded M2-QASK constellation conveying 2{k — 1)
`b/symbol. All the above comparisons still hold, although CG is
`relative to an uncoded constellation conveying the same num-
`ber of bits, but with one-quarter rather than one-half as many
`points. One consequence of the larger signal set size is the num-
`ber of quantization bits to be provided in the branch metrics.
`This is compounded by the fact that unlike the situation for
`MPSK codes, the unmerged path at the free distance is a multi-
`branch path and consequently the most probable error event is
`more sensitive to metric quantization. Also, two decoders are
`
`required for QASK, one for each dimension, if the two dimen-
`sions are coded independently. On the other hand, a single
`encoder-decoder suffices if the encoder modulator alternates
`between selecting the l and Q dimensions on each alternate set
`of k — 1 input bits.
`
`Conclusions
`
`We have shown that with a very simple signal mapping, it is
`possible to utilize existing good binary convolutional encoder-
`decoders to implement trellis—coded modulators with perforin-
`ance gains (in required received energy-to-noise ratios) greater
`than 3 dB and in some cases approaching 6 dB, for moderately
`to highly bandlimited channels. The principal advantage of
`this approach is that a single rate 1/2 encoder-decoder, with
`only moderate modifications to handle parallel branch decod-
`ing, can provide this performance for a wide variety of trellis
`codes. Above all, considerable experience in VLSI implemen-
`tation of this decoder type on a single integrated circuit [15-
`17] gives confidence that this relatively new set of applications
`is no more difficult to implement than the widely accepted ap-
`plications that utilize binary convolutional codes.
`
`Appendix
`
`Bounds on Free Euclidean Distance and A CGfor
`Trellis- Coded Modulation Employing Rate 1/2
`Code
`MPSK Modulation
`
`As established by Equation (2), the squared Euclidean dis-
`tance between nearest neighbors among bundled branches is
`proportional to sin2 (47:/M). This establishes the one-branch
`unmerged Euclidean distance. For the Euclidean distance be-
`tween multi-branch unmerged paths, we start by noting that
`for any rate 1/2 binary convolutional code that, for the given
`constraint length, achieves maximum free Hamming dis-
`tance, df, the first and last unmerged branch pairs differ in
`both symbols. Because of the mapping used, this guarantees
`that those two branches will each contribute squared Euclide-
`an distance proportional to sin2 (21:/2") = sin? (Zn/M), for
`M 2 8. The remaining branches in the unmerged path there-
`fore differ in df — 4 binary symbols. At worst, each pair of
`non-identical branches differ in just one symbol. Then there
`are at most d — 4 branches each contributing the minimum
`Normalized quared Euclidean Distance (NSED) of the map-
`ping, sin? (Ir/M). Consequently, the Euclidean distance for
`unmerged paths of length greater than one branch is lower
`bounded by:
`
`NSED>2~'22n
`=21
`_ sir1(—)+(d -4)-.~.ui(
`M
`M
`f
`M24
`
`)
`
`For the best K = 7, rate 1/2 code, df = I 0. Combining the sin-
`gle branch minimum Euclidean distance with this lower bound
`yields:
`
`FreeNSED 2 Minisiiflfli 2 sin2(a£) + 6 singtln
`M
`M
`M
`
`M28
`
`Taking the ratio of this to the normalized Euclidean distance
`for uncoded performance sin2 (27:/M), as given in Equation ( l ),
`and taking ten times the logarithm to convert to ACG, results
`in:
`
`July 1989 - IEEE Communications Magazine
`
`' 17
`
`

`
`b
`1.0E-03
`
`1.0E-04
`
`1.0E-05
`
`1.0E-O6
`
`1.0E-O7
`
`1.0E-O8
`
`1.0E-09
`
`1.0E-10
`
`OI
`
`,
`
`4-ASK
`
`-
`
`‘
`
`-0- Ungerboeck codes
`
`-0- Pragmatic codes
`
`Fig. 10. BER vs. Eb/N0 for the pragmatic coder/modulator (ASK
`modulation).
`
`1~
`ACG>
`._10 og1U(4
`
`Min
`
`I
`3‘-2-'3
`[cos(M) E
`
`M 2 8
`
`3
`+ --ml)n
`8c0s2(“lM
`
`with equality if the minimum is achieved by the first term.
`MASK Modulation
`
`The mapping for MASK is the same as for MPSK except
`that it is on the line rather than the circle. Letting the minimum
`Euclidean distance between equally spaced points be A/4, the
`minimum NSED between bundled branches is A2 while that
`between multi-branch unmerged paths is:
`
`NSEI) > 2<A )2 + (d
`‘
`2
`
`f
`
`4)(A >2
`4
`
`If for the uncoded M/2 point linear constellation the minimum
`normalized squared distance is A ’, it follows, from the previous
`argument, that
`
`ACG2]()logm{
`
`Min[A2,A2/2 + id’, _ 4)A2/16']
`(A')”
`
`}
`
`with equality if the minimum in the numerator is A24
`
`To complete the argument, it is necessary to nonnalize A
`and A’ to yield equal average energies. For the coded case,
`there are M : 2" points equally spaced at A/4 and hence with
`values i (A/8 + jA/4), j = 0,...M/2— I; consequently,
`
`18 *
`
`July 1989 — IEEE Communications Magazine
`
`8-ASK
`
`16-ASK——
`
`11
`
`13
`
`15
`
`17
`
`b/No (dB)
`
`Coded A uerage Normalized Energy =
`2 A2M/:2:1I
`_) A‘ Mg_I
`— —
`\,
`(-+ r:(—)’(
`M.(4).J.‘:0 2
`4
`'12
`J
`Similarly, for the uncoded case ofM/2 points spaced A 'apart,
`
`2 (M/2)2—1
`12
`
`Uncoded A uerage Normalized Energy : (A')
`
`Normalizing both energies to unity results in
`2
`192
`' 2
`48
`(A )
`
`A2:
`
`M2- 1
`and consequently,5
`
`M2—4
`
`ACGZ10log{(
`
`M2_4
`M2—1
`
`)oMinl4,2+
`
`df—4
`
`J}
`
`with equality if 4 S 2 + (d,- — 4)/4, or d,- 2 12. But for the
`K = 7 (64-state) code, df =' 10, for which
`
`/142-4
`/\CGZ10l0gl4o ‘
`MC:
`
`7
`0-]
`8
`
`M24
`4.5,
`252, M28
`54,
`M216
`
`5Except for normalization, this same formula was derived by Clark
`and Cain [14].
`
`

`
`Note the similarity to the corresponding result for MPSK.
`
`
`2]
`
`3
`4
`
`5
`
`6
`
`7
`
`[8
`
`References
`1]
`J. B. Cain, G. C. Clark, Jr., and J. M. Geist, ”Punctured Convolutional
`Codes of Rate In-1)/n and Simplified Maximum Likelihood Decoding,”
`IEEE Trans. info. Theory, vol. IT-25, pp. 97-100, Jan. 1979.
`Y. Yasuda, K. Kashusi, and Y. Hirata,
`“High-Rate Punctured
`Convolutional Codes for Soft Decision Viterbi Decoding," IEEE Trans.
`on Commun., vol. COM-32, pp. 315-319, Mar. 1984.
`G. Ungerboeck, "Channel Coding with Multilevel/Phase Signals,‘ IEEE
`Trans. on info. Theory, vol. IT-28, pp. 55-67, Jan. 1982.
`J. A. Heller and I. M. Jacobs, ‘Viterbi Decoding for Satellite and Space
`Communication,“ IEEE Trans. on Comm. Tech, vol. COM—19, pp. 835-
`848, Oct. 1971.
`G. D. Forney, Jr., R. G. Gallager, G. R. Lang, F. M. Longstaff. and S. U.
`Oureshi, "Efficient Modulation for Band-Limited Channels," IEEE Trans.
`on Se/ectedllreasin Comm.,vo|. SAC—2, pp. 632-647. Sept. 1984.
`A. R Calderbank and N. J. A. Sloane, ‘New Trellis Codes Based on
`Lattices and Cosets,' IEEE Trans. on Inlo. Theory, vol. IT-33. pp. 177-
`195, Mar 1987.
`‘A New Description of Trellis
`A. R Calderbank and J. E. Mazo,
`Codes,“ IEEE Trans. on Info Theory, vol. IT-30, pp. 784-791, Nov.
`1984.
`L. F. Wei, “Tre|Iis—Coded Modulation with Multidimensional Constella-
`tions," IEEE Trans. on/n/o Theory, vol. IT-33, pp. 483-501 , July 1987.
`[9] A. R. Calderbank and N. J. A. Sloane, “An Eight-Dimensional Trellis
`Code," IEEE Proceedings, vol. 74, pp. 757-759, May 1986.
`10
`S. G. Wilson, H. A. Sleeper, P. J. Schottler, and M. T. Lyons, "Rate 3/4
`Convolutional Coding of 16-PSK: Code Design and Performance
`Study," IEEE Trans. on Commun., vol. COM-32, Dec. 1984.
`E. Zehavi and J. K. Wolf. “On the Error Performance of Trellis Codes,”
`IEEE Trans. on Info. Theory, vol. IT~33, pp.196—202, Mar. 1987.
`A. J. Viterbi and J. K. Omura. Principles of Digital Communication and
`Coding, NY: McGraw-Hill, 1979.
`G. Ungerboeck. ‘Trellis-Coded Modulation with Redundant Signal
`Sets,” Pts. land II, IEEE Communication Mag., vol. 25, pp. 5-21, Feb.
`1987.
`G. C Clark, Jr. and J. B. Cain, Error-Correction Coding for Digital Cam-
`munications, Plenum-Press, 1981
`"OUALCOMM Announces Single-Chip K = 7 Viterbi Decoder Device."
`IEEE Communication Mag, vol. 25, pp. 75-78, Apr. 1987.
`T.
`lshitani et al. "A Scarce-State-Transition Viterbi-Decoder for Bit
`Error Correction,” IEEE Journal of So/id-State Circuits, vol. SC-22.
`pp.575—581,Aug. 1987.
`H. Suzuki, M. Tajima, and M. Shinaja, “Viterbi Decoder Chip Imple-
`mented with Sub-Parallel Architecture.” IEEE Int]. Symposium on Info.
`Theory, Kobe Japan, June 1988.
`J. Hagenauer and C. E. Sundberg, "On the Performance Evaluation of
`TrelIis—Coded 8-PSK Systems with Carrier Phase Offset," Archiv Fuer
`Ere/rtronik Und Uebertragungstecknick, Band 42, Heft 5, pp. 274-284,
`1988.
`
`
`[11
`12
`
`13
`
`[14
`
`15]
`
`16]
`
`17]
`
`18]
`
`Biography
`Andrew J. Viterbi, on July 1, 1985, became a founder and Vice Chairman
`and Chief Technical Officer of QUALCOMM. lnc.. a company concentrating on
`mobile satellite communications