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 IF2n 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}$ = {y1, y2,..., yr} be the set of check vertices in T, and let Xi $ \subseteq$ $ \cal {X}$ denote the neighborhood of yi$ \mbox{$\,\inn\,$}$$ \cal {Y}$ for i = 1, 2,..., r. Further define X*i = X1 $ \cup$ X2 $ \cup$ ... $ \cup$ Xi. Since T is a tree, it is always possible to enumerate the check vertices in T in such a way that Xi intersects X*i-1 in one and only one symbol vertex for all i. Given such enumeration y1, y2,..., yr, we construct $ \cal {G}$ iteratively, check-vertex by check-vertex. First, we represent y1 and its neighborhood X1 by a cycle $ \cal {G}$1 consisting of | X1| edges and | X1| vertices. Now suppose that X2 $ \cap$ X1 = {x2}. Then we create $ \cal {G}$2 from $ \cal {G}$1 by appending | X2| - 1 edges -- one for each symbol vertex in X2 except x2 -- and | X2| - 2 vertices, in such a way that the edges corresponding to the symbol vertices in X2 form a cycle in $ \cal {G}$2. And so forth: if  Xi $ \cap$ X*i-1 = {xi}, we create $ \cal {G}$i from $ \cal {G}$i-1 by appending | Xi| - 1 edges and | Xi| - 2 vertices, in such a way that the edges corresponding to the symbols in Xi 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

d $\displaystyle \le$ $\displaystyle {2n \over k + \omega({\cal G})}$ $\displaystyle \le$ $\displaystyle {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