CIF: Medium: Iterative Decoding Beyond Belief Propagation

点击翻译按钮获取中文摘要

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.