It is obvious from Theorem 3.6 that Tanner graphs without cycles cannot
support asymptotically good codes. Starting with Theorem 3.6, it is not
difficult to show that the same is true for Tanner graphs with cycles,
unless the number of cycles increases exponentially with the length
of the code as
n. To see this, suppose the the cycle rank
of a Tanner graph T = (V, E) representing an (n, k, d ) code
c = | E| - | V| + (T). This means that T contains 2c
cycles and unions of disjoint cycles (cf. [48, p.137]).
Now let xi be a symbol vertex that lies on a cycle in T.
Then removing xi and all the edges incident on xi from T
produces a graph whose cycle rank is strictly less than c.
This procedure is equivalent to shortening
at the i-th
position to obtain an
(n', k', d') code
with n' = n - 1,
k'k - 1, and d'd.
Since the cycle rank strictly decreases each time we cut a cycle
in T in this way, after repeating this procedure tc times
we obtain a cycle-free code
(n*, k*, d*)
code with n* = n - t,
k*k - t, and d*d. Thus
Theorem 3.6 implies
= c/n, and notice that
= 0, then (3.21)
asymptotically reduces to
d 2/R, as in (3.1).
Thus to support an asymptotically good sequence of codes,
c must grow linearly with n, which means
that the number of cycles 2c grows exponentially
It would be useful to find out how
= c/n, which has to do with
the number of cycles, trades off versus the traditional
= d /n and R = k/n as
It would be also interesting to investigate, at least
asymptotically, codes that have Tanner graphs of prescribed