Connections between the edge zeta function of a graph, counting in graph covers, and message-passing iterative decoding

Meeting Time: Dec. 8, 2009, 2:00-2:50pm

Abstract: Graph-based codes and message-passing iterative decoders have become increasingly popular in the last decade. It is fair to say that these codes and decoding algorithms (and ideas related to them) have thoroughly changed much of modern communications. Before this backdrop, a good understanding of these types of communication techniques is obviously highly desirable, especially the understanding of iterative decoding of finite-length codes.

We will focus on a particular message-passing iterative decoder, the so-called sum-product algorithm (SPA) decoder. As the name SPA suggests, this algorithm is counting certain objects, and indeed, when the underlying factor graph has no cycles then it is clear what the SPA is counting. However, when the underlying factor graph has cycles then the situation is much fuzzier.

In this talk we will demonstrate how the technique of graph covers can be used to give a meaning to what the SPA is counting. In particular, we will show that this technique allows one to derive the following result about fixed points of the SPA: a fixed point of the SPA corresponds to a pseudo-codeword that, after taking a biasing channel-output-dependent term properly into account, has locally the most (or the least) pre-images in all M-fold graph covers of the graph defining the code, when M goes to infinity.

As it turns out, the growth rates of the pre-images of pseudo-codewords are, in the case of a cycle code, connected to the edge zeta function of the graph defining the cycle code. This observation extends an earlier result by Koetter, Li, Vontobel, and Walker.

(The talk will mostly be based on elementary counting techniques, and although most results are motivated by applications in a communications setup, a deep understanding of these applications is not required.)

Bio: Pascal O. Vontobel received the Diploma degree in electrical engineering in 1997, the Post-Diploma degree in information techniques in 2002, and the Ph.D. degree in electrical engineering in 2003, all from ETH Zurich, Switzerland. From 1997 to 2002 he was a research and teaching assistant at the Signal and Information Processing Laboratory at ETH Zurich. After being a postdoctoral research associate at the University of Illinois at Urbana-Champaign, at the University of Wisconsin-Madison (visiting assistant professor), and at the Massachusetts Institute of Technology, he joined the Information Theory Research Group at Hewlett-Packard Laboratories in Palo Alto, CA, in the summer of 2006 as a research scientist. His research interests lie in information theory, communications, and signal processing. Dr. Vontobel is an Associate Editor for the IEEE Transactions on Information Theory, has been on the technical program committees of several international conferences, and has co-organized a BIRS workshop in Banff on "Applications of Matroid Theory and Combinatorial Optimization to Information and Coding Theory" (August 2009). Moreover, he has been three times a plenary speaker at international information and coding theory conferences and has been awarded the ETH medal for his Ph.D. dissertation.