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

合作研究：通过和积算法的代数分析改进低密度奇偶校验码

• 批准号: 0635391
• 负责人: Richard Wolski
• 金额: --
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-02-15 至 2011-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0635391&HistoricalAwards=false
• 关键词: Collaborative; Research; Improving; Low; Density

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.

在过去的十年中，使用Sum-Prododuct算法对低密度矩阵（LDPC代码）的代码进行解码已显示出对经典编码方案的显着改进。不幸的是，解码算法的理解不足以表明如何构建最佳的LDPC代码。代码性能只能通过计算密集型模拟来验证。我们的工作的目的将结合理论分析和结构化的，精心定向的计算机模拟，这是拟议的研究包括三个互补创新，这将使人们更好地理解对总产品的算法和代码设计。首先，我们为算法开发了一个代数模型，其中我们可以研究固定基因座以及几次迭代后的动力学。我们已经使用此模型来建立有关小型代码算法收敛性的确切结果，并成功地应用了较小示例的启发式方法，以了解较大实践尺寸的代码。其次，我们已经改进了一种广泛使用的方法，用于构建LDPC代码，其中奇偶校验检查矩阵是带有循环一质量的块矩阵。我们的方法适用于非常通用的块矩阵结构，并控制了检查矩阵的两分图中的小周期的存在。我们将对使用此方法构建的各种代码进行系统比较，并与其他方法进行比较。第三，我们开发了一种基于网格的软件基础架构，用于研究以高信噪比的不同代码的解码属性。使用此基础架构，我们将能够收集有关以高信噪比解码故障的统计数据。我们可以检查输入向量的属性，从而导致解码失败并测试解码失败与代码图形模型之间的关系。Broader的影响：成功完成我们的研究将对错误纠正技术产生重大影响，这在数据通信和存储中起着越来越重要的作用。蜂窝和无线技术领域的商业应用将立即受益。我们的工作还将影响低功率和不可靠的通信系统（例如传感器网络）领域的新兴研究学科。该研究项目将帮助圣地亚哥州立大学的数学和统计系数学和统计学系，其目标是开发针对多种遗传学领域的科学家和科学家的专注于应用数学研究和合作的集中领域。通过该项目的合作，我们认为这还将鼓励学生从事博士研究，将严格的数学与先进的计算机系统技术结合在一起。智能优点：该提案中的知识分子优点体现在其三个功能中。首先，它开发并采用了一种新方法，重点是信念传播的基础和高质量LDPC代码的数学定义。其次，它使用新颖的全国分布式大规模计算功能来指导和援助分析，而不是仅仅提供代码质量的经验证据。最后，它将数学和高性能计算机系统方面的专业知识融合在一起，以既可以产生重大的结果，又将激励学生采用类似的跨学科研究方法。