This project focuses on the mathematical aspects of modern digital communication systems --- in particular on the analysis and design of certain vector spaces over finite fields, called low-density parity-check (LDPC) codes, that have a set of "sparse'' vectors generating the dual space, and among these, on quasi-cyclic and convolutional LDPC codes. In conjunction with an iterative decoding algorithm based on passing probability estimates along the edges of a graph naturally associated to the code, these codes show great promise for current and future communication systems. The analysis consists of an analysis of the associated code graphs, fundamental cones (with implications in linear programming decoding and iterative decoding), pseudo-codeword sets (the culprits that prevent the convergence of iterative decoding) and pseudo-weights (a measure of performance under iterative decoding). The goals are: to develop a theory of finite-length LDPC codes and provide a comparison between different codes having related algebraic structures; to unify relevant notions like near-codewords, pseudo-codewords, girth, minimum distance, minimum pseudo-weight by studying the effect that each has on the others; to derive lower and upper bounds on the performance of LDPC block and convolutional codes based on these parameters and their influences; and to ultimately provide guidelines for designing finite-length LDPC codes that have predictably good performance under iterative decoding.
The inclusion of LDPC block codes in emerging standards such as digital video broadcasting, Ethernet and third-generation (3G) mobile-telephone networks, which will allow wireless access from 3G phones to be over ten times faster than from an old-fashioned dial-up, has recently spurred interest in LDPC convolutional codes. Initial research on LDPC convolutional codes leads the PI to the belief that these codes have several potential practical advantages compared to LDPC block codes. The goal of this project is to analyze these codes and construct new ones with predictably good performance. This research will naturally integrate abstract theory and real-world applications, providing exciting opportunities for cross-cutting research. The PI's continuing collaboration with leading engineering experts from academia and industry enables a transition from the theoretical research findings in this project to practical communication systems. It is anticipated that the project will have an impact on the future information infrastructure and contribute to universal accessibility. This impact will extend to the areas of data compression and communication protocols and security, since their underlying theories are closely related to coding theory.