##

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
(,) can be converted into a simple
Tanner graph for the same code through a vertex-splitting
procedure. Indeed, let
*y* be a check vertex in , let
{*x*_{i1}, *x*_{i2},..., *x*_{i}}
be the neighborhood of *y*, and let be the corresponding
constraint code of length . If
dim = ,
we split *y* into
- vertices
*y'*_{1}, *y'*_{2},..., *y'*_{-}
and create edges between
*x*_{i1}, *x*_{i2},..., *x*_{i}
and
*y'*_{1}, *y'*_{2},..., *y'*_{-}
according to a parity-check matrix *H* for .
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

can be represented
by a general Tanner graph

(,)
such that

is cycle-free and all
the constraints in

are cycle-free,
then

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
which contains a single check vertex
= {*y*}
with the corresponding constraint code being
itself.
The existence of this cycle-free representation for
obviously does not provide any information whatsoever about
.

Notwithstanding the trivial ``counter-example''
discussed above, it is plausible that if the underlying Tanner graph is cycle-free,
the distance of
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.

http://people.bu.edu/trachten