Which codes have cycle-free Tanner graphs?

If a linear block code C of length n has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n(2)). However, we show that cycle-free Tanner graphs cannot support good codes. Specifically, let C be an (n, fi, d) linear code of rate R = k/n that can be represented by a Tanner graph without cycles. We prove that if R greater than or equal to 0.5 then d less than or equal to 2, while if R < 0.5 then C is obtained from a code of rate greater than or equal to 0.5 and distance less than or equal to 2 by simply repeating certain symbols. In the latter case, we prove that d less than or equal to [n/k+1] + [n+1/k+1] < 2/R Furthermore, we show by means of an explicit construction that this bound is tight for all values of n and k. We also prove that binary codes which have cycle-free Tanner graphs belong to the class of graph-theoretic codes, known as cut-set codes of a graph. Finally, we discuss the asymptotics for Tanner graphs with cycles, and present a number of open problems for future research.