  This paper analyzes the distribution of cycle lengths in turbo decoding and
low-density parity check (LDPC) graphs. The properties of such cycles are of
significant interest in the context of iterative decoding algorithms which are
based on belief propagation or message passing. We estimate the probability
that there exist no simple cycles of length less than or equal to k at a
randomly chosen node in a turbo decoding graph using a combination of counting
arguments and independence assumptions. For large block lengths n, this
probability is approximately e^{-{2^{k-1}-4}/n}, k>=4. Simulation results
validate the accuracy of the various approximations. For example, for turbo
codes with a block length of 64000, a randomly chosen node has a less than 1%
chance of being on a cycle of length less than or equal to 10, but has a
greater than 99.9% chance of being on a cycle of length less than or equal to
20. The effect of the "S-random" permutation is also analyzed and it is shown
that while it eliminates short cycles of length k<8, it does not significantly
affect the overall distribution of cycle lengths. Similar analyses and
simulations are also presented for graphs for LDPC codes. The paper concludes
by commenting briefly on how these results may provide insight into the
practical success of iterative decoding methods.
