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 解码器不同，这些解码器不传播信念，而是传播一种相当不同的信念。反映代码图局部结构的消息类型。 设计此类解码器的方法包括识别传统解码器失败的图形结构，并导出消息传递规则，该规则可以用消息中使用的最少位数来纠正大多数这些结构。 通过向在更简单的解码器中传递的消息添加更多位来构建新的、逐渐更好的解码算法。 该项目开发了一个综合框架来研究解码器，以实现低噪声区域复杂性和性能之间的最佳平衡。 此外，通过连续增加表示输入字母表的位数，可以获得连续通道的解码器行为的更好近似。