Codes on Graphs: Past, Present and Future
Speaker: Professor G. David Forney, Jr. (MIT)
Date: Wednesday 12th September 2012
Location: CASL Seminar Room (Belfield Office Park)
The subject of codes on graphs began with convolutional codes and trellis diagrams, and continued with tail-biting trellis realizations and low-density parity-check (LDPC) codes on Tanner graphs. In the past decade, the beginnings of a general theory of graphical realizations of linear and group codes has been developed. Cycle-free graph realizations are special, and are well understood. Trellis realizations are also quite special, and are fairly well understood, even in the cyclic (tail-biting) case. We have some powerful general duality theorems, which have nice theoretical and practical applications. Recently, some progress has been made in establishing conditions under which general graphical realizations may be ''locally reduced,” using extensions of linear-system-theoretic concepts such as observability and controllability. However, the theory of general graphical realizations remains wide open.