驶向信道容量：从信道编码定理说起
——纪念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卷积码可以通过基于滑窗结构的迭代译码器进行译码，因而编译码时延小，适宜于不需要将数据分块的连续数据传输系统以及可变帧长的包通信系统中。
虽然Turbo码和LDPC码的性能已经非常接近信道容量，但都是通过仿真验证的。2008年Arikan提出了Polar码，这是第一类可理论证明,达到任意二进制输入离散无记忆对称信道容量,也就是可以迏到Shannon限的码，并且具有线性复杂度编译码器的信道码。Polar码构造的核心是“信道极化(channel polarization)”。通过极化，多个独立二进制输入信道被变换为容量接近于0或1的极端信道，然后可以在容量接近于1的无噪信道上直接传输信息。
目前，LDPC码已经在通信系统中获得了广泛应用，例如无线局域网(IEEE 802.11n), WiMax (IEEE 802.16e), 数字视频广播 (DVB-S2),10GBase-T以太网 (IEEE 802.3an), NASA的近地轨道卫星通信以及深空通信中（CCSDS建议）。LDPC码在光通信与固态存储器中的应用也正在研究中。LDPC码和Polar码是下一代通信系统（5G）中信道编码方案的强力候选者。
在译码方法上，早期的编码方案主要采用了硬判决译码，即解调器首先对调制器输入符号做出最佳判决，然后将此硬判决结果送给译码器；译码器再对编码器输入消息做一个最佳判决，以纠正解调器可能发生的错误判决，这就是所谓“纠错码”的观点。但这种译码方法损失了一部分信道所提供的有用信息，因而译码性能并不理想。后来，为了提高通信系统的性能，人们从Shannon的数据处理定理出发，提出了软判决译码方法。即如果解调器能送给译码器一个关于“不同调制器输入符号可能性”的似然信息序列，或未量化的输出，让译码器将这些信息与编码信息综合在一起做出判决，则系统性能可以得到较大提高。这就是“软判决”，即在一个高效的数字通信系统中，实际判决是译码器而不是解调器的任务。
总结信道编译码技术的发展，可以看出：由短码通过级联、交织构造长码，或由随机和代数方法直接构造长码，并采用软判决迭代译码逼近最大似然译码，从编码、译码两个方面共同努力，达到了逼近Shannon容量限的性能。我们将上述逼近容量限的具体编译码方法归纳为：
●串/并行级联码、乘积码：由简单的短码构造好的长码;基于迭代译码解决长码的可实用（线性复杂度）最佳译码问题。
●LDPC码：通过随机或代数方法直接构造好的长码;用消息传递算法解决最佳软译码问题。
●空间耦合码：将Turbo、LDPC码等进一步耦合，构造更长的普适码;用滑窗译码解决译码时延问题。
●Polar码：创建极端信道，每个比特子信道具有不等保护能力，在好信道上直接传输信息;极化后的信道可用简单的逐次干扰抵消译码。
信息论是通信与信息系统的基础理论，是现代通信发展的动力和源泉。现代数字通信的重大突破均源自于Shannon信息理论的重要成果。关于信息论对通信系统发展的指导作用，高通公司前技术总监J. Viterbi博士有一个形象的比喻：如果将现代数字通信看作一辆车，那么固态电子就是发动机，而信息论就是方向盘，它指导着通信的发展方向。
二、我校信道编码的相关工作与发展
在国内，我校是我国最早从事信息与编码理论研究的单位之一。早在50年代末，在陈太一院士和胡征教授的建议下，在我校无线电物理系组建了信息论组(室)，由汪漱玉任组长,组内有顾慰文、梁传甲、王育民、杨洽、全西成、王新梅、王以铭、张铭三、应新瑜、蔣锦星、黄铣卿、丘京扬、卢永寿等老师（以后还陆续来了张玉璞、谢武军、吉筮琴、党英等，以及由我校信息论专业的早期毕业生中选留了王永康、张启明、俞在青、宋国文、张甫翊、王冶平、喻尚威等作为老师），并组织了信息论讨论班，开展了学习和相关的教学和研究工作，逐步形成了信息论基础、信道编码、随机过程和信号检测与估值等研究方向。1959年我校无线电物理系开始招收信息论专业的大学生，并由我们信息论教研室开设了信息论与编码类课程，是我国最早开设这类课程的学校之一。
60年代末和70年代初，由肖国镇、梁传甲、王育民和王新梅等老师组织了编码与密码研讨班，由肖国镇老师主持并讲述学习编码和密码所需的数学知识，在校图书馆和当时的馆长金有巽教授的大力支持下，我们几位老师一起学习讨论编码和密码中的几本经典著作和论文，撰写了：代数理论基础、纠错码(分组码和卷积码)、差错控制、伪随机序列、组合数学等参考学习资料，并在校资料室经费的全力支持下，使得我们所写的上述约四、五百万字的资料得以刻写油印出版，这些资料不仅仅是我们讨论班学习、研究的总结，也为以后我们撰写有关教材奠定了坚实基础，并为我们以后进行有关科研、招收硕士、博士生奠定了扎实的理论基础。并且作为我校与我国各有关单位作交换资料，对提高我校知名度和促进我国在编码和密码领域的发展也起到了积极推动作用。
从80年代初开始，我校以信道编码与密码作为二个主要研究方向，开始招收硕士研究生，并在胡征教授指导下从80年代末开始招收博士研究生。开设了代数编码理论以及密码的研究生课程，并且组织了讨论班，定期地与学生一起讨论、研究问题，并一直坚持至今。目前，根据国际通信与信息编码理论的发展趋势，在我校的研究生课程中，既设有信息论基础课程，也有网络信息论作为学位课，既有经典的纠错码基础、代数编码理论，还同时开设有现代数字通信与编码理论，课程体系比较完整，这在国内高校中也是很少见的。
在信道编码方向上，直至目前已培养了约百名博士和百多名硕士，在这些硕士和博士中，既包括有学术界的马建华（日本法政大学教授）、马啸（中山大学数据科学与计算机学院执行副院长、教授）、吴暇（同済大学计算机学院院长、教授）、黄本雄（华中科技大学教授）、谢显中（重庆邮电大学教授）、贺玉成（华侨大学教授）、陈西宏（地空导弹学院教授）、杜伟章(长沙理工大学教授)、柏春燕（美国罗德岛大学教授）等，以及本校的白宝明、马文平、李颖、慕建军、刘东苏等教授，也包括工业界和研究院所的周晓迈、孙韶辉、殷贯西、张国华以及在国外各大公司工作的李元兴、刘斌、刘丰、徐胜波等。2010年左右，我校的几位老师还一起组建了信息传输与编码研究中心。
我们在70年代就开展了代数码软判决译码的研究。从80年代中开始，我们在国内率先开展了基于纠错码的密码系统的研究，在世界上首先构造了基于纠错码的数字签名体制，以及纠错与加密相结合的体制等。在90年代中开始率先在国内开始了Turbo码的研究，随后结合国际发展趋势，较早地开展了LDPC码、空间耦合码、喷泉码和Polar码等的研究工作，先后承担了多项国家科技重大专项、973计划项目、863计划项目、自然科学基金项目等。在通信与编码研究方向上，先后提出了Turbo/Trellis码的逐符号前向译码算法、物理层网络编码与信道编码的联合设计方法，马啸提出的RS码译码算法还被美国T. K. Moon教授写入了其2005年出版的教科书《Error Correction Coding: Mathematical Methods and Algorithms》中；针对多元LDPC码及其编码调制系统，提出了多种构造方法与高效译码算法，目前正与有关公司合作将其推向5G移动通信；针对数字磁记录信道，马啸和A. Kavcic提出了称为匹配信息速率码的串行级联码，该成果2006年获得IEEE通信学会颁发的最佳论文奖。近期我们还与马啸教授一起提出了分组马尔科夫叠加传输（BMST）方法，可以在一定范围内实现任意错误概率、任意码率的信息传输。在工程实践方面，我们与多个研究所合作，为航天测控、无人机、移动卫星通信等系统研制了FEC编译码器。在2006年我们开始研究量子密码和量子纠错码，我校的博士后曾贵华（上海交通大学教授）率先在国内开展了量子纠错码的研究，以后我校的李卓副教授和王云江副教授等在量子纠错码中都做出许多优秀的科研成果。目前，我们正面向5G通信系统和空间信息网络，以及数据存储系统、宽带无线接入系统、互联网和量子通信等开展新型信道编码理论与应用的研究工作。
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在信息科学界中的地位和作用如同牛顿在物理领域内的地位和作用，他们所提出的学术思想与理论将在各自的领域内永放光辉！
来源 西安电子科技大学新闻网
