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解码器，这些解码器并没有宣传信念，但相当不同的是反映代码图的本地结构的信息。 设计此类解码器的方法涉及识别传统解码器失败的图形结构，并得出消息传递规则，这些规则可以纠正这些结构的大多数，而这些结构的大多数则使用消息中使用的数量最少。 通过在简单的解码器中传递的消息中添加更多位来构建新的和依次更好的解码算法。 该项目开发了一个全面的框架来研究解码器，以实现低噪声区域的复杂性和性能之间的最佳权衡。 同样，通过增加表示输入字母的位数，可以依次获得连续通道的解码器行为的近似。