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.

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