Collaborative Research: Improving Low-Density Parity-Check Codes Through Algebraic Analysis of The Sum-Product Algorithm

San Diego State University Foundation, San Diego CA

Investigators

Abstract

In the last decade, decoding of codes from low-density matrices (LDPC codes) using the sum-product algorithm was shown to yield dramatic improvement over classical coding schemes. Unfortunately, the decoding algorithm is not understood well enough to indicate how optimal LDPC codes should be constructed. Code performance can only be verified by computationally intensive simulation. The goal of our work, which will use a combination of theoretical analysis and structured, carefully targeted computer simulation, is The proposed research comprises three complementary innovations, which will lead to a better understanding of the sum-product algorithm and of code design. First, we have developed an algebraic model for the algorithm in which we can study the fixed locus, and the dynamics after several iterations. We have used this model to establish exact results about convergence of the algorithm for small codes and successfully applied heuristics from small examples to understand codes of larger practical sizes. Second, we have improved on a widely used method for constructing LDPC codes in which the parity-check matrix is a block matrix with circulant submatrices. Our method works for very general block matrix structures and provides control over the existence of small cycles in the bipartite graph of the check-matrix. We will pursue a systematic comparison of a variety of codes constructed with this method, as well as comparisons with other methods. Third, we have developed a grid-based software infrastructure for studying the decoding properties of different codes at high signal-to-noise ratios. Using this infrastructure, we will be able to gather statistical data about decoding failure at high signal-to-noise ratio. We can examine properties of input vectors that lead to decoding failure and test the relationship between decoding failure and the graphical model of the code. Broader Impact: Successful completion of our research will have a significant impact on error-correction technology, which is playing an increasingly important role in data communication and storage. Commercial applications in the area of cellular and wireless technologies will benefit immediately. Our work will also influence emerging research disciplines in the area of low-power and unreliable communications systems such as sensor networks. The research project will aid the Department of Mathematics and Statistics at San Diego State University in its goal of developing focused areas of applied mathematics research and collaborations with scientists and engineers in a variety of disciplines. Through the project's collaboration, we believe it will also encourage students to pursue doctoral research that combines rigorous mathematics with advanced computer systems techniques. Intellectual Merit: The intellectual merit in this proposal is embodied in three of its features. First, it develops and applies a new approach that focuses on the foundations of belief propagation and the mathematical definition of high-quality LDPC codes. Second, it uses novel nationally distributed large-scale computing capabilities to guide and aid analysis rather than simply to offer empirical evidence of code quality. Finally, it blends expertise in mathematics and high-performance computer systems in a way that will both generate significant results and will motivate students to pursue similar interdisciplinary approaches to research.