Event
Advanced Networks Colloquium: David Forney, "Codes on Graphs"
Friday, March 28, 2014
11:00 a.m.
1146 AV Williams Bldg
Kimberly Edwards
kedwards@umd.edu
The Advanced Networks Colloquium
Codes on Graphs
David Forney
Massachusetts Institute of Technology
[Roundtable discussion at 2 pm, 1146 AVW]
Host
John Baras
Abstract
Graphical realizations 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 (state-space) realizations of convolutional codes. Capacity-approaching codes (e.g., LDPC codes, turbo codes) are based on graphical representations. For finite cycle-free linear or group realizations, we show that trimness and properness suffice for minimality. 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, and that cyclic realizations may be unobservable or uncontrollable. 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 discuss some recent results relating to observability and controllability of cyclic realizations. However, many open questions remain.
Biography
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.
