# 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