Tanner graphs

Tanner graphs and their generalization to factor graphs have only recently gained renewed interest, and seem to show significant promise for future research. Our research in Chapter 3 uncovered some relations and properties of Tanner graphs.

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 $\gamma$ = c/n, which has to do with the relative number of cycles in a code, trades off versus the traditional asymptotic parameters $\delta$ = d /n and R = k/n as n$\to$$\infty$.