Preliminaries

Let
*H* = [*h*_{ij}] be an
*r*×*n* matrix, with entries drawn from
the finite field
IF_{q} of order *q*. We let * denote a nonzero entry
in *H*. Given *H*, we define a bipartite graph *T* as follows: the
vertex set of *T* consists of the set
= {*x*_{1}, *x*_{2},..., *x*_{n}}
of *symbol* vertices and the set
= {*y*_{1}, *y*_{2},..., *y*_{r}} of
*check* vertices;
there is an edge (*y*_{i}, *x*_{j}) in *T* if and only if
*h*_{ij} = *.
Thus the neighborhood of the vertex
*y*_{i} corresponds to the *i*-th
row of *H*, and the neighborhood of the vertex
*x*_{j} corresponds
to the *j*-th column of *H*. We say that *T* is the *Tanner graph* of
*H*, and denote *T* = *T*(*H*). It is obvious that every matrix defines a unique
Tanner graph. Over
IF_{2}, the converse is also true: every bipartite
graph *T* defines a unique binary matrix *H* such that *T* = *T*(*H*), which
is the
, adjacency matrix of *T*.

We say that a bipartite graph *T* *represents* the linear
code
, or simply that *T* is a Tanner graph for
, if
there exists a parity-check matrix *H* for
such that *T*
is the Tanner graph of *H*. In general, a given linear code
can be represented by many distinct Tanner graphs. On the
other hand, over
IF_{2}, a given Tanner graph represents a unique
binary code.

We say that a matrix *H* is *cycle-free* if the corresponding Tanner
graph *T*(*H*) is cycle-free. Notice that every submatrix of a cycle-free
matrix is also cycle-free. We say that a linear code
over
IF_{q} is
*cycle-free* if there *exists* a cycle-free parity-check
matrix for
. Observe that if the matrices *H* and *H'* differ
by a permutation of rows and columns then the
Tanner graphs *T*(*H*) and
*T*(*H'*) are isomorphic. On the other hand, if *H* and *H'* differ by a sequence
of elementary row operations then *T*(*H*) and *T*(*H'*) are generally not
isomorphic. Thus it is possible to have two parity-check matrices
for the same code, one of which is cycle-free while the other is not.
It is also possible to have two cycle-free Tanner graphs for the same
code that are not isomorphic.

However, the code
is, in fact, cycle-free
since adding the first row of *H* to the second row produces a cycle-free
parity-check matrix *H'* for
.
The graph *T*(*H'*) shown in Figure 3.1b is a cycle-free Tanner graph
for
.

width4pt depth2pt height6pt

A cycle-free graph consisting of a single connected
component is called a tree, and a multiple-component
cycle-free graph will is a forest.
The following simple lemma will serve as our starting point.
This lemma is well-known in graph theory - see,
for instance, West [64, p.52] - and is based on
the fact that
| *E*| = | *V*| - 1 for trees.

Since every forest contains at least one tree, we have

for any cycle-free graph. If

in view of (3.2).

http://people.bu.edu/trachten