Systems Seminar

Factor graphs, the Summary-Product Algorithm, and Analysis of Finite-Length Codes

Dr. Pascal O. Vontobel
Coordinated Science Laboratory
University of Illinois at Urbana-Champaign

Abstract

One of the most important developments in coding theory has been the (re)discovery of iteratively decodable codes. It is fair to say that iterative decoding has thoroughly changed much of modern communications.

An elegant way to describe the working of low-density parity-check and turbo codes is through the use of factor graphs and the summary-product algorithm. The first part of my talk will therefore be an introduction to these concepts. But it will be apparent that the summary-product algorithm, which operates by message passing in a factor graph, subsumes a great variety of algorithms not only in coding theory but also in signal processing and artificial intelligence.

The second part of my talk will be devoted to the analysis of iterative decoding algorithms for finite-length codes. Recently, we have been able to identify a key insight in the "old" subject of iterative decoding, namely pseudo-codewords. In fact, iterative decoding can be tightly characterized by the pseudo-codewords that lie within a certain polytope, the fundamental polytope, as we called it. Interestingly, most of the available concepts for understanding iterative decoding of finite-length codes can now be explained with the help of pseudo-codewords and the fundamental polytope. We will also point out connections to linear programming and statistical physics.

Codes -- by definition -- are discrete objects, a fact which usually makes it relatively hard to state properties about a specific code. But the fundamental polytope is a continuous and convex object: not only is it easier to derive properties of a specific code (like the minimum pseudo-distance), but these properties are also more relevant to the iterative decoding behavior than classical notions like minimum Hamming distance. These observations have interesting implications for code design.

(Parts of this talk are based on joint work with Ralf Koetter, UIUC.)

Biography

Pascal O. Vontobel got a diploma in electrical engineering in 1997, a post-diploma in information techniques in 2002, and a PhD degree in electrical engineering in 2003 (the advisor was Prof. H.-A. Loeliger), all from ETH Zurich, Switzerland; for his PhD thesis he was awarded the ETH medal. From 1997 to 2002 he was a research and teaching assistant at the Signal and Information Processing Laboratory at ETH Zurich. Since October 2002 he has been a postdoctoral research associate at the Coordinated Science Laboratory at the University of Illinois at Urbana-Champaign, IL, USA, with Prof. R. Koetter. Time and Place: Wed., Apr. 21, at 3:30 pm in 4610 EH

SYSTEMS SEMINAR WEB PAGE: http://www.cae.wisc.edu/~gubner/seminar/

File "vontobel.shtml" last modified Tue 15 Oct 2019, 01:45 PM, CDT
Web Page Contact: John (dot) Gubner (at) wisc (dot) edu