香农的信息论

感觉说的都会大白话啊。

本草纲目 发过几篇ISIT, TCOM，离开信息论通信多年

涛吴 等 361 人赞同了该回答

以前读本科的时候，当讲到信源编码率等于H(X)，信道容量等于max_p(X) I(X,Y)的时候，也觉得没什么，只是记到脑子里面而已。直到读博的时候再上信息论的课，才了解到这些结论的证明。
这些定理的结论都是充要条件，所以证明有两个方向。
第一，Achievability. 即提出一种编码方式，以H(X) (或I(X,Y))为编码率，可以达到在码长无限的情况下错误率逼近于零。这样就证明了码率<=H(X) (或I(X,Y))。这种编码方式是理论上成立的，只是复杂度很高而已。方法叫typical set coding，复杂度是指数级的。
第二, Converse，即利用信息论中的不等式结论(比如Fano's inequity)来证明码率>= H(X) （或I(X,Y))。这就证明了自己在第一步里提出来的方法是最优的。

另外，Shannon也证明了信源信道编码是可以分开的，合起来编码不会比分开更优，所以几十年来信源编码和信道编码就像是分道扬镳一样，各自发展。

所以，Shannon的论文定义了点对点通信中两个最重要的问题，给出了解法，并且证明了他的解法在速率角度是最优的。 在Shannon论文前后，通信和编码领域也都有着发展。不过，在他的论文以后，所有人的论文都多了一个benchmark: Shannon limit. 大家都朝着Shannon给出的理论界努力。香农提出的编码方法是很复杂的，之后很多人的努力就是提出工程上可行的方案，比如Convolutioal code, Turbo code, LDPC code 之类，目前比较好的能够接近Shannon limit的是LDPC以及Turbo.

Shannon打开了一扇窗，指明了数字通信和压缩系统发展的目标，同时，信息熵的定义也被其他学科，比如统计，计算机，广泛应用。我认为这是他的主要贡献。IEEE信息论协会做了一个官方的纪念视频： https://www.youtube.com/watch?v=pHSRHi17RKM

在Shannon之后，还有无数科学家和工程师在通信领域努力，达到Shannon得出的理论边界。举一些在信道编码里面的例子。
Robert Gallager: 60年代就发明了LDPC code，可惜由于当年计算能力的限制，没有被重视，直到2000年左右被重新发现，现在已经成为公认的十分接近Shannon的信道容量定理的编码，已经被加入各种无线通信标准中。他有很多有名的学生，比如Elwyn Berlekamp, 做无线通信的David Tse， 做网络编码的Muriel Medard.
Irving Reed and Gustave Solomon: 发明了Reed-Solomon code，走的是代数路线。这种编码用在CD/DVD， 卫星通信（70年代开始），数字电视中.
Elwyn Berlekamp: 发明了Reed-Solomon码的解码算法。他还从Jim Simons手上接手了一个对冲基金，弄出一年55.9%的收益以后又卖回给Jim Simons回Berkeley教书去了。那个基金叫大奖章基金，那家公司叫Renaissance Technologies. 他有一个学生叫Robert Li， 网络编码的发明人之一。
Andrew Viterbi: 发明了Viterbi算法作为卷积码的译码算法，由卷积码延伸出来的Turbo code也是一种capacity achieving code. 该算法也是Hidden Markov Model里求Max Likelihood sequence的经典算法。同时，他还创建了一家公司，叫Qualcomm (高通）。
还有很多人，不一一多说，可以看看历届Shannon Award的获得者：Claude E. Shannon Award. 还有一个不得不提的人，Ralf Koetter，他是近年来信息论界少有的代数和概率功底都极为深厚的人，可惜英年早逝。

Shannon在学术上活跃的时间大约在40-50年代，然后他就开始玩其他东西了。比如他做了能走迷宫的机械老鼠。更有意思的应该还是他和Thorp去拉斯维加斯耍赌场的故事。他们做了一个装置，可以在转盘小球刚开始转动的时候根据小球运动发现出转盘的偏差，从而计算出小球落到某些格子的概率可能会更大。Thorp后来了一本很流行的书，叫Beat the dealer, 讲他在blackjack上的研究。有一本书叫Fortune's Formula，讲做信息论的人在赌博方面的故事。

时隔60年，点对点通信的问题基本已经解决，物理层通信已经非常成熟和标准化。信息论圈子早已开始关注其他的热点。比如2000年开始的网络信息论和网络编码，2006年左右开始的compressive sensing， 2008-09那时候开始的interference alignment， 还有2010年之后David Tse开始做bioinformatics. 可惜这些热点除了Compressive sensing在医学MRI中有比较大的实用价值以外，其他的目前大都缺乏实用的地方。

编辑于 2016-05-07

赞同 361