Princeton University

School of Engineering & Applied Science

Codes on Graphs

Dr. G. David Forney, Jr.
Engineering Quadrangle B205
Thursday, November 7, 2013 - 4:30pm to 5:30pm


Graphical representations of error-correcting codes are useful both for analysis and for devising efficient decoding algorithms. The roots of the subject go back forty years, to trellis representations of convolutional codes. Capacity-approaching codes (e.g., LDPC codes, turbo codes) make heavy use of graphical representations.

We will survey recent results on the foundations of the field of codes on graphs. We particularly focus on the analysis of fragments of realizations, which can range from simple constraints to complete realizations. With linear or finite abelian group codes, duality plays a central role. We develop dual concepts such as trimness, properness, observability and controllability. We show that there are at least two or three possible definitions of observability/controllability for fragments, one of which generalizes classic notions for linear state-space systems, and one of which generalizes that for complete realizations. We develop simple observability/controllability tests.

Cycle-free fragments are well understood, and lead to optimal decoding algorithms. Using cycle-free leaf fragments, we develop a simple proof of the fundamental "minimal=trim+proper" theorem for cycle-free realizations. We give a useful decomposition of a general realization into its cyclic, leafless "2-core," plus a number of cycle-free leaf fragments. However, it is known that low-complexity graphical representations of capacity-approaching codes must have cycles. We discuss some recent results relating to observability and controllability of cyclic realizations. However, many open questions remain.


G. David Forney, Jr. received the B.S.E. degree in electrical engineering from Princeton University, Princeton, NJ, in 1961, and the M.S. and Sc.D. degrees in electrical engineering from the Massachusetts Institute of Technology, Cambridge, MA, in 1963 and 1965, respectively.

From 1965-99 he was with the Codex Corporation, which was acquired by Motorola, Inc. in 1977, and its successor, the Motorola Information Systems Group, Mansfield, MA. Since 1996, he has been an Adjunct Professor at M.I.T.

Dr. Forney was Editor of the IEEE Transactions on Information Theory from 1970 to 1973. He was President of the IEEE Information Theory Society in 1992 and 2008. He received the 1992 IEEE Edison Medal and the 1995 IEEE Information Theory Society Claude E. Shannon Award. He was elected a Fellow of the IEEE in 1973, a member of the National Academy of Engineering (U.S.A.) in 1983, a Fellow of the American Academy of Arts and Sciences in 1998, and a member of the National Academy of Sciences (U.S.A.) in 2003.