Code Representation and Performance of Graph-Based Decoding

University Of California-San Diego, La Jolla CA

Investigators

Abstract

CCF-0829865 Code Representation and Performance of Graph-Based Decoding PI: Paul H. Siegel, UC San Diego Abstract: The discovery of channel codes that approach information-theoretic performance limits when paired with iterative graph-based decoding algorithms represents a major advance in coding theory and practice. Prime examples include turbo codes, low-density parity-check (LDPC) codes, and repeat-accumulate (RA) codes. These coding techniques and their variants have had a profound impact on data transmission applications, including deep space communications, digital video broadcasting, and mobile wireless telephony. They are also poised for use in other settings, such as high density digital data storage. What is common to these coding and decoding schemes is that their performance and implementation complexity depend not only on the code itself, but also on the choice of graphical representation of the code. This research studies the characteristics of code representations that influence the performance of iterative decoding algorithms, as well as methods for constructing the best representations. The research has two major thrusts. The first is the examination of combinatorial and graphical properties of linear code representations that serve as figures of merit for iterative decoder performance on several types of channels having theoretical and practical significance. The understanding of these properties guides improved code design as well as the development of new graph-based decoding strategies. The second thrust is the analysis and enhancement of decoders based upon linear programming. The research studies the adaptive introduction of constraints to reduce decoder complexity and to improve performance. It also considers new linear programming algorithms that exploit sparse code representations. A dynamic interplay between these two research thrusts is achieved by studying the relationship between iterative and linear programming decoders, as well as their application to equalization and detection for channels with memory.