CIF: Medium: Iterative Decoding Beyond Belief Propagation

CIF：中：超越置信传播的迭代解码

• 批准号: 0963726
• 负责人: Bane Vasic
• 金额: $ 67.42万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-15 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0963726&HistoricalAwards=false
• 关键词: CIF; Medium; Iterative; Decoding; Beyond

Error correcting codes are an integral part of modern day communications, computer and data storage systems and play a vital role in ensuring the integrity of data. At the heart of modern coding theory is the fact that the low-density parity check codes can be efficiently decoded by the algorithm known as belief propagation (BP). The BP is an iterative algorithm which operates on a graphical representation of a code by sending coded bit likelihoods - beliefs. The project establishes a new paradigm and develops tools for the design and analysis of decoding algorithms which are much simpler yet better than belief propagation. This novel paradigm provides a new angle in addressing a fundamental coding theory questions and a methodology for designing a class of decoding algorithms with provable performance and large flexibility in controlling complexity and speed.Unlike BP decoders, these decoders do not propagate beliefs but a rather different kind of messages that reflect the local structure of the code graph. The methodology for designing such decoders involves identifying graphical structures on which traditional decoders fail, and deriving message passing rules that can correct a majority of these structures with minimal number of bits used in the messages. New and successively better decoding algorithms are built by adding more bits to the messages passed in a simpler decoder. The project develops a comprehensive framework to study decoders that achieve the best possible trade-off between the complexity and performance in the low noise region. Also by increasing the number of bits to represent the input alphabet successively better approximations of the behavior of the decoders for continuous channels are obtained.

纠错码是现代通信、计算机和数据存储系统的重要组成部分，在确保数据完整性方面起着至关重要的作用。现代编码理论的核心是低密度奇偶校验码可以被称为信念传播（BP）的算法有效解码。BP是一种迭代算法，它通过发送编码位的可能性-信念来对代码的图形表示进行操作。该项目建立了一个新的范式，并开发了解码算法的设计和分析工具，这比信念传播简单得多，但更好。这种新范式为解决基本的编码理论问题提供了一个新的角度，并为设计一类解码算法提供了一种方法，这些算法在控制复杂性和速度方面具有可证明的性能和很大的灵活性。与BP解码器不同的是，这些解码器不传播信念，而是传播一种相当不同的消息，它反映了代码图的局部结构。设计这种解码器的方法包括识别传统解码器无法处理的图形结构，并推导出可以用最少的消息中使用的比特数纠正大多数这些结构的消息传递规则。通过在更简单的解码器中传递的消息中添加更多的比特，可以构建新的和不断改进的解码算法。该项目开发了一个全面的框架来研究解码器，在低噪声区域实现复杂性和性能之间的最佳权衡。此外，通过不断增加表示输入字母表的位数，可以获得连续信道解码器行为的较好近似。