Stanford University
Thursday, March 22, 2007

Lecture Home

 		Kailath Lecture 2007 Abstract
2007 Program

Codes and Graphical Models: A Personal Survey

David Forney

Adjunct Professor, MIT

In the past decade, the promise held forth by Shannon in 1948 has at last been practically realized.  Turbo codes and low-density parity-check (LDPC) codes now approach the Shannon limit within tenths of a dB, and are being implemented in almost all new digital communications systems.

A unified conceptual foundation for these capacity-approaching codes and their decoding algorithms has been developed in a new field called "codes (or systems) on graphs."  This field may be viewed as a generalization of classical discrete-time linear system theory, in which the conventional sequential discrete time axis is replaced by a general graph.

This field evolved out of various antecedents, including:

- the study of convolutional codes as linear finite-state systems over finite fields;

- trellis and tail-biting trellis realizations of block codes;

- Tanner graph representations of LDPC codes;

- Wiberg's unification of all these topics, and his cut-set bound.

We will offer a guided high-level tour through these developments, from a personal perspective. 

 We will also mention some currently open problems.  For example, the classical theory of minimal realizations of linear codes and systems extends rather completely to linear (or group) codes/systems defined on cycle-free graphs.  However, certain fundamental obstacles stand in the way of constructing minimal realizations of linear codes/systems defined on graphs with cycles, such as tail-biting realizations.  Nevertheless, some progress has been made.