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

在过去的十年中，使用和积算法对来自低密度矩阵(LDPC码)的码进行译码被证明比经典的编码方案产生了显著的改进。遗憾的是，译码算法没有被很好地理解以指示应该如何构造最优的LDPC码。代码性能只能通过计算密集型模拟来验证。我们的工作将使用理论分析和结构化的、有针对性的计算机模拟相结合的方式，其目标是拟议的研究包括三个相辅相成的创新，这将导致更好地理解和积算法和代码设计。首先，我们为算法建立了一个代数模型，在这个模型中，我们可以研究固定轨迹和几次迭代后的动力学。我们利用这个模型建立了关于小码算法收敛的精确结果，并成功地将启发式算法从小的例子应用到理解实际规模较大的码上。其次，我们对一种广泛使用的构造LDPC码的方法进行了改进，其中奇偶校验矩阵是具有循环子矩阵的分块矩阵。我们的方法适用于非常一般的块矩阵结构，并提供了对检查矩阵的二部图中是否存在小圈的控制。我们将对用这种方法构造的各种代码进行系统的比较，并与其他方法进行比较。第三，我们开发了一个基于网格的软件基础设施，用于研究不同代码在高信噪比下的译码性能。使用这个基础设施，我们将能够在高信噪比下收集有关解码失败的统计数据。我们可以检查导致译码失败的输入向量的性质，并测试译码失败与代码的图形模型之间的关系。广泛影响：我们的研究的成功完成将对纠错技术产生重大影响，纠错技术在数据通信和存储中发挥着越来越重要的作用。蜂窝和无线技术领域的商业应用将立即受益。我们的工作还将影响传感器网络等低功耗和不可靠通信系统领域的新兴研究学科。该研究项目将帮助圣地亚哥州立大学数学和统计系实现其目标，即发展应用数学研究的重点领域，并与不同学科的科学家和工程师合作。通过该项目的合作，我们相信它还将鼓励学生进行将严谨的数学与先进的计算机系统技术相结合的博士研究。智力的优点：这项提议的智力优点体现在它的三个特点上。首先，它开发和应用了一种新的方法，该方法侧重于信任传播的基础和高质量LDPC码的数学定义。其次，它使用新的全国分布的大规模计算能力来指导和帮助分析，而不是简单地提供代码质量的经验证据。最后，它将数学和高性能计算机系统的专业知识融合在一起，既能产生显著的结果，又能激励学生追求类似的跨学科研究方法。

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 statisticaldata 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.