博文
数字通信介绍（2）香农与信息论
精选
|||
上个世纪四十年代，半导体三极管还未发明，电子计算机也尚在襁褓之中。但是通信技术已经有了相当的发展。从十九世纪中叶，电报就已经很普遍了。电报所用的摩斯码（Morse Code），就是通信技术的一项杰作。摩斯码用点和线（不同长度的电脉冲）来代表字母，而用空格来代表字母的边界。但是每个字母的码不是一样长的。常用的字母E只有一个点。而不常用的Z有两划两点。这样，在传送英语时，平均每个字母的码数就减少了。事实上，摩斯码与现代理论指导下的编码相比，传送速度只差15%。这在一百五十多年前，是相当了不起了。
除了用点，划来表示两个状态外，后来的电报也用极性相反的电流来代表这两个状态，从而使“点”和“划”都能用短的脉冲来表达，加快了传送速度。爱迪生更发明了用四个不同的电流值来同时传输两路电报。这和今天用的数字调幅（ASK）很像，只是没有载波而已（见前文《数字通信介绍（1） 调制》）。另一方面，电话在二十世纪初也迅速发展。电话公司通过在不同载波上的调制，可以用一路电线传输多路电话。
在二次世界大战时，雷达和无线电在军事上广泛应用。无线电受各种噪声的干扰很厉害，这也给通讯技术提出了新的课题。各种不同的调制方式也纷纷问世。于是就出现了这样一个问题：给定信道条件，有没有最好的调制方式，来达到最高的传送速率？
在前文《数字通信介绍（1） 调制》的结尾谈到：“传输速率是波特率与每波特所含比特数的乘积。波特率受频宽的限制，而每波特所含比特数受噪声的限制。”前一个限制，由那奎斯特（Harry Nyquist）在1928年漂亮地解决了。而后一个问题则更复杂。1928年，哈特利（R. V. L. Hartley）首先提出了信息量的概念，并指出编码（如摩斯码）在提高传送速度中的重要作用。但是他未能完整定量地解决这个问题。二战期间，维纳（Norbert Wiener）发展了在接收器上对付噪声的最优方法。但是传输速率的上限还是没有进展。
在这种情况下，香农（Claude E Shannon）在1948年发表了《通信的一个数学理论》(C. E. Shannon, A Mathematical Theory of Communication”, The Bell System Technical Journal, Vol. 27, pp. 379-423, 1948 http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf)，完整地解决了通讯速度上限的问题。“信息论”（Information Science）从此诞生。
香农（1916 – 2001）可说是二十世纪最伟大的科学家之一。他二十岁就以数学和电子工程双学位毕业，进入MIT读研究生。一年以后（1937年），他的硕士论文开创了使用布尔逻辑（Boole’s Logic）分析电子计算机线路的途径。布尔逻辑今天仍是分析数字电路的基本工具。1940年，香农以题为“理论遗传学的代数”的论文得到博士学位，到数学物理研究的圣地普林斯顿高等研究院任职。后来他转任贝尔实验室继续研究工作。除了信息论外，香农在加密理论，取样理论等领域都有开创性的贡献。他还活跃于人工智能，计算机等领域。他1956年到MIT任教，直到1978年退休。
香农虽然是数学出身，却十分重视直觉。他的同事评价说，香农最擅长的就是把一个复杂的问题简化，去掉无关紧要的细节而保留关键的问题。在他创立信息论的工作，就是一个非常优美的例子。我以为，他的原始论文比 我所见到过的所有教科书上的推导都要直观易懂。以下，就简要地介绍一下这个工作【注一】。
要建立信息理论，首先要能够度量信息。信息是由信号传播的。但是信息与信号有本质的区别。所以如何度量一个信号源的信息量，就不是简单的问题。从直觉上说，如果一个信号源发出不变的符号值（比如总是1），它是没有信息量的，因为它没有告诉别人任何东西【注二】。而且如果信号源发出的符号值是变化的但是可以预计的（比如圆周率的数字序列），那也是没有信息量的，因为我不需要接受任何东西，就可以把这些符号值重复出来。而且，即使信号源发出的符号不是完全可确定的，它的信息量也和“确定”的程度有关。例如，如果一个地方90%的时候是晴天，气象报告就没有多大用处。而如果50%的时候是晴天其余时候下雨，人们就需要气象报告了。
从这点出发，香农就把信息量与信号源的不确定性，也就是各个可能的符号值的几率分布联系起来。他从直观上给出了信息量需要满足的几个简单的数学性质（如连续性，单调性等），而给出了一个唯一可能的表达形式。
那么这样定义的信息量与我们通常所说的数据量，也就是需要多少比特来传送数据，有什么关系呢？（比特就是二进制数据的位数）。为此，我们来看看一个含有固定符号数的序列（也就是信号或码字）。由于每个符号值的出现是随机的，这样的序列就有很多可能性。显然，每个可能的符号在序列中出现次数，对于所有可能序列的平均值正比于符号出现的几率。我们把每个符号出现次数“正好”等于其次数平均值的序列叫做“典型序列”，而其他的就叫作“非典型序列”。而数学上可以证明，当N趋于无穷大时，“非典型序列”出现的几率趋于零。也就是说，我们只要注意“典型序列”就行了。而典型序列的个数，就是它们出现概率的倒数（因为总概率为1）。而码字所携带的数据量，就是它的个数以2为底的对数。【注三】所以，这样的分析就得出了序列所含的数据量。除以序列的长度，就得到每个符号所含的数据量。而这个结果恰好就等于上面所说的信息量！
至此，香农开创性地引入了“信息量”的概念，从而把传送信息所需要的比特数与信号源本身的统计特性联系起来。这个工作的意义甚至超越了通信领域，而成为信息储存，数据压缩等技术的基础。
解决了信号源的数据量问题后，我们就可以来看信道了。信道（channel）的作用是把信号从一地传到另一地。在香农以前，那奎斯特已经证明了：信道每秒能传送的符号数是其频宽的一半。但问题是，即使这些符号，也不是总能正确地到达目的地的。在有噪声的情况下，信道传送的信号会发生畸变，而使得接收者不能正确地判断是哪个符号被发送了。前文《数字通信介绍（1） 调制》中谈到，对付噪声的办法是减少每个符号所带的比特数：
“而每个波特所含的比特数，则是受噪声环境的限制。这是因为当每个波特所含的比特数增加时，它的可能值的数目也增加。这样代表不同数据的信号就会比较接近。例如，假定信号允许的电压值在正负1伏之间。如果每个波特含一个比特，那么可能的值是0或1。这样我们可以用-1伏代表0，用1伏代表1。而假如每波特含两个比特，那么可能的值就是0，1，2，3。我们需要用-1伏，-0.33伏，0.33伏，1伏来代表着四个可能值。这样，如果噪声造成的误差是0.5伏的话，那么在前一种情况不会造成解读的错误（例如把-1V错成了-0.5伏，它仍然代表0）。而在后一种情况则会造成错误（例如把-1V错成了-0.5伏，它就不代表0，而代表1了）。所以，每个波特所含的比特数也是不能随便增加的。以上两个因素合起来，就构成了对于数据传输速率的限制。”
其实，除此之外，还有一个对付噪声的办法，就是在所有可能的符号序列中只选用一些来代表信息。例如，如果符号值是0和1，那么三个符号组成的序列就有8个：000，001，010，011，100，101，110，111。我们现在只用其中两个来代表信息：000和111。这样，如果噪声造成了一个符号的错误，比如000变成了010，那我们还是知道发送的是000而不是111【注四】。这个方法的代价与前面的方法一样，就是降低了传送速率（原来可以送三个比特，现在只能送一个比特了）。这种选取特定序列，而不是使用所有序列的方法称为编码。以上的例子，是一个极为简单的码，远非最优。
可见，用降低速率来减少错误的方法有很多选项。那么怎样才能达到速度和准确度之间最好的权衡呢？这看来是一个非常棘手的问题。然而，香农却得出了一个非常简明的结论：对于一个信道，有这样一个速率（称为信道的容量）：一定有一个方法能在这个速率以下传送数据而误差的几率达到任意小；而超过这个速率的话，误差的几率就一定会大于某个下限。也就是说，香农同时给出了无错误的条件下传送速度的上限（即不可能超过）和下限（即有办法达到），而这两者是同一个值！
不仅结论出乎意料地简单，香农的证明也是如此。他的基本思路是：噪声使得接收端收到信号后，对于所发送的信号仍然有个不确定性。也就是说，一个收到的序列可能对应多个发送的序列。这个对应的个数可以用上面讲到的“典型序列”的个数来估计。因为如此，我们只能用这多个发送序列之中的一个来作为码字，代表要传送的信息，而其余都弃之不用。这样才能避免混淆。所以，我们的传送速率就要降低了【注五】。这个直观解释听起来简化得离谱。我们知道，随机过程是很复杂的，怎么可能用平均值就搞定呢？然而，香农在数学上严格地证明了这些结论。关键在于：他考虑序列长度趋向于无穷的情况。这样，在样本数量趋于无穷的情况下，实际情况偏于平均值的几率趋向于零。所以说，香农的简化显示他真正抓住了问题的关键。
对于通常遇到的信道，香农定理说：信道容量（即最高传送速率）与频宽成正比，与信噪比的对数（底数为2）成正比。信噪比是在接收端信号功率与噪声功率的比。增加发射功率能增加信噪比从而增加容量，但因为是对数关系，不是那么有效。而增加频宽则是线性地增加容量。通常，频率较低的频道频宽也小。如前一讲中提到的调幅（AM）广播，在几百千赫频段，频宽是20千赫。而调频（FM）广播是在一百兆赫频段，频宽是200千赫。这就是调频广播音质较好的主要原因【注六】。所以现代的数字通信服务不断往高频段扩展（目前已到2千兆赫）。当我们听到某个服务能提供更高速率的时候，并不等于它使用了性能更好的技术。很可能它只是用了更宽的频道而已。
香农完美地给出了信道容量，所以有人说他“开创并结束”了信息论。但是香农还是留下了一些困难的问题。比如，当信道随时间变化时，应用香农理论就远不是直截了当的。最重要的，是为了达到香农极限，我们处理的符号序列必须无限长。而实际上，信道编码的长度受着传送延迟和系统复杂性的限制。在这样的限制下，如何达到最高的传送速度？六十年后的今天，人们还在为此奋斗。这是下一讲的题目了。
【注一】 为简明起见，我们这里仅讨论符号值是离散的情况。香农的论文中还包括了连续值的情况。
【注二】 我们这里用的术语是：“信号”是携带信息的某种物理量（如电波，声音，光等）。“符号”是一个信号单元，如一个字母，一个音节，一个调制单位，一个脉冲等。信号可以看成是很多符号组成的一个序列。这样的序列也叫“码字”。
【注三】 例如，如果我们有八个可能的码字（例如字母A到H），我们可以将其编号为0到7。用二进制数来代表这八个数，需要3个比特（3 是8以2为底的对数）。如0是000，6是110，7是111等。将这三个比特传到接受者，接收者就能还原出码字的编号，从而知道所传送的码字了。
【注四】 当然，如果错了两个符号，收到了011，那我们就认为发送的是111，而产生了错误。但是，错两位的概率要比错一位小得多。如果错一位的概率是0.001，那么错两位的概率就是0.000001.
【注五】 这里的叙述还是不很清楚，因为我想避免使用数学公式。有兴趣的读者应该去读香农的原始论文，那里的解释要好得多。
【注六】 当然，AM和FM是模拟调制，其性能离香农极限差得远。但基本道理还是一样的。
https://blog.sciencenet.cn/blog-309766-275997.html
上一篇：健保法案解读（3）怎样从Medicare“省钱”？
下一篇：健保法案解读（4）健保改革的目标达到了吗？
除了用点，划来表示两个状态外，后来的电报也用极性相反的电流来代表这两个状态，从而使“点”和“划”都能用短的脉冲来表达，加快了传送速度。爱迪生更发明了用四个不同的电流值来同时传输两路电报。这和今天用的数字调幅（ASK）很像，只是没有载波而已（见前文《数字通信介绍（1） 调制》）。另一方面，电话在二十世纪初也迅速发展。电话公司通过在不同载波上的调制，可以用一路电线传输多路电话。
在二次世界大战时，雷达和无线电在军事上广泛应用。无线电受各种噪声的干扰很厉害，这也给通讯技术提出了新的课题。各种不同的调制方式也纷纷问世。于是就出现了这样一个问题：给定信道条件，有没有最好的调制方式，来达到最高的传送速率？
在前文《数字通信介绍（1） 调制》的结尾谈到：“传输速率是波特率与每波特所含比特数的乘积。波特率受频宽的限制，而每波特所含比特数受噪声的限制。”前一个限制，由那奎斯特（Harry Nyquist）在1928年漂亮地解决了。而后一个问题则更复杂。1928年，哈特利（R. V. L. Hartley）首先提出了信息量的概念，并指出编码（如摩斯码）在提高传送速度中的重要作用。但是他未能完整定量地解决这个问题。二战期间，维纳（Norbert Wiener）发展了在接收器上对付噪声的最优方法。但是传输速率的上限还是没有进展。
在这种情况下，香农（Claude E Shannon）在1948年发表了《通信的一个数学理论》(C. E. Shannon, A Mathematical Theory of Communication”, The Bell System Technical Journal, Vol. 27, pp. 379-423, 1948 http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf)，完整地解决了通讯速度上限的问题。“信息论”（Information Science）从此诞生。
香农（1916 – 2001）可说是二十世纪最伟大的科学家之一。他二十岁就以数学和电子工程双学位毕业，进入MIT读研究生。一年以后（1937年），他的硕士论文开创了使用布尔逻辑（Boole’s Logic）分析电子计算机线路的途径。布尔逻辑今天仍是分析数字电路的基本工具。1940年，香农以题为“理论遗传学的代数”的论文得到博士学位，到数学物理研究的圣地普林斯顿高等研究院任职。后来他转任贝尔实验室继续研究工作。除了信息论外，香农在加密理论，取样理论等领域都有开创性的贡献。他还活跃于人工智能，计算机等领域。他1956年到MIT任教，直到1978年退休。
香农虽然是数学出身，却十分重视直觉。他的同事评价说，香农最擅长的就是把一个复杂的问题简化，去掉无关紧要的细节而保留关键的问题。在他创立信息论的工作，就是一个非常优美的例子。我以为，他的原始论文比 我所见到过的所有教科书上的推导都要直观易懂。以下，就简要地介绍一下这个工作【注一】。
要建立信息理论，首先要能够度量信息。信息是由信号传播的。但是信息与信号有本质的区别。所以如何度量一个信号源的信息量，就不是简单的问题。从直觉上说，如果一个信号源发出不变的符号值（比如总是1），它是没有信息量的，因为它没有告诉别人任何东西【注二】。而且如果信号源发出的符号值是变化的但是可以预计的（比如圆周率的数字序列），那也是没有信息量的，因为我不需要接受任何东西，就可以把这些符号值重复出来。而且，即使信号源发出的符号不是完全可确定的，它的信息量也和“确定”的程度有关。例如，如果一个地方90%的时候是晴天，气象报告就没有多大用处。而如果50%的时候是晴天其余时候下雨，人们就需要气象报告了。
从这点出发，香农就把信息量与信号源的不确定性，也就是各个可能的符号值的几率分布联系起来。他从直观上给出了信息量需要满足的几个简单的数学性质（如连续性，单调性等），而给出了一个唯一可能的表达形式。
那么这样定义的信息量与我们通常所说的数据量，也就是需要多少比特来传送数据，有什么关系呢？（比特就是二进制数据的位数）。为此，我们来看看一个含有固定符号数的序列（也就是信号或码字）。由于每个符号值的出现是随机的，这样的序列就有很多可能性。显然，每个可能的符号在序列中出现次数，对于所有可能序列的平均值正比于符号出现的几率。我们把每个符号出现次数“正好”等于其次数平均值的序列叫做“典型序列”，而其他的就叫作“非典型序列”。而数学上可以证明，当N趋于无穷大时，“非典型序列”出现的几率趋于零。也就是说，我们只要注意“典型序列”就行了。而典型序列的个数，就是它们出现概率的倒数（因为总概率为1）。而码字所携带的数据量，就是它的个数以2为底的对数。【注三】所以，这样的分析就得出了序列所含的数据量。除以序列的长度，就得到每个符号所含的数据量。而这个结果恰好就等于上面所说的信息量！
至此，香农开创性地引入了“信息量”的概念，从而把传送信息所需要的比特数与信号源本身的统计特性联系起来。这个工作的意义甚至超越了通信领域，而成为信息储存，数据压缩等技术的基础。
解决了信号源的数据量问题后，我们就可以来看信道了。信道（channel）的作用是把信号从一地传到另一地。在香农以前，那奎斯特已经证明了：信道每秒能传送的符号数是其频宽的一半。但问题是，即使这些符号，也不是总能正确地到达目的地的。在有噪声的情况下，信道传送的信号会发生畸变，而使得接收者不能正确地判断是哪个符号被发送了。前文《数字通信介绍（1） 调制》中谈到，对付噪声的办法是减少每个符号所带的比特数：
“而每个波特所含的比特数，则是受噪声环境的限制。这是因为当每个波特所含的比特数增加时，它的可能值的数目也增加。这样代表不同数据的信号就会比较接近。例如，假定信号允许的电压值在正负1伏之间。如果每个波特含一个比特，那么可能的值是0或1。这样我们可以用-1伏代表0，用1伏代表1。而假如每波特含两个比特，那么可能的值就是0，1，2，3。我们需要用-1伏，-0.33伏，0.33伏，1伏来代表着四个可能值。这样，如果噪声造成的误差是0.5伏的话，那么在前一种情况不会造成解读的错误（例如把-1V错成了-0.5伏，它仍然代表0）。而在后一种情况则会造成错误（例如把-1V错成了-0.5伏，它就不代表0，而代表1了）。所以，每个波特所含的比特数也是不能随便增加的。以上两个因素合起来，就构成了对于数据传输速率的限制。”
其实，除此之外，还有一个对付噪声的办法，就是在所有可能的符号序列中只选用一些来代表信息。例如，如果符号值是0和1，那么三个符号组成的序列就有8个：000，001，010，011，100，101，110，111。我们现在只用其中两个来代表信息：000和111。这样，如果噪声造成了一个符号的错误，比如000变成了010，那我们还是知道发送的是000而不是111【注四】。这个方法的代价与前面的方法一样，就是降低了传送速率（原来可以送三个比特，现在只能送一个比特了）。这种选取特定序列，而不是使用所有序列的方法称为编码。以上的例子，是一个极为简单的码，远非最优。
可见，用降低速率来减少错误的方法有很多选项。那么怎样才能达到速度和准确度之间最好的权衡呢？这看来是一个非常棘手的问题。然而，香农却得出了一个非常简明的结论：对于一个信道，有这样一个速率（称为信道的容量）：一定有一个方法能在这个速率以下传送数据而误差的几率达到任意小；而超过这个速率的话，误差的几率就一定会大于某个下限。也就是说，香农同时给出了无错误的条件下传送速度的上限（即不可能超过）和下限（即有办法达到），而这两者是同一个值！
不仅结论出乎意料地简单，香农的证明也是如此。他的基本思路是：噪声使得接收端收到信号后，对于所发送的信号仍然有个不确定性。也就是说，一个收到的序列可能对应多个发送的序列。这个对应的个数可以用上面讲到的“典型序列”的个数来估计。因为如此，我们只能用这多个发送序列之中的一个来作为码字，代表要传送的信息，而其余都弃之不用。这样才能避免混淆。所以，我们的传送速率就要降低了【注五】。这个直观解释听起来简化得离谱。我们知道，随机过程是很复杂的，怎么可能用平均值就搞定呢？然而，香农在数学上严格地证明了这些结论。关键在于：他考虑序列长度趋向于无穷的情况。这样，在样本数量趋于无穷的情况下，实际情况偏于平均值的几率趋向于零。所以说，香农的简化显示他真正抓住了问题的关键。
对于通常遇到的信道，香农定理说：信道容量（即最高传送速率）与频宽成正比，与信噪比的对数（底数为2）成正比。信噪比是在接收端信号功率与噪声功率的比。增加发射功率能增加信噪比从而增加容量，但因为是对数关系，不是那么有效。而增加频宽则是线性地增加容量。通常，频率较低的频道频宽也小。如前一讲中提到的调幅（AM）广播，在几百千赫频段，频宽是20千赫。而调频（FM）广播是在一百兆赫频段，频宽是200千赫。这就是调频广播音质较好的主要原因【注六】。所以现代的数字通信服务不断往高频段扩展（目前已到2千兆赫）。当我们听到某个服务能提供更高速率的时候，并不等于它使用了性能更好的技术。很可能它只是用了更宽的频道而已。
香农完美地给出了信道容量，所以有人说他“开创并结束”了信息论。但是香农还是留下了一些困难的问题。比如，当信道随时间变化时，应用香农理论就远不是直截了当的。最重要的，是为了达到香农极限，我们处理的符号序列必须无限长。而实际上，信道编码的长度受着传送延迟和系统复杂性的限制。在这样的限制下，如何达到最高的传送速度？六十年后的今天，人们还在为此奋斗。这是下一讲的题目了。
【注一】 为简明起见，我们这里仅讨论符号值是离散的情况。香农的论文中还包括了连续值的情况。
【注二】 我们这里用的术语是：“信号”是携带信息的某种物理量（如电波，声音，光等）。“符号”是一个信号单元，如一个字母，一个音节，一个调制单位，一个脉冲等。信号可以看成是很多符号组成的一个序列。这样的序列也叫“码字”。
【注三】 例如，如果我们有八个可能的码字（例如字母A到H），我们可以将其编号为0到7。用二进制数来代表这八个数，需要3个比特（3 是8以2为底的对数）。如0是000，6是110，7是111等。将这三个比特传到接受者，接收者就能还原出码字的编号，从而知道所传送的码字了。
【注四】 当然，如果错了两个符号，收到了011，那我们就认为发送的是111，而产生了错误。但是，错两位的概率要比错一位小得多。如果错一位的概率是0.001，那么错两位的概率就是0.000001.
【注五】 这里的叙述还是不很清楚，因为我想避免使用数学公式。有兴趣的读者应该去读香农的原始论文，那里的解释要好得多。
【注六】 当然，AM和FM是模拟调制，其性能离香农极限差得远。但基本道理还是一样的。
https://blog.sciencenet.cn/blog-309766-275997.html
上一篇：健保法案解读（3）怎样从Medicare“省钱”？
下一篇：健保法案解读（4）健保改革的目标达到了吗？
