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 $\cal {X}$ = {x₁, x₂,..., x_n} of symbol vertices and the set $\cal {Y}$ = {y₁, y₂,..., 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 $\mbox{$\,\inn\,$}$ $\cal {Y}$ corresponds to the i-th row of H, and the neighborhood of the vertex x_j $\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 IF₂, 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 IF₂, 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 IF_q 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 (x₁, y₁),(y₁, x₃),(x₃, y₂),(y₂, x₁) 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}$ .