Turbo码给我们的启示
冀复生
今天Turbo码在通信界已经几乎无人不晓。用Google搜索“Turbocode”可以得到800多万结果。在未来的第三代移动通信中，它很可能成为编码方案的标准之一（即使不采用它，新的方案也很可能是受其启发，基于与它相似的思路而产生的类似方案），但是Turbo码诞生过程却有一段引人入胜的故事。1993年在日内瓦召开的IEEE通信国际会议上，两位当时名不见经传的法国电机工程师克劳德伯劳和阿雷恩格莱维欧克斯声称他们发明了一种编码方法，可以使信道编码效率接近香农极限。这一消息太“轰动”了，以致多数权威认为一定是计算或实验有什么错误。许多专家甚至懒得去读完这篇论文。在数字通信领域，编码效率一直是关注的焦点。根据现代信息论的奠基人香农提出的为科学界公认的理论，在一个存在噪声的信道里，可以可靠地传输的最大速率是
CWlog21PN
其中：C是信道内可以可靠传输的最高码率（以比特秒为单位），称之为信道容量；W是信道带宽（以赫兹或1秒为单位）；PN是信道的信噪比（即信号功率与噪声功率之比）。按照这一理论，要想在一个带宽确定而存在噪声的信道里可靠地传送信号，无非有两种途径：加大信噪比或在信号编码中加入附加的纠错码。用生活中的例子类比，就好像在一个嘈杂的啤酒馆里要让侍者听到你的要求，你就得提高嗓门（信噪比），反复吆喝（附加的冗余信号）。多年来人们都在试图接近香农提出的码率极限，然而在这两位法国老兄以前，最好的结果所消耗的功率和香农定理比较还有35分贝的差距。就是说比按照香农定律计算得到的所需功率数值高一倍多。香农曾经指出，要提高信号编码效率达到信道容量，就要使编码的分段（所谓“编码词”的长度）尽可能加长而且使信息的编码尽可能随机。但是，这带来的困难是计算机科学里经常碰到的“计算复杂性”问题。为了使编码接近香农理论，也许需要使编码词长度为1000比特。相应的计算量为21000，即约为10301。为了理解这个数字有多大，只需要指出人类目前所能探索到的宇宙范围里所有原子的总数也只有1080而已。因此在过去的几十年里尽管各种复杂的编码方案不断涌现，35分贝的距离好像被无比高耸的计算复杂性之墙阻挡而变得不可逾越。多年来，编码成为数学家的禁脔。编码专家提出种种方案，试图在可接受的计算复杂性条件下设计编码和算法，以提高效率。但我们的这两位法国老兄的数学功底也许并不怎么样，他们没有试图从数学上找突破口，因此他们的论r