信道编码是在哪完成的：纪念信息论之父

信道编码是在哪完成的：纪念信息论之父现代编码始于1993年。在1993年的IEEE国际通信会议（ICC）会议上，来自法国ENST Bretagne的C. Berrou等人提出了对于信道编码界具有革命性意义的Turbo码。这是第一种能有效逼近信道容量的实用编码方案（码率为1/2的Turbo码在AWGN信道上距信道容量限仅约0.5dB）。Turbo码巧妙地将两个简单的分量码通过伪随机交织器并行级联在一起，从而构造了长码并实现了Shannon随机编码的思想。在接收端Turbo码采用低复杂度的迭代译码来逼近最大似然译码。Turbo码的提出迅速激起了编码界对迭代可译码的研究热情。目前，Turbo码已广泛应用于各种数字通信系统中，例如：CCSDS的深空通信标准、数字视频广播（DVB）标准、第三代移动通信系统以及3GPP LTE标准。上述各信道编码方案虽然译码复杂度大多在可接受的范围内，然而由于码长较短，其性能距Shannon限有较

驶向信道容量：从信道编码定理说起

——纪念Shannon诞辰100周年

■ 白宝明 王新梅

一、信息论与信道编码

1948年，美国贝尔实验室的Claude E. Shannon在贝尔技术杂志上发表了题为《通信的数学理论》的长篇论文，这篇论文用概率统计的方法研究了信息传输的内在特性，揭示了通信系统中传送的对象是信息，并定义了信息的度量和单位；系统设计的中心问题是在干扰噪声中如何有效而可靠地传送信息。指出可以用编码方法实现这一目标，提出了二个信源编码定理和一个信道编码定理；并在理论上证明了信息传输的基本性能限。这篇论文是信息理论的奠基性论文，它开创了信息论与信源和信道编码理论这一新兴学科。

在这篇论文中，Shannon首次提出了熵与信道容量的概念（在Shannon 1948年的原文中，既没有使用“互信息”也没有用一个特殊符号来记它，而总是使用不确定性之差。术语“mutual information”及符号I(X; Y )是后来由Fano引入的），并指出：任一通信信道都有一个参数C，称之为信道容量，如果信息传输速率R小于C，则存在一种编码方法，当码长充分长时，系统的错误概率可以达到任意小。这就是著名的信道编码定理。虽然Shannon给出的仅仅是一个编码的存在性定理，但它不仅开创了信道编码理论这一富有活力的研究领域，而且给出了达到信道容量的编译码方法的指导性路线，即构造随机长码和采用最大似然译码（信道编码定理最初是Shannon基于典型序列方法证明的，后来Gallager基于最大似然译码给出了强编码定理）。此后，构造可达到信道容量或者可逼近信道容量（Shannon限）的信道编码具体方法，及其可实用的(线牲复杂度)有效译码算法一直是信道编码理论与技术研究的中心任务，也就是如何构造出能接近或达到Shannon限的码（称为Shannon码或渐近好码）是编码学者长期追求的目标。

在编码方法上，人们先后提出了Hamming码、Muller码、Reed-Solomon（RS）码和BCH码、Goppa码等线性分组码以及卷积码。BCH码和RS码均可采用代数译码算法进行快速有效译码，RS码同时具有优异的纠随机和突发错误能力，因此被广泛应用于CD、硬盘等存储领域。卷积码是由Elias于1955年提出的。Wozencraft给出了卷积码的序列译码算法。后来，Fano改进了该算法。卷积码的一个重要进展是1967年Viterbi提出了Viterbi译码算法，1973年Forney证明了Viterbi算法实际上是卷积码的最大似然译码算法。在Linkabit公司和美国国家航空航天局（NASA）JPL实验室的推动下，Viterbi算法很快成为了NASA深空通信标准的一部分，并且得到了广泛的商用。

上述各信道编码方案虽然译码复杂度大多在可接受的范围内，然而由于码长较短，其性能距Shannon限有较大距离。为了构造出译码复杂度可接受且差错控制性能优异的长码，Elias在发明卷积码的前一年便提出了乘积码的概念，这是第一个由短码构造长码的方法。乘积码以两个线性分组码作为分量码，其码长为各分量码码长的乘积，译码可通过对各分量码单独译码从而得到次优的结果。1966年，Forney提出了另一种由短分量码构造长码的编码方案：（串行）级联码。级联码通过将内码和外码进行串行级联，在不增加译码复杂度的同时获得较大的性能提升。上世纪70年代，NASA采用以卷积码为内码（并用Viterbi译码）、RS码为外码的级联码作为空间通信用的信道编码标准，在理论上展示了这种码距离Shannon限在3dB以内，并在实际中取得了极好的效果（据估计，在60年代每dB的编码增益可以节约100万美元的开发与发射成本；90年代每dB编码增益对深空网络的价值已增加到8000万美元）。人们将深空通信与编码的结合称为“天仙配”（最初是由我们111基地的学术大师J. Massey给出的，称为“marriage made in heaven”）。这是第一个构造出并在实际中使用的比较接近Shannon限的好码。需要说明的是，几乎同一时期，Gallager提出了低密度校验（LDPC）码，这是一种直接构造长码并采用低复杂度的迭代译码来解决译码问题的编码方法，但在随后的几十年中，由于受硬、软件所限以及级联码的影响，低密度校验码并没有引起太多关注。

