The Turbo Decoding Algorithm and its Relatives

1993年，一组法国研究人员宣布发明了“涡轮码”，这是一种在各种通信信道模型上实现接近香农极限性能的根本新方法。许多研究者认为，涡轮码是自香农论文发表以来在纠错码领域最重要的新思想。McEliece教授在这项NSF资助下的工作是为了为实验验证的迭代涡轮解码算法提供一个合理的理论解释，这是法国小组的关键创新。McEliece的研究发现了turbo解码算法与密码学、信息论、数字通信、信号处理、统计学和人工智能社区中已知的许多其他算法之间的密切联系。McEliece和他的同事已经证明，所有这些算法都可以通过一种他称之为“广义分配律”（GDL）的技术统一起来。在这项工作中，目标是利用GDL来(a)寻找turbo解码算法的理论解释，以及(b)在非turbo情况下设计新的解码算法。

In 1993, a group of French researchers announced the invention of ``turbo-codes,'' a fundamentally new approach to the problem of attaining near Shannon limit performance on a variety of communications channel models. Many researchers believe that turbo codes are the most important new idea in error-correcting codes since Shannon's original paper. Professor McEliece's work under this NSF grant is motivated by the desire to provide a sound theoretical explanation for the experimentally verified iterative turbo decoding algorithm, which is the key innovation of the French group. McEliece's research has led to the discovery of a close connection between the turbo decoding algorithm and a number of other algorithms known in the cryptography, information theory, digital communications, signal processing, statistics, and artificial intelligence communities. McEliece and his co-workers have shown that all of these algorithms can be unified by a single technique which he calls the generalized distributive law, or GDL. In this work, the goal is to exploit the GDL to (a) search for a theoretical explanation of the turbo decoding algorithm, and (b) to devise new decoding algorithms in non-turbo situations.