Preliminaries

Let H = [hij] be an r×n matrix, with entries drawn from the finite field IFq 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 $ \cal {X}$ = {x1, x2,..., xn} of symbol vertices and the set $ \cal {Y}$ = {y1, y2,..., yr} of check vertices; there is an edge (yi, xj) in T if and only if hij = *. Thus the neighborhood of the vertex yi$ \mbox{$\,\inn\,$}$$ \cal {Y}$ corresponds to the i-th row of H, and the neighborhood of the vertex xj$ \mbox{$\,\inn\,$}$$ \cal {X}$ 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 IF2, the converse is also true: every bipartite graph T defines a unique binary matrix H such that T = T(H), which is the $ \cal {X}$,$ \cal {Y}$ adjacency matrix of T.

We say that a bipartite graph T represents the linear code $\ensuremath{\mathbb{C}}$, or simply that T is a Tanner graph for $\ensuremath{\mathbb{C}}$, if there exists a parity-check matrix H for $\ensuremath{\mathbb{C}}$ 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  IF2, 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 $\ensuremath{\mathbb{C}}$ over IFq is cycle-free if there exists a cycle-free parity-check matrix for  $\ensuremath{\mathbb{C}}$. 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.

Example 3..1   Suppose that a parity-check matrix H for the (5, 2, 3) binary linear code $\ensuremath{\mathbb{C}}$ is given by

H  = tex2html_image_mark>#tex2html_wrap_indisplay17051#$\displaystyle \begin{array}{ccccc}
1 & 0 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 & 0
\end{array}$$\displaystyle \left.\vphantom{
\begin{array}{ccccc}
1 & 0 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 & 0
\end{array}}\right]$

The corresponding Tanner graph T(H) is shown in Figure 3.1a. Notice that H is not cycle-free, since the sequence of edges (x1, y1),(y1, x3),(x3, y2),(y2, x1) constitutes a cycle.

Figure 3.1: Tanner graph with cycles and cycle-free Tanner graph for the same code.
\begin{figure}\centerline{\psfig{figure=Figures/tanner-fig1.eps}}\par\end{figure}

However, the code $\ensuremath{\mathbb{C}}$ 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 $\ensuremath{\mathbb{C}}$. The graph T(H') shown in Figure 3.1b is a cycle-free Tanner graph for $\ensuremath{\mathbb{C}}$.

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.

Lemma 3..2   A graph $ \cal {G}$ = (V, E) is cycle-free if and only if | E| = | V| - $ \omega$($ \cal {G}$), where $ \omega$($ \cal {G}$) denotes the number of connected components in $ \cal {G}$.

Since every forest contains at least one tree, we have

| E$\displaystyle \le$ | V| - 1 (9)

for any cycle-free graph. If M is an m×n matrix, then the number of vertices in T(M) is m + n and the number of edges in T(M) is equal to $\ensuremath{\operatorname{wt}}(M)$ -- the total number of nonzero entries in M. Thus if M is cycle-free, then

wt(M)$\displaystyle \le$m + n - 1 (9)

in view of (3.2).

http://people.bu.edu/trachten