IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-28, NO. 1, JANUARY 1982
`
`55
`
`10)
`
`14]
`
`15]
`
`J. M. Wozencraft and I. M. Jacobs, Principles of Communication
`Engineering. New York: Wiley, 1965.
`11] W. P. Osborne and M. B. Luntz “Coherent and Noncoherent
`detection of CPFSK,” JEEE Trans: Commun., vol. COM-22, pp.
`1023-1036, Aug. 1974,
`12] R. de Buda, “About optimal properties of fast frequency-shift
`keying,” JEEE Trans. Commun., vol. COM-22, pp. 1974-1975, Oct.
`1974.
`13) T. A. Schonhoff, “Symbol error probabilities for M-ary CPFSK:
`coherent and noncoherent detection,” /EEE Trans. Commun., vol.
`COM-24, no. 6, pp. 644-652, June 1976.
`T. Aulin, N. Rydbeck, and C. E. Sundberg, “Performance of
`constant envelope M-ary digital FM systems and their implementa-
`tion,” in Conf. Rec. Nat. Telecommun. Conf., Washington, DC, Nov.
`1979, pp. 55.1.1-55.1.6.
`T. Aulin, N. Rydbeck, and C. E. Sundberg, “Transmitter and
`receiver structures for M-ary partial response FM,” in Proc. 1980
`Int. Zitirich Seminar on Digital Commun., Mar. 1980, pp. A.2.1-A.2.6.
`T. Aulin, “Viterbi detection of continuous phase modulatedsignals,”
`in Conf. Rec. Nat. Telecommun. Conf., Houston, TX, Nov. 1980,pp.
`14.2.1-14.2.7.
`T. Aulin and C. E. Sundberg, “Minimum Euclidean distance and
`power spectrum for a class of smoothed phase modulation codes
`with constant envelope,” University of Lund, Nov. 1980 (submitted
`to IEEE Trans. Commun.).
`IM, and C. D. Hsu, “Error boundsfor
`S. G. Wilson, J. H. Highfill
`multi-h phase codes,” University of Virginia, Charlottesville (sub-
`mitted to IEEE Trans. Inform. Theory).
`J. K. Omura and D, Jackson, “Cutoff rates for channels using
`bandwidth efficient modulations,” in Conf. Rec. Nat. Telecommun.
`Conf., Houston, TX, Nov. 1980, pp. 14.1.1-14.L.11.
`T. Aulin, N. Rydbeck, and C. E. Sundberg,“Minimum distance and
`spectrum for M-ary multi-f constant envelope digital FM signals,”
`Tech. Rep. TR-129, May 1979, Telecommun. Theory, Univ. Lund,
`Sweden.
`T. Aulin and C. E. Sundberg, “Further results on M-ary multi-h
`constant envelope digital FM signals,” Tech. Rep. TR-139, Apr.
`1980, Telecommun. Theory, Univ. Lund, Sweden.
`
` {16}
`
`y)sin(x + y) + (x — y)(sin y — sin x) is always = 0 for x and y
`in this region. Thus f(x, y) <4 and dj = 4 for all hy, hh, = 155.
`
`REFERENCES
`
`[2]
`
`[3]
`
`[4]
`
`[5]
`
`{l] H. Miyakawa, H. Harashima, and Y. Tanaka, “A new digital
`modulation scheme, multimode binary CPFSK,”in Proc. Third Int.
`Conf. on Digital Satellite Commun., Nov. 1975, L1-13, Kyoto,
`Japan, pp. 105-112.
`J. B. Anderson and D. P. Taylor, “A bandwidth-efficient class of
`signal space codes,” [EEF Trans. Inform. Theory, vol. IT-24, no. 6,
`pp. 703~712, Nov. 1978.
`J. B. Anderson and R. de Buda, “Better phase-modulation error
`performance using trellis phase codes,” Electron. Lett., vol. 12, no.
`22, pp. 587-588, Oct. 28, 1976.
`J. B. Anderson, “Simulated error performance of multi-h phase
`codes,” in Conf. Rec. Int. Conf. on Commun., Seattle, WA, June
`1980, pp. 26.4.1-26.4.5.
`J. B. Anderson, D. P. Taylor, and A. T. Lereim, “A class oftrellis
`phase modulation codes for coding without bandwidth expansion,”
`in Conf. Rec. Int. Conf. on Commun., Toronto, ON, Canada, June
`1978, pp. 50.3.1-50.3.5.
`[6] A. T. Lereim, “Spectral properties of multi-h phase codes,” M. Eng.
`Thesis, MeMaster Univ., Techn. Rep. no. CRL-57, July 1978,
`Communications Research Laboratory, Hamilton, ON, Canada.
`J. B. Anderson, C-E. Sundberg, T. Aulin, and N. Rydbeck, “Power-
`bandwidth performance of smoothed phase modulation codes,”
`TEEE Trans. Commun., vol. COM-29, no. 3, pp. 187-195, Mar.
`1981.
`[8]. T. Aulin and C. E. Sundberg, “Continuous phase modulation (CPM),
`part I, full response signalling,” [EEE Trans. Commun., vol. COM-
`29, no. 3, pp. 196-209, Mar. 198k.
`{9} T. Aulin, N. Rydbeck, and C. E. Sundberg, “Continuous phase
`modulation (CPM)—~Part II: Partial response signalling,” [EEE
`Trans. Commun., vol. COM-29, no. 3, pp. 210-225, Mar. 1981.
`
`[7]
`
`[17]
`
`{18}
`
`[19]
`
`[20]
`
`[21]
`
`Channel Coding with Multilevel /Phase
`Signals
`
`GOTTFRIED UNGERBOECK,MEMBER, IEEE
`
`the corresponding channel signal sequences, a search procedure for more
`powerful codes is developed. Codes with coding gains up to 6 dB are
`obtained for a variety of multilevel/phase modulation schemes. Simulation
`results are presented and an exampleof carrier-phase tracking is discussed.
`
`I.
`
`INTRODUCTION
`
`Abstract—A coding technique is described which improves error perfor-
`mance of synchronous data links without sacrificing data rate or requiring
`more bandwidth. This is achieved by channel coding with expanded sets of
`multilevel/phase signals in a manner which increases free Euclidean dis-
`tance. Soft maximum—likelihood (ML) decoding using the Viterbi algo-
`rithm is assumed. Following a discussion of channel capacity, simple
`hand-designed trellis codes are presented for 8 phase-shift keying (PSK)
`and 16 quadrature amplitude-shift keying (QASK) modulation. These
`simple codes achieve coding gains in the order of 3-4 dB.It is then shown
`that the codes can be interpreted as binary convolutional codes with a
`mapping of coded bits into channel signals, which we call “mapping by set
`partitioning.” Based on a new distance measure between binary code
`sequences which efficiently lower-bounds the Euclidean distance between
`
`Manuscript received May 24, 1977; revised January 7, 1981.
`The author
`is with the IBM Zurich Research Laboratory, 8803
`Rischlikon, Switzerland.
`
`N CHANNEL CODING of the “algebraic” coding
`type, one is traditionally concerned with a discrete
`channel provided by some given modulation and hard-
`quantizing demodulation technique. Usually, inputs and
`outputs of the channel are binary. The ability to detect
`and/or correct errors can only be provided by the addi-
`tional transmission of redundantbits, and thus by lowering
`the effective information rate per transmission bandwidth.
`00 18-9448/82/0100-0055$00.75 ©1981 TEEE
`
`1
`
`LGE 1025
`LGE 1025
`
`

`

`56
`
`IEEE TRANSACTIONS ON INFORMATION THEORY,VOL. IT-28, NO. 1, JANUARY 1982
`
`ing channel-signal sequences. Based on this distance mea-
`sure, a search procedure for more powerful codes is devel-
`oped in Section V, and codes with coding gains up to 6 dB
`ate obtained for a larger variety of coded one- and two-
`dimensional modulation schemes. In Section VI simulation
`results are presented. Finally in Section VII, the problem
`of carrier-phase tracking, which can play an important role
`in the practical application of coded two-dimensional mod-
`ulation schemes, is discussed for one specific case of coded
`8-PSK modulation.
`
`II. CHANNEL CAPACITY OF MULTILEVEL/PHASE
`MoDULATION CHANNELS
`
`Before addressing the code-design problem with ex-
`panded channel-signal sets, it is appropriate to examine in
`terms of channel capacity the limits to performance gains
`which may thereby be achieved. Because of our intended
`use of soft ML-decoding in the receiver, we must study
`modulation channels withdiscrete-valued multilevel/phase
`input and continuous-valued output. One- and two-
`dimensional modulation is considered and intersymbolin-
`terference-free signaling over bandlimited channels with
`additive white Gaussian noise (AWGN)is assumed. With
`perfect timing and carrier-phase synchronization, we sam-
`ple at time nT + 7, where T is the modulation interval and
`7,
`the appropriate sampling phase. The output of the
`modulation channel becomes
`Zy = ay, + Was
`
`(1)
`
`where a, denotes a real- or complex-valued discrete chan-
`nel signal transmitted at modulation time nT, and w, is an
`independent normally distributed noise sample with zero
`mean and variance a? along each dimension. The average
`SNRis defined as
`2
`
`E{| wil}
`
`1 illustrates the channel-signal sets considered in this
`Fig.
`paper. Normalized average signal power E{|a2|} = 1
`is
`assumed,
`Extension of the well-known formula for the capacity of
`a discrete memoryless channel [11] to the case of continu-
`ous-valued output yields
`
`z/ak
`
`(3)
`
`In addition, hard amplitude or phase decisions made in the
`demodulator prior to final decoding cause an irreversible
`loss of information. In the binary case, this amounts to loss
`_ equivalent to approximately 2 dB in signal-to-noise ratio
`(SNR).
`In this paper, we take the viewpoint of “probabilistic”
`coding and decoding and regard channel coding and mod-
`ulation as an entity [1]. Comparisonsare strictly made on
`the basis of equal data rate and bandwidth. A possibility
`for redundant coding can therefore only be created by
`using larger sets of channelsignals than required for nonre-
`dundant
`(uncoded)
`transmission. Maximum-likelihood
`(ML)soft decoding of the unquantized demodulator out-
`puts is exclusively assumed, thus avoiding loss of informa-
`tion prior to final decoding. This implies that codes for
`multilevel/phase signals should be designed to achieve
`maximum free Euclidean distance rather than Hamming
`distance. For coded 2-amplitude modulation (AM) and
`4-phase-shift keying (PSK) modulation,
`this was never a
`problem because in this case, binary Hamming distance
`(HD) and Euclidean distance (ED) are equivalent. The
`situation is different, however, if signal sets are expanded
`beyond two signals in one modulation dimension.
`The investigations leading to this paper started some
`time ago with the heuristic design of simple trellis codes for
`8-PSK modulation conveying two bits of information per
`modulation interval. When soft ML-decoded by the well-
`known Viterbi algorithm (VA)[2], coding gains of 3-4 dB
`were found over conventional uncoded 4-PSK modulation.
`Theinvestigations were then extended to other modulation
`forms. First results were presented in [3], A much better
`understanding of the subject was later obtained by inter-
`preting the hand-designed codes as binary convolutional
`codes with a mapping of coded bits into multilevel/phase
`channelsignals called “mapping by set partitioning.”
`Related work was reported in [4]-[8]. The approaches
`taken in [6]-[8] aim at constant-envelope modulation which
`is in contrast to the present paper. In [9], a comparison of
`various “bandwidth-efficient” modulation techniques by
`_|E{| a; |} /o? --- (a) one-dimensional modulation
`computer simulation is presented which includes codes of
`
`E{|a?a; |} /20° --- (b) two-dimensional modulation ,
`this paper.
`In Section II, we investigate the potential gains in terms
`(2)
`of channel capacity obtained by introducing more signal
`levels and/or phases. The results are similar to those of
`Wozencraft and Jacobs [10] on the exponential bound
`parameter Ry, and suggest that for coded modulation, it
`will be. sufficient
`to use twice the number of channel
`signals than for uncoded modulation. In Section III, heur-
`istically designed trellis codes for coded 8-PSK and 16-
`QASK modulation are presented and the concept of map-
`ping by set partitioning is introduced. The codesare inter-
`preted in Section IV as binary convolutional codes of rate
`R=m/(m + 1) with the above mapping of coded bits
`into channel signals. Preference is given to realizations in
`the form of systematic encoders with feedback. The map-
`ping rule allows the definition of a new distance measure
`that can easily be applied to binary code sequences and
`efficiently lower-bounds the ED between the correspond-
`
`N-1
`
`ke
`
`c= 00)N=) 2 Qk)f p(z/a*)
`‘log, —_Plz/at) dz
`> Q(i)p(z/a')
`i=0
`
`in bit/7. N is the number ofdiscrete channel inputsignals
`
`2
`
`

`

`UNGERBOECK: CHANNEL CODING
`
`37
`
`olo
`°
`°
`}
`
`
`ac BIT}
`of}02|*
`
`°
`2-AM
`°
`8
`oje
`4-PSK
`8~PSK
`
`
`
`a
`o
`
`eo]
`
`o
`
`°
`fo
`
`°
`eo;
`8-AMPM
`
`foo
`° 0
`80
`og 0
`0° obo
`o dog
`a 0/6 &
`
`oooboo?oof ae
`32-AMPM
`
`o ofo 0
`o aloo
`0efoo
`cafe o
`16- QASK
`
`coeoloooe
`90cg|D000
`Bo0gpos9
`GOOKID00G
`oot
`oes
`
`oocgooos8960}0000
`64 - QASK
`
`o—0--+--0-_0
`4-AM
`
`o-0-0-0fo-6-0-0
`8-AM
`
`16-Am
`
`
`
`
`
`
`
`
` oO
`410° 64- 0AsK
`log (t+ SAR)
`
`
`
`loan * SNR)
`
`4
`2
`t ope nn
`6
`B
`10
`92
`44
`48
`18
`20
`22 24 26 28 30
`(b)
`Fig. 2. Channel capacity C* of bandlimited AWGN channels with
`discrete-valued input and continuous-valued output. a) One-dimensional
`modulation. b) Two-dimensional modulation.
`
`—
`[dB
`
`signal-set expansion if at given SNR satisfactory error
`performance can no longer be achieved by uncoded modv-
`lation.
`
`III.
`
`SimpLe TRELLIS CODES
`
`Coding gains can be realized either by block coding or
`by state-oriented trellis coding. There exists also the possi-
`bility of concatenation, ¢.g., by assigning short block-code
`words to state transitions in a trellis structure. Note that
`the choice of a signal set for two-dimensional modulation
`
`(a)
`(2m07) 1”
`(b))
`(2707)!
`With the further assumption that only codes with
`equiprobable occurrence of channel input signals are of
`interest, the maximization over the Q(k) in (3) can be
`omitted. Equation (3) can now be written in the form
`
`1
`Cougjstyn = log, (N)- N
`‘SS eto. S op|—tewaetaleyt
`
`-AM
`
`24TT 3
`SNR
`-
`0+ T
`TTT TT
`0
`2
`4
`&
`8 10 12 49 46 18 20 22 29 26 28 30.32 34.36
`[48]
`(a)
`
`4c" [pir/7}
`
`AMPM
`
`/g°
`
`46 - QASK
`
`AMPM
`PSK
`
`PSK
`
`(b)
`(a)
`Fig. 1. Channel-signal sets considered in this paper. (a) One-dimensional
`modulation. (b) Two-dimensional modulation.
`
`{a°---a%~'} and Q(k) denotes the a priori probability
`associated with a*. Because of AWGN, we can substitute
`in (3)
`P(z/a*) = exp[—|z — a*?/20?|
`
`(4)
`
`k=0
`
`i=0
`
`2
`
`20
`
`(5)
`
`In (5) we have integration replaced by expectation over the
`normally distributed noise variable w which is real with
`variance o” for (a), and complex with variance 207 for(b).
`Using a Gaussian random numbergenerator, C* has been
`evaluated by Monte Carlo averaging of (5). In Figs. 2(a)
`and 2(b), C* is plotted as a function of SNR for the signal
`sets depicted in Fig. 1. The value of SNR at which in
`uncoded transmission symbol-error probability Pr(e) =
`10~* is achieved is also indicated.
`In order to interpret Figs. 2(a) and 2(b), we consider as
`an example transmission of 2 bit/T by uncoded 4-PSK
`modulation where Pr(e) = 10~° occurs at SNR = 12.9 dB.
`If the number of channel signals is doubled, eg., by
`choosing 8-PSK modulation, error-free transmission of 2
`bit/T is theoretically possible already at SNR = 5.9 dB
`(assuming unlimited coding and decoding effort). Beyond
`this—with no constraint on the number of
`signal
`levels/phases except average signal power—only 1.2 dB
`can further be gained. Similar proportions hold for the
`other modulation schemes. It can be concluded that by
`doubling the number of channel signals, almost all
`is
`gained in terms of channel capacity that is achievable by
`
`3
`
`

`

`58
`
`ye
`
`
`
`IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-28, NO. 1, JANUARY 1982
`40: 8-PSKos
`Se
`[—~
`BINARY
`0
`ee
`} wee--- Ag® 2 SIN(7T/B) + 0.765
`
`
`
`ENCODER
`:
`:
`=o
`sd
`a,=Mly,)
`R= mi (m+4)
`7
`ss
`eo SUBSET BI
`oF
`Ry
`Ye
`0,oct 621414
`Fig. 3. Multilevel/phase encoder structure.
`fs
`¥ ON
`.
`Clog
`«3°
`oe
`
`©
`
`oo SUBSET C3
`\-5 7&2? 2.000
`
`oe C2
`2
`
`4 m
`
`CO 4 9
`
`y
`
`ON
`
`
`
`: =o:|MAPPING|oonvotutionac| |g
`
`corresponds already to a simple form of block coding. In
`this paper however we do not further pursue the block
`coding aspect because the richer structure and omission of
`block boundaries together with the availability of Viterbi
`ML-decoding algorithm make trellis codes appear to us
`more attractive for the present coding problem.
`Following the arguments of Section II, in order to im-
`prove error performance, m bit/T must be transmitted in
`redundantly coded form by a set of 2”*! channel signals.
`The coding expert will easily conclude that this may be
`accomplished by expanding the binary data sequence by
`suitable convolutional encoding with rate R = m/(m + 1),
`and subsequent mapping of groups of m + 1 bits into the
`larger set of channel signals. The encoder structure is
`shown in Fig. 3. With d(a,,, a’,) denoting the ED between
`channel signals a, and a’,
`the encoder should be de-
`signed to achieve maximum free ED:
`y 3
`@(a,, a
`
`free
`
`min
`
`om.a|
`
`( |
`
`1/2
`
`(6)
`
`6
`
`between all pairs of channel-signal sequences {a,} and
`{aj} which the encoder can produce. If soft ML-decoding
`is applied,
`the error-event probability will approach
`asymptotically at high SNR the lower bound [2]
`Pr(e) ZN(dtree) . O(dtree/20).
`
`(7)
`
`Here N(dj,c¢) denotes the (average) multiplicity of error
`events with distance d,,,., and Q(-) is the Gaussian error-
`probability function.
`For transmission at 2 bit/T by coded 8-PSK modulation
`it has been suggested [4], [5] to use known R = 2/3 binary
`convolutional codes with maximum free HD for given
`constraint
`length [12], and Gray coding as a mapping
`function. Yet there are problemswith this approach.Firstly,
`the Gray code mapping does not monotonically translate
`larger HD into larger ED and secondly, permutations of
`the binary outputs of the convolutional encoder will have
`an- unknown, perhaps significant
`influence on the ED
`structure of the resulting 8-PSK codes. Neither does the
`approach seem to be extendable to all modulation forms of
`Fig. 1.
`therefore pursue a different design method
`We will
`which aims more directly at maximizing free ED. The
`approach is based on a mapping rule called “mapping by
`set partitioning.” This mapping follows from successive
`partitioning of a channel-signal set into subsets with in-
`creasing minimum distances Ay < A,<A,---
`between
`the signals of these subsets. The concept is illustrated in
`Figs. 4 and 5 for 8-PSK and 16-QASK modulation, respec-
`tively, and is applicable to-all modulation formsof Fig.1.
`Before addressing the systematic search for convolu-
`tional codes for the encoder suggested by Fig. 3, we discuss
`
`°
`°
`“e
`@
`9
`o
`.
`a0 6
`°°
`°
`WOO)
`(000)
`
`0°
`
`of
`oe
`“5
`oo
`(O40)
`
`2
`
`\
`\
`oo
`o
`eo
`M101
`
`%e
`
`07
`
`\
`\\
`of
`20
`90
`“eo
`°
`ao
`°
`.
`(001)
`“on
`
`a”
`
`f \
`eo
`8
`Mo
`4
`a 6
`.
`oo
`5g (4340)
`why s y?y'y
`(O41)
`
`Fig. 4. Partitioning of 8-PSK channel signals into subsets with increas-
`ing minimum subset distances (A, < 4, < Ay; E{|a2|} = 1.
`
`in the remainder of this section the heuristic construction
`of simple but already very effective codes. This does not
`require knowledge of convolutional codes and will estab-
`lish an intuitive basis for the development of more power-
`ful codes later in the paper. Work leading to this paper
`progressed also in this order.
`Weregard an encoder simply as a finite-state machine
`with a given number of states and specified state transi-
`tions. If m bits are to be encoded per modulation interval
`T, there must be 2”possible transitions from each state to
`a successor state. More than one transition may occur
`between pairs of states, and for obvious reasons only
`regular structures are of interest. After selecting a suitable
`trellis state-transition diagram, the remaining task consists
`of assigning channelsignals from an extended set of 2”*!
`signals to the transitions such as to achieve maximum free
`ED. For codes with up to eight states,
`this could be
`accomplished “by hand,” and a 16-state code could still be
`found with the aid of a computer program that checked
`free ED.
`The heuristic design of 8-PSK codes for coded transmis-
`sion of 2 bit/T will be discussed in more detail. Uncoded
`4-PSK modulation is regarded as a reference system. As
`shown in Fig. 6, we can view uncoded 4-PSK as coding
`with a trivial one-state trellis and four “parallel” transi-
`tions, to which are assigned from the 8-PSKsignal set four
`signals with largest minimum distance among them,ie.,
`the signals of subset BO (or B1). Next consider a two-state
`trellis. The first code illustrated in Fig. 7 was easily found.
`Signals of subsets BO and B1are assignedto the transitions
`originating from thefirst and the secondstate, respectively,
`which guarantees that free ED is at least as large as for
`uncoded 4-PSK modulation. However with twostates,it is
`not possible to have the same property also for transitions
`joining into one state, and hence the gain in free ED over
`4-PSK remainslimited to 1.1 dB.
`The other 8-PSK codes depicted in Fig. 7 with 4, 8, and
`16 states, and gains in free ED of 3 dB, 3.6 dB, and 4.1 dB,
`respectively, required more effort. Nevertheless after con-
`siderable experimentation with various trellis structures
`and channel-signal assignments, we were convinced that
`these codes are optimum for the given numberofstates.
`The following rules for assigning channel signals were
`applied:
`
`1) all 8-PSK signals should occur with equal frequency
`
`4
`
`

`

`UNGERBOECK: CHANNEL CODING
`
`359
`
`AO = 16-QASK
`=
`_
`eee
`seelo- ccm: Ag=2/ {10=0.632
`oO.
`eeee
`y =O
`eee
`1
`_——
`~,
`
`80
`e000
`oeoe
`eoeo
`oeo@
`
`1
`nN
`
`=
`c2
`co Y=Y
`ooo°0
`eoeo
`aaqao
`@oeo
`oece
`e000
`oege
`eooo
`oe
`02
`pa
`of
`\1
`poy*=0f \1
`eoad oaeo eooo0
`oo00 0
`ooo6o ooo 0
`eeo°0 eoooe
`
`SUBSET 81
`alee.
`9e0
`i ae “By = 2B
`coeoe
`@eoeo
`
`0
`ov
`
`1
`‘\
`
`c3
`C1
`e000
`oeoe
`oo
`°
`o#oe
`oo foo A2= Fas
`ooo0
`@o
`9°
`eoocso
`03
`of \1
`07
`vs
`01
`of \1
`o0g0o°0 e000
`eoo0o @
`oeoa0o
`eoo080 ooo 0o e080
`900
`
`ooeo eco 8 0000 09000 oeo0 ooo @ 9000 oi A
`veoPTTTTLULLLLLILLe. b
`
`eoo00
`
`ooofo
`
`oo00oe oeoo eeoo ooo°o
`
`#oa0o0
`
`00
`
`°o
`
`3
`
`0000 1000 0100 1100 0010 1010 0110 1110 00O01 1001 0101 1101 0011 1011 O111 1111 Sy
`
`Fig, 5. Partitioning of 16-QASK channelsignals into subsetswith increasing minimum subsetdistances (Ag <A, <A, <A;
`= 0.
`E{\a,
`
`4 TRELLIS STATE
`
`2TRELLISSTATESTRELLIS STATES
`
`0C2oo2 22
`0,
`-O
`Stree = 4a.gesk = 1444.
`20426ee
`c1 c2
`Prie) 22 Old gree 42a)
`os?
`4TRELLISSTATES
`Fig. 6. Uncoded 4-PSK modulation, 2 bit/T.
`wc—
`O42
`pn
`ct
`¢3
`3
`o
`2
`
`and with a fair amountof regularity and symmetry,
`2) transitions originating from the same state receive
`signals either from subset BO or Bl,
`3) transitions joining in the same state receive signals
`either from subset BO or Bl,
`4) parallel transitions receive signals either from subset
`CO or Cl or C2 or C3.
`
`Rule 1) reflects the intuition that good codes should
`exhibit regular structures, and rules 2), 3), and 4) guarantee
`that the ED associated with all single and multiple signal-
`error events exceeds the free ED of uncoded 4-PSK modu-
`lation by at least 3 dB. We have seen that with only two
`states, rules 2) and 3) cannot be simultaneously satisfied.
`Since this is not unique to coded 8-PSK, weshall not be
`further interested in two-state codes.
`Note that parallel transitions imply that single signal-
`error events can occur. This limits achievable free ED to
`the minimum distance in the subsets of signals assigned to
`parallel transitions. On the other hand, parallel transitions
`reduce the “connectivity” in the trellis and thus allow
`extension of the minimum length of multiple signal-error
`events. With four states, the trade-off still worked in favor
`of parallel transitions; the best 4-state 8-PSK code gains 3
`dB over 4-PSK,with single signal errors being mostlikely,
`whereas codes with distinct
`transitions to all successor
`states remained inferior because rules 2) and 3) could not
`be satisfied simultaneously. With eight and morestates,
`only trellis structures with distinct transitions can be of
`interest because otherwise free ED gains would remain
`limited to 3 dB.
`The ideas can also be applied to the other modulation
`forms. As a further example, we consider transmission of 3
`
`TATE s 7 © deet
`
`(47+a3 = 1.608
`
`(.1.d8 GAIN OVER 4-PSK).
`Pr(e) 22.0 (d¢pg/28).
`
`“Sue
`c
`a
`
`1
`
`7 Stree = Ba = 2.000
`6
`(3.0 dB GAIN OVER 4-PSK),
`Pr(e) 2 1.Q(dy 99/26).
`
`Pr(e) % 2.0 (dfpee/20).
` 0426
`
`Gtree =JAi tora, = 2.141
`(3.6 dB GAIN OVER 4-PSK).
`
`Stree = [07 +05 +h5+h7 = 2.274
`(41 dB GAIN OVER 4-PSK).
`prie)2 (371004 free/2e)
`
`16 TRELUS STATES
`O—apine OmanJomo0:
`°
`a
`"70
`o
`o2 0
`°
`°
`°
`$
`2
`°
`2
`o
`°
`9
`°
`oO
`7 0
`°
`°
`°
`°
`°
`°
`°
`°
`°
`°
`°
`°
`°
`°
`°
`o
`°
`°
`
`1
`
`°
`°
`
`1537
`$193
`3748
`6240
`7351
`4062
`5173
`0426
`1537
`6240
`7351
`2604
`3715
`
`Fig. 7. Coded 8-PSK modulation, 2 bit/T.
`
`bit/T by coded 16-QASK modulation. Uncoded 8-PSK or
`8-AMPM modulation is regarded as a reference system.
`From the preceding discussion and the partitioning of the
`16-QASK signal set into subsets shown in Fig. 5, codes
`follow easily. In the 8-PSK codes of Fig. 7,
`the 8-PSK
`signals must only be replaced by the corresponding 16-
`QASKsignal subsets D0-D7 of Fig. 5. An 8-state 16-QASK
`code obtained in this manner is presented in Fig. 8. The
`reader must be cautioned, however, about this approach. A
`similarly obtained 16-state 16-QASK code turned out to
`
`5
`
`

`

`JEEE TRANSACTIONS ON INFORMATION THEORY, VOL, IT-28, NO. 1, JANUARY 1982
`Boh —2 ‘
`MAPPING
`
`
`— rearee
`
`J
`8
`alt
`*
`w—ty y2-[oo00r 111] 00...1'
`
`
`Lg!
`walt
`
`
`
`
`
`
`
`
`
`60
`
`8 TRELLIS STATES
`0, 0,0,
`D5
`9
`ees
`1454307
`q%
`§
`D, Depaps aN
`D4 Do De O2
`
`Dg Dz Dg Do © Ye
`
`550,D;D3 49
`Dz Dg Do Og
`D3D7D, Ds
`
`&
`
`0,0,D,d1 4
`
`ee
`Speet |A7 4854021414
`tree= {4140444 =
`141
`‘40 dB GAIN OVER 8-AMPM
`5.3.48 GAIN OVER 8 -PSK
`d
`Pr(e) 2 (70.0 (dieg/2s)-
`
`Fig. 8. Coded 16-QASK modulation, 3 bit/7.
`
`have only the same free ED as the 8-state 16-QASK codes.'
`Partitioning of the one-dimensional N-AM signal sets
`results in minimum subset distances A;,, =2-A,, i=
`0,1,:--
`(6 dB steps), whereas for two-dimensional N-
`AMPMand N-QASKsignalsets we have A,,., = ¥2 - A,‘
`i=0,1--+ (3.dB steps). Numerical values are given in the
`code tables of Section V for all signal sets of Fig.
`1 and
`normalized signal power. Partitioning of larger signal sets
`will soon lead to values of A, that exceed the free ED that
`one can ever expect to achieve at given code complexity.
`Therefore it will usually be sufficient—even for very com-
`plex codes—to partition a signal set two or three times,
`and associate the signals of the subsets not further parti-
`tioned with parallel transitions in the code trellis.
`One further remark is necessary. The specific mapping
`of coded bits into channel signals indicated in Figs. 4 and 5
`—which in the case of Fig. 4 leads to a straight binary
`numbering of the 8-PSK signals—is not important. By
`permuting subsets, other mappings can be obtained with
`the same pattern of increasing minimumsubset distances.
`Only this latter property is significant.
`
`IV. MULTILEVEL/PHASE CODES VIEWED AS
`BINARY CONVOLUTIONAL CODES WITH
`MAPPING BY SET PARTITIONING
`
`The codes presented in Figs. 7 and 8 have been selected
`among equivalent codes because with some effort they can
`be identified as binary convolutional codes of rate R =
`m/(m + 1) generated by feedback-free encoders in cascade
`with the mapping by set partitioning illustrated by Figs. 4
`and 5. Fig. 9 shows the encodersin this form of implemen-
`tation for constraint lengths » = 2,3,4, corresponding to
`4, 8, 16 states.
`Using polynomial notation, the binary output sequence
`y(D) must satisfy the parity check equation:
`[y"(D)--- y'(D), y(D)|
`(8)
`-[H™(D) ---H"(D), H(D)]"=0.
`For the encoders of Fig. 9, the parity check matrices are
`y=2: H(D)=[(0). 0, D,
`p>+1
`|,
`y=3: H(D)=[(0), D, dD’,
`D+1— |,
`y=4: H(D)=[
` D,D? + D?, D*+ D+ I],
`
`(9)
`
`‘Among the codes presented in Section V, there will be a better 16-state
`16-QASKcode.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Fig. 9. Realization of 8-PSK and 16-QASK codes by means of minimal
`convolutional encoders.
`
`Gn
`
`where the trivial entry (0) accounts for the additional
`unchecked bit in coded 16-QASK modulation. Note that
`the encoders are minimal [13] since y = maximum degree
`of H4(D), 0 <j <m. Considering (9), we observe that the
`parity-check polynomials have the form (v = 2):
`H(D)=0, m<jsm,
`HA(D)=0 +hi_,D7'4+---hiD+0,
`
`(10a)
`lsjsm,
`(10b)
`(10c)
`H°(D)= D’+ho_ D7! 4+--- kD +1,
`Equation (10a) means that there can be m — m unchecked
`bits at
`the binary encoder output. This leads to 277”
`parallel transitions between states and hence allows single
`errors to occur. Note further the difference between (10b)
`and (10c):
`
`.
`
`.
`
`m=ni= {i if oh.
`
`j~0
`
`(p=2).
`
`(1)
`
`The significance of this condition will be explained below.
`Instead of generating code sequences y(D) by minimal
`encoders, one can also envisage their generation by equiva-
`lent systematic encoders with feedback which represent the
`second canonical form of convolutional! encoders [13]. Code
`sequences y(D) are then generated by
`[y™(D) -- (D)]
`
`0
`
`=[x"(D) +-- x\(D)] |
`
`Amn
`
`H"(D)/H%(D)
`
`},
`
`| H'(D)/H(D)
`(12)
`
`where £(D) represents a scrambled version of the input
`
`6
`
`

`

`UNGERBOECK: CHANNEL CODING
`
`
`
`2
`
`61
`
`46- GASKnn
`
`
`
`
`
`
`=
`
`
`
`~
`
`vse
`
`Yu "1BPSK
`e
`xs
`
`
`
`
`-_
`
`46-QASK
`wecne rss ne once ee neces eeeenn een ees yea2
`Yq
`1
`Yu "18-PSK
`
`xoe
`x.
`xessn.
`
`
`1
`Ire T mo
`
`
`
`
`
`x
`
`
`
`—— Yq —18-PSK
`
`
`
`
`
`OTOL
`
`
`
`
`
`
`
`
`
`
`
`
`
`structure with feedback
`Fig. 10. Systematic convolutional encoder
`satisfying condition (11).
`
`x(D) to the feedback-free encoders. Because of [11], the
`rational functions in (12) are realizable. A general realiza-
`tion of (12) with » delay elements is depicted in Fig. 10,
`and the specific systematic encoders corresponding to the
`minimal encoders of Fig. 9 are shown in Fig. 11.
`Let y(D) and y’(D) = p(D) ® e(D) be two similar bi-
`nary code sequences where ® denotes modulo 2 addition.
`Since we deal with linear codes, the binary error sequence
`e(D) = e¢,D* + e,., DET) + >> a4,DE",
`€,5@.4,%90,
`L=O (13)
`
`belongs to the set of code sequences. In order to lower-
`bound the ED between the channel-signal sequences a(D)
`and a’(D) obtained from y(D) and y’(D), we define the
`Euclidean weights w(e,;) = min d[a(z), a(z ® e;)], where
`minimization goes over all z= {(z”---z',z°], and d[--+ |
`is the ED between the channel signals specified. For the
`squared ED between a( D) and a’(D), we then obtain
`kth
`k+L
`
`a d*|a( yi) a( y, ® e:)] = 2 w(e;,) s w*[e(D)].
`(14)
`
`Theorem: For each e(D) there exists a pair a(D) and
`a’(D) for which (14)is satisfied with equality.
`
`Proof: Because of symmetry in the channel signal sets
`we;) = min d[a(z), a(z © e,)] is already achieved by let-
`ting the last element z° in z be arbitrarily 0 or 1, and
`carrying out the minimization only over [z”--- z']. Since
`encoding at rate R = m/(m + 1) allows any succession of
`elements [y"--- y!] to occur (best seen from Fig. 10),
`there exists for each e(D) a code sequence y(D) that leads
`in (14) to equality for each individual term ofi.
`
`Free ED between channel-signal sequences can therefore
`be determined in an analogous mannerto finding free HD
`between the binary code sequences y(D).
`In the ap-
`propriate search algorithm that examines all nonzero code
`sequences e(D) (or y(D)], the Hamming weights of e, must
`only be replaced by the squared Euclidean weights w(e;).
`Hence
`
`dzfree = minw*[e(D)]
`overall code sequences e(D) # 0.
`
`(1Sa)
`
`7
`
`Ls
`
`ve4
`
`Fig.
`
`IL.
`
`Equivalentrealization of 8-PSK and 16-QASK codes by means
`of systematic convolutional encoders with feedback.
`
`Let q(e,) be the numberoftrailing zeros in e,, e.g., for
`e, = [e?"--- e?,1,0,0] we have q(e;) = 2. From the map-
`ping by set partitioning, one can see that w(e,)>A,.),
`and that equality holds for almost all e,. In the 8-PSK
`mapping illustrated by Fig. 4, we have only found that
`w((101]) > Ay, and that in the 16-QASK mapping in Fig.
`5, only w({1001}), w([1101]), and w([1111]) exceed Ay. In all
`other cases, w(e;) = Aj. (note w(0) = A,@ = 0). This
`motivates us to write
`
`AL
`ince x Mire = min > Mie) min A*[e(D)]
`i=k
`:
`
`(15b)
`
`over all code sequences e(D) # 0.
`iS very small be-
`The risk taken in setting ds.¢ = Age.
`cause the minimum in (15b) is usually achieved by more
`than one e( D). This is especially true if # < m, i-e., higher
`order bits of e, are not involved in the parity-check opera-
`tion. We could never find a code where d,,.. was not equal
`to Arce. Therefore we adopt this latter definition of free
`ED in terms of minimum subset distances, which makes
`the calculation independent of the exact mapping of coded
`bits into channel signals as long as the same pattern of
`these minimum distancesresults.
`To conclude this section, we note another important
`property of condition (11). From Fig. 10, one can see that
`multiple signal errors (L>0) must
`start with e, =
`[ev -++e,,0] and with e,,,=[e"™,---el,,,0]. The
`squared ED associated with these errors is therefore at
`least 2 - Aj. In other words, the condition guarantees that
`transitions originating from one state or joining in one
`state can have signals only from subset BO or Bl
`(cf.
`Section-III, conditions 2) and 3)). We note further that
`m<m implies d;,.. = A,,, since then single-signal errors
`(L = 0) with ED equal to A, are possible.
`
`

`

`62
`
`V.
`
`SYSTEMATIC SEARCH FOR MORE POWERFUL
`CODES
`
`IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-28, NO. 1, JANUARY 1982
`
`Get vy Bo,Bam idm (=O); : hm
`
`
`
`
`
`"
`
`+ Tiree
`Print? ih
`|"Best code so far
`
`found"
`
`
`
`Fig. 12. Block diagram of code search program.
`
`The problem to be solved is to find for given constraint
`length » and given minimum subset distances A, <A,
`<.---A,,, the systematic encoder with feedback that maxi-
`MiIZES dtree = Atee Considering (10), there are (7% + 1) - (v
`— 1) coefficients in the parity-check polynomials to be
`determined. For a feedback-free encoder with a restriction
`equivalent
`to (11), one can show that there would be
`(h@ + 1)-(» — 1) + m? + 1. generator-polynomial coeffi-
`cients to decide on. The difference of m? + 1 accountsfor
`the fact
`that with the systematic encoder
`stru