Chapter 3 focuses on Tanner graphs in an attempt to get around the exponential growth in decoding complexity which is inherent in trellis decoding. It was mentioned in the background section that decoding can be done very quickly for codes with cycle-free Tanner graphs. However, both intuition and experimentation (cf.[40]) suggest that powerful codes cannot be represented by cycle-free Tanner graphs. The notion that cycle-free Tanner graphs can support only weak codes is by now widely accepted. In Chapter 3 we make this ``folk knowledge'' precise.

Specifically, we provide a rigorous answer to the question: ``Which codes can have cycle-free Tanner graphs?'' We consider extensions to this question and show that, as with trellis-decoding, asymptotically good codes will require asymptotically increasing numbers of cycles. The majority of this chapter was presented as a joint work with Tuvi Etzion and Alexander Vardy at the 1998 International Symposium on Information Theory [19] and has appeared in the IEEE Transactions on Information Theory [20] and as a technical report [18].

In Chapter 4 we summarize the results of this dissertation and examine possible future directions for this research. We consider several problems which are still open and provide natural extensions for this work. In addition, we briefly describe unrelated research into full-rank tilings [59] and database reconciliation [44,57], which was developed concurrently with this work. Finally, the appendices include results of implementing some algorithms from Chapter 2 in addition to some more technical aspects of proofs from Chapter 3.

http://people.bu.edu/trachten