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.