General Tanner graphs without cycles

We now return to the case of general Tanner graphs, as defined in the introduction to the chapter, and observe that every general Tanner graph ($\cal {G}$,$\cal {L}$) can be converted into a simple Tanner graph for the same code through a vertex-splitting procedure. Indeed, let y$\mbox{$\,\inn\,$}$$\cal {Y}$ be a check vertex in $\cal {G}$, let {x_i1, x_i2,..., x_i$\delta$} $\subseteq$ $\cal {X}$ be the neighborhood of y, and let $\cal {C}$ be the corresponding constraint code of length $\delta$. If dim$\cal {C}$ = $\kappa$, we split y into $\delta$ - $\kappa$ vertices y'₁, y'₂,..., y'_{$\delta$-$\kappa$} and create edges between x_i1, x_i2,..., x_i$\delta$ and y'₁, y'₂,..., y'_{$\delta$-$\kappa$} according to a parity-check matrix H for $\cal {C}$. An obvious but important observation is this: if H is cycle-free, then this procedure does not create new cycles. Thus we have proved the following statement.

Proposition 3..13   If a linear code $\ensuremath{\mathbb{C}}$ can be represented by a general Tanner graph ($\cal {G}$,$\cal {L}$) such that $\cal {G}$ is cycle-free and all the constraints in $\cal {L}$ are cycle-free, then $\ensuremath{\mathbb{C}}$ can be represented by a simple Tanner graph without cycles.

An immediate consequence of Proposition 3.13 is that all the results derived so far for simple Tanner graphs, including the bound of Theorem 3.6, straightforwardly extend to general Tanner graphs with cycle-free constraints.

In the general case, where check constraints are not necessarily cycle-free, it appears to be very difficult to say anything about the structure/properties of the code being represented. As an example, consider a general Tanner graph for $\ensuremath{\mathbb{C}}$ which contains a single check vertex $\cal {Y}$ = {y} with the corresponding constraint code being $\ensuremath{\mathbb{C}}$ itself. The existence of this cycle-free representation for $\ensuremath{\mathbb{C}}$ obviously does not provide any information whatsoever about  $\ensuremath{\mathbb{C}}$.

Notwithstanding the trivial ``counter-example'' discussed above, it is plausible that if the underlying Tanner graph is cycle-free, the distance of $\ensuremath{\mathbb{C}}$ should be limited by the distances of the constraint codes in some manner. Furthermore, if simple decoding is sought, simple constraint codes must be used. It thus appears that the range of code parameters that are possible with cycle-free Tanner graphs will depend on the decoding complexity tolerated. We leave further investigation of this relation as an open problem.