## Cycle-free codes and graph-theoretic codes.

There is an interesting connection between cycle-free codes and cut-set codes of a graph. Let = (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 is a set of edges which consists of all the edges having one endpoint in some set X V and the other endpoint in  V X. Under the operation of symmetric difference, the cut-sets in 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 , called the cut-set code of . The dual code of  is the cycle code of , defined as the linear span of the characteristic vectors of cycles in . 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 be a cycle-free binary linear code of length n. Then there exists a graph  with n edges, such that is a cut-set code of .

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

Let = {y1, y2,..., yr} be the set of check vertices in T, and let Xi denote the neighborhood of yi for i = 1, 2,..., r. Further define X*i = X1 X2 ... 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 iteratively, check-vertex by check-vertex. First, we represent y1 and its neighborhood X1 by a cycle 1 consisting of | X1| edges and | X1| vertices. Now suppose that X2 X1 = {x2}. Then we create 2 from 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 2. And so forth: if  Xi X*i-1 = {xi}, we create i from 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 = r will contain exactly n edges and n - (r-1) vertices. Furthermore, the code generated by H is precisely the cycle code of . Since the cut-set code of 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.

For cut-set codes, it is well-known [29,48] that 2nmd, where m is the number of vertices in the underlying graph . Indeed, this follows immediately from the fact that if the minimum distance of is d, then every vertex of 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 , where () is the number of connected components in . Thus we obtain the following cut-set bound on the minimum distance of cycle-free codes

 d (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.

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 from the construction in Theorem 3.11, and its dual graph D. Absent the vertex corresponding to the outer region of , each path in D corresponds to a path through the Tanner graph T: vertices in D correspond to check nodes of T, and edges in D correspond to symbol nodes of T. Since a path in T cannot contain a cycle, the same is true for D absent the outer vertex. Thus, 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 D has a cycle among vertices other than the outer vertex.

width4pt depth2pt height6pt

http://people.bu.edu/trachten