Cycle-free codes and graph-theoretic codes.

There is an interesting connection between cycle-free codes and cut-set codes of a graph. Let $\cal {G}$ = (V, E) be a multi-graph (a graph that may contain multiple edges with both endpoints the same) with n = | E| edges and m = | V| vertices. A cut-set in $\cal {G}$ is a set of edges which consists of all the edges having one endpoint in some set X $\subset$ V and the other endpoint in  V $\setminus$ X. Under the operation of symmetric difference, the cut-sets in $\cal {G}$ form a subspace of the binary vector space of all subsets of E. Hence replacing subsets of E by their characteristic vectors in IF₂ⁿ produces a binary linear code $\ensuremath{\mathbb{C}}({\cal G})$, called the cut-set code of $\cal {G}$. The dual code of  $\ensuremath{\mathbb{C}}({\cal G})$ is the cycle code of $\cal {G}$, defined as the linear span of the characteristic vectors of cycles in $\cal {G}$. Graph theoretic codes, namely cut-set codes and cycle codes of a graph, have been extensively studied -- see [10,29,28,51,52] for instance. The connection between cycle-free codes and cut-set codes of a graph can be summarized as follows.

Theorem 3..11   Let $\ensuremath{\mathbb{C}}$ be a cycle-free binary linear code of length n. Then there exists a graph $\cal {G}$ with n edges, such that $\ensuremath{\mathbb{C}}$ is a cut-set code of $\cal {G}$.

Proof.  Let H be an r×n cycle-free parity-check matrix for $\ensuremath{\mathbb{C}}$, and let T = T(H) be the corresponding cycle-free Tanner graph that represents $\ensuremath{\mathbb{C}}$. The following procedure converts T into a graph $\cal {G}$, such that $\ensuremath{\mathbb{C}}$ is the cut-set code of $\cal {G}$. We will describe this procedure assuming that T is a tree, in which case $\cal {G}$ is connected. In case T is a forest consisting of $\omega$ trees, the same procedure should be carried out independently for each tree in T, and $\cal {G}$ will have $\omega$ connected components.

Let $\cal {Y}$ = {y₁, y₂,..., y_r} be the set of check vertices in T, and let X_i $\subseteq$ $\cal {X}$ denote the neighborhood of y_i$\mbox{$\,\inn\,$}$$\cal {Y}$ for i = 1, 2,..., r. Further define X^*_i = X₁ $\cup$ X₂ $\cup$ ^... $\cup$ X_i. Since T is a tree, it is always possible to enumerate the check vertices in T in such a way that X_i intersects X^*_i-1 in one and only one symbol vertex for all i. Given such enumeration y₁, y₂,..., y_r, we construct $\cal {G}$ iteratively, check-vertex by check-vertex. First, we represent y₁ and its neighborhood X₁ by a cycle $\cal {G}$₁ consisting of | X₁| edges and | X₁| vertices. Now suppose that X₂ $\cap$ X₁ = {x₂}. Then we create $\cal {G}$₂ from $\cal {G}$₁ by appending | X₂| - 1 edges -- one for each symbol vertex in X₂ except x₂ -- and | X₂| - 2 vertices, in such a way that the edges corresponding to the symbol vertices in X₂ form a cycle in $\cal {G}$₂. And so forth: if  X_i $\cap$ X^*_i-1 = {x_i}, we create $\cal {G}$_i from $\cal {G}$_i-1 by appending | X_i| - 1 edges and | X_i| - 2 vertices, in such a way that the edges corresponding to the symbols in X_i form a new cycle. It is easy to see that $\cal {G}$ = $\cal {G}$_r will contain exactly n edges and n - (r-1) vertices. Furthermore, the code $\ensuremath{\mathbb{C}}^\perp$ generated by H is precisely the cycle code of $\cal {G}$. Since the cut-set code of $\cal {G}$ is the dual of its cycle code, our proof is complete.

width4pt depth2pt height6pt

For example, the cycle-free codes defined by the parity-check matrices in (3.16) and (3.19) are cut-set codes of the graphs depicted in Figure 3.7a and Figure 3.7b, respectively.

Figure 3.7: Two inequivalent cycle-free cut-set codes.

For cut-set codes, it is well-known [29,48] that 2n$\ge$md, where m is the number of vertices in the underlying graph $\cal {G}$. Indeed, this follows immediately from the fact that if the minimum distance of $\ensuremath{\mathbb{C}}({\cal G})$ is d, then every vertex of $\cal {G}$ must have degree at least d, otherwise the cut-set that isolates this vertex will have less than d edges. It is also well-known that $\dim \ensuremath{\mathbb{C}}({\cal G}) = m - \omega({\cal G})$, where $\omega$($\cal {G}$) is the number of connected components in $\cal {G}$. Thus we obtain the following cut-set bound on the minimum distance of cycle-free codes

$$\le {2n \over k + \omega({\cal G})} \le {2n \over k + 1}$$ (9)

If it is known that d is even, then the cut-set bound of (3.20) obviously implies Theorem 3.6. In general, however, Theorem 3.6 is stronger than the cut-set bound based on Theorem 3.11. Indeed, there exist cut-set codes that are not cycle-free. As a simple example, consider the (6, 3, 3) cut-set code of the graph depicted in Figure 3.8, and notice that the minimum distance of this code violates the upper bound of Theorem 3.6.

Figure 3.8: A cut-set code which is not cycle-free.

We have proved that every cycle-free binary linear code is a cut-set code. We now attempt to make this correspondence more precise by examining exactly which cut-set codes correspond to cycle-free binary linear codes. An answer to this question follows from a closer look at the construction in Theorem 3.11 and relies on star graphs, which are graphs where the removal of a vertex, which is connected to all the other vertices, results in a forest.

Theorem 3..12   There is a one-to-one correspondence between cycle-free binary linear codes and cut-set codes of graphs whose dual is a star.

Proof.  Consider a cycle-free Tanner graph T for a given cut-set code, the corresponding graph $\cal {G}$ from the construction in Theorem 3.11, and its dual graph $\cal {G}$^D. Absent the vertex corresponding to the outer region of $\cal {G}$, each path in $\cal {G}$^D corresponds to a path through the Tanner graph T: vertices in $\cal {G}$^D correspond to check nodes of T, and edges in $\cal {G}$^D correspond to symbol nodes of T. Since a path in T cannot contain a cycle, the same is true for $\cal {G}$^D absent the outer vertex. Thus, $\cal {G}$^D is a star corresponding to T.

The other direction of the correspondence is similarly straightforward. Given a cut-set code of a graph whose dual is a star, we may simply reverse the algorithm in Theorem 3.11 to arrive at a Tanner graph. This Tanner graph must be cycle free, or else $\cal {G}$^D has a cycle among vertices other than the outer vertex.

width4pt depth2pt height6pt