BP 4 MAP: Better Performance 4 Many Arduous Problems

Ruediger Urbanke
Ecole Polytechnique Federale de Lausanne (EPFL), Switzerland

Monday, November 15, 2010 at 12:30PM
54-134 Engineering IV Building
Refreshments Served

Abstract: Error correcting codes based on graphs and their associated low-complexity decoding algorithms can be found in virtually any new communication standard or product. These days they can even be found in hard disk drives, a product with extremely stringent requirements.

A key focus of modern coding theory is to study the interplay between the graphical structure of a code and its decoding performance. I will focus on the particular structure which emerges when codes are "coupled". This structure was introduced by Zigangirov and Felstrom in the form of convolutional LDPC codes in 1999. It has since been studied extensively and it is well known that codes of this form have excellent performance. Why do these codes perform so well? Simplifying slightly, the structure magically ensures that the performance under low-complexity belief propagation (BP) decoding is essentially equal to the performance of the underlying (uncoupled) code under optimal maximum-a-posteriori (MAP) decoding. This is quite remarkable and gives rise to a new paradigm in code design.

Graphical models and low complexity algorithms play an important role not only in coding. I will survey some extensions within communications and computer science where the same principle applies and I will conclude by posing open questions in this area.

[This is joint work with Shrinivas Kudekar and Tom Richardson.]

Biography: Rdiger L. Urbanke was born on 31 December 1966 in Linz, Austria. He obtained a Dipl. Ing. degree from the Vienna University of Technology, Austria in 1990 and the M.Sc. and PhD degrees in Electrical Engineering from Washington University in St. Louis, MO, in 1992 and 1995, respectively.

From 1995 to 1999, he held a position at the Mathematics of Communications Department at Bell Labs. Since November 1999, he has been a faculty member at the School of Computer & Communication Sciences (I&C) of EPFL, Lausanne, Switzerland, where he is the head of the Communications Theory Lab and the Director of the Doctoral Program of I&C.

He is best known for his analysis and design of iterative coding schemes, which allow reliable transmission very close to theoretical limits at low complexities. Such schemes are part of most modern communications standards, including wireless transmission, optical communication and hard disk storage. More broadly, his research focuses on the analysis of graphical models and the application of methods from statistical physics to problems in communications.

From 2000-2004 he was an Associate Editor of the IEEE Transactions on Information Theory and he is currently on the board of the series "Foundations and Trends in Communications and Information Theory."

Dr. Urbanke is a recipient of a Fulbright Scholarship. He is a co-recipient of the IEEE Information Theory Society 2002 Best Paper Award and co-author of the book "Modern Coding Theory" published by Cambridge University Press. He is the co-recipient of the 2011 Koji Kobayashi Award "for developing the theory and practice of transmitting data reliably at rates approaching channel capacity."