Organization

This dissertation is organized as follows. In Chapter 2 we study trellis decoding using the Viterbi algorithm. More precisely, we are interested in designing codes that can be efficiently decoded using the Viterbi algorithm on a trellis. We study a generalization of the greedily-constructed ``lexicographic codes''. This generalization enables the design of codes which meet specific decoding constraints, such as bounds on the time and space complexity alloted for decoding. We also determine a theoretical relationship between cosets of these codes, which allows us to explicitly compute their generator matrices and to improve upon known bounds of their parameters. This research extends and improves earlier work in [56]. In addition, a version of this chapter has been published as a joint work with Alexander Vardy in the Proceedings of the Conference of Information Sciences and Systems [60] and is being prepared for submission to the IEEE Transactions on Information Theory [58].

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.