TRELLISES AND TRELLIS-BASED

DECODING ALGORITHMS FOR

LINEAR BLOCK CODES

Part !

Shu Lin and Marc Fossorier

January 15, 1998

 1 INTRODUCTION

1.1 TRELLIS REPRESENTATION OF CODES

A code trellis is a graphical representation of a code, block or convolutional, in

which every path represents a codeword (or a code sequence for a convolutional
code). This representation makes it possible to implement maximum likelihood
decoding (MLD) of a code with reduced decoding complexity. The most well
known trellis-based MLD algorithm is the Viterbi algorithm [23, 79, 105]. The
trellis representation was first introduced and used for convolutional codes [23].
This representation, together with the Viterbi decoding algorithm, has resulted
in a wide range of applications of convolutional codes for error control in digital
communications over the last two decades.
The recent search for efficient MLD schemes for linear block codes has moti-

vated some coding theorists to study the trellis structure of these codes so that
trellis-based decoding algorithms can be devised to reduce decoding complexity.
Trellis representation of linear block codes was first presented in [1] and then

D R A F T January 6, 1998, 8:40pm D R A F T

2 TRELLISES
AND TRELLIS-BASED DECODING ALGORITHMS

in [67, 109]. The first serious study of trellis structure and trellis construction
for linear block codes was due to Wolf. In his 1978 paper [109], Wolf presented
the first method for constructing trellises for linear block codes and proved that
an N-section trellis diagram for a q-ary (N, K) linear block code has at most
qmla(K,N-K) states. He also presented a method for labeling the states based on
the parity-check matrix of a code. Right after Wolf's work, Massey presented
a simple but elegant paper [67] in which he gave a precise definition of a code
trellis, derived some fundamental properties, and provided implications of the
trellis structure for encoding and decoding of codes. However, these early works
in trellis representation of linear block codes did not arouse much enthusiasm,
and for the next 10 years, there was basically no research in this area.

There are two major reasons for this inactive period of research in this area.
First, most coding theorists at that time believed that block codes did not have
simple trellis structure like convolutional codes and maximum likelihood decod-
ing of linear block codes using the Viterbi algorithm was practically impossible,
except for very short block codes. Second, since almost all of the linear block
codes are constructed algebraically or based on finite geometries, it was the
belief of many coding theorists that algebraic decoding was the only way to
decode these codes. These two reasons seriously hindered the development of
efficient soft-decision decoding methods for linear block codes and their appli-
cations to error control in digital communications. This led to a general belief
that block codes are inferior to convolutional codes and hence, that they were
not useful.

In fact, for more than two decades, most of the practicing communication
engineers believed that the rate-l/2 convolutional code of constraint length 7
with Viterbi decoding was the only effective error control coding scheme for
digital communications, except for perhaps ARQ schemes. To achieve higher
reliability for certain applications such as NASA's satellite and deep space
communications, this convolutional code concatenated with a Reed-Solomon
outer code was thought the best solution.

It was really Forney's paper in 1988 [24] that aroused enthusiasm for research
in the trellis structure of linear block codes. In this paper, Forney showed that
some block codes, such as Reed-Muller (RM) codes and some lattice codes,
do have relatively simple trellis structures, and he presented a method for con-

D R A F T January 6, 1998, 8:40pm D R A F T

 INTRODUCTION
3

structingsectionalized
trellises
forlinearblock codes and assertedthatthe con-

structionresultsin minimal trellises

with respect to the statecomplexity (the
number of states).Motivated by Forney's work and the desireto achievemax-
imum likelihooddecoding of linearblock codes to improve errorperformance
over traditionalhard-decisionalgebraicdecoding, there have been significant
efforts
instudying the trellis
structureand devisingtrellis-based
decoding algo-
rithms forlinearblock codes over the lasteightyears. Developments have been
dramatic and rapid,and the new resultsare excitingand [Link]-
based decoding algorithmsthat are more efficient
than the conventionalViterbi
decoding algorithm have recentlybeen devised [32,37] and implementation of
trellis-based
high-speed decoders for NASA's high-speed satellite
communica-
tionsisnow underway [52,63].All ofthese new developments make block codes
more competitive with convolutionalcodes.

1.2 ORGANIZATION OF THE BOOK

Chapter 2 gives a brief review of linear block codes. The goal is to provide
the essential background material for the development of trellis structure and
trellis-based decoding algorithms for linear block codes in the later chapters.
Chapters 3 through 6 present the fundamental concepts, finite-state machine
model, state space formulation, basic structural properties, state labeling, con-
struction procedures, complexity, minimality, and sectionalization of trellises.
Chapter 7 discusses trellis decomposition and subtrellises for low-weight code-
words. Chapter 8 first presents well known methods for constructing long
powerful codes from short component codes or component codes of smaller
dimensions, and then provides methods for constructing their trellises which
include Shannon and Cartesian product techniques. Chapter 9 deals with con-
volutional codes, puncturing, zero-tall termination and tail-biting. It shows
that trellis construction procedures for both block and convolutional codes are
essentially the same, except that the trellises for convolutional codes or termi-
nated convolutional codes are time-invariant and the trellises for block codes
are in general time-varying. For both types of codes, trellis states are defined
based on a certain set of information bits, called the state-defining information
set.

D R A F T January 6, 1998, 8:40pm D R A F T

4 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Chapters 10 through 13 present various trellis-based decoding algorithms,

old and new. Chapter 10 first discusses the application of the well known
Viterbi decoding algorithm to linear block codes, optimum sectionalization of
a code trellis to minimize computation complexity, and design issues for IC
(integrated circuit) implementation of a Viterbi decoder. Then it presents a
new decoding algorithm for convolutional codes, named differential trellis de-
coding (DTD) algorithm. DTD algorithm is devised based on the principle of
compare-select-add (CSA) which is simply the opposite of the principle of
add-compare-select (ACS) used in the Viterbi algorithm. This new algo-
rithm is more efficient than the Viterbi decoding algorithm. For rate-l/2 an-
tipodal convolutional codes and their higher rate punctured codes, it requires
about 1/3 less real number operations than the Viterbi decoding algorithm.
This DTD algorithm can also be applied to trellis decoding of block codes.
Chapter 11 presents a trellis-based recursive MLD for linear block codes, the
RMLD algorithm. This decoding algorithm is devised based on the divide
and conquer principle. The implementation of this algorithm does not re-
quire the construction of the entire code trellis; only some special one-section
trellises of much smaller state and branch complexities for constructing path
metric tables recursively are needed. This reduces the decoding complexity
significantly and it is more efficient than the Viterbi decoding algorithm. Fur-
thermore, it allows parallel/pipeline processing of received sequences to speed
up decoding. Chapter 12 presents a suboptimum reliability-based iterative de-
coding algorithm with a low-weight trellis search for the most likely codeword.
This decoding algorithm provides a good trade-off between error performance
and decoding complexity. All the decoding algorithms presented in Chapters 10
through 12 are devised to minimize word error probability. Chapter 13 presents
decoding algorithms that minimize bit error probability and provide the corre-
sponding soft (reliability) information at the output of the decoder. Decoding
algorithms presented are the MAP (maximum a posteriori probability)
decoding algorithm and the SOVA (soft-output Viterbi algorithm) algo-
rithm. Finally, the minimization of bit error probability in trellis-based MLD
is discussed.

D I% A F T January 6, 1998, 8:40pm D R A F T

 LINEAR BLOCK CODES

Chapter 2 gives a brief review of linear block codes. The goal is to provide
the essential background material for the development of trellis structure and
trellis-based decoding algorithms for linear block codes in the later chapters.
We mainly present the basic concepts of encoding and decoding of linear block
codes and state some facts without derivations or proofs. Since in most present
digital data communication systems, information is coded in binary digits, '0'
or '1', we discuss only linear block codes with symbols from the binary field
GF(2). First, linear block codes are defined and described in terms of generator
and parity-check matrices. Second, coset partition of a linear block code is dis-
cussed, which is needed in analyzing the code trellis structure and construction.
Third, the concepts of minimum distance, weight distribution and distance pro-
file are presented, which are needed in the later chapters for presenting decoding
algorithms and their error performances. Finally, the concepts of hard-decision,
soft-decision, and maximum likelihood decoding are presented.

D R A F T January 6, 1998, 8:40pro D R A F T

6 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

References 3, 9, 14, 59, 63, 78 and 79 contain excellent treatments of linear

block codes.

2.1 GENERATION OF LINEAR BLOCK CODES

In block coding, an information sequence of binary digits (called bits) is divided

into message blocks of fixed length; each message block consists of K informa-
tion bits. There are a total of 2 K distinct messages. Each message is encoded

into a codeword (or code sequence) of N bits according to certain rules, where
N > K. Therefore, corresponding to the 2 K possible messages, there are 2 K
codewords. This set of 2 K codewords forms a block code of length N. For
a block code to be useful, the 2 K codewords must be distinct. Hence, there
should be a one-to-one correspondence between a message and a codeword.

Definition 2.1 A binary block code of length N and 2 K codewords is called an

(N, K) linear block code if and only if its 2 m codewords form a K-dimensional
subspace of the vector space of all the N-tuples over the binary field GF(2).
The parameter K is called the dimension of the code space.

An (N,K) linear block code C is generated by a K x N generator matrix

over GF(2),

gl glt g12 "'" gtl "'" gin

g2 g21 g22 "'" g2i "'" g2N
C= •
= . : ° .
(2.t)

gK gKt gK2 "'" gKi "'" gKN

where the rows, gl, g2, ..., gK, are linearly independent over GF(2). The 2 K
linear combinations of the K rows of G form the codewords of C. We say that
the rows of G span the code C, or C is the row space of G. Let

O. = (a1,tt2,...,aK)

be a message to be encoded. A natural encoding mapping is that the codeword

= (-I,-2, ,-.)
for the message a = (at,a2,... ,aK) is given by

D R A F T January 6, 1998, 8:40pro D R A F T

 LINEAR BLOCK CODES '7

gl

= ("1,_= ...,aK) g2

gK

= al "gl -t-a= "g2 -t-... -I-aK ".qK. (2.2)

From (2.1) and (2.2), we find that for 1 < i < N, the i-th component of u is

given by
ui = at • gl_ -F a2 • g2i +"" + aK • gK_. (2.3)

During an encoding interval, K information bits are encoded into N code

bits. These N code bits are shifted onto the channel, one at a time, in N units

of time. An encoding interval, denoted F, is represented by a set of N + 1 time

instants,

F = {0, 1,2,... ,g}. (2.4)

For 1 < i < N, the i-th unit of time is the interval from time-(/- 1) to time-/.

During this interval, the i-th code bit u, is formed and transmitted. By time-i,
the transmission is completed. This interval is called a bit interval.

Example 2.1 Consider a binary (8, 4) linear block code which is generated by

the following generator matrix:

gl I I I I I I I I

G= g2 = 0 0 0 0 1 1 1 1 (2.5)
g3 0 0 I 1 0 0 1 1

g4 0 1 0 1 0 1 0 1

If a = (1101) is the message to be encoded, its corresponding codeword, ac-

cording to (2.2), is given by

U = l.g1+[Link]+O.g3+l.g 4

= (11111111)-I- (00001111)+ (01010101)

---- (10100101).

The 16 codewords of this code are listed in Table 2.1.

AA

D R A F T January 6, 1998, 8:40pm D R A F T

8 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Table 2.1. The codewordsof the code generatedby (2.5).

Messages Codewords Messages Codewords

(oooo) (oooooooo) (oool) (01010101)

(lOOO) (11111111) (lOOl) (10101010)
(OLOO) (00001111) (OlOl) (01011010)
(11oo) (11110000) (11Ol) (10100101)
(0010) (00110011) (0011) (01100110)
(1010) (11001100) (1011) (10011001)
(0110) (00111100) (0111) (01101001)
(1110) (11000011) (1111) (10010110)

A binary (N, K) linear block code C is also uniquely specified by an (N -

K) x N matrix over GF(2), called a parity-check matrix,

hll ht2 "" AtN

h21 h22 "'" h2N
H= (2.6)
: ".. :

hN-K,t hN-K,2 "'" hN-K,N

where the rows are linearly independent. A binary N-tuple u = (ut, u2,..., UN)
is a codeword in C if and only if the following condition holds:

u-H T = 0, (2.7)

where 0 denotes the all-zero (N - K)-tuple, (0,0,...,0). Code C is called

the dual (or null) space of H. H itself generates an (N, N - K) linear code,
denote C ±. For any codeword u = (ul,u2,... ,UN) E C and any codeword
u = (vl,v2,... ,vjv) E C ±, the inner product

&
1/,.1) = U l .U 1 +U 2.u 2 +... + U N.u N

= O.

C -L is called the dual code of C and vise versa.

D R A F T January 6, 1998, 8:40pm D R A F T

 LINEAR BLOCK CODES 9

In general, the generator matrix G of a linear block code C is used for

encoding, while the parity-check matrix H is used for decoding, particularly
for error detection.

Example 2.2 Consider the (8,4) linear block code given in Example 2.1. A
parity-check matrix for this code is the generator matrix itself given by (2.5),
i.e°_

I 1 1 1 I 1 1 i
0 0 0 0 1 1 1 1
H =G-._
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1

In thiscase,C = C ± and C issaid to be self-dual.

AA

For an (N, K) linear block code C, the ratio R = K/N is called the code
rate which represents the average number of information bits carried by a code
symbol (or the average number of information bits transmitted per channel
usage).

2.2 COSET PARTITION OF A LINEAR BLOCK CODE

