784 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-30, NO.

6, NOVEMBER 1984

A New Description of Trellis Codes

ROBERT CALDERBANK AND JAMES E. mzo, MEMBER, IEEE

Abstract-A trellis code is a “sliding window” method of encoding a

00
binary data stream as a sequence of real or complex numbers that are input
to a noisy transmission channel. Ungerboeck has constructed simple trellis
codes that provide the same noise immunity as is given by increasing the
power of uncoded transmission by factors ranging from two to four. His IO
method is to specify an underlying convolutional code and a rule (mapping
by set partitioning) that maps the output of this code onto a fixed signal
constallation. A new description of a trellis code is given that combines
01
these two steps into one. The new description is analytic rather than
graphical. Many practical codes can be described very simply, and strict
bounds on performance can be obtained. A method for differential encod-
ing trellis codes is presented that was suggested by the authors’ representa-
tion.

Fig. 1. Diagram of trellis code.

I. INTRODUCTION

TRELLIS code is a “sliding window” method of

A encoding a binary data stream {a,}, a, = 0,l into a
sequence of real numbers {xi} that are input to a noisy
We propose an alternative description of trellis codes.
Our description is analytic rather than graphical, allowing
some statistical questions to be easily treated. Further,
transmission channel. The purpose of the encoding is to many practical codes will be simple to describe. We will
gain noise immunity. When a trellis code is used to encode discuss how to obtain performance bounds, and we will
data at the rate of k bits per channel symbol, each channel describe a method of differential encoding that is suitable
input xi will depend not only on the most recent block of for two-dimensional symbol transmission.
k data bits that enter the encoder but will also depend on
the u bits preceding this block. Formally, II. ANOTHER DESCRIPTION OF TRELLIS CODES
xi = x(ajk, ajkpl; -. 3'jk-(k-1); a(j-l)k,~~~,a(j-l)k-(,-l)) In (1) we regard the channel input xj as a real-valued
most recent k-bit block u bits preceding this block. function of (k + u) binary variables. In so doing we now
adopt the more natural indexing
(1)
xj = x(a,, a*; . *, a,) (4
The u bits determine one of 2” states of the encoder, and
2k possible output symbols are associatedwith each state where n = k + u, (al,. . ., ak) is the most recent k-bit
-one symbol for each possible input block of k bits. The input block and (u~+~;.., a,) are the u preceding bits.
state for the next channel symbol is determined by shifting We regard each ai as a 0, l-valued real variable, and we
every a, appearing in (1) k places to the right, dropping note that any real-valued function x may be written as a
the right-most k bits, and inserting the new k-bit block at sum of products of the ai ’
the beginning.
Drawing this encoding procedure sequentially in time x(a,,*~ -3 a,) = x0+ fxiai+ 2 xijaiaj
results in a trellis structure; hence the name trellis code. i=l i,j=l
jzi
The trellis code with k = 1 and u = 2 is shown in Fig. 1.
For example, if the encoderis in state 10 and the new input + *a- +x I... nala2 * * * a*. (3)
bit is 1 then a transfer from state 10 to 11 occurs and the
There are 2” constants on the right side of (3), one for each
encoder output is x(1; 10).
distinct product of the variables aj. They are determined
If only a subset consisting of u’ of the u preceding bits
by the 2” values that ~(a,, . * . , a,) can take. As pointed
actually enters the function x( *) in (l), then the code may
out in [l], the constants in the expansion may be de-
have as few as 2”’ states, the precise number being de- termined iteratively as follows. First, set all a, = 0, yield-
termined by the requirement that the new state must be
ing x0 = x(0,0; * ., 0). Then set only one a, = 1 to find xi.
determined by the old state and last input.
Then set only two ai to unity to determine the xij, and so
on. In this way a simple proof of (3) is obtained.
Manuscript received October 25, 1983; revised April 6, 1984.
The authors are with AT&T Bell Laboratories, Murray Hill, NJ 07974,
U.S.A. ‘This expansion is introduced in [l] in a different application.

0018-9448/84/1100-0784$01.00 01984 IEEE

Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on September 02,2024 at 08:10:43 UTC from IEEE Xplore. Restrictions apply.
CALDERBANK AND MAZO: NEW DESCRIPTION OF TRELLIS CODES 785

For trellis codes,(3) is not as useful as the version of (3) 00

that is obtained by taking the binary data to be bj = f 1 3
rather than a, = 0,l. The linear transformation
IO 3
1 - b.
a.I = d
2
-3

z3E
provides the connection.Substituting (4) for a, in (3) yields 01
the desired form
x A x(b,; . . , b,) = x,, + xx,b, + c xijbibj
i i,i II -3
j>i
STATES
+ ... +xl.unbl ..a b,, (5) Fig. 2. A trellis code.

where, of course,the constantsin (5) are not the sameas in

(3). and there are no cross terms surviving from terms in (5)
A good way to determinethe constantson the right side that are of different order in b. W e note a simple corollary
of (5) is to regard the 2” valuesof x(b, . . . b,) as a vector of (8): if no Zth-order term is obtained from another by a
x of dimension 2”. Similarly, regard the 2” valuestaken by series of k shifts, then Ex,x, = 0, r # s. That is, the
each product of the variables bi as a vector of dimension autocorrelation matrix of the channel inputs is propor-
2”. The latter vectorshave all componentsequal to f 1, are tional to the identity matrix, and the transmitted power
orthogonal, and have norm-squaredequal to 2”. Thus, if spectrum is not affected by the coding.2
the vector correspondingto one such product is p, then the
coefficient of that term is simply the inner product (1/2”)/3 III. SPECIFIC CODES
. x. In short, the vector of coefficients on the right side of W e will now use (5) to describespecific practical codes.
(5) can be viewed as the Hadamard transform of the vector A simple code of rate 1 bit/symbol (k = 1) that usesfour
x [71. states (u = 2) and provides a coding gain of 2.5 dB was
From now on, we will only be concerned with the given by Ungerboeck [3] in a paper that stimulated much
representation (5), and we will assumethat the sequence work in this area. (SectionIV contains a description of how
{ bi} is independent and identically distributed (i.i.d.) with this coding gain is calculated.)The code uses f 1, f 3 as
values f 1 occurring with equal probability. An important channel inputs and is describedby the trellis given in F ig.
parameter of the code is k, the number of bits per channel 2, where each edge has been labeled with the appropriate
symbol. This describesthe amount by which the bi are channel symbol. Our descriptionof this k = 1 code is
shifted when calculating the next channel symbol.
Some important averagesthat involve the channelinputs x = b, - 2b,b,
(9)
may be evaluated using (5). If E denotes mathematical where x is the value of the transmitted symbol, b, is the
expectation then input bit, b, is the precedingbit, and so on.
Ex( b, . . . b,) = x,, Ungerboeck describedhis codesby giving the polynomi-
n als for a rate k/(k + 1) binary convolutional encoder,and
Ex2(b, . . . b,) = x0’+ 1 x; then separately giving a rule for m a p p ing the (k + 1)
i=l binary output symbols of this convolutional code to 2k+1
+ c x,?j+ ... +x;...,.
channel inputs that were arbitrarily chosento be + 1, f 3.
(6)
I.
However, note that (5) is also a complete description of
i, j=l how the channel inputs are to be chosen. No separate
j>i
m a p p ing of blocks of binary bits to real numbers needsto
Henceforth, we will choosethe additive constant x0 to be be done; (5) combinesthe two stepsinto one.
zero, since this will not affect distancesbetweencodewords Another k = 1, u = 2 code with a coding gain of 2.5 dB
but will m inimize the transmitted power (which is propor- is
tional to Ex2).
x = b, - 2b,b,b,. (10)
Next consider the correlation of the channel symbols
taken at times Y and s # r. If we set Consider the codes
x, = x(b, . . . b,) x = b, - 3b,b, (9’)
x, = .(a, -. . in) (7) and
x = b, - 3b,b2b3.
then
*If Exixj is not roportional to S,, then the transmitted power is not
Ex,X,= E[ (Cxibi)(CXi’i)] proportional to Ex f unless “square-root nyquist” shaping is used for the
transmitted pulses. See [2, Introduction] for some relevant formulas that
+E [ (CXijbibj)(Cxijbihj)] + * . . (8) relate symbol correlation and power spectra.

Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on September 02,2024 at 08:10:43 UTC from IEEE Xplore. Restrictions apply.
786 IEEE TRANSACTIONS O N INFORMATION THEORY, VOL. IT-30, NO. 6, NOVEMBER 1984

TABLE I TABLE II
OPTIMUM TWO-TERM CODES WITH ONE AND THREE COEFFICIENT ELEVATED k = 2 CODES DERIVED FROM THE k = 1 CODES IN TABLE I
Coding Upper Coding Upper
Gain Bound Ungerboeck [3] Gain Bound Ungerboek [3]
u Best Code (dB) (W (W u Elevated Code (W (dB) (W
2 b, - 3b,b2b3 3.0 4.3 2.5 2 b, - 3b,b,b, + 6b, 3.4 8.2 3.3
3 b, - 3b,b,b, 3.4 5.2 3.0 3 b, - 3b,b,b, + 6b, 3.8 10 3.8
4 b4 - 3b,b2bs 4.2 6.0 3.4 4 b, - 3b,blb, + 6b2 4.5 10 4.2
5 b,b, - 3blb4b6 4.6 6.7 4.2 5 bib, - jb;b;b,, +-6b, 5.0 11.3 5.0
6 b,b, - 3b,b,b,b,b, 4.9 7.3 4.5 6 b,b,, - 3b,b3bgb,,b,, + 6b, 5.3 11.3 5.2
7 b,b, - 3b,b,b,b,b, 5.3 7.8 5.1 7 b5b,, - 3b,b,b,b,,b,, + 6b, 5.7 12.2 5.8

pairs b,b,. The bit b, and the other even bits will not enter
00 the encoder, and the code (10) will be used only on the odd
bits. For k = 2 Ungerboeck choosesequally spacedchan-
nel inputs + 1, f 3, f 5, f 7. We require a three-term code
with coefficients one, two, and four. The four should go
IO with the uncoded bit to give it the largest signal, and so
x = b, - 2b,b,b, + 4b,. (11)
Since k = 2, in (ll), any even indexed bit influences the
channel input only once; in this senseit is uncoded. The
Oi state of the encoder is determined by the pair (b3, b,),
because k = 2. Again, we have a four-state code, but now
the code has the trellis structure shown in Fig. 3. Note in
Fig. 3 that the trellis has double edges,or parallel transi-
tions, because of the uncoded bit. These edgeshave been
Ii
LI
labeled with the new bit pair and the channel input.
STATES The same method leads to a k = 3 code
Fig. 3. Trellis diagram of the code given in (11).
x = 8b, + 4b, + b4 - 2b,b,b, (12)
with four parallel transitions in the four-state trellis.
These codes are evidently similar to (9) and (lo), but they
Table II presents the results of “elevating” the codes of
use (after an unimportant scaling) f. 1, +2 for channel
Table I to rate k = 2 codes.O ther coefficients close to the
inputs instead of + 1, + 3. It is possible to show that the
ratio of those given in Table II may result in further small
coding gain of (9’) is still 2.5 dB, whereas(10’) provides a
gains. For example, the k = 2, u = 2 code
3-dB gain.
For small u, Dan Sleator performed a computer search x = 3b, - 7b,b,b, + 14b, (13)
of all two-term k = 1 codeswith coefficients fixed at 1 and yields a 3.5 dB coding gain, and the k = 2, u = 3 code
3. Details are given in Appendix A, and the results are
presented in Table I. The designerof a trellis code is free to x = 3b, - 7b,b,b, + 14b, tw
chooseboth the signal constellation and the rule for assign- achieves4.1 dB.
ing signal points to successiveblocks of input data. A final remark about Table II. The upper bounds given
Ungerboeck always choosesequally-spacedchannel sym- are for arbitrary k = 2 codes, and they are valid for any
bols +l, +3, f5, -.. . Table I demonstrates that it is choice of signal constellation and any rule for mapping
sometimes possible to increase the coding gain by using input data to signal points. It can be shown that the coding
unequally-spacedchannel symbols and a well-chosencod- gain for k = 2 codes with parallel transitions cannot ex-
ing scheme. ceed 7 dB just .by consideringthe length-one error eventsof
For u = 2-5 inclusive, the codesof Table I were uniquely the parallel transitions. O f course, an optimal rate k = 2
optimum-at least up to a reversalof indices. Observethat code might not involve parallel transitions.
if u = 3, then b, - 3b,b,b, has the same coding gain as
b, - 3b,b,b,. IV. PERFORMANCE MEASURES
The upper bound in Table I is an upper bound on the
The coding gains quoted in earlier sections referred to
gain of any k, u trellis code (any signal constellation and
any rule for assigning signals to blocks of input data), and the number
it was obtained using the results given in [4].
We now turn to a technique given by Ungerboeck to coding gain (dB) = 10 log,,
i i%cded/i+i..odedl
obtain a code with k = 2 given a code with k = 1, and we
illustrate this in our notation using (10) as the k = 1 code. 05)
We want a k = 2 code, so that new input bits come in where di,, refers to a characteristicsquared distance and
Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on September 02,2024 at 08:10:43 UTC from IEEE Xplore. Restrictions apply.
CALDERBANK AND MAZO: NEW DESCRIPTION OF TRELLIS CODES 787

Term Associated Vector Coefficient

b,b,b, 111 3

b, 010 1

Component Edges Contribution c

1 100 36
2 110 4
3 011 4
4 001 36
d$, = 80

Fig. 4. Two paths forming an error event. Fig. 5. A sample distance computation.

the power P is the averagedsquaredchannel input (P = N = 2” trellis states, and an error event is specified by
Ex2). In the uncoded situation with k bits/symbol the giving a sequenceof pairs of states. Therefore, a state
channel inputs are taken to be the 2k real numbers diagram representationof error events requires N2 states.
fl, &-3,-a. , ~b(2~- l), and so P = (4k - 1)/3. The By contrast, for a linear convolutional codewe may assume
quantity d&, for the uncoded case is the squared m ini- that the all zero input sequencedeterminesone of the paths
m u m distance betweendistinct channel inputs and is easily and so only N states are needed.If we are willing to settle
seen to be 4. For the (trellis) coded case, d& is the for a lower bound on distancesof error events in a trellis
m inimum distance of error eventsin the trellis. code (hence a lower bound on coding gain for a given
Two paths of finite length through the trellis form an code), then the representation(5) suggestshow to reduce
error event if they start in the samestate, finish in the same the number of statesrequired from N2 to N. For example,
state, and do not simultaneouslyoccupy the same state in consider the code x = b, - 3b,b2b3.If b,b,b, are the bits
between. An error event is shown in F ig. 4, and with it we associatedwith the channelsymbol on one path in an error
associate the squared distance d2 = (a - b)2 + (b - c)~ event and if b;b;b; are those for the other path, then this
+ (d - e)2. component of the error event contributes
The distance d2(8) associatedwith an error event d is
of interest becausethe probability Pi that a Viterbi decoder [(b, - b;) - 3( b,b,b, - b;b;b;)]’
outputs an incorrect path starting at state i is upper to the distance. In general, two products llbi and KIb(
bounded (see [5]) by differ if and only if an odd number of pairs (b,, bj) are
different. If such is the case, we say that the term is
Pi12 fJ -$ c g(q) “excited” becauseonly then can it contribute to the dis-
I=I,, IES(I,i)
tance. If there are p terms excited in a componentand they
SE
I=&
exp(-d2(&‘)/Se2). (16) have coefficients ti, i = 1 . * . p in the code (5), then the
contribution of that component to the squared distance
must be at least
In (16), S(I, i) is the set of error events of length 1 that
starts at state i. The function Q is given by

Q(x) = + /me-Y2/2 d’ 2 +x2/2 07)

?r x where the m inimum is over all vectors c having -t 1 compo-
and a2 is the variance of the zero-meani.i.d. Gaussian nents zi.
noise added to each channel input by the channel. Equa- Consider the following sample computation of an error
tion (16) illustrates the importance of the m inimum dis- event distance involving the code (10’). In F ig. 5 we
tance among all the error events since, if the series(16) associatedO-l vectors with the terms of the code and also
converges, this m inimum distance will determine the with pairs of edgesin a component: a 1 in the i th position
asymptotic performancefor small noise variance u2.3 of the edge vector means that b, and b( are different. An
W e now turn to discussingthe m inimum distanceprop- edge vector excites a term if the vector associatedwith that
erties of a trellis code and illustrate the utility of (5) in such term has an odd number of onesin common with the edge
an investigation. Size is a m a jor problem associatedwith vector. Equation (18) has been used to compute the dis-
calculating the performance of trellis codes. There are tance contribution. One may verify that 80 is indeed the
m inimum obtained for the code. Thus, P = l2 + 32,
d&,/P = 8, and a 3-dB coding gain is achieved.
3A11nonlinear one-term k = 1 codes (such as b,b, 6,) have d,‘& = 8.
This would appear to give a 3-dB coding gain using only & l’for channel From (18) it is clear that the lower bound on d,, that
inputs. However, an infinite number of error events have this distance, we have given doesnot dependon the choiceof sign of the
and so the upper bound (16) is infinite. W e assume such pathologies terms of the code. In principle, however, the true distance
would be quickly realized in practice. The adjective “nonlinear” in the
code description simply means that the one term is not simply bi, for may depend on the choiceof sign. W e denote distanceand
some i, but that a product of the b, are involved. error events determinedby the O-l labeling of edges(given

Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on September 02,2024 at 08:10:43 UTC from IEEE Xplore. Restrictions apply.
788 IEEE TRANSACTIONS ON INFORMATIONTHEORY,VOL. IT-30, NO. &NOVEMBER 1984

in Fig. 5) by d and &?.4Then, the upper bound for the RAW

DATA CHANNEL
probability P of an error event starting at a given time is EN&ER + = 0.180~

Fig. 6. One-dimensional differential encoding using a trellis code with

only odd-order terms.

TABLE III
TRANSFORMSOFTHEPOINT
where the sum is taken over all error events 2,. The usual Rotation Angle Transformed Point
transition matrix evaluation of (19) is applicable, and only 0 (x2 Y)
an N X N matrix needs to be inverted, where N = 2”. n/2 c-v, x)
As a final remark on the use of (5) in performance
3:,2 ‘;y”-5’
, x
evaluations, we note that in an earlier publication Massey
[6] gave a lower bound on the minimum distance of con-
volutional codes. The representation (5) allows a modifica- With a 180” phase hit sequence(21) becomes
tion of this argument to be made so that a lower bound on
minimum distance for k = 1 trellis codes can be obtained. 1, -3, -1,3, -l,l, -1, -l,l, -1, -1, -3;**
This is given in Appendix B. (24
and as can be seen from Fig. 2, this is not an allowed
V. SYSTEM CONSIDERATIONS
sequence of output symbols for the code (9). One proce-
Trellis codes generate the real-valued channel inputs x dure is to monitor the Viterbi decoder, and if it is not
sequentially. For transmission over a passband channel, “ working”, assume the phase error and change the phase
these inputs might be taken in pairs and transmitted as the by 7~. This takes its toll in time, however, and for this
inphase and quadrature components of a carrier. However, reason the differential encoding procedure that we shall
we use an alternate approach, splitting the incoming bit describe is preferred.
stream into two streams and using a separate trellis en- Our main requirement for differential encoding is that
coder for each stream. The output symbols of each encoder the code must have the following reflection property: if
then separately modulate the two carrier components. {xi} is a sequence of output symbols corresponding to
Thus we consider a new two-dimensional transmitted inputs { bi}, then { -xi} is the sequenceof output symbols
symbol, with components corresponding to the inphase corresponding to inputs { - bi}. Thus, a code such as (10)
and quadrature components. The set of all possible such that has an odd number of variables bi in each term is
pairs (i.e., the signal constellation) will then have a 7r/2 required. We then precede the trellis encoder by the usual
rotational symmetry. Becauseof the way an equalizer or differential encoding operation. By this we mean that a
phase-locked loop recovers after a phase hit, the received dummy bit say + 1 is inserted at the start of (20). There-
signal points are sometimes rotated by a multiple of r/2 after, an input + 1 is encoded by repeating the preceding
compared to an initial determination of phase. This section binary symbol, and an input - 1 is encodedby changing it.
describes the first method of “differentially encoding” data The resulting differentially encoded bit stream for (20),
in a trellis code to overcomethis phase ambiguity.5 including the initial dummy bit, would then be
To illustrate this, we begin with a one-dimensional ver- l,l,-l,l,-l,-l,l,-l,-l,-l,l,l,l;... (23)
sion of the differential encoding problem. The sequence
{xi} is transmitted, but the sequence {-xi} is received. Now the trellis code (10) is used with (23) as input. The
For example, consider the code of Fig. 2 and (9). Assume entire procedure is sketchedin Fig. 6.
that the encoder is initially in the state (00), and let the Now consider a two-dimensional differential encoding of
input data be pairs of binary symbols. This form of encoding (and decod-
ing) will provide end-to-end transparency to “channel”
l,-l,-l,-l,l,-l,-l,l,l,-l,l,l;**. (20) rotations that are multiples of m/2. Direct encoding of the
binary pairs (1, l), (- 1, l), (- 1, -l), and (1, - 1) associ-
The output sequenceis ates with each pair the point of the plane having these
-1,3,1,-3,1,-1,1,1,-1,1,1,3;*~. coordinates. If one transmits an initial dummy pair, then
(21)
the pairs of binary data bits can be differentially encoded
into these four pairs by advancing the last transmitted
4The k = I codes 46, b, - 2 b, b4 T b, be provide examples of the fact
that it need not be true that d,, = dmin and that signs may matter. As a
symbol by 0, ?r/2, 7~, or 3a/2 radians if, for example,
hint, consider the edge label sequence lOOOO0,110000, 011000, 001100, (1, l), (- 1, l), (- 1, -l), or (1, - 1) are the raw-data pairs.
etc. In general, a point (x, y) in the plane is transformed
5A method simplifying the implementation of this differential encoding
scheme and others was recently discovered by Ungerboeck and indepen- under the rotations we are considering according to Table
dently by Lee-Fang Wei. By introducing feedback, they were able to III.
transform a trellis code requiring external differential encoding/decoding We now turn to two-dimensional differential encoding
into a single finite-state machine with built-in transparency to 90” phase
shifts. Their methods apply to the coding schemes described here and with trellis codes. First consider the case when k = 1, and
eliminate the need for external differential encoding/decoding. then separate the initial binary data stream into two paral-
Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on September 02,2024 at 08:10:43 UTC from IEEE Xplore. Restrictions apply.
CALDERBANK AND MAZO: NEW DESCRIPTION OF TRELLIS CODES 789

(4

2AD!M.
ENCODER
TRELLIS
ENCODER
CHANNEL:
+=o, t9v
180”
2 DIM TRELLIS 42
ENCODER
EN&R 000
(b) Fig. 8. Possibletransitions for the code given by (24).
Fig. 7. (a) Proposed differential encoding with k = 1 trellis codes. (b)
Proposed differential encodingwith k = 2 trellis codes.
“m o d 4” differential encodingis used in place of the one
we have specified, the overall procedureof encodingtrellis
(or block) codes will not work. Thus, place (O,O), (0, l),
lel streams. Encode each stream with a trellis code having (l,O), (1,l) consecutivelyat the corners of a square, and
only odd-order terms (as in the one-dimensionalexample), then replace each label (a, p) by (p, a). Note that the
and transmit the resulting output pair (x, y). As we note in resulting figure is not a rotation of the original one.
Table III, a r/2 rotation will causethe x-channel decoder Our procedureclearly dependson the reflection property
to output the negative of the y-channel bits, and the holding and on the specialway that we applied differential
y-channel decoder to output the x-channel bits with the encoding to uncoded bit pairs. Further, this procedure
proper sign. Therefore, regarding the bit pairs as points in clearly applies to block codes as well. All we require is
the plane, they too will be rotated by n/2. Thus, we independent block encoderson each channel. If the trans-
precede the trellis encodersby a conventional differential m itted block of channel symbols is negated, the resulting
encoder and follow the Viterbi decoderwith a differential block is in the code and complementsall input bits.
decoder,as shown in F ig. 7(a). This completesthe differen-
tial encoding for trellis codeswhen k = 1. ACKNOWLEDGMENT
The procedure generalizeswhen the higher rate (k > 1)
trellis codes are used on each carrier component. These It is the authors’pleasureto acknowledgethe valuable
codes must be identical odd-order codes. Consider the contribution m a d e by Dan Sleator in performing the com-
input bit stream to be 2k parallel bit streamsregardedas k puter searchof two-term codes.
parallel pairs of bit streams. Each of these k pairs is
independently differentially encoded;that is, one bit from APPENDIX A
each encodedpair is sent to the inphasetrellis encoderand MINIMUM DISTANCE CALCULATIONS
the other bit is sent to the quadraturetrellis encoder.Thus, W e elaboratehereon somespecifictechnical points that ap-
each encoder receivesits k-bit input block. After transmis- pear in Sections 1-V. W e discuss the computer search used to
sion and Viterbi decoding,the bits are recombinedinto the find d,?,,,for two-term k = 1 codes, we give an example of an
k differentially encodedpairs, and each of these k streams explicit evaluationof the upperbound(19),and we givea proof
of pairs is differentially decoded.This is illustrated in F ig. that d&, = 8 for nonlinear one-term k = 1 codes.
7(b) for the case k = 2. The procedureworks becausethe W e illustratethe first two pointsusingthe k = 1 code
choice of odd-order codesguaranteesthat the net result of b, - ab, b, b, (24)
the trellis encoding, channel, and trellis decodingsequence
where O Lis an arbitraryfixed constant.In light of the discussion
is to rotate each bit pair of each differentially encoded preceeding Fig. 5, introduce a directed graph of 2k+” vertices
stream by the angle of the phasehit (assumedhere to be a (eight in this case) by labeling the vertices with the labeling used
m u ltiple of m /2). for edges in Fig. 5; that is, a 1 in the ith position means that bi
The differential encoding of these bit pairs is unusual, and b( are different. The first k bits are the new input, and the
and this is best seenin 0,l notation. Denote a binary pair last v are the trellis state. A sequence of components of the error
by ((Y,j?) and use a bar to denote the complementof a bit. event 8 is a walk on this directed graph. Thus, for (24) we have
Our procedure is to uniquely assign to each of the four the graphof F ig. 8, whereedgesarelabeledwith the contribution
possible input pairs either (a, p), (fl, cu),(& p), or (p, (u), of the transition to d* as calculated from (18). More specifically,
where (cw,/I) was the previous output of the differential in Fig. 8 the state to which the transition is made is used to
encoder. By contrast, a common implementation of dif- determine which terms of the code are excited when evaluating
ferential encodingis as follows. Assign the numbers0, 1,2,3 (18). A state (000) has been introduced as a starting state, and an
error event c? of length I corresponds in Fig. 8 to a path of length
to the pairs (0, 0), (0, l), (1, 0), (1, 1), respectively.If the last 1 from 000 to 001. The search for Table I (a = 3) took less than
output pair of the differential encodercorrespondedto the five minutes on a VAX@11/780.
number x, and if y correspondsto the new input pair, then
the new output pair correspondsto (x + y) (mod4). If this mVAX 11/780 is a trademark of Digital Equipment Corporation.

Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on September 02,2024 at 08:10:43 UTC from IEEE Xplore. Restrictions apply.
790 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-M, NO. 6, NOVEMBER 1984

Fig. 9. A more compact representation.

ox
2.0 2.5 3.0
a
3.5 1 0

We now turn to the evaluation of the upper bound (19), again

using the code in (24) as an example. However, this time we use Fig. 10. Error Probability Bound as a Function of a.
the smaller graph in which nodes are identified only by the trellis
states (still only keeping track if bits are the same or different).
The code (24) thus requires’ four states. But note that we must We had noted earlier that the normalized minimum distance
begin with the transition 00 + 10, end with 01 + 00, and never coding gain for (24) was 2.5 dB, when ti = 2, and 3 dB, when
be at the state 00 in between. Hence, we may remove the state 00 a = 3. This gain is reflected in the upper bound as well.
from the graph if we remember these transitions. The resulting Finally we show that nonlinear k = 1 one-term codes3 have
three-state transition graph is shown in Fig. 9, and the edges dL,, = 8. Actually, we show coin = 8, but for one-term codes
again are labeled with a2 (2). dmin = ii&,.
Assume a fixed signal-to-noise ratio P/2a2 of 8 and exponen- In the notation of Fig. 5 let vi be the following sequence of
tiate the edge weights. To calculate exp (- a’( E)/802), we take (k + u)-dimensional edge vectors. Set ut = 10 . . . 0, and obtain
the path corresponding to i? and multiply the exponentiated edge u, + i by shifting the entries of vi one position to the right (k = l),
weights of that path. If dropping the right bit of u and inserting a new left bit so as to
have either vj+i = 0 . . . 01 p v* or, if this is not possible to have
x = exp( -8.4a2/4(1 + a’)) = exp( -8o1*/(1 + a”)) u, + i . b = 0. Here . denotes the mod 2 dot product, and b is the
binary vector associated with the one-term code. If the sequence
y = exp( -8.4/4(1 + a’)) = exp(-8/(1 + a’)) does indeed terminate at u*, then we get a contribution to the
squared distance of four from this term and from r+, and zero
z = exp( -8.4(a - 1)2/4(1 + a’))
from the other terms, yielding d2, = 8. We now prove that the
= exp( -8(cu - l)“/(l + a’)) sequence terminates at u* by proving that a given vector cannot
repeat.
then the state transition matrix A for Fig. 9 is given by Thus, suppose that vi = ui, i > 1. Then vi- I = 0 . . . O*, and
the process would have terminated at oi-i since the all-zero
10 01 11
vector can never occur (if it does, find when it first occurred and
10 Z Y go back one step).
Next, suppose that the first repeat occurs at step i and that 9
A= 01 1 has been repeated where 2 < j < i. Both v,-r and 4-i (which
exists since j > 1) precede vi and have zero inner product with b
11 Y Z (since j - 1 > 1). But they both cannot have zero inner product
H4
with b if they differ in the right-most bit (since i is minimal).
The contribution to
We thus are reduced to showing that uz cannot repeat using
$exp(-d2(&)/802) our rules. Note that 4 is either 0100 . . . or 1100 . . . . If v, = v,,
i > 2, then uiP2 has the form 0 . * . O**. The pair ** cannot be 00
made by all error events G?of length 1 is simply the (lO,Ol)-th since 0 cannot occur. If the pair is 01 we terminated at uim2 and
entry of Alm2 multiplied by x2. Hence, (19) can be written if its either 11 or 10, we must terminate at u,- i.

PI ic exp( -d2(g)/8a2) = ix2(A + A2 + . . .)l,,ol APPENDIX B

E A LOWER BOUND ON THE PERFORMANCE OF
TWO-TERM CODES
= +x2( Z - A),f,,
We derive a lower bound on the coding gain of k = 1 codes.
The method is a modification of that used by Massey [6] to
= -- 1 x2( z2 - z - y’) obtain an analog of the Gilbert bound for some convolutional
2 z2 - 22 - y2 + 1.
codes.
Consider the two-term code
Fig. 10 shows how the upper bound on error probability varies
with (Y. b, t- 2b,b,b,.
Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on September 02,2024 at 08:10:43 UTC from IEEE Xplore. Restrictions apply.
CALDERBANK AND MAZO: NEW DESCRIPTION OF TRELLIS CODES 791

9-w To and
ym = number of pairs 01 (score 16).
An output sequence is bad if
y+P+4ylh

l-wgTl
and the number of bad sequences is

There are 2” input sequences, and together an input sequence

Fig. 11. A convolutional encoder. and an output sequence determine the generator polynomial
G(x) that has degree I 2m - 1. If

The products b, , b, b, b3 determine the rate half-convolutional

code shown in Fig. 11. The input data stream
(25)
Z = Z(x) = i, + i,x + i2x2 + . . .
then we can find a code with the property that the first 2m
is related to the outputs To = T,(x) and Z’i = Ti( x) by outputs are guaranteed to be good. W e sketch a proof that (25)
To(x) = xz( x) holds for r( = 9/40 = 0.225.
Taking logarithms to base two, we have to show that
and
T,(x) = (1 + x + x2)1(x). H*(a) +(1 - a>ff2(8/(1 - a))

The interlacing of q and Tl is described by +(1 -a. - P>f&(Y/(l -a -P)) < 1

T(x) = T,(x2) + xT,(x’) whenever (Y + p + 4-r = X. Now the left side of the equation
simplifies to
= (x + x2 + x3 + x5)Z(x2). -(Ylogcr - p1ogp - ylogy
The polynomial G(x) = x + x2 + x3 + x5 is called the generu- -(l - a - p - y) log(1 - (Y - p - y)
tor polynomial of the convolutional code. The constraint length of
a convolutional code is the number of output symbols influenced and since -(Y log (Y - /I logp is maximized by setting LY= p =
by a given input signal. Then (X - 4y)/2, we must guarantee

constraint length = 1 + deg G( x) = 2( 1 + u) -(0.225 - 4~) log((0.225 - 4y)/2) - ylogy -

where u is the memory of the code. (0.775 + 3y) log(O.775 + 3y) < 1.
The performance of convolutional codes is usually measured
by the free distance, which is the minimum weight of all nonzero It can be checked that this is indeed the case.
output sequences. W e shall divide the output sequence into 2-bit Since we have been considering two-term codes for which the
blocks and score the 2-bit blocks as power P = l2 + 2’ = 5, we have proved that

00 I 0

The upper bound for k = 1 codes derived in [4] gives

The score of the output sequence is the sum of the contributions
from each two-bit block. The state of the shift register is to be * sf(2 + u).
thought of as an edge vector. The score of the corresponding
two-bit block is the lower bound on the contribution to the
squared distance given by (18). Thus, d,$, is the minimum score REFERENCES
over all output sequences.
Other two-term codes II b, k II bi determine rate half-convolu- [l] 0. Agazzi, D. G. Messerschmitt,and D. A. Hodges, “Nonlinear echo
cancellation of data signals,” IEEE Trans. Commun. Technol., vol.
tional codes in exactly the same way. The output T(x) and input COM-30, no. 11, pp. 2421-2433, Nov. 1982.
Z(x) are related by T(x) = G(x)Z(x2), where G(x) is the [2] D. Slepian, “On maxentropic discrete stationary processes,”Bell
generator polynomial of the code. For a fixed integer m we Syst. Tech. J., vol. 51, no. 3, pp. 629-653, Mar. 1972.
consider the set of all rate half-convolutional codes for which the [3] G. Ungerboeck, “Channel cc&g with multilevel/phase signals,”
constraint length is no more than 2m. W e shall prove that there IEEE Trans. Inform. Theorv. vol. IT-28. no. 1. DD. 55-67. Jan. 1982.
[4] A. R. Calderb&k, J. E. M&o, and H. M. Shapiro, “Upper bounds
exist codes (generator polynomials) with the property that the on the minimum distance of trellis codes,”Bell Syst. Tech J., vol. 62,
score of the first 2 m outputs is guaranteed to be at least 4Xm, no. 8, pp. 2617-2646, Oct. 1983.
where X is a constant to be optimized later. [5] A. J. Viterbi and J. K. Omura, Principles of Digital Communication
Given an output sequence of length 2m consisting of m 2-bit and Coding. New York: McGraw-Hill, 1979, Section 4.4.
pairs let [6] J. L. Massey, “Some algebraic and distance properties of convolu-
tional codes,” in Error-Correcting Codes, H. B. Mann Ed. New
am = number of pairs 10 (score 4) York: John W iley, 1969, pp. 89-109.
[7] M. Harwit and N. J. A. Sloane, Hadumard Transform Optics. New
j3m = number of pairs 11 (score 4) York: Academic, 1979.
Authorized licensed use limited to: Georgia Institute of Technology. Downloaded on September 02,2024 at 08:10:43 UTC from IEEE Xplore. Restrictions apply.