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.