CIF: Medium: Iterative Decoding Beyond Belief Propagation

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

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.