CAREER: Codes on Graphs, Factor Graphs, and Iterative Algorithms

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

CAREER: Codes on Graphs, Factor Graphs, and Iterative Algorithms The primary focus of this research is the investigation of creative new methods for reliable transmission of information in the context of modern error-control techniques. Error-correcting codes are an essential part of modern communication and storage systems and much of today's technology would not be possible without them. This study is focused on graph-based, iterative decoding algorithms, which, without doubt, are one of the most significant coding-theoretic developments of the last decade. The goal of the investigator's research is to develop a broad, analytical, and constructive approach to research and education, unifying graphical models, coding theory, and iterative algorithms. The interplay between codes on graphs and other areas, like iterative graph-based algorithms, system theory, and network information theory, is in the focus of this investigation with the goal of discovering and utilizing fundamental connections between these fields. The central notion of this research is the framework of "codes on graphs" and "factor graphs". Three main thrusts of research are present. The first main thrust is directed towards the analysis and theoretical study of iterative decoding algorithms in graphs with and without cycles. The main tools for this research originate in recent successes in the analysis of codes on graphs as the codelength approaches infinity, and in the notion of pseudo-codewords for short codes on relatively simple graphs. Both approaches are made viable by drawing heavily on the properties of the underlying graph in the code construction. The second main thrust involves problems arising from generalizations of minimal realizations of codes on graphs. This work has important ramifications to behavioral system theory, network information theory and iterative decoding. The goal is to derive algorithms that achieve a "minimal" realization of a code on a graph. A solution to this question is closely related to important problems in network information theory and the achievability of desired information flows in a given network topology. The third objective of the investigator's study is aimed at jointly optimized receiver functions in a graph-based iterative setup. Factor graphs provide a natural and generic framework for the study of iterative, belief propagation algorithms on graphical models. One of the most exciting opportunities offered by the factor graph framework is the possibility of incorporating a variety of different estimation tasks into a joint optimization. The research focuses on opportunities to realize, in jointly optimized subsystems, the gains that are essential for future communication systems.