Consider a binary (N, K) linear block code C with a generator matrix G. Let
K1 be a nonnegative integer such that 0 < K1 _< K. A subset of 2 K' codewords
in C is said to be a linear subcode of C if this subset itself is a/(1-dimensional
subspace of the vector space of all the N-tuples over GF(2). Any K1 rows of
the generator matrix G span an (N, K1) linear subcode of C, and they form a
generator matrix for the subcode. If KI = 0, the subcode consists of only the
all-zero codeword 0 of C. For Kl = K, the subcode is just the code itself.
Let C1 be an (N, K1) linear subcode of C. Then C can be partitioned into
2 g-g_ disjoint cosets of C1; each coset is of the following form:

vLe C1 _ {vl +u: u e C1} (2.8)

with 1 < l < 2 K-K_, where for vl _ O, vl is in C but not in C1 and for vl = O,
the coset 0 _ C1 is just the subcode C1 itself. This partition of C with respect
to C1 is denoted with C/CI, and the codeworcls v_ for 1 < l < 2 N-K_ are called

D R A F T January 6, 1998, 8:40pro D R A F T

10 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

the coset representatives. Any codeword in a coset can be used as the coset
representative without changing the composition (the codewords) of the coset.
Important properties of cosets are:

(1) The sum of two codewords in a coset is a codeword in the subcode Cl.

(2) Let z and y be two codewords in cosets vi@C1 and vj _3C1 , respectively,
where i _ j. Then the sum _:+y is a codeword in the coset (vi+vi)t_C1
with vi + vj as the coset representative.

The set of representatives for the cosets in the partition C/C1 is denoted [C/CI]
which is called the coset representative space for the partition C/C1. Code
C can be expressed a.s the direct-sum of C1 and [C/C1] as follows:

C = [C/Cl] _9 Cl a_ {v + u: v E [C/Cl] and 'u E C'1}. (2.9)

Let G1 be the subset of K1 rows of the generator matrix G which generates

the subcode C1. Then the 2 K-K1 codewords generated by the K - K1 rows in
the set G \ G1 can he used as the representatives for the cosets in the partition
C/C1. These 2 K-El codewords form an (N,K - K1) linear subcode of C.
Let Cs be an (N, Kz) linear subcode of C1 with 0 < Kz < K1. We can
further partition each coset vz $ C1 in the partition C/C1 based on Cs into
2KI-K2 cosets of Cs; each coset consists of the following codewords in C:

• • -'--{,.,,+ + ,.,: ,, (2.1o)

with 1 < l < 2 K-KI and 1 < k < 2 Kt-K2 where for wk # O, wk is a codeword
in C1 but not in Cs. We denote this partition with C/C1/Cs. This partition
consists of 2 K-K2 cosets of C=. Now C can be expressed as the following
direct-sum:

C = [C/C, l • [C,/Cs] _) C2. (2.11)

Let C1, Cs,..., C,_ be a sequence of linear subcodes of C with dimensions

K1, Ks,..., Kin, respectively, such that

C D Cl D (72 D... _DCm (2.12)

and

K > KI >/(2 _... _> Kin_> 0. (2.13)

D 1% A F T January 6, 1998, 8:40pro D 1%A F T

 LINEAR
BLOCK
CODES 11

Then we can form a chain of partitions,

C/C1, C/C1/O2,..., C/C1/C,.J,/.../C,,.,, (2.14)

and C can be expressed as the following direct-sum:

C = [C/C,] • [c,/c_] e... • [c,,,_,/c,,,] • c,,,. (2.15)

2.3 THE MINIMUM DISTANCE AND WEIGHT DISTRIBUTION OF A

LINEAR BLOCK CODE

Let u and v be two N-tuples over GF(2). The Hamming distance between
u and v, denoted d(u, v), is defined as the number of places where they differ.
The minimum (Hamming) distance of a block code C, denoted drain(C),
is defined as the minimum Hamming distance between all distinct pairs of
codewords in C, i.e.,

dr, i.(C) _ min{d(u,v) : u,v E C,u :p v}. (2.16)

The (Hamming) weight of an N-tuple v, denoted w(v), is defined as the

number of nonzero components of v. It follows from the definition of Hamming
distance and the fact that the sum of two N-tuples over GF(2) is an another
N-tuple over GF(2) that the Hamming distance between two N-tuples, u and
v, is equal to the Hamming weight of the sum of u and v, i.e.,

d(u,v) = w(u + v). (2.17)

For a linear block code C, it follows from (2.16) and (2.17) that

drain(C) = min{w(u+v):u, vEC, u#v}

= min{w(x): x E C,x _ O}

*-- (2.18)

The parameter Wmi,(C) A min{w(x) :x E C,x _ O} iscalledthe minimum

weight ofC. Eq.(2.18)simply saysthat the minimum distanceofa linearblock
code isequal to the minimum weight of itsnonzero codewords. The minimum

D R A F T January 6, 1998, 8:40pm D R A F T

12 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

weight of the (8,4) linear block code given in Table 2.1 is 4; therefore, its
minimum distance is 4.

Let C be an (N, K) linear block code. For 0 < i < N, let Ai be the number
of codewords with weight i. The numbers Ao,A1,A2,... ,AN are called the
weight distribution of C. It is clear that A0 = 1. The weight distribution of
the (8,4) linear block code given in Table 2.1 is

A0= 1, A1 =A2=Aa=0, A4 = 14, As =A6=AT=0, As=l.

The weight distribution is often expressed as a polynomial,

A(X) = Ao + A_X + ...+ ANX N,

which is calledthe weight enumerator of C. Let W = {O,wx,w2 ....,win}

denote the setof allweights of codewords in C such that:

(i) 0 < wl < w2 < "" <wm < N; and

(ii) For I < i < m, the number of codewords in C with weight wi is not
equal to zero.

This set is called the weight profile of C. The weight profile of the (8, 4)
linear block code given by Table 2.1 is {0,4,8}. Let u be any codeword in
C. The weight distribution of C actually gives the distribution of distances of
codewords in C from the codeword u. The weight profile W of C gives the
profile of distances of codewords in C from the codeword u.
The error performance of a linear block code is determined by its minimum
distance and weight distribution. For an (N, K) linear block code with min-
imum distance drain, we often use the notation (N,K, dmin) to represent the
code. Therefore, the code given by Table 2.1 is an (8, 4, 4) linear block code.

2.4 DECODING

Suppose an (N, K) linear block code C is used for error control over an ad-
ditive white Gaussian noise (AWGN) channel. Let u = (ul,uz,...,ut¢) be
the codeword to be transmitted. Before the transmission, a modulator maps
each code bit into an elementary signal waveform. Binary PSK or FSK are
commonly used signal waveforrns for transmitting the bits in a codeword. The

D R A F T January 6, 1998, 8:40pm D R A F T

 LINEAR BLOCK CODES 13

resultant signal sequence is then transmitted over the channel and corrupted
by noise. At the receiving end, the received signal sequence is processed by a
demodulator and sampled at the end of each signal (bit) interval. This results

in sequence of real numbers,

r =
which is called the received sequence. For 1 < i < N, the i-th received
component ri is the sum of a fixed real number ci and a Gaussian random
variable nl of zero-mean and variance No/2 where ci corresponds to the trans-
mitted code bit ul at time-/. These received components may or may not be
quantized. At one extreme, the demodulator can be used to make firm deci-
sions on whether each transmitted code bit is a '0' or a '1'. Thus the output

is quantized to two levels, denoted as 0 and 1. We say that the demodulator

has made a "hard decision" on each transmitted code bit. This hard decision
results in a binary received sequence,

z = (zl, zM),

which may contain transmission errors, i.e., for some i, zl # ui. This bi-
nary hard-decision sequence is fed into a decoder which attempts to correct the
transmission errors (if any) and recover the transmitted codeword u. Since the
decoder operates on the hard decisions made by the demodulator, the decoding
process is called hard-decision decoding. At the other extreme, the unquan-
tized outputs from the demodulator can be fed directly into the decoder for pro-
cessing. We refer to the resulting decoding as soft-decision decoding. Since
the decoder makes use of the additional information contained in the unquan-
tized received samples to recover the transmitted codeword, soft-decision decod-
ing provides better error performance than hard-decision decoding. Decoding
based on the quantized outputs from the demodulator, where the number of
quantization levels exceeds two, is also referred to as soft-decision decoding.
Soft-decision decoding provides better error performance than hard-decision
decoding; however, hard-decision decoding is much simpler to implement. Var-
ious hard-decision decoding algorithms based on the algebraic structures of
linear block codes have been devised. These hard-decision decoding algorithms
are also termed algebraic decoding algorithms. Recently, effective soft-decision

D R A F T January 6, 1998, 8:40pm D R A F T

14 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

decoding algorithms have been devised, and they achieve either optimum error

performance or suboptimum error performance with reduced decoding com-

plexity.

Let u" be the estimate of the transmitted codeword at the output of the

decoder. If the codeword u was transmitted, a decoding error occurs if and

only if u" _ u. Given that r is received, the conditional error probability of

the decoder is defined as

P(Elr ) A P(u" # u I')- (2.19)

The error probability of the decoder is then given by

P(E) = __, P(E 1 r)P(r). (2.20)

P

P(r) is independent of the decoding rule used since r is produced prior to

decoding. Hence, an optimum decoding rule (i.e.,one that minimizes P(E))

must minimize P(E I r) = P(u" _ u [ r) for all r. Since minimizing P(u" #

u I r) is equivalent to maximizing P(u" = u It), P(E I r) is minimized for a

given r by choosing u" as the codeword that maximizes

P(u It) = P(r I u)P(u)

P(r) ' (2.21)
that is, u" is chosen as the most likely codeword given r is received. If all

the codewords are equally likely,maximizing (2.21) isequivalent to maximizing

P(r I u). For an AWGN channel,

P(r l u) = H P(r, l u,), (2.22)

i=l

since each received symbol depends on the corresponding transmitted symbol.

A decoder that chooses its estimate to maximize (2.22) is called a maximum

likelihood decoder and the decoding process is called the maximum like-

lihood decoding (MLD). Maximizing (2.22) is equivalent to maximizing

logV(r l u) = _logP(r, l ui) (2.23)

i=1

which is called the log-likelihood function.

D R A F T January 6, 1998, 8:40pro D R A F T

 LINEAR BLOCK CODES 15

Suppose BPSK signaling is used. Assume that each signal has unit energy.

Let u -- (ul,u_,... ,UN) be the codeword to be transmitted. The modulator

maps this codeword into a bipolar sequence represented by

c = (cl,c2,...,CN)

where for 1 < i < N,

cl = 2u_ - 1. (2.24)

From (2.24), we see that

c, = (2.25)
-1,
4"1, if ui
if ui = 0,
= 1.

The squared Euclidean distance between the received sequence r = (rl, r2,

• .., rN) and c is given by

Ir - cl2 A _(r, - c,) 2. (2.26)

i=1

For an AWGN channel, maximizing the log-likelihood function is equivalent to

minimizing the squared Euclidean distance between r and c. If we expand the

right-hand side of (2.26), we have

N N N

- cl2= r, -
i=1 i=l i=1

In computing Ir - cl 2 for all codewords in C, _N=I r, 2 is a common term and

EN__,
c,2 = g. Therefore, minimizing Ir - cl 2 of (2.26) is equivalent to maxi-

mizing

r •C : ri • ci
i--1
N

= 1). (2.28)
i=1

The inner product given by (2.28) is called the correlation between the re-

ceived sequence r and the codeword u.

D R A F T January 6, 1998, 8:40pm D R A F T

16 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Furthermore, (2.28) can be expanded as follows:

N N

r.c = 2_: r,.,, - _ r,. (2.29)

i=1 i=1

Since the second term EN=, r, in (2.29)is a common term in computing r. c

for allcodewords in C, maximizing r •c isequivalentto maximizing

r'u a= _ r_. ,,. (2.30)

i=I

The inner product given by (2.30) is called the binary correlation between
the received sequence r and the codeword u.
Summarizing the above, MLD can be stated in four equivalent ways:

(1) Log-likelihood function

Decode the received sequence r into a codeword u for which the log-
likelihood function
N

log P(r ]u)= y_ log P(r, l tt,)

i=1

is maximized.

(2)Squared Euclidean distance

Decode the received sequence r into a codeword u for which the squared
Euclidean distance
N

I_- =1_A _(_, - (2., - 1))_

i=1

is minimized.

(3) Correlation function

Decode the received sequence r into a codeword u for which the corre-
lation function
iv

i=1

is maximized.

D R A F T January 6, 1998, 8:40pm D R A F T

 LINEAR BLOCK CODES 17

(4) Binary correlation function

Decode the received sequence r into a codeword u for which the binary
correlation function
N
b(r, u) = E r, . ui
i=1
is maximized.

2.5 REED-MULLER CODES

i

Reed-Muller (RM) codes form a class of multiple error-correction codes. These

codes were discovered by Muller in 1954 [78], but the first decoding algorithm
for these codes was devised by Reed, also in 1954 [83]. They are finite geometry
codes and rich in algebraic and geometric structures. The purpose of including
these codes in this reviewing chapter is that they have very simple and regular
trellis structures and their trellises can be easily constructed. These codes can
be decoded effectively with trellis-based decoding algorithms. Furthermore,
they provide good example codes. Throughout this book, many example codes
are RM codes.
For any nonnegative integers rn and r with 0 < r < m, there exists a binary
r-th order RM code, denoted RMr,m, with the following parameters:

Length Nr.m -- 2 m
Dimension Kr,,,_ = 1 + (_') +... + (7)
Minimum distance d.,,,_ = 2 '_-'.

In the following, we first present the original construction of RM codes and

then we describe an alternate construction for these codes. For 1 < i < m , let
vi be a 2m-tuple over GF(2) of the following form:

v, = (,_,_ I_ 0_,_..., I_,_,) (2.31)

2,-1 2,-t 2,-I 2i-t

which consists of 2 m-i+1 alternate all-zero and all-one 2i-Z-tuples. For m = 3,

we have the following three 8-tuples:

v3 = (00001111),

v2 = (00110011),

vl = (01010101).

D R A F T January 6, 1998, 8:40pm D R A F T

18 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Let a = (at,a2,...,aN) and b = (bl,b2,...,bN)be two binary N-tuples.

Define the followinglogic(boolean) product of a and b,

a.b =A (al. bl,a2, b2,... ,aN" blv),

where '.' denotes the logic product (or AND operation), i.e. ai • bi = 1 if and
only if both al and bl are '1'. For m = 3,

v3 • u1 = (00000101).

For simplicity,
we use ab for a. b.
Let 1 denote the ail-one2_n-tuple,
1 = (I,i,...,I). For I __il < iz < ...<
iz__m, the product

t_ixUi2 " " " _il

is said to have degree I. Since the weights of v l, v2,..., um are even and powers
of 2, it can be shown that the weight of the product vilvi3 ... vi, is also even
and a power of 2, in fact 2 "_-l.
The r-th order RM code, RM,.,m, of length 2 "_ is generated by the following
set of vectors:

GRM(r,m) = {1,VhV2,...,V,_,VlV2,VlV3,...,V,,_-lV,_,

...up to products of degree r). (2.32)

There are
m

÷(:)
vectors in GaM(r,m) and they are linearly independent. If the vectors in
GRM(r,m) are arranged as rows of a matrix, then the matrix is a generator
matrix of the RM code, RMr,m. For 0 < l < r, there are exactly ('_) rows
in GaM(r,m) of weight 2 m-l. All the codewords of the RM code, RM_,m with
0 <_ r < m, have even weights. It is also clear that the (r - 1)-th order RM
code, RM,-1,,_, is a proper subcode of the r-th order RM code, RM ....

D R A F T January 6, 1998, 8:40pm D R A F T

 LINEAR BLOCK CODES 19

Example 2.3 Let rn = 4. The 2nd order RM code of length 16 isgenerated

by the followingII vectors:

v0 =1 1111111111111111
v4 0000000011111111
va 0000111100001111
_ 0011001100110011
Vl 0101010101010101
v3v4 0000000000001111
v2v4 0000000000110011
vlv4 0000000001010101
v2v3 0000001100000011
vlv3 0000010100000101
vlv2 0001000100010001

This is a (16, 11) code with minimum distance 4.

AA

The code given in Example 2.1 is the 1st order RM code, RM1,3, of length 8.
Let

G(2'2)_ [ 10 11 ] (2.33)

be a 2 x 2 matrix over GF(2). The two-fold Kronecker product of G(2,2) is

defined as

G(2"2') 0 1 1]
1]o[I 0 I

1 1 1 1
0 1 0 1
(2.34)
0 0 1 1
0 0 0 1

where ® denotes the Kronecker product. The 3-foldKronecker product of

G(2,2)isdefinedas

D R A F T January 6, 1998, 8:40pm D R A F T

20 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1
(2.35)
0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1

Similarly, we can define the m-fold Kronecker product of G(z,z). Let N = 2 m.

We use G(N,jv) to denote the m-fold Kronecker product of G(a,2). G(t¢,#) is a
2 m x 2 'n matrix over GF(2). The rows of G(tc,_t) have weights, 2 °, 21, 22,..., 2 m,
and the number of rows with weight 2 'n-t is ('_) for 0 < l < m.
The RM codes of length N = 2 m can be expressed in terms of the rows of
G(N#v). Let GaM(r,m) denote the matrix formed by the rows of G(_¢,/¢) with
weights equal to or greater than 2 m-r. Then GRM(r,m) is a generator matrix
for the r-th order RM code, RM .... of length N = 2" [24]. Actually, GRM (r, m)
is the same set of rows as that given in (2.32). In the above construction of
RM codes, we can also set the base matrix G(2,2) of (2.33) as

For m = 3 and r = 1, the rows of weights 4 and 8 in G{2_,23) of (2.35) form

the generator matrix of the 1st order (8,4) RM code given in Example 2.1.
Let u = (ul,u2,...,ulv) and v = (vl,v2,...,vlv) be two N-tuples over
GF(2). From u and v, we form the following binary 2N-tuple:

+ v[ + vl.... + vN). (2.36)

Let C1 and C2 be an (N, Kl,dl) and an (N, K2,d2) binary linear codes, re-
spectively. Assume that d2 > dl. Form the following code:

ICIICI+ C21 _= {lulu + vl: u e CI and u 6 C_}. (2.37)

Then IC, lC_ + C21 is an (2N,/(1 +/(2, d) binary linear code with

d -- min{2dl, dz}. (2.38)

D R A F T January 6, 1998, 8:40pm D R A F T

 LINEAR BLOCK CODES 21

The above construction of a code from two component codes is called the

[ulu + vl-construction [66] which is a powerful technique for constructing pow-

erful long codes from short codes.

RM codes of length 2rn can be constructed from RM codes of length 2 m-I

using the lulu + vl-construction [66]. For m > 2, the r-th order RM code

RMr,_ in lulu + _l-construction is given below:

RM,, = {l ,lu + ,,1: • .... 1 v • RM,_,.m_J (2.39)

with generator matrix

VaM(r,m) = [ GaM(r, 0 rn--1) GaM(r,m--1)

Gau(r- 1,m- 1) ] ' (2.40)

where 0 is a zero matrix. Equation (2.40) shows that a RM code can be

constructed from short RM codes by a sequence of lulu + vl-constructions.

Consider a boolean function f(xl, x2,..., zm) of m variables, xl, x2,. • •, xm,
which take values 0 or 1. For each combination of values of xl, x2,.. •, and xm,

the function f takes a truth value either 0 or l. For the 2 "_ combinations of

values of xl,x2,... ,xm, the truth values of f form a 2m-tuple over GF(2).

For a nonnegative integer I less than 2 "_, let (ba, bz2,..., him) be the standard

binary representation of 1, such that I = ba + bl_ 2 + bla 2_ +-'" + btm2 m- 1. For a

given boolean function f(xl, _2,..., xm), we form the following 2"_-tuple (truth

vector):
v = (vl,v2,... ,v,+l,... ,v2-) (2.41)

where

111+ 1 A f(ba,b_2,... ,blm) (2.42)

and (bn, hi2,..., bl,_) is the standard binary representation of the index integer

I. We say that the boolean function f(zl,z2,... ,x_) represents the vector v.

We use the notation b(f) for the vector represented by f(zl, x2,..., xm).

For 1 < i < m, consider the boolean function

f(xl,X2,... ,x,n) = x,. (2.43)

It is easy to see that this boolean function represent the vector vi defined by

(2.31). For 1 < i,j < m, the function

= (2.44)

D R A F T January 6, 1998, 8:40pro D R A F T

22 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

representsthe logicproduct of ui and vj, representedby g(zt,z2,...,z,_)= =i

and h(=1,z2,...,z,_) = =i, respectively.
For 1 < ii < i2 < ...< i, __m, the
boolean function

f(x1,=2,...,=m) = x,,=h ""=,, (2.45)

representsthe logicproduct of _iL,ui2,...,and uir. Therefore,the generator

vectors of the r-th order RM code of length N -- 2m are representedby the
boolean functionsin the followingset

= =-,-1=,,,,
... up to all products of r variables}. (2.46)

Let P(r,m) denote the set of allboolean functions(orpolynomials) of degree

r or lesswith m [Link]

RM,,_, = {b(f) : f E P(r,m)}. (2.47)

Finally,we want to point out that the dual code of the r-thorder RM code,
RM ....is the (rn- r - 1)-thorder RM code, RM .... 1,m.

D R A F T January 6, 1998, 8:40pm D R A F T

 3 TRELLIS REPRESENTATION OF
LINEAR BLOCK CODES

A code trellis is a graphical representation of a code, block or convolutional, in

which every path represents a codeword (or code sequence). This representation
makes it possible to implement maximum likelihood decoding (MLD) of a code
with a significant reduction in decoding complexity. Chapter 3 presents the
fundamental concepts and basic structural properties of trellises for linear block
codes. An encoder with finite memory for a linear code is modeled as a finite-
state machine. With this model, representation of the dynamic behavior of the
encoder by a trellis diagram is easy to conceive. During an encoding interval,
the state of the encoder at a specific time instant is simply defined by the
information bits stored in the memory which affect both the past and future
outputs of the encoder. To facilitate the construction of a code trellis, the
generator matrix of a code is put in trellis oriented form. From this trellis
oriented generator matrix, some basic structural properties can be derived.

D R A F T January 6, 1998, 8:40pm D R A F T

24 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

3.1 TRELLIS REPRESENTATION OF CODES

An encoder for a linear code C with a finite memory, for which the output
code bits at any time instant during an encoding interval F -- {0,1,2,...}
are uniquely determined by the current input information bits and the state
of the encoder at the time can be modeled as a finite-state machine. The

dynamic behavior of such an encoder can be graphically represented by a

state diagram expanded in time, called a trellis diagram (or simply trellis)
as shown in Figure 3.1.

The encoder starts from some initial state, denoted c0. At any time instant i
during its encoding interval F, the encoder resides in one and only one allowable
state in a finite set. In the trellis diagram, the set of allowable states at time-
i is represented by a set of vertices (or nodes) at the i-th level, one for each
allowable state. The encoder moves from one allowable state at one time instant
to another allowable state at the next time instant in one unit of time. This
is called a state transition which, in the trellis diagram, is represented by
a directed edge (or branch) connecting the starting state to the destination
state. Each edge is labeled with the code bits that are generated during the
state transition. The set of allowable states at a given time instant i is called
the state space of the encoder at time-i, denoted Zi(C). A state _i E Y_i(C)
is said to be reachable if there exists an information sequence that takes the
encoder from the initial state _0 to state oi at time-i. Every state of the encoder
is reachable from the initial state _r0. In the trellis, every vertex at leveL/for
i E r is connected by a path from the initial state _r0. The label sequence of
this path is a code sequence (or a prefix of a code sequence). Every vertex
in the trellis has at least one incoming edge except for the initial state and at
least one outgoing edge except for a state called the final state. Encoding of
an information sequence is equivalent to tracing a path in the trellis starting
from the initial vertex or0. If the encoding interval r is semi infinite, the trellis
continues indefinitely; otherwise it terminates at a final state, denoted _I.
Convolutionai codes have semi infinite trellises, while the trellises for linear
block codes terminate at the end of each encoding interval.

For i E 1", let Ii and Oi denote the input information block and its corre-
sponding output code block, respectively, during the interval from time-/ to

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS REPRESENTATION OF LINEAR BLOCK CODES 25

i-th level

2nd level 4
o

Time ----+ state

transition

Figure 3.1. Trellis representation of a finite state encoder.

time-(/+ 1). Then the dynamic behavior of the encoder for a linear code is

governed by two functions:

(i) Output function,

Oi = fi(o'i, li),

where fi(eri, li) _-/i(cq,/:) for li _: I:.

(ii) State transition function,

ai+l = gi(ai, li),

where oi 6 ]Ei(C) and ai+l E Zi+z(C) are called the current and next states,

respectively. In the trellis diagram for C, the current and next states are

connected by an edge (cri, hi+z) labeled with Oi.

A code trellis is said to be time-invariant if there exists a finite period

{0, 1,..., v} C F and a state space E(C) such that

4

D R A F T January 6, 1998, 8:40pm D K A F T

2(3 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

0 0

0 0

0 0

Figure 3.2. A time-varying trellis diagram for a block code.

Figure 3.3. A time-invariant trellis diagram.

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS REPRESENTATION OF LINEAR BLOCK CODES 27

(1) _i(C) C _(C) for 0 _<i < v and }31(C) = _(C) for i > v and

(2) [i = f and gi = g for all i E r.

A code trellis that is not time-invariant is said to be time-varying. A trellis

diagram for a linear block code is, in general, time-varying. However, a trellis
diagram for a convolutional code is usually time-invariant. Figure 3.2 and 3.3
depict a time-varying trellis diagram for a block code and a time-invariant trellis
diagram for a convolutional code, respectively.

3.2 BIT-LEVEL TRELLISES FOR BINARY LINEAR BLOCK CODES

Consider a binary (N, K) linear block code C with generator and parity-check
matrices, G and H, respectively. During each encoding interval, a message
of K information bits is shifted into the encoder memory and encoded into a
codeword of N code bits. The N code bits are formed and shifted onto the

channel in N bit times. Therefore, the encoding span 1" is finite and consists
of N + 1 time instants,

r = {0, 1,2,...,N}.

C can be represented by an N-section trellis diagram over the time span r. Let
g(C) denote the encoder for C.

Definition 3.1 An N-section trellis diagram for a binary linear block code C
of length N, denoted T, is a directed graph consisting of N+ 1 levels of vertices
(called states) and edges (called branches) such that:

(t) For 0 < i < N, the vertices at the i-th level represent the states in the
state space Zi(C) of the encoder E(C) at time-/. At time-0 (or the 0-th
level) there is only one vertex, denoted a0, called the initial vertex (or
state). At time-N (or the N-th level), there is only one vertex, denoted
cry, called the final vertex (or state).

(2)For 0 < i _< N, a branch in the i-th section of the trellis T connects
a state _ri-1 E _i-t(C) to a state ai E ]Ei(C) and is labeled with a
code bit ui that represents the encoder output in the bit interval from
time-(/- 1) to time-/. A branch represents a state transition.

D R A F T January 6, 1998, 8:40pm D R A F T

28 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

(3) Except for the initialstate, every state has at least one, but no more

than two, incoming branches. Except for the finalstate, every state has

at least one, but no more than two, outgoing branches. The initialstate

has no incoming branches. The final state has no outgoing branches.

Two branches diverging from the same state have different labels.

(4) There is a directed path from the initialstate ao to the final state a I
with a label sequence (u_, u2,..., u/v) ifand only if (u_, us,..., u/v) is a
codeword in C.

A/x

Two states in the code trellisare said to be adjacent ifthey are connected

by a branch. During one encoding interval F, the encoder starts from the initial
state a0, transverses a sequence of states

O'0,al,... ,O'i,...,0"I) ,

generates a code sequence

Ul, U21 • • • ,Ui,. • • , B/V),

and then reaches the final state a/. The bit-level 8-section trellis diagram

for the (8,4) linear block code given in Example 2.1 (Table 2.1) is shown in

Figure 3.2.
For 0 < i < N, let I_i(C)l denote the cardinality of the state space [_i(C).

Then, the sequence,

(Ir.o (C)I, I_ (C)l,..., Ir./v-_ (C)l, Ir-/v (C)l),

is called the state space complexity profile, which is a measure of the

state complexity of the N-section code trellis T. We will show later that for

0 < i < N, IZi(C)[ is a power of 2. Define

p,(C) = log 2 Ir.,(C)l,

which is called the state space dimension at time-i. When there is no

confusion, we simply use Pl for pi(C) for simplicity. The sequence,

(PO, Pl, • • •, P/V),

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS REPRESENTATION OF LINEAR BLOCK CODES 29

is called state space dimension profile. From Figure 3.2, we see that the
state space complexity and dimension profiles for the (8, 4) code given in Ex-
ample 2.1 are (1, 2, 4, 8, 4, 8, 4, 2, 1) and (0, 1, 2, 3, 2, 3, 2, 1, 0), respectively.

3.3 TRELLIS ORIENTED GENERATOR MATRIX

To facilitate the code trellis construction, we put the generator matrix G in a

special form. Let u = (ul, u2,..., ujv) be a nonzero binary N-tuple. The first
nonzero component of u is called the leading '1' of u and the last nonzero
component of u is called the trailing '1' of u.
A generator matrix G for C is said to be in trellis oriented form (TOF)
if the following two conditions hold:

(1) The leading '1' of each row appears in a column before the leading '1'
of any row below it.

(2) No two rows have their trailing _ones" in the same column.

Any generator matrix for C can be put in TOF by two steps of Gaussian
elimination.

Example 3.1 Consider the (8, 4) RM code given in Example 2.1 with following
generator matrix,

1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1

It is not in TOF. By interchanging the second and the fourth rows, we have

1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1

DR AFT January 6, 1998, 8:40pro D RA FT

30 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Add the fourth row of the above matrix to the first,second and third rows.

These additions result in the following matrix in TOF:

gx 1 1 1 1 0 0 0 0

G= g2 = 0 1 0 1 1 0 1 0
g3 0 0 1 1 1 i 0 0

g4 0 0 0 0 1 1 1 1

A/x

The span of a row g = (gl,g2,... ,gs) in a trellisoriented generator matrix

(TOGM) G is defined as the smallest interval {i,i + 1,..., j} which contains

all the nonzero bits of g. This is denoted as span(g) A_ [/,j]. For a row g in

a TOGM G whose span is [i,j], the active span of g, denoted aspan(g), is

defined as aspan(g) _A [i,j - 1]for i < j and aspan(g) _ 0 (empty set) for i = j.

Let gx,g2 .... ,gK be the K rows of a TOGM G with

gl = (ga,gz2,...,gIN)

for l<l<K. Then

gl gll g12 ... glN

G : g2 g21 g22 ... g2N

• . • ...

gK gK1 gK2 ... gKN

Let (al, a2,..., aK) be the block of K information bits (called a message) to

be encoded. The corresponding codeword is given by

=
= ax • gl + a2 • g2 -[- "'" _- aK " gK"

We see that the/-th information bit al affects the output u of the encoder

£(C) over the span of the/-th row gt of the TOGM G. This span(g_) may be

regarded as the constraint length of the code associated with the/-th input

information bit at.

At time-/with 1 < i < N, the number of information bits that affect the next

output code bit u_+l is equal to the number of rows in G whose active spans
contain i. These information bits define the state of the encoder at time-/.

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS REPRESENTATION OF LINEAR BLOCK CODES 31

3.4 STATE SPACE FORMULATION

In the following, we give a mathematical formulation of the state space of the

N-section trellisfor an (N, K) linear block code (7 over GF(2) with a TOGM

G.

At time-i, 0 < i < N, the rows of G are divided into three disjoint subsets:

(I) G_ consists of those rows of G whose spans are contained in the interval

[1,il.
(2) G / consists of those rows of G whose spans are contained in the interval

[i+ 1, q.
(3) G_ consists of those rows of G whose active spans contain i.

Let A v, A{ and A_ denote the subsets of information hits that correspond to

the rows of G i,G
v ! and
i s respectively. The
Gi, information bits in AiP do not
affect the encoder outputs after time-i, and hence they become the past with

respect to time-/. The information bits in A { only affect the encoder outputs

after time-/. Since the active spans of the rows in G_ contain the time instant

i, the information bits in A_ affect not only the past encoder outputs up to
time-/ but also the future encoder outputs beyond time-/. We say that the

information bits in A_ define a state of encoder C(C) for the code (7 at time-i.

Let p_ _ IA_I = IG_I. Then there are 2 m distinct states that the encoder £.((7)

can occupy at time-i; each state is defined by a specific combination of the Pi

information bits in A_. These states form the state space El(C) of the encoder

g(C) (or simply of the code C). The parameter p_ is the dimension of the
state space Ei(C). In the trellis representation of C, the states in El(C) are

represented by 2p' vertices at the i-th level of the trellis.

Example 3.2 Consider the TOGM G for the (8, 4) RM code given in Exam-

ple 3.1. The spans of the four rows are: span(g1) = [1,4], span(g2) = [2,7],

span(g3) = [3,6], and span(g4) = [5,81. Their active spans are therefore:

pan(gl)
= [i,
31,pan(g =)[2,
61,'pan(g3)
= [3,
5]and = [5,
7].
For each i with 0 < i < 8, counting the number of rows which are active at

time-/yields the state space dimension profile (0,I,2,3, 2,3, 2, 1,0).

D R A F T January 6, 1998, 8:40pm D R A F T

32 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

The above formulation of a state space actually provides a sequential ma-

chine model for the encoder E(C).

3.5 STATE TRANSITION AND OUTPUT

For 0 < i < N, suppose the encoder E(O) isin state_rlE Ei(C). From time-/
to time-(/+ 1),E(C) generates a code bit ui+z and moves from state _ri to a
state _i+z E Ei+z(C). Let

c,'.= "1.9z ,g2 ,"" ,s(,,',

I) (3.1)
and

A_ -- t_'z1"(i)
,"2_(i),... , a(pid)
} (3.2)

where Pi = [G_I. The current state cri of the encoder is defined by a specific
combination of the information bits in A_.
Let g" be the row in G / whose leading '1' is at position-(/+ 1). The unique-
ness of this row 9" (if it exists) is guaranteed by the first condition in the
definition of a generator matrix in TOF given in section 3.3. Let g.+z denote
the (i+ l)-th component of g'. Then g_+z = 1. Let a" denote the inforxna-
tion bitthat corresponds to row g'. It followsfrom (2.3)and the structureof
the TOGM G that the output code bit ui+z generated during the bitinterval
between time-iand time-(/+ 1) isgiven by

Pi

ui+z a" + _ (0_(0

al gl,i+l' (3.3)
/=1

where _(0
Y/,i+ 1 is the (i + 1)-th component of g_0 in G_. Note that a" begins
to affect the output of the encoder £(C) at time-(/+ 1). For this reason, the
bit a" is regarded as the current input information bit. The second term
in (3.3) is the contribution from the state _i defined by the information bits
in AiO __ Luzs-(0,"z-('),.. . ,a_, )} which are stored in memory. From (3.3), we see
that the current output ui+z is uniquely determined by the current state _i of
the encoder C(C) and the current input a °. The output bit ui+l can have two
possible values depending on the current input information bit a'; each value
takes the encoder £(C) to a different state at time-(/+ 1). That is, there are
two possible transitions from the current state _i to two states in Ei+z(C) at

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS REPRESENTATION OF LINEAR BLOCK CODES 33

time-(/+ 1). In the code trellis, there are two edges (or branches) diverging

from the vertex ai labeled with '0' and T, respectively.

Suppose there is no such row g" in G//. Then the output code bit is given

by
Pi

ui+t _-_ Y_al i) -(I}

" YI,I+I" (3.4)

In this case, we may regard that the current input information bit a" is being

set to "0", i.e. a" = 0 (this is called a dummy information bit). The output

code bit ui+l can take only one value given by (3.4) and there is only one

possible transition from the current state ai to a state in Ei+I(C). In the

trellis T, there is only one branch diverging from the vertex ai.

Example 3.3 Again we consider the (8,4) code with its TOGM G given in
Example 3.1. Consider time-2. Then we find that Vp = O,G_ =- (Y3,Y4) and

G_ = (gt, Y_ }. Therefore, the information bits al and a2 define the state of the

encoder at time-2 and there are 4 distinct states defined by four combinations

of values of al and a2, (00,01, 10, 11). We also see that g* = g3. Therefore,

the current input information bit is a" = a3. The current output code bit u3

is given by

us = a3 +at'glS +a2"g23

= a3 + al.

For every state defined by al and a2, us has two possible values depending on

as. In the trellis, there are two branches diverging from each state at time-2,

as shown in Figure 3.2.

Now consider time-3. At i = 3, we find that V_ = 0, G_ = {g4} and

G_ = {91,g2, g3}. Therefore, the information bits al, a2 and as define 8 states
at time-3, as shown in Figure 3.2. There is no row 9" in G_ with leading '1'

at position (or time) i = 4. Hence we set the current input information bit

a* = 0. The output code bit u4 is given by

u4 = al.g14+a2.g24+as'g34

= at+a2+as.

D R A F T January 6, 1998, 8:40pm D R A F T

34 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

In the trellis, there is only one branch diverging from each of the 8 states, as
shown in Figure 3.2.
/x/x

Let gO be the row in G_ whose trailing '1' is at the position-(/+ 1). (Note
that this row gO may not exist.) The uniqueness of the row gO (if it exists)
is guaranteed by the second condition of a generator matrix in TOF given in
Section 3.3. Let a ° be the information bit in A_ that corresponds to row go.
Then at time-(/+ 1),

G,'+I = (a_\{g°}) U {g'} (3.5)

and

= u {a'). (3.6)

The information bits in Asi+1 define the state space _i+l(C) at time-(/+ 1).
The change from AS to A,_+I defines a state transition from the current state _i
defined by A is to the next state ai+l defined by Ai+
s 1. Therefore from AS, Ai%,,
(3.3) and (3.4), we can construct the N-section code trellis T for C.
The construction of the N-section trellis T is carried out serially, section by
section. Suppose the trellis has been constructed up to section-/. Now we want
to construct the (i + 1)-th section from time-/to time-(/+ 1). The state space
_(C) is known. The (i + 1)-th section is constructed by taking the following
steps:

(1) Determine G"i+1 and AS+l from (3.5) and (3.6). Form the state space
_i+l(C) at time-(/+ 1).

(2) For each state al 6 E_(C), determine its state transition(s) following the
state transition rules given above. Connect ai to its adjacent state(s) in
Zi+,(C) by edge(s).

(z) For each state transition, determine the output code bit u_+t from the
output function of (3.3) or (3.4), and label the corresponding edge in
the trellis with ui+l.

DRAFT January 6, 1998, 8:40pm D R A F T

 TRELLIS
REPRESENTATION OF LINEAR BLOCK CODES 35

3.6 TIME-VARYING STRUCTURE

During the encoding interval r = {0, 1,...,N}, the output function of the
encoder £(C) changes between (3.3) and (3.4). Also, the set __gl,i+l(i) ' Y2,1+
_(i) I ' " " " '
g(i)
p,,i+l } in the summations of (3.3) and (3.4) may change from one time instant
to another. This is because each column in the TOGM is, in general, not a
downward shift of the column before it. Therefore, the output function of £(C)
is time-varying. As the encoder £(C) moves from time-/ to time-(/-I- 1), its
state space may also change, i.e., _i+x(C) _ Yl'i(C). Consequently, the trellis
for £(C) is time-varying.
To describe the time-varying state space of £(C), there are four cases to
consider.

Case I: There is no such row gO in G_, but there is a row g" in G[. As
the encoder moves from time-/ to time-(/-t- 1), the active span of g"
contains the time instant i -t- 1. Therefore, g" is added to the set G_

to form G_+ 1. The information bit a" that corresponds to 9" is now
in the encoder memory and is included in determining the next and
future states of the encoder. The next state cri+l is determined by the
information bits

G1(i) (i)
,0. 2 ,...,0, (pl,),a*

Since IGL_I = IC/I + 1, p,+_ = m + 1. This results in state space

expansion.

CaselI: There is a rowg° E G_ and arow g" E G{. When the encoder
moves from time-/to time-(/+ 1), the span of g0 moves into the interval
[1,i + 1] and 9 ° is replaced by g" in G_+ 1. In this case, the information
bit a ° that corresponds to g0 becomes part of the past with respect to
time-(/+ 1) and will not affect the encoder outputs further; however, the
information bit a" is now in the memory and is included in determining
the next and future states of the encoder. Assuming that a ° = a_i), the
next state ai+l of the encoder is then determined by the information
bits
a_ i) , a_'),..., a_, ) , a'.

Therefore, from time-/ to time-(/+ 1), the state space of the encoder
and its dimension remain the same, i.e., Pi+l = Pi-

D R A F T January 6, 1998, 8:40pm D R A F T

36 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Case Ill: There is no such row gO in G_ and no such row g" in G{. In this

case, G_+l ----

G_ and there in no change in the state space dimension

as the encoder moves from time-/ to time-(i + 1). The next state is

determined by the saxne set of information bits as at time-i, i.e.,

Case IV: There exists a row gO E G_ but there is no such row g" fi G{. In

this case, gO is excluded from G_ to form G_+ 1 and its corresponding

information bit a ° becomes part of the past as the encoder moves from

time-i to time-(/q- 1). Assuming that a ° -- a_ i), the state _i+1 of the

encoder is determined by the information bits

a(i)
2 ,"3_,(1) _..._a _,) .

Consequently, IG_+I[ = IG_I- I and pi+1 = Pi - 1. This results in state

space reduction.

Example 3.4 Consider the (8,4) code given in Example 3.1. From itsTOGM

G, we see that for i = 0, 1 and 2, there is no such row go in G_, but there is

a row g" in G{. Hence there is state space expansion from time-0 to time-3
as shown Figure 3.2. We note that there is such a row go in G] and there is

no such row g" in Ga/. Therefore, there is state space reduction from time-3 to

time-4, as shown in Figure 3.2.

AA

From the above analysis of the N-section trellisfor an (N, K) linear block

code C, we have the following observations. At time-i, with 0 < i < N,

(1) The information bits in A p become the past and do not affectthe future

outputs of the encoder beyond time-/.

(2) The information bits in A{ affect the encoder outputs only beyond time-

i, i.e.,they axe the future input information bits.

(3) The information bits in A_ are the bits stored in the encoder memory
that define the encoder state at time-/.

The above observations make the formulation of a trellisdiagram for a block

code the same as for a convolutional code [62].

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS REPRESENTATION OF LINEAR BLOCK CODES 37

3.7 STRUCTURAL PROPERTIES

For 0 <_ i < j _< N, let Cij denote the subcode of C consisting of those

codewords in C whose nonzero components are confined to the span of j - i

consecutive positions in the set {i + 1, i + 2,... ,j}. Clearly, every codeword in

Cid is of the form,

i N-j

It follows from the definition of Cij and the structure of the TOGM G for

C that Cij is spanned by those rows in G whose spans are contained in the

interval [i + 1,j]. The two subcodes, Co,i and Ci,N, are spanned by the rows
in G_ and G{, respectively, and they are called the past and future subcodes

of C with respect to time-/.

For a linear code D, let k(D) denote its dimension. Then, k(C0,,) = IG_'I

and k(C_,_) = IG{I. Recall that the dimension of the state space E_(C) at

time-/is

re(C) = IGCI-- K-IGfl- IG{I

= K - k(Co,i) - k(Ci,N). (3.7)

This gives a relationship between the state space dimension pi(C) at time-/

and the dimensions of the past and future subcodes, C0,i and Cijv, of C with

respect to time-/.

Note that Co,i and Cijv have only the all-zero codeword 0 in common.

The direct-sum of C0,i and Ci,N, denoted C0,i $ Ci,/v, is a subcode of C with
dimension

k(co,,) + k(c_._,).

Let C/(Co,i _ Ci,/v) denote the partition of C with respect to Co,i _ Cijv.

Then this partition consists of

ICl(Co,, • C,,_,)l = 2K-k(Co.,)-k(C..N)

= 2m (3.8)

cosets of Co,i • CI,N. Eq.(3.8) says that the number of states in the state space

_ (C) at time-/is equal to the number of cosets in the partition C/(Co,/$ C_,jv).

D R A F T January 6, 1998, 8:40pm D R A F T

38 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Time 0 i N

o- o

C-=-_ a/

A coset in A coset in
po,,(c)/c_:h p,,,,(C)/Ct,'N

Figure 3.4. The paths in the code trellis that represent the 2 K-O' codewords in v

(Co,,_ C,,N).

Let Si denote the subspace of C that is spanned by the rows in G_. Then
each codeword in Si is given by

: _(,I
_I _._ s''" ,a_)). G:
'_2

= + +... + (3.9)
where al ') E A_ for 1 < l _ pi. The 2 0` codewords in S, can be used as
the representatives for the cosets in the partition C/(Co,i _ C,,N). Therefore,
S, is the coset representative space for the partition C/(Co,, ¢_ Ci,N). From
(3.9), we see that there is one-to-one correspondence between v and the
state o'i £ Ei(C) defined by l, a I(i) ,a 2(,) ,.. ., a(',_). Since there is a one-to-one
correspondence between v and a coset in C/(Co,, _ Ci,N), therefore, there is
a one-to-one correspondence between a state in the state space Ei(C) and
a coset in the partition C/(Co,i _ Ci,N).
With the above one-to-one correspondence in the trellis T, the codeword v
given by (3.9) is represented by a path that passes through the state a, defined
by the information bits, a_ 0, a_0, ..., a_. ) (i.e., a path that connects the initial
state a0 to the final state a! through the state a,). If we fix the information
bits, a_ 0, a(20,..., a(p',), and allow the other K - p, information bits to vary, we
obtain 2K-P'codewords of C in the coset

_,_ (Co,,¢ C_,N) _-{,, + ,-,: u _ co,, $ C_,N} (3.10)

with u as the coset representative. In the trellis, these 2 K-p' codewords are
represented by paths that connect the initial state a0 to the final state o!

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS REPRESENTATIONOF LINEAR BLOCK CODES 39

through the state ai at time-/defined by the information bits, a_ i), a_ i), ...,
a(oi,), as shown in Figure 3.4. Note that

K - p, = k(C0.,) + k(C,._,) (3.11)

which is simply the dimension of Co.i • Ci,lv.

For 0 <_ i < j <_ N, let pij(C) denote the linear code of length j - i obtained
from C by removing the first i and last N - j components of each codeword
in C. This code iscalleda punctured (or truncated) code of C. Let C_,%
denote the punctured code of the subcode Cij, i.e.,

cl 5 =" pid(Cij). (3.12)

Itfollowsfrom the structureof the TOGM G that

k(pij(C)) = K - k(Co,i) - k(Cj, N) (3.13)

and
k(, C_' _ = k(Cij).
,,.1, (3.14)

Consider the punctured code po,_(C). Partition poj(C) based on C 0,i"

tr It
follows from (3.13) and (3.14) that the partition po,i(C)/C_: i consists of

2K-k(Co..)-I=(C,.,'_) = 2p'

cosetsof C_:[Link] can readilyseethatthere isa one-to-one correspondence

between the cosetsinpo,i(C)/C_:iand the cosetsin C/(Co,i$Ci,lv),and hence a
one-to-one correspondence between the cosetsinPo,i(C)/C_:iand the states
in the state space ]Ei(C).The codewords in a coset in po,i(C)/C_riare simply
the prefixesof the codewords in itscorresponding coset in C/(Co,i _ Ci,_v).
Hence the codewords in a coset of po,i(C)/C_:i willtake the encoder £(C) to
a unique state ai E _i(C). In the trellis
T, they are the paths connecting the
initial
statea0 to the stateai as shown in Figure [Link] L(a0, hi) denote the
paths in the trellis
T that connect the initial
state a0 to the stateai in FII(C).
Then L(a0,ai) is a cosetin the partitionpo,i(C)/C_;i.
Now we consider the punctured code pijv(C). Partitionp,,.,v(C)
based on

ctri,N = Pi,N(Ci,N). Then it follow from (3.13) and (3.14) that the partition

D R A F T January 6, 1998, 8:40pm D R A F T

40 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Time 0 i 0 j N

0 0
0 __ 0
O'o . . ) al

o,

Figure 3.5. Paths in the code trellis that represent the codewords in Cij.

pi,lv(C,)/Ct,_ consists of

2K-k(Co.,)-_(C,.rv) = 2m

cosets of C i,N.
tr Again we see that there is a one-to-one correspondence

between the cosets in pidv(C)/Gt,_ and the cosets in C/(Co,i (_ Gi,lv), and

hence a one-to-one correspondence between the cosets in pijv(C)/Ctr, N and

the states in the state space _i(C). In the trellis, the codewords in a coset

pi,N(C)/C_,_ form the paths that connect a state _ri E Ei(C) to the final state

_r! as shown in Figure 3.4. Let L(al, al) denote the paths in the trellis T that

connect the state ai E _i(C) to the final state a I. Then L(c_,al) is a coset in
C tr
the partition pijv(C)/ i,lv"
For 0 < i < j < N, let a_ °) and _(o) denote two states on the all-zero path 0

in the trellis T at time-/and time-j, respectively. Let "_tcri (o) ,a i(o), )denotethe

paths of length j -- i in T that connect _(o)

o i to o_(o)
i • Consider the paths in T

that start from the initial state a0, follow the all-zero path 0 to the state al °),

transverse through ,, (o),_j(o), ] to the state a_ °),

the paths in _(ai then follow the

all-zeropath 0 until they reach the final state a! as shown in Figure 3.5. These

paths represent the codewords in the subcode Ci,j of C. This implies that

L, [ai (o) ,aj (o), ] = [Link]" (3.15)

Let v = (vz,v2,... ,vlv) be a path in the code trellis T. For 0 <_ i < j < N,

letoi-(w) and a_') be two states on the path v at time-/and time-j, respectively.
_, (w) (_),
Let _(_r i , aj ) denote the paths of length j - i that connect a}') to a_ ").

Consider the paths in T that start form the initial state or0, follow the path v
to the state or}"), transverse through the paths in "'
_tai (') ,o-(')x
i 1, then follow the

D R A F T January 6, 1998, 8:40pro D R A F T

 TRELLIS REPRESENTATION OF LINEAR BLOCK CODES 41

Time 0 i v j N
U

(3
O" o
° o
oi " -- .'_,,,oj- °l

p_a(v)+ c:'.

Figure 3.6. Paths in the code trellis that represent the codewords in the coset u _ Ci,j.

path v until they reach the final state a I as shown in Figure 3.6. These paths

represent the codewords in the following coset of Ci,j:

v e C_,s_={v + u : u _ C_,j}. (3.16)

., (-) (-)
This is a coset in the partition C/Ci,j. This implies that Lta i ,a i ) is a coset

of Ct,_ in pi,s(C), i.e.,

L. [a (_,)
i ,a s(-), ) = pi,j(u) + C i,S
tr 6Pi,St ,C,.Ct_
)/ i,S, (3.17)

where Pi,j (v) denotes the vector of length j- i obtained from v by removing the
first i and last N-j components of v. For any two connected states ai 6 _,(C)

and a s 6 Zj(C) with 0 < i < j < N, they must be on a path in the trellis T.

It follows from (3.17) that

L(al, aS) e p ,s(C )/ C ,,,-

t' (3.18)

Therefore, the number of paths that connect a state ai E _i(C) to a state

a s 6 _j(C) is given by

(3.19)
]L(ai,aj)] = 2t(c[_
0, ), al and
if ai aa#s are connected,
not connected.

For 0 < i < j < k __ N, let _j(ai, ak) denote the set of states in Es(C )

through which the path in L(ai,ak) connect the state ai to the state ak as

shown in Figure 3.7. Let

L(a,, aj) o L(aj, ak) a_ {u o v: u C L(ai, a s), v e L(a i, a_)} (3.20)

D R A F T January 6, 1998, 8:40pm D R A F T

42 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Time i j k

D,

£2)- ak

o. i

Figure 3.7. The state set Ej(al, ak).

where u o v denotes the concatenation of two sequences u and v. In the trellis,

L(ai, aj) o L(aj,a_) consists of those paths in L(ai, ak) that connect the state

ai to the state at through the state aj. Then,

L(a,,aj:)= U L(a"aj)°L(ai'a_)" (3.21)

ojE_j(crs,a_)

The above developments give some fundamental structural properties of an

N-section trellisT for a linear block code C.

D R A F T January 6, 1998, 8:40pm D R A F T

 STATE LABELING, TRELLIS
CONSTRUCTION PROCEDURES AND
TRELLIS SYMMETRY

The construction of a code trellis can be facilitated by labeling the states at

each level of the trellis. State labeling is also necessary in the implementation
of a trellis-based decoding algorithm. This chapter presents three methods
for labeling the states of the N-section trellis for an (N, K) linear block code.
The first two methods are based on the information set that defines the state

space at a particular encoding time instant and the third method is based on
the parity-check matrix of the code. The first two methods are more efficient
than the third one for codes with K < N - K; however, the third method is
more efficient for codes with N - K < K. Based on these labeling methods,
construction procedures for the N-section trellis for an (N, K) linear block code
are presented. Also presented in this chapter is the mirror symmetry structure
of a code trellis. This symmetry structure is useful in decoding.

D R A F T January 6, 1998, 8:40pm D R A F T

44 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

4.1 STATE LABELING BY THE STATE DEFINING INFORMATION

SET

In a code trellis, each state is labeled by a fixed sequence (or given a name).
This can be accomplished by using a K-tuple A with components correspond-
ing to the K information bits, al,a2 .... ,azc, in a message. At time-i, all the
components of A are set to zero except for the components at the positions
_ (_) (i)
corresponding to the information bits in A i = _tat ,a 2 ,..., a(i, )}. Every com-
bination of the Pi bits at the positions corresponding to the information bits
in A_ gives the label l(ai) for the state ai defined by the information bits,
al (i) (1), •..
_ (2 2 , a_i).

Example 4.1 Consider the (8,4) code given in Example 3.1. At time-4, we
find that A_ = {az, a3}. There are 4 states corresponding to 4 combinations of
a: and a3. Therefore, the label for each of these 4 states is given by (0, a2, a3,0).
AA

The construction of the N-section trellis for an (N, K) linear block code C
can be carried out as follows. Suppose the trellis T has been constructed up to
section-/. At this point, G[, A_ and _i(C) are known. Each state ai E _i(C)
is labeled by a K-tuple. The (i + 1)-th section is constructed by taking the
following steps:

(1) Determine Gi'+l and A_+ 1 from (3.5) and (3.6).

(2) Form the state space _i+x(e) at time-(/+ 1) and label each state in
Z,+I(C) based on li_+l. The state in _+x(C) form the vertices of the
code trellis T at the (i + 1)-th level.

(3) For each state ai • _,i(C) at time-i, determine its transition(s) to the
state(s) in _i+x(C) based on the information bits of a* and a °. For each
transition from a state ai • _i(C) to a state ai+l E _i+l(C), connect
the state ai to the state ai+l by an edge (ai, ai+l).

(4) For each state transition (al, ai+x), determine the output code bit ui+l
and label the edge (al, ai+l) with ui+l.

Recall that at time-i, there are two branches diverging from a state in _]i(C)
if there exists a current information bit a*. One branch corresponds to a* =

D R A F T January 6, 1998, 8:40pm D R A F T

 STATE LABELING, TRELLIS CONSTRUCTION PROCEDURES 45

Table 4.1. State defining sets and state labels for the 8-section trellis for the (8, 4) linear
block code.

GS 0.= 0.0 State Label

0 0 G1 -- 0 (oooo)
1 G2 -- (0. ooo)
2 a3 (0.1a200)
3 {gz,gz,g3} -- 0.1

4 a4 - (0a a30)
5 -- a3 (Oa2a3a4)
6 -- 0.2 {o,,0.,} (Oa20a4)

7 {g,} -- 0.4 (0000.4)

8 0 ¢ (oooo)

0 and the other corresponds to a* = 1. For the convenience of graphical

representation, in the code trellis T, we use the upper branch to represent

a" = 0 and the lower branch to represent a" = 1. If a" is a dummy information

bit, then there is only one branch diverging from each state in ZI(C). This single

branch represents a dummy information bit. Using the above representation,

we can easily extract the information bits from each path in the trellis (the

dummy information bits are deleted).

Example 4.2 Consider the state labeling and trellis construction for the (8, 4)

RM code given in Example 3.1 whose TOGM G is repeated below,

91
1 1 1 1 0 0 0 0

0 1 0 1 1 0 1 0
G ____
g2 =
g3 0 0 1 1 1 1 0 0

94 0 0 0 0 1 1 1 1

For 0 < i < 8, we determine the submatrix G s and the state defining in-

formation set A s as listed in Table 4.1. From AS, we form the label for each

state in _i(C) as shown in Table 4.1. The state transitions from time-/to time-

(i + 1) are determined by the change from A_ to AS+ z. Following the trellis

D R A F T January 6, 1998, 8:40pm D R A F T

46 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

0 0

Figure 4.1. The 8-section trellis diagram for the (8, 4) RM code with state labeling by
the state defining information set.

construction procedure given above, we obtain the 8-section trellis diagram for
the (8,4) RM code as shown in Figure 4.1. Each state in the trellis is labeled

by a 4-tuple.

AA

In many cases, we do not need K bits for labeling the states of the N-section

trellis for a binary (N, K) linear block code C. Let (P0,Pl,... ,pie) be the state

space dimension profile of the trellis. Define

Pmax(C) max Pi (4.1)

o<_i<N

which is simply the maximum state space dimension of the trellis. From (3.7),

we find that Pm_x(C) _< K. In general, Pmax is smaller than K. Since the

number of states at any level of the trellis is less than or at most equal to

D R A F T January 6, 1998, 8:40pro D R A F T

 STATE LABELING, TRELLIS CONSTRUCTION PROCEDURES 47

Table 4.2. State labeling for the (8, 4) RM code using Pmax(C) = 3 bits.

State Label

0 (ooo)
1 (a,oo)
2 (aia20)
3

4 (a a30)
5

6 (a2a, O)
7 (a, O0)
8 0 (ooo)

2 p"'x(c), Pmax(C) bits are sufficient for labeling the states in the trellis. Con-

sider the state space Ei(C) at time-/with 0 < i < N which is defined by the set
{(1)
a 1 ,a 2(i) ,.. . ,a(pi,)} of Pi information bits. For each state aie Ei(C), we form

a pmax(C)-tuple, denoted l(a_), in which the first p_ components are simply

a(01 _(i) ''

' u2 "" ,a_, ) and the remaining Pmax(C) - Pi components are set to 0, i.e.,

l(a_) =•,,[a c,I

1 ,a2 , .... ,0). (4.2)

Then l(ai) is the label for the state ai.

Example 4.3 Again we consider the (8,4) RM code given in Example 4.2.

From the TOGM G of the code, we find the state space dimension profile of

the 8-section trellis for the code to be (0, 1, 2, 3, 2, 3, 2, 1, 0). Hence pm_x(C) - 3.

Using 3 bits for labeling the states as described above, the state labels are given

in Table 4.2. Compared to the state labeling given in Example 4.2, one bit is

saved.
AA

D R A F T January 6, 1998, 8:40pm D R A F T

48 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

4.2 STATE LABELING BY PARITY-CHECK MATRIX

Consider a binary (N, K) linear block code C with a parity-check matrix

H -- [hl, h2,..., hi,..., hN], (4.3)

where, for I _ j _< N, hj denotes the j-th column of H and is s binary

(N - K)-tuple. A binary N-tuple c is a codeword in C if and only if

C" H T --= _, (4.4)

N-K

where H T denotes the transpose of H. C is called the null space of H.

Let 0N-K denote the all-zero (N - K)-tuple (0,0,... ,0). For 1 < i < N,

let Hi denote the submatrix that consists of the first i columns of H, i.e.,

Hi = [hl, hs,..., hi]. (4.s)

It is clear that the rank of Hi is at most N - K, i.e.,

Rank(Hi) _< N - K. (4.6)

Then for each codeword c E C_i,

c" H T = 0_'-K- (4.7)

C_:i is the null space of Hi.

Now we consider the partition

po,iCC)lC :i.
Let D be a coset in po,i/C_: i and 19 ¢ C_: i. For every vector a e D,

a. H T = (s,, ss,... , sir-K) # ON-K (4.8)

and is the same for all vectors in D, i.e., for al,a2 E D and al _ a2,

a 1 • H_/= a s • _ = (s1,$2,... ,$N-K). (4.9)

The (N- K)-tuple (sl, ss,..., SN-K) is called the label for the coset D. Let
D_ and Ds be two different cosets in po,i(C)/Ct:i. Let al E D1 and as E Ds.
It follows from the theory of linear block codes that al ¢ as and

.H? # as.

D R A F T January 6, 1998, 8:40pm D R A F T

 STATE LABELING, TRELLIS CONSTRUCTION PROCEDURES 49

This says that different cosets in po,i(C)/C_[ i have different labels.

Recall the mathematical formulation of the state spaces of a code trellis.
There is a one-to-one correspondence between a state a in the state space
_i(C) at time-/and a coset D 6 po,i(C)/C_[ i, and the codewords of po,i(C) in
D form the paths that connect the inltiM state a0 to state a. This one-to-one
correspondence leads to the definition of a state label.
Let L(cr0,a) denote the set of paths in the code trellis for C that connect
the initial state a0 to a state a in the state space _i(C) at time-i.

Definition 4.1 For 0 < i < N, the label of a state _ G Ei(C) based on a
parity-check matrix H of C, denoted l(a), is defined as the binary (N- K)-
tuple
a. = (sl,s2,,.. (4.10)
for any a 6 L(ao,a). For i = O, Hi = @and the initial state a0 is labeled with
the all-zero (N- K)-tuple, 0N-K. For i - N,L(ao,af) = C and the final state
_1 is also labeled with ON-K.
AA

It follows from the above definition of a state label, the one-to-one correspon-
dence between the states in Z,(C) and the cosets in po,i(C)/Ct_i for 0 < i < N,
and (4.10) that every state a 6 _i(C) has a unique label and different states
have different labels.
For 0 < i < N, let ai and ai+l be two adjacent states with ai 6 Ei(C)
and ai+t G _i+l(C). Let ui+l be the label of the branch in the code trellis
that connects state cq to state ai+l. The label ui+l is simply the encoder
output bit in the interval from time-/to time-(/+ 1) and is given by (3.3) or
(3.4). For every path (ul,u2 ..... ul) 6 L(ao,ai), the path (ul,u2,... ,ut,u,+l)
obtained by concatenating (ul, u2,..., ul) with the branch ui+, is a path that
connects the initial state a0 to the state ai+l through the state a,. Hence,
(u,,u2 .... ,ul,ui+l) 6 L(ao, ai+l). Then it follows from the definition of a
state label that

l(ai+l) = (ut,u2,...,ui,ui+x).H_i+t

= (u,, HS + u,+,.
= t(,r,) + ui+l • hir+l. (4.11)

DRAFT January 6, 1998, 8:40pro DR AFT

50 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Eq.(4.11) simply says that given the starting state labeled l(#_) at time-/and
the output code bit ui+t during the interval between time-/and time-(/+ 1),
the destination state labeled l(a_+x) at time-(/+ 1) is uniquely determined.
Now we present a procedure for constructing the N-section trellis diagram
for a binary (N, K) linear block code C by state labeling using the parity-
check matrix of the code. Let u = (ux,u2,... ,UN) be a binary N-tuple. For
0 < i _< N, let po,i(u) denote the prefix of u that consists of the first i
components, i.e.,

po,i(u) = (ul, u2,..., ui). (4.12)

Suppose that trellis has been completed up to the i-th section (or time-i). At
this point, the rows of the TOGM G in the set G_ = t:_lYn(i),_"(1),--. ,g(pi,)) and
their corresponding information bits a I(i) ,a 2(i) ,...,tip_ _(1) uniquely define a state
a_ E E_(C). Let

, = g ,l+o?. gg,I+... + g;,,.

Then po,i(u) is a path connecting the initial state a0 to the state a, defined by
a_i), a_i),..., a(i,). The label of state a, is given by

= po.,(-)HT.

The construction of the (i + 1)-section of the code trellis is accomplished by

taking the following four steps:

(1) Identify the special row g" (if any) in the submatrix G{ and its cor-
responding information bit a*. Identify the special row gO (if any) in
the submatrix G_. Form the submatrix G_+ 1 by including g" in G_ and
excluding gO from G_.

(2) Determine the set of information bits, A_+ 1 r (i+1) _,u_(i+x)

1(21 2 ,... (i+1) J,
,Gpi+s 1.
that correspond to the rows in G_+ 1. Define and label the states in
E,+I(C).

(3) For each state ai E Ei(C), form the next output code bit ui+l from
either (3.3) (if there is such a row g* in G[ at time-i) or (3.4) (if there
is no such row g" in Gi"f at time-i).

D R A F T January 6, 1998, 8:40pm D R A F T

 STATE LABELING, TRELLIS CONSTRUCTION PROCEDURES 51

0 0

0 0

Figure 4.2. 8-section trellis for (8, 4) RM code with state labelingby parity-checkmatrix.

(4) For each possible value of Ui+l (two if computed from (3.3) and one if
computed from (3.4)), connect the state ai to the state az+l E Ei+l (C)
with label

= + u,+l. h,T÷l.

The connecting branch, denoted L(ai, o'i+1), is labeled with Ui+l. This
completes the construction of the (i + 1)-th section of the trellis.

Repeat the above steps until the entire code trellis is constructed.

Example 4.4 Consider the (8, 4) RM code given in Example 3.1. This code is
self dual. Therefore, a generator matrix is also a parity-check matrix. Suppose

D R A F T January 6, 1998, 8:40pm D R A F T

52 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

we choose the parity-check matrix as follows:

1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 1
H
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1

Using this parity-check matrix for labeling and following the above trellis con-
struction steps, we obtain the 8-section trellis with state labels shown in Fig-
ure 4.2. To illustrate the construction process, we assume that the trellis has
been completed up to tlme-3. At this time instant, G_ = {gl,g2,g3} and
A_ = {al,a2,a3} are known. The eight states in E3(C) are defined by the
eight combinations of al,a2 and as. These 8 states and their labels are given
below:
states defined statelabels

by (al, as, a3)

(000) (oo0o)
0-_ 1) (001) (lOlO)
a_ s) (OLO) (lOOl)
0-(33) (o11) (oo11)
(lOO) (lO11)
(101) (OOOl)
(11o) (OOLO)
a_7) (111) (1ooo)
Now we want to construct the 4-th section of the trellis up to time-4. At time-3,
from the TOGM G, we find that 90 = gl and there is no such row 9" with
leading '1' at time-4. Therefore, G_ = {Ys,g3} and A_ = {as,a_). The four
states in E4(C) at time-4 are defined by the four combinations of as and a3.
The four codewords generated by the rows in G_ are:

as, a3 ) paths

(0,0) _o= (o000ooo0)

(o,1) Ul = (00111100)
(1,o) us = (01011010)
(1,1) us = (01100110)

D R A F T January 6, 1998, 8:40pm D R A F T

 STATE LABELING, TRELLIS CONSTRUCTION PROCEDURES 53

The four paths that connect the initial state a0 to the four states, denoted al °),

_(1) _ 0"4
(2) and a (3) in E4(C) are:

po,,(,_o) = (oooo),
po,,(ul) ---- (0011),

po,,(,,_) = (OlOl),
po,,(_,_) = (OliO).
The submatrix//4 is
1 1 1 1

0 0 0 0
H

0 0 1 1

0 I 0 i

From po,4(uy), with 0 < j _< 3 and/-/4, we can determine the labels for the four
states, a_°),a_l),a_ 2) and a_ s), in E4(C) which are given below:

states defined state labels

by (a2, as)

(oo) (0000)

al i) (Ol) (0001)

a_ 2) (10) (ooio)

a_ s) (ii) (00ii)

The four states and their labels are shown in Figure 4.3 at time-4. Now suppose

the encoder is in the state _r3{s) with label l(ai 5)) = (0001) at time-3. Since no

such row g" exists at i = 3, the output code bit u4 is computed from (3.4) as
follows:

_4 = 1 • gl4 + 0 • g24 -}- 1 • 934

= I'I+0"I+I'I

= O.

Then the state a_ s) is connected to the state in E4(C) with label

z(4_))
+,,.h_ = (oooi)
+ o.(io_1)
= (00Ol),

D R A F T January 6, 1998, 8:40pro D R b F T

54 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

oooo)

oool)

oolo)

(1ooi)0

l
Time-3 Time-4

Figure 4.3. State labels at the two ends of the 4-th section of the trellis for (8, 4) RM

code.

which is state u O). The connecting branch is labeled with u4 = 0. The connec-
tions from the other states in E3(C) to the states in E4(C') axe accomplished
in the same manner.
/xA

State labeling based on the state defining information sets requires K (or

Pmax(C)) bits to label each state of the trellis;

however, state labeling based on

D R A F T January 6, 1998, 8:40pm D R A F T

 STATE LABELING, TRELLIS CONSTRUCTION PROCEDURES 55

the parity-check matrix requires N - K bits to label each state of the trellis.

Therefore, labeling method-1 is more efficientfor codes with K < N - K while

labeling method-2 ismore efficientfor codes with K > N - K.

4.3 STRUCTURAL SYMMETRY

Consider a binary (N, K) linear block code C with even length N and TOGM

gl gll g12 "'" glN

g2t g22 "'" g2s

e
g2 ----
: : ... :

gK gK_ gK2 "" gKN

Let T denote the N-section trellisdiagram for C. Suppose the TOGM G has

the following symmetry property: For each row g in G with span(g) = [a,b],

there exists a row g' in G with span(g') = [N + 1 - b,N + 1 - a]. With this

symmetry property in G, we can readily see that for 0 < i < N/2, the number

of rows in G that are active at time-(N - i) is equal to the number of rows in

G that are active at time-/. This implies that

= IS,(C)l

for 0 < i < N/2. We can permute the rows of G such that the resultant matrix,
denoted G _, is in a reverse trellis oriented form:

(1) The trailing '1' of each row appears in a column before the trailing '1'

of any row below it.

(2) No two rows have their leading "ones" in the same column.

If we rotate the matrix G' by 180 ° counter clockwisely, we obtain a matrix G"

in which the i-th row g_' is simply the (K r

+ I - i)-th row 9K+t-_ of G I in

reverse order (the trailing'1' of gK+I-_

' becomes the leading 'I'of g_' and the

leading '1'of gK+I-_ becomes the trailing '1' of g_'). From the above, we see
that G" and G are structurally identical in the sense that

span(g_') = span(g,)

D R A F T January 6, 1998, 8:40pro D R A F T

56 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

for 1 < i < K. Consequently, the N-section trellis

T for C has the following
mirror symmetry [101]:The lastN/2 sectionsof T form the mirror image
of the firstN/2 sectionsof T (not includingthe path labels).

Example 4.5 Consider the (8, 4) RM code given in Example 4.2 with TOGM

gl 1 I I 1 0 0 0 0
0 1 0 1 1 0 i 0
e
g2 =
gs 0 0 1 1 1 I 0 0

94 0 0 0 0 1 i 1 1

We find that span(g 1) = [1, 4], span(g4) = [5, S], and gl and g, are symmetrical
with each other. Row g2 has span [2, 7] and is symmetrical with itself. Row
g._ has span [3, 6] and is also symmetrical with itself. Suppose we permute the
second and third rows of G. We obtain the following matrix in reverse trellis
oriented form:

1 1 1 1 0 0 0 0

9'2 0 0 1 1 1 1 0 0
0 1 0 1 1 0 1 0

g', 0 0 0 0 1 1 1 1

Rotating G' 180 ° counter clockwisely, we obtain the following matrix:

1 1 1 I 0 0 0 0
0 I 0 1 1 0 I 0

g'; 0 0 1 1 1 1 0 0
0 0 0 0 1 1 1 I

We find that G" and G are in fact identical, not just structurally identical.
Therefore, the 8-section trellis T for the (8, 4) RM code has mirror symmetry
with respect to the boundary location 4, the last four sections form the mirror
image of the first four sections as shown in Figures 3.2 and 4.1.
AA

For the case that N is odd, if the TOGM G of a binary (N, K) code C has
the mirror symmetry property, then the last (N- 1)/2 sections of the N-section
trellis T for C form the mirror image of the first (N - 1)/2 sections of T.

D R A F T January 6, 1998, 8:40pm D R A F T

 STATE LABELING, TRELLIS CONSTRUCTION PROCEDURES 57

For the case that G" --- G, the N-section trellis T of C has full mirror
symmetry structure [101]. For N even, the last N/2 sections of T in reverse
direction (the final state _rf is being regarded as the initial state) is completely
identical to the first N/2 sections of T (including the path labels). The 8-section
trellis of the (8, 4) RM code has full mirror symmetry as shown in Figure 4.1.
For N odd, the last (N - I)/2 sections of T in reverse direction are completely
identical to the first (N - 1)/2 sections of T (including the path labels).

D R A F T January 6, 1998, 8:40pm D R A F T

 5 TRELLIS COMPLEXITY

This chapter is devoted to analyzing the complexity of an N-section trellis

diagram for an (N, K) linear block code. Trellis complexity is, in general, mea-
sured in terms of the state and branch complexities. These two complexities
determine the storage and computation requirements of a trellis-based decod-
ing algorithm, such as the Viterbi decoding algorithm. The state complexity of
a trellis is measured by its state space dimension profile and the branch com-
plexity is measured by the total number of branches (or edges) in the trellis.
In Section 5.1, a simple upper bound on the maximum state space dimension
is derived. It is proved that the state complexity of a linear block code is the
same as that of its dual code. In Section 5.2, the concepts of a minimal trellis
diagram and optimum bit permutation in terms of state complexity are intro-
duced. It is proved that the trellis construction based on a TOGM results in
a minimal trellis. In Section 5.3, the branch complexity of an N-section trellis
diagram is analyzed. Finally, in Section 5.4, the general structure of N-section

D R A F T January 6, 1998, 8:40pro D R A F T

60 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

trellis
diagrams forcycliccodes is given. It itshown that the maximum state
space dimension meets the upper bound derived in Section 5.1.

5.1 STATE COMPLEXITY

For a binary (N, K) linear block code C, the state complexity of an N-section
bit-level code trellis is measured by its state space dimension profile

(Po,Pl,p2,... ,PN),

where for 0 < i < N,

p_= log2IS,(C)l.
Let Pmax(C) denote the maximum among the statespace dimensions, i.e.,

pm,x(c)
= max p_.
o_i_

Using the constructionmethod described in Chapter 3, the statespace dimen-

sion at time-/isgiven by (3.7),

o, = K - k(Co,,)- k(C_,_,),

for 0 < i < N. Since k(Co,i) and k(Ci,u) axe nonnegative, we have

pm,,x(C) _ K. (5.1)

However, itfollowsfrom (4.6)and the definition

and uniqueness of a statelabel
at any time-i (see(4.10))that

Ir._(C)l < 2N-x

and

Pi _ N - K (5.2)

for 0 < i < N. Eq.(5.2) implies that

Pm-x (C) < N - g. (5.3)

Combining (5.1) and (5.3), we have the following upper bound on the maximum
state complexity:

pm,x(C) < rain{K, N - K}. (5.4)

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS COMPLEXITY 61

This bound was first proved by Wolf [109]. In general, this bound is quite loose.

However, for cyclic (or shortened cyclic) codes, this bound gives the exact state

complexity. For noncyclic codes, tighter upper bounds on pm_(C) have been
obtained.

If the Viterbi algorithm is applied to the N-section trellis of a code, then the

maximum numbers of survivors and path metrics needed to be stored are both

2 p=-(c). Therefore, the parameter pm_.(C) is a key measure of the decoding

complexity (or trellis complexity).

For 0 < i < rain{K, N - K}, it follows from the structure of a TOGM G

that the number of rows in G whose active spans contain the time index i is no

greater than i. For i >_ max{K, N - K}, since there is one-to-one correspon-

dence between the states in _i(C) and cosets in the partition p,,N(C)/C_rN,

m = ktC t,

< k(p,,N(C))
< N-i

_< min{K,N- K}. (5.5)

Therefore, for 0 < i < N, we have the following upper bound on Pi:

p, < min{i, K, N - K, N - i}. (5.6)

Let C -Ldenote the dual code of C. Then C "Lis an (N, N - K) linear block

code. Consider the N-section trellisdiagram for C "L. For 0 _< i _< N, let

_i(C "L) denote the state space of C "L at time-/. Then there is a one-to-one

correspondence between the states in _i(C "L)and the cosets in the partition

po,i(c-L)/Co,i-L'tr where c-L'tr05 denotes the truncation of C_i in the interval [1, i].

Therefore, the dimension of Ei(C "L) is given by

"L,tr

Mc') = k(po.,(c'L))- ). (5.7)

Note that Po,i(C "L) is the dual code of C 0,i

t' and C 0,i
"L'tr is the dual code of
po,i(C). Therefore,

_-" i -- wc"
_ O,i]

= i- k(Co,d (5.s)

D R A F T January 6, 1998, 8:40pm D R A F T

62 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

and

k/fy-L,tr$
,= i- (5.9)

It follows from (5.7), (5.8) and (5.9) that

p (c ±) = K - k(Co, )- k(C,,N). (5.10)

From (3.7) and (5.10), we find that for 0 < i < N,

pi(C J')= p,(C). (5.11)

This says that C and its dual code C ± have the same state complexity.

5.2 MINIMAL TRELLISES

An N-section trellis
issaidto be minimal ifthe totalnumber of statesin the
trellis
isminimum. A minimal trellis
isunique within isomorphism [77],i.e.,
two minimal trellises
forthe same code are isomorphic (structurally identi-
cad). The above definition
of mlnimality is commonly used in the literature.
However, a more meaningful and usefuldefinition
of minimality of a trellis
is
in terms of itsstate space dimension [Link] N-section trellis
issaid to
be a minimum state space dimension trellisifthe statespace dimension
at each time of the trellis
isminimum. A more precisedefinition
is given as
[Link] T be an N-section trellis
for an (N, K) code C with state space
dimension profile(P0,Pt,...,Ply). T is said to be minimal if,for any other
N-section trellis
T' for C with state space dimension profile(P'o,P_,...
,P_v),
the followinginequalityholds:
pi < p_,

for0<i<N.
Suppose a minimum state space dimension trellis T exists. Then, it is clear
that T is a minimal trellis in total number of states. The formulation of state

spaces given in Section 3.4 results in a minimum state space dimension trel-
lis (or minimal trellis) for an (N, K) linear block code. This will be proved
in Theorem 5.1. This says that a minimum state space dimension trellis T
exists for any linear block code C. From the uniqueness of a minimal trellis
in total number of states within graph isomorphism, the minimal trellis is a

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS COMPLEXITY 63

minimum state space dimension trellis. This gives the equivalence between the
two definitions of minimality of a trellis for a linear block code.

Theorem 5.1 Let C be a binary (N, K) linear block code with trellis oriented
generator matrix G. The N-section trellis T for C constructed based on G is a
minimum state space dimension trellis.
Proof: We only need to prove that for 1 < i < N, the number of states, 2 p',

at time-/in the trellis T is minimum over all the trellises for C, where

= K - k(Co,d -

Let C_ denote the linear subcode of C that is spanned by the rows in the
submatrix G_ of G. Then IC_I = 2 a'. For two different codewords u and v in
C_, it follows from condition (1) of a TOGM that

This implies that

: = • C }l = 2.,.
Suppose there is a trellis T t for C whose number of states at time-/is less
than 2 p'. Then, there must be two different codewords u and v in C_ such
that: (1) there are two paths connecting the initial state to a state tr at time-/
in T' whose label sequences are po,i(u) and po,iCv), respectively; and (2) there
is a path connecting the state a to the final state in T _ whose label sequence is
pi,N(U). Without loss of generality, we assume u # 0.
Let u' denote the binary N-tuple such that po,:(u') = po,:(v) and pi,N(U') =
pi,N(U). Since u' is a path in T' connecting the initial state to the final state,
it follows from condition (4) of Definition 3.1 of an N-section trellis for a linear
block code that u' is a codeword in C. Therefore, u + u_ • C. Note that
po,:(u + u') = po,i(u) + po,:(v) # 0 and pi,N(U + U') = pd,N(U) + pi,N(U') = O.
This implies that u + u _ • C0,:. There are three cases to be considered:

(1) Suppose u _ • Co,i. This implies that u • Co,: which is a contradiction

to the hypothesis that u • C_ and u # 0.

(2) Suppose u' • C_'. This implies that u + u' • C_. Since u + u' # 0,
u + u _ can not be in both C_ and C0,:. This results in a contradiction.

D R A F T January 6, 1998, 8:40pm D tt A F T

64 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

(3) Suppose u _ E Cij¢. This implies that u E Co,i (_ Cijv, which is not
possible.

Therefore, u + u _ can not be a codeword in C. This results in a contradiction

to our earlier hypothesis that there exists an N-section trellis T _ for C whose
number of states at time-/is less than 2 p'. Therefore, the hypothesis is invalid
and 2 p' gives the minimum number of states at time-/for 1 < i < N.
/xA

It followsfrom Theorem 5.1 that Eq.(3.7) gives the minimum state space
dimension Pi with 0 < i < N foran N-section trellis
foran (N, K) linearblock
code. Prom (3.7),we see that the state space dimension p_ at time-/depends
on the dimensions of the past and future codes, Co,i and Ci,N. For a given
code C, k(Co,i) and k(Ci,N) are fixed.
Given an (N, K) linear block code C, a permutation of the orders of the bit
(or symbol) positions results in an equivalent code C t with the same weight
distribution. Different permutations of the bit positions may result in different
dimensions, k(Co,i) and k(Cijv), of the past and future subcodes, Co,i and
Ci,N, and hence different state space dimensions pi at time-i. A permutation
that yields the smMhst state space dimension at every time of the code trellis is
called an optimum permutation (or bit ordering). It is clear that an optimum
permutation reduces the state complexity and is often desirable. Optimum
permutation is hard to find, however optimum permutations for RM codes
are known [45] but they are unknown for other classes of codes.

5.3 BRANCH COMPLEXITY

The branch complexity of an N-section trellis diagram for an (N, K) linear

block code C is defined as the total number of branches in the trellis. This

complexity determines the number of additions required in a trellis-based de-

coding algorithm to decode a received sequence.
Consider the N-section treUis diagram T for C which is constructed based
on the rules and procedures described in Chapters 3 and 4. Recall that at
time-/with 0 _< i < N, there are two branches diverging from a state in P.i(C)
if there exists a row g" in Gff; and there is only one branch diverging from a

D R A F T January 6, 1998, 8:40pro b R A F T

 TRELLIS COMPLEXITY 65

state in Zi(C) if there exists no such row g" in G[. Define

1, if #"
I,(_') _= 2, g- e¢ G{.
G{, (5.12)
Let E denote the total number of branches in the N-section trellis T. Then
N-1

E = _ Ir.,(C)l.I,(g')
i----0
N-1

= _-a 2"''Ii(g'). (5.13)

i=0

Example 5.1 Again we consider the (8, 4) linear block code given in Exam-

ple 3.1. From Table 4.1, we find that

lo(g') = It(g') = I2(g') = h(g °) = 2

and

I3(g') = h(g') =/,(g') = I7(g') = 1.

The state space dimension profile of the 8-section trellis for the code is (0, 1,

2, 3, 2, 3, 2, 1, 0). From (5.13), we have

E = 2°.2+21"2+22"2+23"1+22"2+23"1+22"1+ 21"1

= 2+4+8+8+8+8+4+2

= 44.

AA

An N-section trellis diagram for an (N, K) linear block code is said to be

a minimal branch (or edge) trellis diagram if it has the smallest branch

complexity. A minimal trellis diagram has the smallest branch complexity [69].

Branch complexity also depends on the bit ordering of a code. Proper permuta-

tion of the bit positions of a code may result in a significant reduction in branch

complexity. A permutation that results in minimal branch complexity is called

an optimum permutation. From (5.13), we can readily see that a permutation

which minimizes each product in the summation of (5.13) is a minimal edge

trellis diagram. A good permutation in terms of branch complexity should have

the following property: for 0 < i < N, when pi is large, Ii(g °) should be equal
to 1.

D R A F T January 6, 1998, 8:40pro D R A F T

66 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

S.4 TRELLIS STRUCTURE OF CYCLIC CODES

Consider an (N, K) cycliccode C over GF(2) generatedby the followingpoly-

nomial [62],

g(X) = 1 + glX + _X 2 +... + gN-K-IX N-K-I + X N-K,

where for 1 _< i < N - K, gi E GF(2). A generator matrix for this cyclic code
is given by

1 gl _ ...... gN-K-1 1 0 0 ... O"

0 1 gl g_ ...... gN-K-! 1 0 .." 0

G (s.14)
".

0 0 ... 0 1 gl g2 .... gN-K-1 1

The K rows of G are simply the K cyclic shifts of the first row. This generator
matrix has the following properties:

(1) It is in trellis oriented form.

(2) For 1 < i < K, the span of the i-th row gi is

span(gi) = [i, N - K + i].

(3) The active spans of aU the rows have the same length, N - K.

Now we consider the bit-level trellis structure for this (N, K) cyclic code.
There are two cases to be considered: K > N - K and K _< N - K. Consider
the case for which K > N - K. For 1 < i < N - K, the number of rows whose
active spans contain the time index i is i. These rows are simply the first i
rows. For N - K < i _< K, the number of rows whose active spans contain the
time index i is N - K. For K < i _< N, the number of rows whose active spans
contain the time index-/is N - i. Since i > K,

N-i<N-K.

From the above analysis, we see that the maximum state space dimension is
Pmax(C) = N - K and the state space profile is

(0,1,...,N- K- 1,N- K,...,N- K,N- K- 1,...,1,0).

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS COMPLEXITY 67

Now consider the second case for which K < N - K. For 1 < i < K, the
number of rows whose active spans contain the time index i is i (the first i
rows). For K < i < N- K, the number of rows whose active spans contain the
time index i is K. For N - K < i <_.N, the number of rows whose active spans
contain i is N - i. Since i > N - K, N - i < K. From the above analysis, we
find that the maximum state space dimension is

p_.x(C) = K,

and the state space dimension profile is

(0,1,...,K- 1,K,...,K,K- l,...,1,0).

Putting the results of the above two cases together, we conclude that for an
(N, K) cyclic code, the maximum state space dimension is

pm,x(C) = rrfin{ g, N - K }.

This is to say that a code in cyclic form has the worst state complexity (i.e., it
meets the upper bound on the state complexity).
The generator polynomial g(X) of an (N, K) binary cyclic code C divides
X 2v + 1 [62]. Let
x N + 1 = g(X)h(X).
Then h(X) is a polynomial of degree K of the following form:

h(X) = i -b hlX d" h2 X2 "{-"'" -}- hE-1XK-1 d- X K

with hi E GF(2) for 1 _< i < K. This polynomial is called the parity-check
polynomial. The dual code C 1 of C is an (N, N-K) cyclic code with generator
polynomial

XKh(X -1) = 1 + hK-1X +'" + hlX K-1 + X K.

The generator matrix for the dual code C ± is

H= 0 0 1 hK-l hK-2 ............... 1 ... (5.15)

0 1 hK_ 1 hK_ 2 ............... 1 0 ...

0 ......... 0 1 hK-lhK-2"'"

D R A F T January 6, 1998, 8:40pm D R A F T

68 TRELLISES
ANDTRELLIS-BASED
DECODING ALGORITHMS

which isin trellis

orientedform. The trellis
structurefor C ± can be analyzed
in the same manner as for C.

The trellisof a cycliccode has mirror symmetry, i.e.,the right-halfand

left-half
of the trellis
with respectto the centerare structurallyidentical.
To reduce the state complexity of a cycliccode, a permutation of the bit
positionisneeded [45,46].
The branch complexity of the N-sectiontrellis
diagram T constructed based
on the TOGM G given by (5.14)can be [Link] we note that

/__(g . ) = { 2,
1, for0<i<K,
otherwise.

Suppose K < N - K. Then branch complexity of the trellis T is

K-I K-I
E --_ _ 2' . 2-1- (N-- 2K) . 2K -1- __ 2K-' . 1
i=0 i----0
= 2. (2_ - l) + (N - 2K). 2K+ 2. (2_ - 1)
= (N-2K+4).2K-4. (5.16)

For K > N- K, we have

N-K-I N-K-I
E = 2'. 2+ 2. N)-2 + 2"-"'
i=0 i=0
= (4K- 2N+4).2 _V-K- 4. ([Link])

5.5 TRELLISES FOR NONBINARY LINEAR BLOCK CODES

The methods for constructing trellises for binary linear block codes can be gen-
eralized for constructing trellises for nonbinary linear block codes with symbols
from GF(q) in a straightforward manner. The symbol-level N-section trellis
diagram for an (g, K) linear block code C over GF(q) has the following basic
properties: (1) every branch is labeled with a code symbol from GF(q); (2)
except for the initial state, every state has at least one, but no more than q,
incoming branches; (3) except for the final state, every state has at least one,
but no more than q, outgoing branches; and (4) the initial state has no in-
coming branch and the final state has no outgoing branch. In the definition of

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS COMPLEXITY 69

a trellis oriented generator matrix, the leading "1" and trailing "1" of a row

are replaced by leading and trailing "nonzero components", respectively. The

maximum state space dimension pm_x(C) of the minimal N-section trellis for

C is upper bounded by

Pmax(C) __<min(K,N - K},

and the maximum number of states, [E(C)[m_, is upper bounded by

iS(C)lm.., < _,,{x,_-K}.

For Reed-Solomon (RS) codes over GF(q), the above equalities hold, i.e.,

p_,x(C) = min{K, N - K},

and
IS(C)l,... = qmin{K,N-K}.

D R A F T January 6, 1998, 8:40pro D tt A F T

 6 TRELLIS SECTIONALIZATION

So far, we have only considered bit-level N-section trellis diagrams for linear
block codes of length N. In a bit-level trellis diagram, every time instant in
the encoding interval F = {0, 1, 2,..., N} is a section boundary location and
every branch represents a code bit. It is possible to sectionalize a bit-level
trellis with section boundary locations at selected instants in the encoding
interval F. This sectionalization results in a trellis in which a branch may rep-

resent multiple code bits and two adjacent states may be connected by multiple
branches. Proper sectionalization may result in useful trellis structural prop-
erties and allow us to devise efficient trellis-based decoding algorithms. This
chapter is devoted in analyzing sectionalized trellis diagrams for linear block
codes. Section 6.1 presents the concepts and rules for trellis sectionalization.
In Section 6.2, the branch complexity and state connectivity are analyzed and
expressed in terms of the dimensions of codes related to the code being con-
sidered. In Section 6.3, construction of a sectionalized trellis diagram for a

D R A F T January 6, 1998, 8:40pro D R A F T

72 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

linear block code based on the trellis oriented generator matrix is presented.
Section 6.4 studies the parallel structure of a sectionalized trellis diagram.

6.1 SECTIONALIZATION OF A CODE TRELLIS

For a positive integer L _<N, let

U A .{he, hx,he,... ,h_} (6.1)

be a subset of L + 1 time instants in the encoding interval F = {0, 1, 2,..., N}

for an (N,K) linear block code C with 0 = he < hi < h2 < ... < hL = N.
An L-section trellis diagram for C with section boundaries at the locations
(time instants) in U, denoted T(U), can be obtained from the N-section trellis
T by: (1) deleting every state in _]h(C) for h E {0,1,... ,N} \ U and every
branch to or from a deleted state, and (2) for 1 _ j _ L, connecting a state
a E Ehj_l to a state a _ E Ehj by a branch with label a if and only if there is a
path with label a from state a to state a' in the N-section trellis T. In an L-
section trellis with boundary locations in U = {h0, hi,..., hL}, a branch from
a state in Ehj_,(C) to a state in Eh,(C) represents (hi - hi_l) code symbols.
A subgraph of a trellis diagram is called a subtrellis. The subtrellis of
T(U) which consists of the state space Eh__,(C) at time-h/_l, state space
_h_(C) at time-hi, and all the branches between the states in )']h__,(C) and
Ehj (C), is called the j-th section of T(U). The length of the j-th section is
hj - hi_ 1. If the lengths of all the sections of an L-section code trellis T(U)
are the same, T(U) is said to be uniformly sectionalized. In an L-section
trellis diagram with L < N, two adjacent states may be connected by multiple
branches (called parallel branches) with different labels.
Let ph s _= log s [_h# (C) I be the dimension of the state space ]Eh, (C) at time-
h 1. Then
(p0, Phi, ph,, • • •, P_L-I, PN)

is the state space dimension profile of the L-section code trellis T(U) with
section boundary set U = {0, h_, h2,..., hL-_, N}. From (3.7), we have

Ph# = K - k(Co,h,) - k(Ch,,N) . (6.2)

If we choose the section boundaries, U = {h0, hi,..., hn}, at the places where
Phl,Ph3,... ,PhL-I are small, then the resultant L-section code trellis T(U) has

D R A F T January 6, 1998, 8:40pro D R A F T

 TRELLIS SECTIONALIZATION 73

ao a I

Figure 6.1. A 4-section trellis for the (8, 4) RM code.

a small state space dimension profile. The maximum state space dimension is

pL,_(C) _ max Ph,.

---- (6.3)
O<i<L "

In implementing a trellis-based decoder, such as a Viterbi decoder, a proper

choice of the section boundary locations results in a significant reduction in

decoding complexity.

Example 6.1 Again, we consider the (8,4) RM code given in Example 3.1

whose 8-section trellis diagram is shown in Figure 3.2 (or Figure 4.1). Suppose

we choose L = 4 and the section boundary set U = {0,2,4,6,8}. Follow-

ing the above rules of sectionalization of a code trellis, we obtain a uniform

4-section trellis diagram as shown in Figure 6.1, in which every branch repre-
sents 2 code bits. The state space dimension profile for this 4-section trellis

is (0,2,2,2,0) and the maximum state space dimension is P4,max(C) = 2. It

is a 4-section, 4-state code trellis. From Figure 6.1, we notice that the right-

half of the trellis (the third and fourth sections) is the mirror image of the

left-half of the trellis (the first and second sections). This mirror symmetry

allows bidirectional decoding. Furthermore, the code trellis consists of two

parallel and structurally identical (isomorphic) subtrellises without cross

connections between them. This parallel structure allows us to devise two

identical 2-state (Viterbi) decoders to process the trellis in parallel. The mirror

D R A F T January 6, 1998, 8:40pro D R A F T

74 TRELLISES AND TRELLIS-BASED DECODINGALGORITHMS

symmetry and parallel structure not only simplify the decoding complexity but
also speed up the decoding process. For large code trellises, these structural
properties are very important in IC (integrated circuit) implementations.
AA

An L-section trellis diagram obtained from a minimal N-section trellis dia-

gram by deleting states and branches at places other than the section boundary
locations is minimal, i.e., it is a minimal L-section trellis diagram for a given
section boundary set U.

6.2 BRANCH COMPLEXITY AND STATE CONNECTIVITY

Consider the j-th section of a minimal L-section trellis diagram T(U) with
section boundary set U -- {ho,hl,... ,hL} for an (N,K) linear code C. The
boundaries of this section are hi_l and hi. Each branch in this section is
labeled with hj - hi-1 bits. Let a and _' be two adjacent states in the state
spaces _n,_l (C) and _hj (C), respectively. Let L(a, a t) denote the set of parallel
branches connecting _r and or'. Let L(cr0, _r) denote the set of paths connecting
the initial state or0 to the state s,. Sometimes, it is convenient to regard the
parallel branches, L(a, at), between two states as a single branch. This single
branch is called a composite branch, and L(cr, a _) is called a composite
branch label.
The branch complexity of a trellis section is measured by: (1) the size of a
composite branch; (2) the number of distinct composite branches in the trellis
section; and (3) the total number of composite branches in the trellis section.
The overall branch complexity of the trellis is then the sum of the trellis section
branch complexities. These three branch complexity parameters can be ex-
pressed in terms of the dimensions of Chj_l,h_, C0,h#_l, Ch_,A', and Ph__l,h_ (C)
which can be obtained from the TOGM G of C.

Let ah__l and _rh# be two adjacent states with _hj-i E _h__l(C) and cr_j
E Ehi(C). It has been shown in Section 3.7 that the parallel branches in
L(ah___, _hj) form a coset in the partition

tr

pn,_,,h,(C)/Ch__,,_,,.

D R A F T January 6, 1998, 8:40pro D R A F T

 TRELLIS SECTIONALIZATION 75

Therefore, the number of parallel branches between two adjacent states ah__1

and ah# in the j-th section of T(U) is

IL(,,n,_,,ah,)l = 2_(c",-1.',). (6.4)

In Section 3.7, we have also shown that

L(a0, ah#_, ) 6 Po.n,_, (C)/C_'a,_I (6.s)

and

L(ao,,%) epo,h,(c)IC_',n,. (6.6)

Ifan,_1 and an, are adjacent, then

L(ao,an,_,) o L(ahj_:,ah,)

{U 0 V: U e n(ao, an,_1 ) and v e L(ah,_,, an, )}, (6.7)

is the set of paths in T(U) that diverge from the initial state a0, converge

at the state an#_,, and then transverse the parallel branches in L(anj_l,an,)

to the state o'nj as shown in Figure 6.2. It has also been shown in Sec-

tion 3.7 that L(ao,an,_,) o L(ah#_,,ah_) is a subcode of a coset in the par-

tition po,h# (C)/Ct:n#. Let Y:'h,_, (an#) denote the set of states in the state space
:Enj_I (C) that are adjacent to state an# as shown in Figure 6.2. Then

U LCao,an,_,) oL(a.,_l, an,) _ LCao,an,) (6.8)

is a ¢osetin the partitionP0,n,(C)/C_%.

Note that the dimensions of L(ao, an,_1), L(ah,_,, an,) and L(ao, an#) are
klC tr _ k,C tr _ k/C tr
o,h#_,J, ( nj_,,njJ and t 0,h,J, respectively. It follows from (6.8) that
the number of states in 3_uj_l (ah_) is given by

klCtf _ k_C _ _ kiC_r

Ir%_,(an,)l = 2' o_,,-, o.,_,,-, .,_,.,)
= 2k(c°.%)-_(c°.%-,)-_(c%-,'% } (6.9)

This implies that the number of composite branches converging into a state

anj E _ni(C), called the incoming degree of anj, is given by

deg(o'nj)ia a_ 2k(Co,,.fl-k(Co.,.__l)-k(C%_,.,,,). (6.10)

D R A F T January 6, 1998, 8:40pm D R A F T

76 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

l l
Time-hj_t Time-hi

Figure 6,2. State connectivity.

This number is a measure of the state connectivity of the sectionalized code

trellis T(U). In an IC implementation of a Viterbi decoder, this number is

known as the radix number, a key design parameter.

Since each composite branch L(crh__l,_rh,) in the j-th section of T(U) is a

coset in the partition Phj__,hj (C)/Cth__s,h_, the number of distinct composite

branches in the j-th section of T(U) is

2k(nh__,,hj(C))--k(Ch_-I,"j). (6.11)

It follows from (6.2) and (6.10) that the total number of composite branches in

the j-th section of T(U) is given by

2K--k(Co'h_-l)--k(Chj'N)--k(ChJ-l'_J ). (6.12)

From (6.11) and (6.12), we find that each distinct composite branch appears in

the j-th section of T(U)

2/(- _(co.hj_ 1) -_(ch, .N)-- k(nh__ l.h_ (C)) (6.13)

D R A F T January 6, 1998, 8:40pro D R A F T

 TRELLIS SECTIONALIZATION 77

times.
Prom (6.2) (with hj replaced by fij-1)and (6.12),we can compute the
number of composite branches divergingfrom a state #hj-1 E _j_I(C) at
time-fij-
i as
2t(Ch__1.N)--t(C_#.N)--h(Ch#_1.h#) (6.14)

which iScalledthe outgoing degree of ch#_s,denoted deg(ch#_s)o,[Link]-

tions (6.4),(6.10)-(6.12)
and (6.14)givethe branch complexity and statecon-
nectivityof the j-th sectionof a minimal L-sectiontrellis
T(U) with section
boundary locationsin U = {rio,
hl,...,h/,).
Define
5 3 A log_ deg(_h#)iu

with anj E End(U). The ordered sequence (#1,6:,...,5L) is called the con-
verging branch dimension profile (CBDP). Define

Aj A log 2 deg(o'_,_)out.

The ordered sequence (A0,A1,... ,AL-1) is called the diverging branch di-
mension profile (DBDP).
Let M i denote the total number of composite branches in the j-th trellis
section (given by (6.12)) and define

_j A log 2 Mj.

The ordered sequence

(_1,_,... ,_)
is called the branch complexity profile (BCP). The branch complexity of
the minimal L-section trellis T(U) in terms of the total number of branches in
the trellis is given by
L

B = _ 2_,. 2_c%-,.', _. (6.15)

j=l

Since each branch in the j-th section of T(U) represents hj - hj-1 code bits, it
is equivalent to hj - hi_ i branches in the bit-level N-section trellis T for the
code. Therefore, the branch complexity in terms of bit branches is given by
L

E = _(hj- hj__)
2_,.2_I_',-,.',_. (6.16)
j=l

D R A F T January 6, 1998, 8:40pm D R A F T

78 TRELLISES
ANDTRELLIS-BASED
DECODING
ALGORITHMS

Ifthe sectionboundary isU = {0,1,2,...,N}, then (6.16)givesthe branch (or

edge) complexity of the bit-level
N-section minimal trellis
of the code.

6.3 A PROCEDURE FOR CONSTRUCTING A MINIMAL L-SECTION

TRELLIS

A minimal L-section trellis diagram for an (N, K) linear block code C can be
constructed directly from the TOGM G. Let U = {ho, hi,..., hL} be the set of
section boundary locations with/to = 0 < hi < ... < hL-1 < hL = N. Again
the construction of the minimal L-section trellis diagram T(U) with section
boundary set U is carried out serially, section by section. Suppose T(U) has
been constructed up to the j-th section (i.e., up to time-hi) with 1 _< j <: L.
Now we begin to construct the (j -t- 1)-th section from time-hi to time-hj+l.
Partition the rows of the TOGM G into three disjoint subsets, GPj, G/, and
G'h_as follows(alsoshown in Figure 6.3):

(i) Gnh# consistsof those rows in G whose spans are containedin the interval
[1,hj].

(2) G_j consists of those rows in G whose spans are contained in the interval
[h# -I- 1, N].

(3) G'hj consists of those rows in G whose active spans contain the time
index hi.

It is clear that G_j and Gh/i generate the past and future codes, Co,hi and
Ch_,Jv,[Link] A"hj be the set of informationbits that correspond
to the rows of G 8_. Then the bits in Ash#define the state space Ehj(C) at
time-hi. That is,for any binary Ph, = [A"h_[-tuple,
which representsvalues of
information bitsin A s
hj, there isa correspondingstatein Eaj (C).

To determine the composite branches between statesin Eh# (C) and states
in Zh_+_(C) and the parallelbranches between two adjacentstates,we further
partition the rows of G/j into three subsets, Gl'Phj,hj+_, Gh_,hj+_l'"and Gfhj+l as
follows (see Figure 6.3):

(1) Gl'Ph#,hj+:
consistsof those rows of Ghf whose spans are contained in the
interval[hi+ 1,hi+l].

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS
SECTIONALIZATION
79

Time _..

0 h hi+z N

G_, 0 0

p,,.,_,, ¢at,_'.,,,) 0

o 1,s
P_j,_s+, (Ghj ,_j+, )

0 } a_,÷,
0
Phj,hj+,
(Ga,,aa+1
) 0
,I 0 Gl,V

Figure 6.3. Partition of the TOGM G.

(2) --h,,h,+,
f:-f'" consists of those rows of Gh/ whose active spans contain the
time index hj+l.

(3) The remaining rows in G_, form G lh,+,"

Let A Lp and A l's denote the subsets of information bits that corre-
hj,hi+ , h,,hj+,

spond to the rows in G y'p and _'-f" respectively. Then the information
hi,hi+, V h_,hj+ , '

bits in these two sets may be regarded as the current input information bits.
These input bits together with the state of the encoder at time-h/ uniquely
determine the output code bits between time-hi and time-hi+,. Note that
the information bits in A Lp only affect the output during the interval be-
hj,h3+l

tween time-hi and time-hj+l. Therefore, they determine the parallel branches

D R A F T January 6, 1998, 8:40pm D R A F T

80 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

between two adjacent states. The information bits in A/'° determine the
h_,hj+l

diverging composite branches from a state in Ea_ (C).

l,p
Let Ph,,h,+_ (Gh#,_j+_), Ph,,_#+i (G/_'j_h,+ x) and Ph,,hj+l (G_#) denote the trun-

cations of G f'p
h_,hj+l 1
Gfh:h#+_ and G_,# from time-hi to time-hj+l. The rows in

phi ,h j+l
,fd.p
_s"r hj,h_+l
'_span
/
the code C tr
hj,hj+l '
and the rows in ph,,h,+.(Glh_hj+,).
f,J
Ph,,a,+l (Ghj,hj+_) and ph,,aj._ (G_#) span the truncated code Pa#,a,+x (C). Then
every composite branch between a state ahs E Y'.hj(C) and a state ah#+x E

Zaj+I (C) is a coset in the partition Ph,,nj+l (C)/C_,h#+ x. The number of par-

allel branches between two adjacent states is therefore [C_,a#._ [.

Let aaj be the state at time-hi defined by the binary ph,-tuple formed by

the binary information bits in the set A_,,

where Phj= log21_j(C)l = IG"h_l" Let - (D ,g2 (i) , .-.

lgl ,g_)} denote the rows

in G_. Then

u = a_ j)" 9[J) + ag j)" g_J) +'"-F a_: ), "g_:)j (6.18/

is a codeword (or path) passing through the state ahj at time-h/. Let ph_,_,+, (u)

denote the branch on u from time-hi to time-h/+x. Let Bh_.h,+, denote the

code of length h1+1 - h I generated by p_,,.h,+, (G_:h,+x). Then for every vector

b _ Bh_,hj+_, there is a composite branch diverging from the state ahj which
consists of the following parallel branches,

(p_,,h,+, (U) + b + • : • _ C tr
h_,h.j+_ }. (6.19)

Therefore, the number of composite branches diverging from the state am, is

IB_,,_,+, [.
Next, we analyzethestatetransitions.
Partition
the matrixG_,,intotwo
submatrices, where
G_,:_,+, and G_,':,_,+,,

(1) G_:_+I consists of those rows in G °h_ whose active spans do not contain
the time index hj+_, and

(2) G_,,_+,"" consists of those rows in G'h_ whose active spans contain the
time index hj+x.

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS SECTIONALIZATION 81

Let A°'Pn_,aj+Iand A_h_+l denote the sets of information bits corresponding

to G_n,+I and G_'j',hi+_, respectively. Then the set of information bits that
defines the state space Eh,+l (C) at time-hj+l is given by

At,., -- (A_,\ A',_h,,_,+,)uA_;'_,÷,

,... o 1.,.,, (6.20)

Therefore, the state transitions from time-hi to time-hj+l are completely spec-
flied by the change from A °h_ to A °hj+l"
Define

Ph,,h,+, = IAh,,h,+,l = IG,,,h,+, I. (6.21)

Then it follows from (6.20) (also Figure 6.3) that

As'P ] = Ph, -- [Link]+l , (6.22)

and

IA_';h,,I = ,_,+, - p_,,_.,. (6.23)

Let a° be the binary (Ph_ -- Phj,h_+=)-tuple formed by the binary information

bits in the set A°'Phj,h_+l, ahj be the binary phj,hj+_-tuple formed by the infor-
mation bits in the set Ah,,h,+_,
s,8 and a_,, be the binary (Ph_+_ - ph_,hj+_)-tuple
formed by the information bits in the set Ahf':h,.. Then (a°hj,ah_) defines a
state, denoted cr(a_,, ah_), in the state space E_,, (C) at time-h/, and (am,, a'h_)
defines a state, denoted a(ah,, a_,,), in the state space Eh,+, (C) at time-hj-+x.
State a(a%, ah,) is adjacent to state a(ah,, a'h,). The composite branch that
connects these two states in the trellis is given by (6.19) with

b = a'h, .pha,h,+ , (Gfh'_h,+,). (6.24)

Note that these two states share a common ahj. For a phj _ ah,, the state c(a%,
ah#) at time-hi is not adjacent to the state a(a_h,, a_,,) at time-hj+_. Therefore,
from each state ff(O,°hj, aha) in _h, (C), there are 2P_, +' -P_'",+_ possible tran-
sitions to the states a(a_,, a_,) in _,+_ (C) with a_, • {0, 1}P_,+ x-p_,'_,+'.
This completely specifies the state transitions from time-h/to time-h_+_.
State labeling based on the state defining information set A_ with 0 < j < L
is exactly the same as described in Section 4.1. We may use either a K-tuple

D R A F T January 6, 1998, 8:40pm D R A F T

82 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

or a PL,max(C)-tuple to label a state. In general,pL,,,_x(C)is much smaller

than K, and hence using a PL,m.x(C)-bitlabelfora stateismore efficient.
Suppose an L-sectiontrellis
diagram T(U) with boundary locationsetU =
{ho,h,,...,hL} has been constructed up to time-hi. The trellis
sectionfrom
time-hi to time-h#+, can be constructed by the followingprocedure:

(1) Form and labelthe statesin Eh#+,(C) based on A_#÷.

(2) For each state in Eh,(C), determine its transitionsto the states in
Eh#+, (C) based on the statetransitionrulesdescribedabove.

(3) For two adjacent states, _,(a°h#,ah#) and ¢r(ah,,a;,,), at time-hi and
time-hi+l, connect them by parallel branches given by (6.19).

Repeat the above procedure until the L-section trellis T(U) is completed.

Example 6.2 Consider the (8, 4, 4) RM code with the TOGM G as

i 1 1 I 0 0 0 0
0 1 0 1 1 0 1 0
G ____

0 0 1 1 1 1 0 0
0 0 0 0 1 1 1 I

Suppose we want to construct a 4-sectiontrellis

forthiscode with boundary
locationsin U -- (0,2,4,6,8). First,we find from G that the state space
dimension profileis(0,2,2,2,0). Therefore,P4,max(C)= 2. We alsofindthat

C t'
0,5= C t' C" C"e,,={o},

P°'2(G°/i_)--- [11]0 1 ' p2,4(G2,,)=i. [ ] 1 1 ,

p,,s(a,,s) i,. = [ 1 1 ], Ps,s(GI:;) = 0.

The state defining information sets at the boundary locations, 0, 2, 4, 6, and 8,

are given in Table 6. I. Following the constructing procedure given above, we
obtain the 4-section trellis diagram for the (8, 4, 4) RM code as shown in Fig-
ure 6.4, where the states are labeled based on the information defining sets
using p,,max(C)-tuples with p,,max(C) = 2.
AA

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS SECTIONALIZATION 83

Table 6.1. State defining information sets for a 4-section trellis for the (8, 4, 4) RM code.

Time

0 2 4 6 8

A"
hs 0 {a_,a2} {a2,a__} {a_,_4} 0

AI,,
hj,hj+l
{a_ a_} {,,_) {_,} 0 0

Statelabel (al,_2) (a2,_3) (_2,a4)

fro a!

10_01

Figure 6.4. A minimal 4-section trellis diagram for the (8, 4, 4) RM code with 2-bit state
labels.

Construction of T(U) can be achieved by using the state labeling based on

a parity-check matrix H for C [101]. Let

Hh,,h_+_ -- [hhj+l, hh#+z,..., hh#+,] (6.25)

denote the submatrix of the parity-check matrix H of C that consists of columns

from hhj+l to hhj+,. Let l(_Yhj) be the label for the state ahj. Then the

composite branch given by (6.19) connects the state ah, to the state a_i+ _ E

Ehj+_ (C) at time-h/+1 that is labeled by

l(ahj+,) ----l(ah,) ÷ (ph,,h,+,(u) % b). I_h,,h#+ . (6.26)

D R h F T January 6, 1998, 8:40pro D R A F T

84 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

Eq.(6.26)gives the connection from a startingstateah, at time-hi to a desti-

nation state erh,+1at tirne-hj+,.
To facilitate
the constructionof the (j+ 1)-thtrellis
sectionbetween time-
hj and time-hi+x, we form a table,denoted Qh#, at the completion of the
constructionof the [Link] entry in Qh# isa triplet,

(1,1(.),
c).

The first
component f isa binary ph,-tupleformed by a specificcombination
of the p_j information bitsin A ha"
s This ph#-tupledefinesa specific
statea in
Eh, (C). The second component l(_r)issimply the labelof state #. The third
component isgiven by

= Ph,.hj+_
(.f"
G_#), (6.27)

where u = f. G_j is given by (6.18).

Construction of the (j + 1)-th section of T(U) is carried out as follows:

(1) Form C_,r,h,+, and Bh,,h,+,.

(2) For every entry (f,/(a),c) e Qh, and every b E Bhj,h,+l, form the
composite branch,

{b+c+z : z • C_r#,h#+,}, (6.28)

(3) For every starting state a • Ehj(C), and b • Bhj,h,+,, the destination
state a' • Eh,+,(C) is labeled with

l(.') = l(.)+(b+c) T
•ghj,h,+,• (6.29)

Repeat the above process until the L-section trellis T(U) is completed.
The trellis construction procedures presented in Section 4.1, Section 4.2, and
this section only provide the general steps of construction. A detail and efficient
trellis construction procedure is given in Appendix A.

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS SECTIONALIZATION 85

6.4 PARALLEL STRUCTURE

Consider the trellis section from time-h I to tlme-hi+t. For a given Phj,h#+s"

tuple ah_, define the following two sets of states at time-h I and time-hi+l,
respectively:

= ): o • 10, (6.30)
and

=" .;, e {0, }. (6.30

Then SL(ah,) and SR(ah,) are subspaces of the state spaces, _%(C) and
_%+1 (C), respectively. From the state transition analysis given in the previous
section, we observe the following:

(1) Every state in SI,(a%) is adjacent to all the 2Ph'+l--Ph''h#+ 1 states in

SR(ah#) and is not adjacent to any other state in _%+_(C).

(2) Every state in SR(a%) is adjacent from all the 2P_#-Ph#'%+* states in
SL(ah_) and is not adjacent from any other state in _hj(C).

Therefore, the states in SL(a%), the states in Sn(a%), and the composite
branches connecting them form a completely connected suhtrellis (known
as a complete bipartite graph). Since there are 2P_J'hJ+1 possible p%,%+_-
tuple a%, there are 2Ph,'%+ * such completely connected subtrellises in the
trellis section time-h/ and time-hj+l. All these subtrellises are structurally
identical (isomorphic), and there are no cross connections between them.
These subtrellises are called parallel components. The parallel structure of
a trellis section is shown in Figure 6.5.
It follows from the definition of P%,h_+! given by (6.21) and the partition of
the TOGM G shown in Figure 6.3 that

Ph,,h,+, = K -- k(Ch,,N) -- k(Co.%+,) + k(C%,%+ 1). (6.32)

Therefore, the total number of parallel components in the trellis section from
time-h/to time-hj+l is

2K-k(C%._)-k(Co.%+O+l,(C%.%+ _). (6.33)

D R A F T January 61 1998, 8:40pm D R A F T

86 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

• time hi hj+l

2Ph#--P_#'h#+II_
Istates 2Ph#+1-Ph#'"#+tstates

2Phj._#+._
parallel
components

2PhJ--OhJ'_'J+_I_
states 1 20hJ+_
states--Phi'hJ+'

r,h,(c) r,h,+,(c)

Fisure 6.5. Parallel structure in a trellis section.

From (6.2) and (6.33), we find that the numbers of states in SL(ah,) and
SR(ah,) are:
2k(co._j+_ )-k([Link])-k(C_._+z) (6.34)

and

2k(c_j .,,..)-k(Chj+ 1.:v)-Ic(C,,_.hj+ s), (6.35)

respectively. Equations (6.30) to (6.35) completely characterize the parallel

components in the (j + 1)-th trellis section of T(U).
Consider the 4-section trellis diagram for the (8, 4) RM code shown in Fig-
ure 6.4. There are two parallel components in both the second and third sections
of the trellis. Each component has two states at each end.
Analysis of the parallel structure of a sectionalized code trellis is presented
in the Appendix A.

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS sEcTIONALIZATION 87

4 states 4 states 4 states

ao al

4 states 4 states 4 states

a coset of RMo,2 in RM2,2

Figure 6.6. The 4-section minimal trellis diagram T({0, 4, 8, 12, 16}) for RM2,4.

Example 6.3 Consider the RM2,4 code which is a (16,11) code. The 4-
section minimal trellis diagram T(U) with section boundary locations in U --

{0, 4, 8, 12, 16} is depicted in Figure 6.6. There are two parallel and structural
identical components in both the second and third sections of the trellis, and

each component is a complete bipartite graph. Each component has 4 states at

each end. Each state at boundary location 8 has 4 composite branches diverg-

ing from it. For 1 _< j _< 4, p4(i_l),4i(RM2,4) = RM2,2 and C tr4(i_1),41 = RMo,2.
Therefore, there are 2 parallel branches between any two adjacent states whose

4-bit label sequences form a coset of RM0,2 in RM2,2. In both the second and

third sections of the trellis, each coset in RM2,2/RM0,2 appears 4 times as the

D R A F T January 6, 1998, 8:40pm D R A F T

88 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

composite branch label. In fact, the entire trellis consists of two 4-section par-
allel and structurally identical subtrellises without cross connections between
them. The maximum state complexity is 8. Therefore it is possible to devise
two identical trellis-based decoders, say Viterhi decoders, to process the entire
trellis in parallel. This not only simplifies the decoding complexity but also
speeds up the decoding process.
AA

The parallel components in a trellis section can be partitioned into groups of

the same size in such a way that [44]: (1) two parallel components in the same
group are identical up to path labeling, and (2) if there is a common label
sequence in two parallel components, then they are in the same group. Since all
the parallel components in a group have the same label set, in a trellis-based
decoding algorithm, only the metrics of the branches in one of the parallel
components need to be computed. This results in a reduction of branch metric
computation.
Let Ca_,h,+, denote the subcode of C that consists of those codewords
whose components from the (hi + 1)-th bit to the hj+l-th bit positions are
all zero. Then each group consists of 2 xh, .h,+, (c) identical parallel components
where [44]

_n,,n,., (c) = k(G,,_,.,) - k(po,h,(Co,h,+,)n po.h,(G,,a,÷,)) -- a(Ch,+,,M).

(6.36)

Each paralhl component can be decomposed into subtrellises with simple

uniform structure [44] as shown in Figure 6.7. Consider a parallel compo-
nent, denoted A. Let _h, (A) and _n_+l (A) denote the state spaces at two ends
of A. We first partition En# (A) into blocks, called left U-blocks, which satisfy
the following condition:

(B1) If two statesan, and a'h# in _n# (A) are in the same leftU-block, then
they have the same setof divergingcomposite branches,i.e.,

{L(_n,,_n,+,) : an., e r%+,(^))

= {L( a'h#,ah,+,) : an#+, • r%+,(^)} (6.3?)

D R A F T January 6, 1998, 8:40pro D R A F T

 TRELLIS SECTIONALIZATION 89

A left A U-block pair and A right

U-block branches between them U-block

r-

Time hj h j+l

Figure 6.7. Partition of a parallel component.

D R A F T January 6, 1998, 8:40pm D R A F T

90 TRELLISES AND TRELLIS-BASED DECODING ALGORITHMS

and otherwise

e
(6.38)

We next partition _hj+l (A) into blocks, called right U-blocks, which satisfy
the following conditions:

(B2) If two statesaa)+, and a' hj+l in _h)+l (h) are in the same right U-block,
then they have the same set of converging composite branches, i.e.,

{L(ah,,ahj+,): a_, E _h,(A)) = (L(ah,,_,_+,): ah) E _h,(A))

(6.39)
and otherwise

{L(ah,,ah,+,) : ah, e _h)(h)} N {L(ah,,a_,+,) : ah, e Eh,(A)) = 0.

(6.40)

Each left U-block (or right U-block) consists of 2 v',''*+' (c) states [44], where

va,,n#+,(C) _=k(po,h)+,(_h,,hj+, n (Co,at+ , ¢_ ebb,N))) -- k(Co,hj). (6.41)

A pair of a left U-block and a right U-block is called a U-block pair. It follows
from the conditions (B1) and (B2), that eaz.h U-block pair (Bh, Bh_+, ) has the
following uniform properties:

(1) For any two states ah_+l and a ph_+t in Bh,+,,

{L(_h,,an,+,) : ah, • Bh)} = (L(an,,a_,+,) : a,,, • Bh,). (6.42)

(2)For any two states _n# and a _hj in Bn_,

(L(an,, an,+,): an,+, • Bn,+, } = {L(a_,, an,+,): ah_+l • Bn,+, }.

(6.43)

D R A F T January 6, 1998, 8:40pm D R A F T

 TRELLIS SECTIONALIZATION 91

The first property simply says that for a U-block pair (Bha,Bhl+t), the set
of composite branches from states in the left U-block Bh2 converging to any
state in the right U-block Bh_+_ is the same. The second property simply
says that the set of composite branches diverging from any state in Bhj to
states in Bhj+_ is the same. Two different U-block pairs have mutually disjoint
composite branch sets.

D tt A F T January 6, 1998, 8:40pro D It A F T