The main result of the chapter shows that a code that can be represented by cycle-free Tanner graphs must necessarily have asymptotically poor error correction. This is particularly significant in light of the fact that the well-established decoding algorithms on Tanner graphs are only guaranteed to converge to the maximum-likelihood decoding for cycle-free graphs. In fact, the structure of cycle-free codes is so weak that exponentially many cycles are needed for asymptotically good error-correction. On the path towards these results, we determined precisely a family of cycle-free codes that exhibit the maximum possible error-correction, and we also establish a relationship between cycle-free codes and graph theoretic cut-set codes.

These various results lead to several natural extensions. For example, the connection between cycle-free codes and cut-set codes expressed in Section 3.5 suggests the possibility of a simpler graph-theoretical analysis of our main result. The details of our main result make its proof quite complicated, and it is possible that in a graph-theoretic setting it would follow more directly.

Another extension of our research involves a more
careful analysis of the cycle structure of the Tanner graph of a code.
Though it is impossible to entirely eliminate cycles in an asymptotically
good code, it is possible to constrain the relative number
of cycles in a graph so as to
allow for many cycle-free subgraphs in which the min-sum decoding
algorithm can operate efficiently. Specifically, it would be interesting
to study how
the parameter
= *c*/*n*, which has to do with
the relative number of cycles in a code, trades off versus the traditional
asymptotic parameters
= *d* /*n* and *R* = *k*/*n* as
*n*.