现代编码始于1993年。在1993年的IEEE国际通信会议（ICC）会议上，来自法国ENST Bretagne的C. Berrou等人提出了对于信道编码界具有革命性意义的Turbo码。这是第一种能有效逼近信道容量的实用编码方案（码率为1/2的Turbo码在AWGN信道上距信道容量限仅约0.5dB）。Turbo码巧妙地将两个简单的分量码通过伪随机交织器并行级联在一起，从而构造了长码并实现了Shannon随机编码的思想。在接收端Turbo码采用低复杂度的迭代译码来逼近最大似然译码。Turbo码的提出迅速激起了编码界对迭代可译码的研究热情。目前，Turbo码已广泛应用于各种数字通信系统中，例如：CCSDS的深空通信标准、数字视频广播（DVB）标准、第三代移动通信系统以及3GPP LTE标准。

Turbo码问世后不久，剑桥大学的MacKay和MIT的Spielman等人几乎同时发现：Gallager早在1962年提出的LDPC码在迭代译码算法下也能够逼近信道容量（如码率为1/2、码长为107比特的LDPC 码距离Shannon限不到0.04dB）。这些成果让这个沉寂三十多年的码重新焕发活力，同时迅速引发了又一轮对迭代译码研究的热潮。

上述LDPC码属于分组码，1999年Felstrom和Zigangirov提出了LDPC卷积码及其编译码技术，它可以看作是将一些标准LDPC分组码以链的形式耦合在一起而得到的，因而也被称为空间耦合LDPC码。LDPC卷积码可以通过基于滑窗结构的迭代译码器进行译码，因而编译码时延小，适宜于不需要将数据分块的连续数据传输系统以及可变帧长的包通信系统中。

1986年在美国召开的国际信息论会议（ISIT’1986）上，C.E.Shannon与中国学者在一起（前排左一是王新梅教授）

2013年在我校召开的通信与信息论国际研讨班（前排左一是白宝明教授）

在国际学术交流方面，早在70年代末我们就邀请了美国夏威夷大学计算机系主任著名的编码学者、第一本纠错码专著的作者W.W.Peterson教授，他是改革开放后我校邀请的第一位外国教授 以后还陆续邀请了许多知名的各国专家、教授如：Massey、Blahut、林舒(Shu Lin)、曾开明(K.M.Tzeng) 、Imai(今丼秀树)等到我校访问和讲学。自1982年至今我们已多人多次地参加了国际信息论会议(ISIT)以及其它有关国际学术会仪，并在1961年由陈太一院士主持，由我校主办了全国首届信息论会议。2013年我们在西电校园承办了通信与信息理论国际研讨会，这是国际上唯一一次将信息与编码理论领域的7位学术大师（MIT的Gallager、Forney 我校名誉教授UC Davis的Shu Lin等）聚集在一起进行研讨的盛会。

三、结束语

今年是Shannon诞辰一百周年（Shannon 1916年出生于美国密歇根州）。从Shannon于1948年创立信息论算起，也已经过去近70年了，人们在信道编码定理的指引下，一步步地从构造出比较接近容量限的码到提出可逼近容量限的码，最后终于研究出了能够达到信道容量限的实用编译码方法。目前，信道编码已经作为信息传输与存储等领域的一项关键技术而获得了广泛应用。在时延非严格受限（允许码长充分长）的通信系统中，我们已经能够在简单的点对点信道上实现逼近容量限的信息传输。但在时延受限（有限长）的情况下，我们还需要继续寻找好码。另外，在复杂信道环境以及网络通信情况下的信道容量，许多还是未知的，需要继续探索。对于网络通信，信息论与排队论还未完成有效的联合。从90年代开始，仿照信道编码的编译码方法，国内外开展了量子纠错码的研究，虽然取得了一系列成果，但是并没有取得突破性进展，仍需深入研究。此外，Shannon信息论在各个领域（如量子信息论、生物信息论等）的应用研究和推广也正方兴未艾。

Shannon创建信息论至今已接近七十年了，无论是信源编码、信道编码还是密码等，虽然已取得了许多优秀成果，并在实际中得到了广泛应用，但是仍有许多问题没有完全解决，需要我们继续努力！Shannon在信息科学界中的地位和作用如同牛顿在物理领域内的地位和作用，他们所提出的学术思想与理论将在各自的领域内永放光辉！

来源 西安电子科技大学新闻网