九章格数学 PhiloMath · 数学家的故事绘本 · 第四辑

香农 · 比特与通信

第 40 册 · 数学家的故事 · 第四辑 · 1916—2001 · 美国 · 明线:信息论 · 比特 · 信道容量 · 编码 · 暗线:通信的本质是不确定
明线 · 信息 · 比特 · 信道 · 编码暗线 · 通信的本质是不确定1916—2001 · 美国全龄通识 · 三层可读
题解这一册怎么读p.2

香农(1916—2001),密歇根州人。他二十岁同时拿下电机工程与数学两个学位,二十一岁在一篇硕士论文里把开关电路变成代数,三十二岁发表一篇论文,给「信息」立下度量——从此世界上多了一个词:比特。

他一生做了三件事。第一件在电路:把继电器开关的通断写成代数式,电路设计从此可以像解方程一样进行。第二件在战时:把密码学变成数学——保密有严格的极限,达到极限的密码在原则上不可破。第三件立一门学科:一条线路、一个噪声源、一串符号,信息有多少、信道能传多少、编码能省多少,三笔账一次算清。

明线四样:开关代数(电路的最小语法)、完全保密(不确定性的用尽)、熵与信道容量(信息的度量与线路的定价)、编码(把不确定压下去、把噪声抵消掉)。

暗线一句:通信的本质是不确定。一条消息携带的信息,恰好等于它消除了多少不确定;噪声是别人加进来的不确定;保密是把不确定用到底;压缩是把不确定省下来;纠错是把不确定顶回去。全册的数学,都围着这一句转。

五幕:第一幕讲一个爱摆弄机器的学生怎样把开关变成代数(p.6—p.12);第二幕讲战时的密码与语音加密(p.13—p.19);第三幕讲比特的诞生(p.20—p.26);第四幕讲噪声与编码(p.27—p.33);第五幕讲会玩的头脑与身后的事(p.34—p.40)。

三层读法照旧:故事层无需预备知识;数学层只用到加、减、乘、除、乘方、对数与一张小表(p.7—p.9、p.14—p.16、p.21—p.23、p.28—p.30、p.35—p.37),每一步都从头算起;注疏层给出原书、版本与研究文献,逐页可查。

引子一根铁丝网上的电报p.3

先看一件少年人的小工程。密歇根州北部的小镇,两家农舍隔着约半英里的田野。一个少年把自家与朋友家之间那段带刺铁丝网接进电路:铁丝当导线,两端各装一只电铃与开关——按下开关,半英里外的铃就响。约定好的次数代表约定的意思:响一下是「出来玩」,响两下是「晚饭好了」。

这件小事里藏着通信的全部骨架。一端有话要说,另一端等着听;中间隔着距离,只能靠信号过去;信号又慢又少,一次只传得动一点点。怎么办?把想说的话事先约成一张短表:一下、两下、三下,各有各的意思。

那张表,就是编码。铃声本身不包含任何意思——意思是双方事先说好的。半英里铁丝传过去的不是话,是「约好了的记号」。

现在把问题摆正。半英里靠铃声,跨洋靠电报,穿越星系靠无线电——距离越远、噪声越大、线路越忙,那张「事先约好的表」该多长、多短、多省?怎样的表能把话说清、把错纠掉、把时间用满?

1948 年,一个三十二岁的贝尔实验室数学家给这组问题写下了答案。他说,铃声那点「事先约好的记号」,有一个精确的名字:信息。它论个卖,单位叫比特。

引子一个爱摆弄机器的学生p.4

1916 年 4 月 30 日,香农生在密歇根州佩托斯基,在盖洛德镇长大。父亲是镇上的遗嘱检验法官,母亲教语言;家里有一间能拆能装的角落,少年香农的偶像是一位大发明家——据家族记载,两家还是远亲。

1936 年,他在密歇根大学同时修完电机工程与数学两个学位。两条线并行走路:电机系教他对待真实的机器——电路、继电器、损耗与噪声;数学系教他对待抽象的结构——方程、证明与代数。此后一生的风格由此定型:凡抽象的,落到机器上检验;凡机器的,提到代数上看清。

同年他进了麻省理工学院,做研究助理。系里有一台五层楼高的机械计算装置:上百根旋转的轴,把微分方程「演」出来。轴会老化、误差会累积,他的差事是熟悉它的每一根传动链。这台机器里布满继电器——电流一通一断,机器就换一种走法。

看着那些继电器,他想起大学里一门几乎无人问津的课:一门十九世纪的代数,讲的是「真」与「假」怎么运算。开关只有通与断,命题只有真与假——两边的形状,一模一样。

1937 年,他把这层对照写成硕士论文。一年后论文刊出,工程界从此多了一门设计语言。它的来历与分量,下一幕从头细说。

引子三样东西:一台开关箱、一台密码机、一条被噪声淹没的线路p.5

这本册子要处理三样东西。三样看起来毫不相干:一块只有通与断的开关面板、一台把人声搅成乱码的密码机、一条被噪声淹没的传输线路。

第一样,开关。它是最省的自动装置:通、断,两种状态。香农证明:开关的组合可以用一门代数来运算——线路图与代数式可以互相翻译,设计电路等于解方程。一切数字机器的最小语法,就写在这块面板上。

第二样,密码机。战争把它推到台前。香农给「保密」立了一条精确的判据:最完美的密码,是让密文对明文毫无泄露——破译者看再多密文,对明文的猜测与瞎猜毫无分别。这样的密码存在,条件苛刻,但数学上说得清。

第三样,噪声。线路上的杂音会把 1 改成 0。香农证明了一件反直觉的事:只要传输速率低于一个可以算出来的上限,再吵的线路也能做到几乎不出错——前提是把消息编得足够巧妙。上限有名有姓:信道容量。

三样东西有一个共同点。它们都先回答「这件事的最小单位是什么」:电路的最小单位是开关的通断;保密的最小单位是一份不确定;传输的最小单位是一个比特。最小单位立住,剩下的交给代数。

这个办法,本册把它叫做「先分成 0 和 1」。

先算一道最小的题:两枚开关、一盏灯,几种接法?下一幕从一间摆满旋转轴的地下室讲起。

第一幕 · 故事地下室的旋转轴与一块继电器p.6

1937 年,麻省理工学院的地下室。那台五层楼高的机械计算机正在演算微分方程:上百根轴同时旋转,转速与转角就是答案。香农的差事是伺候它——哪根轴磨损了、哪段传动在打滑,他一清二楚。

机器里最不起眼的零件是继电器。一只电磁铁,通电就吸合开关,断电就弹开——用一个小电流去扳动一个大电路的「扳手」。整台机器里,继电器成百上千,全在通与断之间来回。

当时工程界的难题是:继电器电路凭经验拼装,线路越复杂越靠试错。几百只继电器的控制网,设计一只电话交换机要靠一支队伍手工排线,排完还要靠人力核查——没有人问过一句:这件事能不能「算」出来?

香农想起大学里一门冷门课。十九世纪中叶,一位英国数学家把逻辑写成了代数:命题有真有假,真与假可以像数一样相乘相加。「真且真为真,真或假为真」——这是一套完整的运算规则。可是写出来半个多世纪,谁也没见过它有什么用处。

香农看出两边是同一件东西:开关的通与断,恰好对应命题的真与假;串联、并联、反接,恰好对应与、或、非。继电器网络,原来是一门代数。

1937 年,他把这层对照写成硕士论文;1938 年刊出。论文的贡献在标题里写得明白:继电器与开关电路的「符号分析」——从此电路可以先用代数式设计、化简、验算,再落到铜线上。后世的评论说它是二十世纪最重要的硕士论文;说这话的人,是第一台电子计算机的工程负责人之一。

下一页把这门代数一条一条摆出来。

第一幕 · 数学通与断:两种状态的一门代数p.7

先立记号。一枚开关只有两种状态:通记 1,断记 0。两枚开关串联成一条路,通不通?串联记作相乘,并联记作相加;反接(平时通、按下断)记作取反。灯亮为 1,灯灭为 0。

三条基本规则,逐枚核对即得:

串联:两枚全通才通 → A × B = 1 当且仅当 A = B = 1
并联:任一枚通即通 → A + B = 1 当且仅当 A、B 至少一个为 1
反接:通变断、断变通 → 若 A = 1 则 A′ = 0

普通代数里 A × A = A2,这门代数里却有一条怪规则:一枚开关与它自己串联,还是一枚开关——通与断的状态没有变。同理,它与自身并联也是一枚开关:

A × A = A   A + A = A

再核对几条。枚举 A、B 的四种取值(00、01、10、11),逐行代入,四行全部吻合:分配律两边成立——代数的手筋原封不动地搬进了电路:

A × (B + C) = A × B + A × C  (普通代数也有)
A + B × C = (A + B) × (A + C) (普通代数没有!)

第二条值得停一停。它说:一枚开关并联在「两枚串联的开关」上,等效于两枚并联开关各再串一枚——线路的形状变了,灯的亮灭一模一样。四行真值核对:00 时两边皆 0,01 时两边皆 0,10 时两边皆 1,11 时两边皆 1。

这说明:同一个行为,有无穷多种线路画法;而代数式一旦相等,线路就等效。设计问题从「怎么接」变成了「怎么化简」。

第一幕 · 数学化简一道电路:从六枚开关到两枚p.8

出一道工程题。控制要求写成代数式:(A + B)×(A + C)——两路并联,各路串一枚。照式施工要用四枚开关。能不能更省?

用上一页的第二条分配律,从右往左拆:

(A + B)×(A + C)= A + B × C

右式只含三枚开关:一枚独走,另外两枚串联后与它并联。逐步核对:枚举 A、B、C 的八种取值,八行两边的值全部相等。

省三枚开关,行为分毫不差。这不是手工的聪明——是代数的必然。任何表达式只要代数上能化简,电路就能省钱。继电器时代的工程师,把一本化简手册用成了生产工具。

香农的论文走得更远,两条方向相反的定理:

分析:给定线路 → 写出表达式 → 枚举真值,行为一目了然
综合:给定行为(真值表)→ 反解出表达式 → 化简 → 施工图

第二条是真正的发明:电路设计从「凭经验拼装」变成「按定理推导」。给出任何一张「灯该什么时候亮」的表,就有一套死板程序产出线路——而且保证是最省的一批之一。

再看一眼这件事的位置。通断只有两态的开关,靠「与、或、非」三件工具,就能搭出任何一张真值表要求的任何行为。往远处说一句:今天一切数字芯片的最小语法,仍是这三件。第一块多米诺骨牌,1938 年推倒。

下一页用这套语言造一台最小的机器——两位数加法的进位。

第一幕 · 数学用开关造一台加法器p.9

任务:两个一位二进制数 A、B 相加,输出「和」与「进位」。先把四种情形全部列出来:

0 + 0 = 0  和 0,进位 0
0 + 1 = 1  和 1,进位 0
1 + 0 = 1  和 1,进位 0
1 + 1 = 10  和 0,进位 1

对照发现两条规律:只有「两枚都通」时才进位——进位就是与门:C = A × B。和是「恰有一枚通」——两枚同通同断时和为 0:这就是异或。用已有工具写出:

进位:C = A × B
和:S = (A + B)×(A × B)′

逐行验算第二条。四种取值代入:00 时 A+B = 0,乘后仍 0,对;01 时前因式 1、后因式 1,积 1,对;10 同理得 1,对;11 时前因式 1、后因式取反为 0,积 0,对——四行全中,这正是「半加器」。

数一数成本:进位一枚与门;和需要或门、与门、反相器各一枚,共四枚。全机的图纸由两条代数式完全决定——没有任何一步依赖手感。

往上叠就是加法。把本位和与上一位的进位再送进同一套线路,级联一位就是「全加器」;级联 n 位,就能算 n 位加法。十进制 3 + 5 = 8,在这台机器里是 0011 + 0101 = 1000,四列全加器各算各的。

停一下看后果。1938 年这台纸上机器里,「算术」与「电路」之间不再有任何神秘地带:加法是一张真值表,真值表是一组代数式,代数式是一张接线图。机器能算数,从此是一条可以验算的定理。

第一幕 · 暗线先分成 0 和 1p.10

布尔写下那门代数,讲的是逻辑;香农接过它,讲的是开关。中间那次关键的搬运,做了一件事:把连续的世界切成两半——通与断、亮与灭、有与无。切成两半之后,代数才接得上。

这就是本册的暗线:先分成 0 和 1。凡是「只有两种状态」的东西,都可以交给同一门代数:开关的通断、命题的真假、记录的有无、脉冲的有无。状态一旦离散,运算就成了查表。

后面几幕会反复看到它:谈保密,是把「破译者知道多少」写成一条不确定的量;谈声音,是把连续的声波切成每秒几千个样点;谈文本,是把字母切成比特;谈纠错,是在比特的层面上把翻掉的位顶回来。每一步都是同一个动作:离散,然后运算。

也要看清这条线的脾气。离散化有代价:声波被切成样点,就不可能比样点更细;消息被切成比特,就要为「怎么切」付出额外的信息。代价不是免费的——但它可以被精确地算出来,算出来就可以讨价还价。这正是接下来四幕的全部内容。

第一幕 · 交汇两个世纪的接力:莱布尼茨、布尔与一块继电器p.11

把第一幕放回它的年代。十七世纪,莱布尼茨梦想一种「普遍文字」:把推理化成计算,争论的双方各自算一遍,答案自动出现。梦想太早——那时连「真与假可以运算」的代数都还没有。

1854 年,布尔把它写成书:思维规律的研究。真假成了可以相乘相加的量,推理成了运算。但布尔之后八十年,这门代数停在纸面上——它描述的是思维,谁也不知道哪里有「按真假运转」的实物。

1938 年,实物出现了:继电器网络。香农的论文等于宣布:布尔代数描写的世界是真实存在的——电话交换机就是它的肉身。一门纯逻辑的代数,第一次有了工程上的家。

接力的下一棒来得很快。1940 年代,贝尔实验室的工程师用这套语言设计了千里级的电话交换网;战时的密码机与火控装置里,继电器逻辑已是现成的设计工具。第一台电子计算机(1945—1946)的运算核心,就是一套写满真值表的加法与控制线路。

回头看这条链:莱布尼茨要计算代替争论;布尔把逻辑变成代数;香农把代数变成电路。三棒接力,从「推理可以算」走到「机器会推理」——间隔恰好三个世纪。

而三棒都齐了之后,剩一个问题悬着:线路会算了,那么传输呢?信息沿着线路跑,一路上被磨损、被噪声搅乱——这件事有没有一个总账?下一幕,战争把答案逼了出来。

第一幕 · 小结一块面板上的代数p.12

一、开关接上了代数。通与断记 1 与 0,串联乘、并联加、反接取反——布尔代数与继电器电路在 1938 年被证明是同一种东西。抽象的逻辑第一次找到了实物。

二、等效即省钱。代数式相等,线路等效:四枚开关化简成三枚、八行真值核对无一失手。电路设计从手艺变成定理。

三、两条方向相反的路。从线路读出行为是分析,从行为反解出线路是综合。给一张真值表,就有一套死板程序产出施工图——设计被程序化。

四、加法是它的第一个战果。半加器的两条式子决定一张接线图,级联即是加法器。「机器会算数」从奇观变成可以验算的定理。

下一幕,战争把这位刚出校门的年轻人送进一间大实验室。在那里,他要对付两件带噪声的东西:被敌人偷听的电话,和被噪声淹没的信号——前者逼出了完美保密,后者逼出了信息的度量。

第二幕 · 故事战时:大实验室里的两件差事p.13

1941 年,香农进了新泽西州的一间大实验室——贝尔实验室。战争打响后,这间实验室的多数人转向两件差事:火控与通信保密。香农两件都沾。

第一件,火控。高炮要打中飞机,炮弹得提前一点到——飞机在动,观测有误差,提前量怎么算?这需要从一串带噪声的数据里「猜」出目标的真实轨迹。这套数学的名字叫滤波与预测,另一位数学家维纳在同时期做同一件事。香农的火控工作做得扎实,但他心里记着另一个题目。

第二件,保密。盟军高层要越洋通话,无线电波谁都能收——必须把话音加密。一项庞大的语音加密系统在实验室里成形:把话音切成频带、打乱、再用密钥流掩埋。香农是该系统的顾问之一,密钥要用纸带灌录,一次一卷,绝不重复。

比系统更重要的是他在私下做的事。1945 年,他写了一份内部备忘录,标题平平常常:密码学的数学理论。备忘录里没有一架具体机器——它问的是普遍问题:什么叫保密?保密有没有极限?极限是多少?

1943 年,一位英国客人来实验室访问。两人常在职工食堂的角落里长谈。客人是图灵——正在为英国破译德军密码,顺路访问美国。谈的是同一个词,两种问法:图灵问,机器能不能思考;香农问,一条消息里到底有多少东西。多年后两人各自拿出的答案,都会改变世界。

下一页把那份备忘录的第一问算清楚:什么叫「完美的保密」。

第二幕 · 数学完美保密:让密文什么都不说p.14

先给「保密」定一条铁的判据。完美的保密是:破译者拿到密文后,对明文的判断与拿到密文前完全一样——密文什么都不泄露。数学的说法:明文的后验概率等于先验概率。

这判据苛刻到近乎不讲理,可它有解。设明文是一位二进制 M(0 或 1),取一枚均匀的硬币掷出密钥 K(0 或 1),密文是两者相加:C = M + K,逢 2 进掉(异或)。算一遍:

明文 0:密文 0 或 1,各半(硬币说了算)
明文 1:密文 0 或 1,各半(硬币说了算)

两行一模一样。破译者盯住密文:看见 0,明文还是 0 与 1 各半;看见 1,同样各半。密文携带的明文信息恰为零——判据成立。

把长度放开。n 位的明文配 n 位真随机密钥,逐位相加。给定任何一段密文,与它相符的明文恰有 2n 个——每一种都有,且概率均等。这是「一次一密」:密钥真随机、与明文等长、只用一次。

香农的备忘录证明得更狠:完全保密要求密钥的不确定量至少与明文一样多。密钥不足,密文里必有泄露——泄露多少可以精确算出。一次一密不是「很难破」,是「数学上不可破」,而它是唯一的完全保密。

代价同样清楚:密钥与明文一样长,还得安全送达对方。战时用它护送最高层的通话——密钥纸带一次一卷、用完即毁。贵,但值得。便宜点的密码呢?香农给了另一把尺:密文里残留的统计规律,就是它的破绽——第三幕将把「规律」本身变成可计量的东西。

第二幕 · 数学声音可以数出来:采样的账p.15

语音加密的第一步是把连续的声音变成可以运算的东西。声波是一条连续起伏的曲线,每一点的值都有无穷多种可能——不能直接加密。办法:每隔一小段时间取一个值,把曲线变成一列数。

取多密才够?这有一把现成的尺:声音的成分有高有低,一段话音里的高频成分大约到三千多赫就到顶了——高到某个限度,波形再怎么扭,也扭不出更细的褶皱。带宽记作 B(赫),那么每秒取 2B 个样点,就能把整条曲线分毫不差地存下来。这就是采样定理。

算一笔账。电话话音的带宽约 B = 3000 赫,需每秒 2B = 6000 个样点。音乐的高频更丰富,带宽取 20000 赫,需每秒 40000 个样点——后来的唱片工业取每秒 44100 个,多出的四千多个是给滤波器的余量。

定理的来历要摆正:它不是香农首证。奈奎斯特 1928 年已给出关键结果,科捷利尼科夫 1933 年在苏联独立证明。香农的贡献是 1949 年把它放进信息论的框架里:采样的极限、重建的条件与噪声的影响,一次说清。这个定理是「先分成 0 和 1」在声音上的胜仗——连续的曲线,被一列数完全接管。

注意样点还只是数,不是比特。每个样点的取值也有无穷多档,还得再切一刀:把取值分成有限档,每档编一个号——量化。量化有损耗,损耗多少、怎么编,都是可以精确计算的题。声音彻底变成比特之后,加密、传输、存储便全部进入开关的领地。

第二幕 · 数学从噪声里捞轨迹:预测一笔p.16

火控的核心是一道朴素的题。雷达每秒报回几次飞机的方位,每次都带误差。要把炮弹送到飞机「将要」到达的位置——从一串抖动的数据里,预测下一时刻的位置。

最小的做法:假定目标在匀速直线上飞,用最近几笔观测拟合一条直线,再外推一步。手算一遍。取五次等距观测:

时刻 1 2 3 4 5;位置 10.0 12.0 14.0 15.0 17.0(千公里计,示意)

均值:时刻五笔平均得 3,位置五笔平均得 13.6。斜率 = Σ(时刻−均值)(位置−均值) ÷ Σ(时刻−均值)2:

分子 = (−2)(−3.6) + (−1)(−1.6) + 0 + 1×1.4 + 2×3.4 = 17.0
分母 = 4 + 1 + 0 + 1 + 4 = 10  斜率 = 1.7

预测第 6 时刻:13.6 + 1.7 × 3 = 18.7。炮口指向按 18.7 校正。

这门功课有两个方向值得记。其一,观测越多、外推越短,预测越稳——误差的账可以精确列出(最小二乘的方差公式)。其二,目标会机动:匀速假设下预测直线,机动目标则要「打折外推」。维纳在 1942 年的战时报告里给出了系统的答案:在「信号像什么、噪声像什么」都已知的假设下,让平均误差最小的滤波器,存在,且可以造出来。

维纳滤波与香农的工作是同根的两枝:两者都把信号与噪声当成带统计规律的随机过程,都用「已知过去、最优地估计未来」来定义任务。维纳的方向是滤波,香农的方向是编码。两条线在 1948 年前后同时收束——那是下一幕。

第二幕 · 暗线不确定性:用尽与挤掉p.17

第二幕做的两件事,方向相反,用的却是同一种本钱。

保密是把不确定用尽。一次一密把密文的每一位都做成「怎么猜都对、怎么猜都错」——破译者面对的不确定被推到顶格。保密的极限,就是不确定的总量:密钥提供多少不确定,密文就最多藏住多少明文。极限可以写成一个不等式,等号那边是完美保密。

预测是把不确定挤掉。噪声往观测里掺假,滤波从抖动的数据里拎出轨迹——拎出来的那部分,是信号自己固有的规律。挤得掉多少不确定,也有精确的答案:维纳滤波的均方误差公式。能挤掉的是规律,挤不掉的才是真噪声。

一件东西,两副面孔。对破译者,不确定是护城河——多多益善;对炮手,不确定是绊脚石——越少越好。但两边的算盘都是同一套:把「不确定」当成一种可以计量、可以增减、可以买卖的东西。1945 年的备忘录里,这种东西还没有名字;第三幕它将得到自己的名字与单位。

这也是暗线在此处的第二次现身:先分成 0 和 1 的下一步,是给「不确定」记账。记账的单位一旦确定,保密、压缩、纠错三件看似无关的事,会变成同一本账上的三笔收支。

第二幕 · 交汇食堂角落的两次长谈p.18

1943 年的那几次长谈值得单独立一页。图灵以英国战时使节的身份到纽约,顺访贝尔实验室——他在为英国海军密码处工作。香农与他年龄相差四岁,题目不同,脾气相投。食堂的角落里,两人谈机器、谈棋、谈自动机。

谈话内容没有留底,但从两人日后的工作能拼出轮廓。图灵把机器智能的问题摆出来——他的那篇著名论文要到 1950 年才写;香农把「思考的机器」往操作上引——机器要能下棋、能走迷宫。多年后香农回忆:图灵想造的机器让他着迷。一个人带着破译德军密码的底细,一个人带着语音加密的差事,两人谈的却是机器会不会想——战争年代最奢侈的一段闲聊。

两人背后的同一张图纸也值得看清。图灵的密码工作与香农的保密研究,问的是同一个问题的两半:把信息藏住(密码)与把信息传出(通信)。1949 年香农公开保密理论时,明说它与通信理论是姊妹篇——同一套度量,一页写加密,一页写传输。

还有第三位同代人。维纳的《控制论》与香农的通信理论在 1948 年同年出版;两人都从战时的滤波与统计问题出发。维纳的兴趣在「反馈与控制」,香农的兴趣在「信息与编码」——同一场战事,长出两门学科。

下一幕回到香农自己的账本:1948 年,那篇把「信息」变成可计量之物的论文,落笔了。

第二幕 · 小结战争中攒下的三笔账p.19

一、保密有数学极限。完美保密的判据是「密文不泄明文」——后验等于先验。一次一密达到它,且是唯一的。代价:密钥与明文等长、真随机、只用一次。

二、连续可以离散。带宽 B 赫的信号,每秒 2B 个样点即可无损保存。采样定理把声音交给了数——这是香农 1949 年系统陈述、但根基在奈奎斯特与科捷利尼科夫的一条定理。

三、噪声可以挤掉一部分。从抖动的观测外推轨迹,误差的账可以精确列出;维纳滤波给出系统答案。能挤掉的是规律,挤不掉的才是真噪声。

四、同代人的坐标。图灵与香农在食堂角落谈机器,维纳与香农从同一场战事长出两门学科。1940 年代是一张协作网的鼎盛期,下一幕的主角将从中间站起来。

战争结束,密码的成果封存。香农带着三笔账回到明面上的题目:信息,到底怎么量?1948 年,答案落纸——比特,登场。

第三幕 · 故事1948:一篇论文,一个新词p.20

1948 年 7 月与 10 月,贝尔系统的技术期刊分两期刊出一篇论文。标题:《通信的数学理论》。作者:克劳德·香农,三十二岁。没有序言里的客套,开篇一句就立了规矩:通信的根本问题,是在一处精确或近似地复现另一处选定的消息——至于消息是什么意思,与工程无关。

这句「与意思无关」是整篇论文的地基,也是最容易被误解的一句。香农不是不懂意义,他是刻意把意义切出去:让「传得动」与「传的是什么」分开处理。工程的第一步,是把大问题切小。切掉的那一半由韦弗续上——次年,韦弗把两篇论文合成小册子,加了一篇面向外行的导读,从此这门学科有了通行名字:信息论。

论文给消息选了最普遍的形态:一列从有限符号表里取出的符号。可以是电报的通断、声音的样点、文本的字母——只要能列成符号串,就进得了论文的框架。

然后是那个新词。论文需要一个「二进制位」的名字,同事图基提了一个缩写:比特。香农采纳了它。这个词随着论文流遍世界——今天它挂在每一台设备的规格表上,是科学史上传播最快的单位名之一。

论文安静地落地。没有发布会,没有头条——工程期刊的读者先是沉默,几年之内,通信工程师的桌案上人手一份。1949 年起,它被反复重印;半个世纪后,它被列为信息时代的第一份蓝图。下一页看论文的第一笔账:信息怎么量。

第三幕 · 数学信息怎么量:一份不确定的账p.21

「信息量」的直觉定义:一条消息带来的信息,等于它消除了多少不确定。猜硬币是 1 比特,掷骰子大约 2.58 比特——候选项越杂、分布越平,消掉的不确定越多。

香农把这直觉写成一个公式。符号表里各符号出现概率为 p、p……时,每个符号的平均信息量(记作 H)为:

H = −Σ p log2 p

公式里两项都要交代。概率小的事件「出人意料」,取对数后权重大——罕见的事携带更多信息;取 2 为底,答案的单位就是比特。负号把对数的负值翻正。

实算一遍。某信源发四种符号,概率各为 1/2、1/4、1/8、1/8。逐项算:

1/2 × log22 = 0.5 × 1 = 0.5
1/4 × log24 = 0.25 × 2 = 0.5
1/8 × log28 = 0.125 × 3 = 0.375(两项)
H = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 比特/符号

对照两种极端。若四种符号等概(各 1/4),H = 2 比特——分布越平,不确定越大。若某符号概率为 1、其余为 0,H = 0——毫无悬念的信源,不携带任何信息。

这个量为什么值得一个专名?它有温度统计学的血统:热力学里,熵度量的正是「微观状态的不确定」。1948 年论文里它被称为通信理论中的熵。下一页拿它量一样人人都熟的东西:一门语言。

第三幕 · 数学英语有多少比特:冗余是铠甲p.22

拿公式去量字母。若二十六个字母等概率出现,每字母信息量 = log226 ≈ 4.70 比特。但英语显然不等概:字母 e 最常见,q 后面几乎必跟 u——真正的不确定远小于 4.70。

香农 1951 年设计了一个漂亮的实测:让人读一段被遮住部分字母的英文,猜下一个字母。猜对的比例,就是听懂「上下文」后剩余不确定的估计。多次实验的结果:每字母大约 0.6 到 1.3 比特——远低于等概的 4.70。

差额有个名字:冗余度。按 1.3 比特计,冗余度约 1 − 1.3/4.70 ≈ 72%——一门语言里七成以上的容量,花在「可预测」的部分上。

冗余不是浪费,是铠甲。噪声混进一个错字,读的人靠上下文自动纠正——纠正靠的正是可预测的那部分。校对员能读出「这门课很难越」里的错字,因为「越」在此处不可预测、「很」后面的搭配有限。通信工程师读到这里会心一笑:语音里元音拖长的部分、报纸标题里的套话,全是天然的校验位。

但冗余也压得住传输。同一个意思,去掉可预测的部分再传,能省下来的正是压缩的全部空间。压缩的极限在哪?答案现成:熵。把每符号传到 1.3 比特以下,信息就开始丢失;传到熵的水平,信息一毫不丢。这条界线就是下一条定理的内容。

第三幕 · 数学两条定理:压到熵,传到容量p.23

1948 年论文里立着两根柱子。第一根管发信端:无噪声的线路,每符号平均至少要传多少?答案:不少于熵 H;而用足够巧妙的分组编码,可以无限逼近 H——既压不破熵,也总能压到熵附近。

用 p.21 的信源演示。四符号概率 1/2、1/4、1/8、1/8,熵 1.75 比特。给它们编码:最可能的给最短的码:

甲(1/2)→ 0  乙(1/4)→ 10  丙(1/8)→ 110  丁(1/8)→ 111

平均码长 = 0.5×1 + 0.25×2 + 0.125×3 + 0.125×3 = 1.75 比特——与熵分毫不差。这个码还有一条好性质:任意一串码字首尾相接,接收端都能唯一切分(没有哪个码字是另一个的开头)。短码配高概率,账全在概率里。

第二根柱子管线路:带宽 B、信噪比 S/N 的信道,容量为 C = B log2(1 + S/N)。这是线路的定价:速率低于 C,配合足够巧妙的编码,错误可以做到任意小;速率高于 C,任何编码都救不了——错误率必然抬头。

实算一条老线路。电话话音带宽 3000 赫、信噪比 30 分贝(即 1000 倍):

C = 3000 × log2(1001) ≈ 3000 × 9.967 ≈ 29 900 比特/秒

约每秒三万比特。年代久远的拨号上网顶速与这个数字惊人地接近——公式是 1948 年写下的,线路换了好几代,天花板纹丝不动。

两根柱子合成一句话:压缩到熵,传输到容量。剩下的唯一敌人是噪声——第四幕,正面进攻。

第三幕 · 暗线信息=消减的不确定p.24

暗线在此页立起它的正身:信息=消减的不确定。这一句不是修辞,是定义:收信之前,符号表悬在概率里;消息一到,概率收拢成一个事实。收拢了多少,就是传了多少——公式里的每一项都在记这笔账。

回看三幕,全部是这一句的变形。开关代数:把「通不通」的不确定压成 0 和 1;保密:把破译者的不确定顶到上限;预测:把观测里的不确定挤到下限;熵:不确定的计量;编码:不确定的搬运与折叠。

而「与意思无关」也要在此处重读一遍。香农切掉意义,不是粗疏,是把度量立起来的唯一办法:意义因人而异,不确定可以公算。一门学科能不能成为科学,先看它的量有没有公认的单位。信息论的全部成功,始于这一刀切得狠。

切出去的部分并不消失。语义、价值、理解——它们还在门外等着。香农晚年被人问起时说过大意如此的话:意思的问题更难,先让工程把能算的算清楚。门外的问题到今天也没有公认的度量——这是 p.43 里的悬题之一。

第三幕 · 交汇同年同月:两门学科一起落地p.25

把 1948 年摆进它的年代。同年,维纳的《控制论》出版。两本书从同一场战事出发——滤波、预测、统计——长成两门学科:维纳问「机器怎样自我调节」,香农问「信息怎样计量与搬运」。术语上还有一个耐人寻味的巧合:两人用了同一个「熵」,定义只差一个常数。

合流的脚步很快。1949 年,韦弗的导读把信息论介绍给外行;同年香农的保密理论与采样定理先后刊出。整个 1950 年代,信息论被各个领域争相借用——语言学、心理学、生物学,一时风头无两;也因滥用而一度遇冷。冷静下来之后,它在自己的本行——通信工程——里扎下了根。

借用最成功的地方之一,是计算机科学。1948 年的比特成了存储与传输的通用货币;图灵 1950 年的模仿游戏与香农 1950 年的机器下棋,同一年面世,两人在 1943 年的食堂里已经对过表。第三位同代人冯·诺依曼,则在存储程序计算机的架构报告(1945)里为程序与数据统一编址——三件工作在十年内合流成计算机的全幅图景。

一门学科落地时的样子,值得记一笔:香农 1948 年没有做报告、没有立项,论文是在本职工作之外写成的。后来他常说,做研究最难的是把问题问到点子上——问题问对了,答案往往不远。这句话,是本册全册的注脚。

第三幕 · 小结一门学科的三件家当p.26

一、度量立起来了。熵 H = −Σp log2p:不确定的计量,单位比特。罕见的事信息多,注定的事信息为零。

二、语言被量了一遍。等概字母 4.70 比特,实测英语约 0.6—1.3 比特——七成冗余是铠甲,也是压缩的空间。

三、两条定理立柱。压缩的极限是熵(四符号信源 1.75 比特的编码分毫不差地到达);传输的极限是容量 C = B log2(1+S/N)(3000 赫、30 分贝的老线路约每秒三万比特)。极限都是可以算出的数,不是感觉。

四、「与意思无关」的一刀。把语义切出去,度量才立得住。切出去的问题没有消失——它们在门外排队,排到了今天。

下一幕处理论文里最惊人的那部分:噪声在线路里兴风作浪,香农却证明它拦不死通信——只要传得比容量慢,错误可以压到任意小。这道定理起初没人相信,因为它听起来太便宜。

第四幕 · 故事一道「太便宜」的定理p.27

1948 年论文的第 11 节,藏着全书最惊人的一句话。有噪信道编码定理:只要传输速率低于信道容量,就存在一种编码方式,使错误概率任意小——哪怕线路噪声大得离谱。

这句话在当年听来近乎荒唐。常识是:噪声进来,错误必进来,只能靠提高功率、反复重发、认命。香农却说:不必大声,不必重发——把消息「编」得足够巧妙,噪声就掏不动它。错误不但可以减少,还可以压到任意接近零,而速率只受容量一个数管。

证明的风格更加离经叛道。香农不给出任何具体的码。他证明的是:把所有可能的编码方式放在一起平均,平均错误率低于某个数——那么至少有一种码不差于平均。码长足够时,平均错误率趋于零。这种「平均即存在」的论证,数学上无懈可击,工程上却让同行抓耳挠腮:定理说好码存在,不递给它一张设计图。

于是 1950 年代的处境是:定理在纸上成立,工程师手里没有好码。信奉的与能造的之间隔着几十年。这条鸿沟要靠一整门新学科去填——编码理论,它从此以「逼近香农极限」为终身目标。

回到贝尔实验室,当时已有人开始填沟。同实验室的哈明被一道现实难住:机器周末两天无人值守,读到的错误码只能停机——他想造「机器自己能纠错」的码。下一页先做一道最小的纠错题,再看哈明的答案。

第四幕 · 数学最笨的纠错码:说三遍p.28

最笨的纠错办法:每位说三遍。发 1 就发 111,发 0 就发 000;收端按多数表决——三个里两个以上是 1 就记 1。

设每位被噪声翻转的概率为 p。表决出错,当且仅当三位里至少两位被翻转。按二项分布:

出错概率 = C(3,2)p2(1−p) + p3 = 3p2 − 2p3

代入数字:

p = 0.1:3×0.01×0.9 + 0.001 = 0.027 + 0.001 = 0.028
p = 0.01:3×0.0001×0.99 + 0.000001 ≈ 0.000298

十分之一的错误率压到 2.8%;百分之一的错误率压到万分之三——压掉约 33 倍。

代价写在明处:速率只剩三分之一。想更稳,就再说五遍、七遍——错误率一路下探(五连码在 p = 1/6 时约 3.5%,见 p.45 的动手题),速率也一路掉。所以重复码不是好码,它是定理精神的教科书演示:错误可以交易,筹码是速率。

但定理许诺的远比这好:存在这样的码——速率接近容量、错误又任意小。重复码离两个目标都差得远:它保住了可靠性,牺牲了全部速率。好码必须在「又不重、又快、又准」的刀刃上走——这正是哈明面对的问题。

先把交易的地图画全。横轴速率、纵轴错误率;定理给出一条不可逾越的边界:容量。边界之下,任意小的错误皆可达;边界之上,任何技巧皆败。此后七十年编码学的全部工作,就是从左上角的重复码出发,一寸一寸向边界逼近。

第四幕 · 数学定理为什么对:把码拉长p.29

存在性证明的直觉可以一句话说清:把码字拉得足够长,噪声就认不出谁是谁。

细说。把消息分成 k 位一组,用长 n 的码字(n > k)发送。所有长 n 的串共有 2n 个,有用的码字只取 2k 个。噪声把发出的码字搅动——小概率的错误只挪动少数几位,收到的串落在原码字附近。码字若彼此离得远,附近的「错串」就不会撞到别的码字头上。

关键在数量对比。当 k/n 低于容量对应的比值,随机选出的码字之间的距离,随 n 增大而拉开得比噪声的典型破坏半径更快——碰撞的概率随码长指数衰减。香农算出的正是这个衰减的账:只要速率在容量以内,码长足够时,平均错误率可以低于任何指定的数。

两条定理合在一起,全幅地图就完整了。

发信端:压到熵——信息的最少比特数有下界,可达
信道上:传到容量——无错速率有上界,可达
合起来:任何信源、任何信道,两头都有精确的价

这套「存在性」的语言还有一个重要的克制。定理不说「随便编都行」,也不给出码;它说的是「好码存在」。找到好码、让译码跑得动,是工程接下来七十年(详见 p.32)的活。理论定界,工程填图——分工清清楚楚。

第四幕 · 数学哈明码:机器自己纠错的第一批码p.30

哈明的思路:给数据附上几位校验位,让每一位数据同时被几条校验「盯着」——出错时,报错的组合直接指出错误的位置。

造一个最小的。七位码:位置 1 至 7。数据占 4 位(放在 3、5、6、7 位),校验占 3 位(放在 1、2、4 位)。三条校验规则:第 1 位使位置 1、3、5、7 里的 1 成偶数个;第 2 位管 2、3、6、7;第 4 位管 4、5、6、7。发数据 1011:

第 1 位 = 1⊕0⊕1 = 0  第 2 位 = 1⊕1⊕1 = 1  第 4 位 = 0⊕1⊕1 = 0
码字:0 1 1 0 0 1 1(位置 1 至 7)

现在让噪声咬一口:第 5 位被翻转,收到 0 1 1 0 1 1 1。收端把三条校验重新各算一遍:

验 1:0⊕1⊕1⊕1 = 1(不平) 验 2:1⊕1⊕1⊕1 = 0(平) 验 4:0⊕1⊕1⊕1 = 1(不平)
报错组合(第 4、2、1 位读成二进制):101 = 5 → 第 5 位是坏位

把第 5 位翻转回去,数据 1011 完璧归赵——单错全纠。三条校验为何有此神通?位置 1 至 7 写成二进制恰好是 001 到 111 三位数:每一位数据至少被两位校验覆盖,坏位的位置号被校验结果直接「读」出来。这不是巧合,是编号系统设计的巧劲。

算速率:4 位数据付 3 位校验,速率 4/7 ≈ 0.57——比重复码的 1/3 高出一大截,还能纠错。1950 年哈明论文发表后,交换机与计算机的存储系统最先装上这批码。好码的世代从此开场。

第四幕 · 暗线噪声被定价p.31

第四幕的账全部记在同一本册子上:不确定的收支。

噪声是支出:每一位都可能被翻转,错误率是噪声开出的价。校验位是保费:多付几位,换错误率的下探。容量是预算上限:保费交得再多,也买不回超出容量的速率。哈明码是一张划算的保单:4/7 的速率,换单错全纠。

回头看,第二幕的保密与这一幕的纠错是镜像。保密要给破译者制造不确定——不确定是资产;纠错要替通信消灭不确定——不确定是负债。同一枚硬币,在密码学的账本上记收入,在通信的账本上记支出。两本账的计量单位,都是比特。

暗线至此走完它的全程:先分成 0 和 1(第一幕)、给不确定记账(第二、三幕)、按账本做交易(第四幕)。通信从此不再是一门手艺,而是一套有单价、有预算、有底线经济学。第五幕看看这个把一切算得清清楚楚的人,怎样度过他后半生的日子。

第四幕 · 交汇逼近极限的七十年p.32

定理说好码存在,找码的路走了七十年,分几代。

第一代:代数码。哈明码(1950)开篇;里德–所罗门码(1960)把纠错能力推上一大步——它护送过旅行者号深空探测器的照片,也守着每一张激光唱片的坑点,代价是离香农极限仍有一段距离。

第二代:迭代码。低密度奇偶校验码其实是 1962 年的老想法,沉睡三十年后被重新发现(1990 年代);涡轮码 1993 年横空出世。两类码用「反复迭代译码」逼近极限,距香农极限只剩零点几分贝——定理许诺的边界,第一次被摸到。

第三代:极化码。2009 年提出,第一个被严格证明能达到任意二进制对称信道容量的码类;2016 年被定为第五代移动通信控制信道的编码方案之一——从纸上的存在性证明到千万部手机,隔了六十七年。

压缩一侧的接力同样清晰:哈夫曼编码(1952)把「短码配高概率」做成了通用算法;算术编码再进一步;字典式编码(1977—1978)不依赖概率模型,成了通用压缩格式的祖源——今天压缩包的扩展名里,就躺着那两篇论文的年份。

一句话收拢:香农给出的是地图的边界;七十年编码史是把海岸线画准的过程。每一次「逼近极限」,都在兑现 1948 年那笔纸上的账。

第四幕 · 小结噪声拦不死通信p.33

一、定理管着两头。速率低于容量,错误任意小;速率高于容量,必错无疑。1948 年之前,通信是手艺;1948 年之后,通信是有单价与预算的生意。

二、证明是存在性的。随机码平均论证,不递设计图。理论定界、工程填图——这七十年分工的清白账本。

三、笨码先行。重复码三倍冗余压错三倍价(0.1 → 0.028);哈明码 4/7 速率单错全纠。好码的谱系由此起跑,终点是极化码摸到的容量线。

四、两本账一本记。保密记不确定的收入,纠错记不确定的支出,单位同为比特。香农把两门学问接在同一根桩上。

下一幕回到本册最松弛的段落:下棋的程序、走迷宫的机器鼠、赌桌上的比例公式——一个把不确定性算到极致的人,后半生玩出了哪些名堂,又被历史怎样记取。

第五幕 · 故事会玩的头脑p.34

1956 年起,香农逐步离开贝尔实验室,转往麻省理工学院任教,1958 年成为教授。此时的他已不需要证明什么——需要的是一间能装下奇思妙想的实验室。学校给了他一间:里面后来堆着杂耍机器人、下棋机器、独轮车和一大柜子藏品。

1950 年他造过一只出名的机器鼠:一只小车上装着磁铁与继电器,放进一座迷宫。第一次它笨拙地到处碰壁;第二次放进同一座迷宫,它径直走到终点——「学会」了。这只机器鼠巡展多年,是「机器能学习」最早的实物演示之一。

他还会杂耍,且把杂耍做成了学问:自己练,造抛球机,再造一个真会抛球的机器人——鼓、机械臂与球循环往复。他骑独轮车穿过实验室走廊,据说最难的是边骑边抛球。同事眼里这位老先生不太体面;学术史回望,这些都是把随机与控制玩到极限的实验。

他还认真下过功夫在赌桌上与市场上。同实验室的凯利在 1956 年发表了一个公式:有胜算的赌局,每次押多少比例最稳。香农把公式用到个人投资上,几十年下来的复利成绩远超市场平均——这份业余成绩单,近年才随史料整理为外人所知。

1990 年代起,阿尔茨海默病逐渐带走他的记忆。写过「不确定」的人,被病痛一点点抹去确定的部分;2001 年 2 月 24 日,他在马萨诸塞州逝世,八十四岁。身后的事记在 p.38—p.39;本幕先看他晚年留下的两笔正经账:机器下棋与信息的去向。

第五幕 · 数学让机器下棋:剪一棵大得吓人的树p.35

1950 年,香农发表〈为计算机编程下棋〉——这门学科的第一篇系统论文。问题先算账:国际象棋平均每步约 35 种走法。往深看两层,352 = 1225;三层 353 ≈ 42 875;一部典型的对局双方各走 40 步——全谱局面数约 10120。宇宙里的原子不过 1080 量级。

结论写在最前面:树太高,硬算必死,必须剪枝。他的方案两件套:

其一,搜索有限层:只往深处看几步,再深就止步
其二,评估函数:给止步处的棋盘打一个分——子力、机动、王的安全,加权求和

极小极大规则把两层粘起来:己方走法取分最高的一支,对方的应手取分最低的一支——交替向上推。手算一个两层小例:叶子四个分数 3、5、−2、4;下层是对方走,取每两片的最小值:min(3,5) = 3,min(−2,4) = −2;上层己方走,取最大:max(3,−2) = 3。故选第一支。

评估函数给一个最小的例子。只计子力(兵 1、马或象 3、车 5、后 9),棋盘甲合计多一马、少一兵:3 − 1 = 2;棋盘乙多两兵:2。分同,再比机动——「数字把棋盘折成一个数,比较就有了轴」。

这套「搜索+评估」的骨架七十年未换,越走越深。1997 年,机器在国际象棋上胜过世界冠军——骨架仍是 1950 年的;差别只在搜索的深度与评估的精细。香农在论文结尾写下的克制保留至今:机器赢棋靠的是穷举的深度,人赢棋靠的是「看见」——两者的差别,也许才是真正有趣的问题。

第五幕 · 数学押多少:凯利公式的账p.36

1956 年,贝尔实验室的物理学家凯利把香农的信息论读出了一个意外用途。一道题:一个胜率占优的赌局,每次押上全部身家的几成,长期增长最快、又绝不破产?

最简单的一档算清。胜率 p = 0.6,输则输掉注额、赢则赢回同额(赔率 1 比 1)。每次押注比例 f,赢则本钱乘 (1+f),输则乘 (1−f)。长期看,本钱的增长速率(每局平均的比特数,香农式的账)为:

g(f) = p log2(1+f) + (1−p) log2(1−f)

对 f 求极值(求导取零),得最优比例:f* = p − (1−p) = 2p − 1 = 0.2。胜率六成,就押两成。代回验算增长速率:

g = 0.6 × log21.2 + 0.4 × log20.8 ≈ 0.6 × 0.263 − 0.4 × 0.322 ≈ 0.029 比特/局

三个极端对照出公式的脾气。全押(f = 1):一次输局就归零,长期速率 = 负无穷——数学上禁止。押太多(f = 0.5):单局常赢,长期速率仍低于 0.2 的最优值——过度自信是有价格的。押太少:稳是稳,白耗胜算。最优比例恰好让「赢的复利」与「输的回撤」打平手筋。

这套账的谱系值得点明:增长速率的表达式与香农的熵公式同一形状——赌局就是一条信道,优势就是信息。凯利在论文里明说:香农的工作是出发点。从贝尔实验室到量化投资,这条线今天仍在运行。

第五幕 · 数学比特的世界:一张清单p.37

1948 年的两条定理(压缩到熵、传到容量)在此后几十年里逐一兑现。点几处最贴近日常的。

声音的数字化。激光唱片每声道每秒取 44100 个样点、每样点 16 比特,双声道合计 44100 × 16 × 2 = 1 411 200 比特/秒,约 1.41 兆——「先分成 0 和 1」在音乐上的落地。声音文件能压缩,因为音乐也有熵、也有冗余。

传输的极限。拨号线路的天花板、光纤的每秒太比特、深空探测器的每秒几十比特——工程各不相同,天花板都由同一条公式给出:带宽与信噪比。旅行者号在一百多亿公里外发回照片,靠的正是把每一比特都编进逼近容量的码里。

纠错无处不在。扫描枪扫过的每一枚方码、手机收发的每一帧数据、存储盘里的每一段文件,背后都有校验位在值班。方码四角留存的部分即使污损也能读出——那是里德–所罗门式的后裔在兜底。

生命也在记账。遗传分子用四个字母写成长串——每字母的信息量是 log24 = 2 比特;一串基因能压缩多少、突变相当于多大的噪声,都是信息论的题。神经编码、生态信号、语言的度量,同一套账本。

清单点到即止。这些应用没有一件是香农亲手做的;但每一件的可行性证明,都写在 1948 年那篇论文里。理论家的胜利方式:他不造任何东西,此后的一切却都绕不开他。

第五幕 · 暗线把一切算得清的人,失了忆p.38

暗线走到最后一幕,有一处不得不停:一个把「不确定」计量了一生的人,晚年失去了记忆。

1990 年代起,阿尔茨海默病慢慢收走他的往昔。同事探望,他还认得人,还能下几步棋;谈话越来越短。2001 年 2 月,他在马萨诸塞州逝世,八十四岁。命运的注脚写得太工整,工整到不该多评一个字。

但暗线在这一幕要说的是一个平静的事实:比特的世界不依赖任何人记得。1948 年写下的两条定理,不需要作者的在场——压缩器照旧运行,纠错码照旧值班,容量公式照旧给每一条新线路定价。「写下来」自带邮资,这句话在图灵册说过一遍,在这里再说一遍:一个可检验的结构不欠任何人的时间。

还有一层,只有这一幕能说。香农一生都在把「不确定」变小:信息是消减的不确定,保密是封顶的不确定,编码是打包的不确定。可他晚年最着迷的,是那些故意不化简的东西——杂耍的节奏、赌局的分寸、机器鼠碰壁的样子。也许他比谁都清楚:被算清的不确定之所以值得算,正因为世上还留着算不清的那部分。留白不是工程做不完,是承认工程之外还有东西。

第五幕 · 交汇身后:一门学科为他记名p.39

生前荣誉按年份排。1966 年,美国的国家科学奖章与电机电子工程师学会的最高荣誉奖章同年落到他头上;1985 年,日本的京都奖(基础科学)授予他——授奖词称他「为信息时代奠定理论基础」。

学科内的记名更家常也更长久。信息论学会的年度最高讲座以他为名——香农讲座自 1972 年起年年开讲;学会的最高奖后来也称香农奖。任何一位做编码的人,职业生涯里最重要的几页纸上都会出现他的定理与他的界。

身后十年,史料陆续整理。1993 年,两卷本文集出版——战时的保密工作、火控报告与那些杂耍论文第一次汇齐。2000 年前后,通信工程界惯例性称 1948 年论文为「信息时代的大宪章」;教科书把它排在第一章的第一节。

纪念之外,最持久的纪念是结构性的:今天每一次扫码、通话、下载与存盘,都在不知情地执行 1948 年的作业。比特这个单位活在每张规格表上——它不属于某家公司,属于所有人。一个单位的命名权被历史如此彻底地兑现,科学史上罕见。

本册以一个对照收束第四幕与第五幕:图灵问机器能不能想,答案悬着;香农问信息怎么量,答案当年就落了地。两问一起在 1943 年的食堂角落谈过——悬着的与落地的,都是那个年代的遗产。

第五幕 · 小结五幕归拢:把不确定算清楚p.40

一、会玩是认真的另一种写法。机器鼠学迷宫,杂耍机器人守节拍,凯利公式管赌注——晚年每一件玩具底下,都埋着同一套关于不确定与增长的数学。

二、下棋给出了骨架。搜索有限层、评估打分、极小极大上推——1950 年的两件套用到今天,赢家换了几代,图纸没换。

三、比例是数学给的。胜率六成押两成,全押必归零,过度自信有价。熵的公式直接搬到赌桌与市场——信息与增长是同一本账。

四、比特的世界不欠谁的时间。两条定理的工程后代遍布日常,作者被病痛收走记忆之后,结构照旧运行——写下来的东西自带邮资。

全册说完。半英里铁丝网上那一串约定好的铃声,长成了今天每一台设备的规格表上的一个词:比特。通信的本质是不确定——把不确定算清楚,就是把世界传得更远一点。

收束回望:八十五年p.41

把一生的节点排成一行。

1916 生于密歇根州佩托斯基,4 月 30 日;长于盖洛德镇
1936 密歇根大学双学位(电机工程、数学)
1937 麻省理工硕士论文〈继电器与开关电路的符号分析〉
1938 论文刊出;电路设计从此有了代数
1940 麻省理工博士(理论遗传学代数);普林斯顿高等研究院一年
1941 入贝尔实验室;战时火控与语音加密
1943 与图灵在职工食堂多次长谈
1945 密码数学密件成文(1957 年解密)
1948 〈通信的数学理论〉两期刊出;「比特」一词随论文问世
1949 保密系统与采样定理两篇刊出;韦弗合集出版
1950 机器鼠走迷宫;〈为计算机编程下棋〉
1951 〈印刷英语的预测与熵〉
1956—58 逐步转往麻省理工学院任教
1966 国家科学奖章;电机电子工程师学会荣誉奖章
1985 京都奖
2001 2 月 24 日逝世于马萨诸塞州梅德福

十六行之外,补四行身后:

1972 信息论学会设香农讲座  1993 两卷本文集出版
2009 极化码达容量(定理落地) 2016 其码入第五代移动通信规范

寿数八十五年。生前十六个节点,一半在两间实验室里;身后二十年,他的两条定理在每一部手机里照常上班。

收束三种读法:这门代数、这两条定理、这个人p.42

小读者的读法:一台开关。记住那枚拨杆就够——通与断,0 和 1。玩两遍 p.44 的编码游戏,玩一遍 p.45 的表决实验,能亲眼看见「把话约成记号」的力量,也亲眼看见「说三遍」怎样把错误压下去。

中学生的读法:两条定理。抓两笔账:熵的实算(p.21—p.23 的 1.75 比特编码)与重复码的实算(p.28 的 0.1 压到 0.028)。它们只用对数与二项计数,不仰仗任何高等工具;各自亲手推一遍,胜过读十篇介绍。

成年读者的读法:一个人。一个把「不确定」计量了一生的人:给了通信定价,给了保密判据,给了压缩极限;晚年把这些本钱都换成了玩具与实验。他的定理今天仍在运行,他的切分(工程与意义)仍是值得争论的起点。

三层可以叠读。开关是底,定理是墙,人是把两者都玩过一遍的人。任何一层读顺了,另外两层会自己跟上来。

收束三个未完的问题p.43

一、好码与译码的代价。极化码已经摸到容量(p.32),但译码的时延与复杂度仍是大问题:一条千亿比特的链路上,理论极限与实时运行之间还隔着工程。逼近极限的下一寸,要看译码器的算力账。

二、语义怎么量。香农在 1948 年把意义切了出去(p.24)——切得果断,留下的空白也大:一条消息的「价值」、一段话的「要旨」,至今没有公认的度量。机器处理语言的年代,这道门外的题重新排到了队首。

三、生命的信息账。基因是四个字母的文本,神经是带噪声的信道——把信息论用到生命上,话说了一代又一代,公算的账仍然零零星星。生命的熵、生命信道的容量,是本领域最诱人也最难下笔的几页。

三个问题共享一个出身:都诞生于「把不确定计量」之后——先有明确的框架,才有可讨论的悬而未决。香农留问题的方式与解题如出一辙:把题目切到任何人都能接手的程度。

动手做亲手编一串码p.44

器材:纸条一条、铅笔。要编的码是 p.23 的那一套——短码配高概率:

甲(1/2)→ 0  乙(1/4)→ 10  丙(1/8)→ 110  丁(1/8)→ 111

任务一:编码一段消息「甲乙丁甲」,数总长。逐个写出:0、10、111、0,连成 0101110,共 7 比特。若按「每符号固定 2 比特」的老办法要 8 比特——省下 1 比特。再把这一串亲手译回去:0|10|111|0,逐位往前读,先到先切——只有一种切法,消息原样出来。这就是「异前缀」的便利:不加分隔符也不怕歧义。

任务二:等概的信源压不动。四个符号各 1/4 概率时,熵是 log24 = 2 比特。给它们编等长码 00、01、10、11——平均码长恰 2,一分也压不动。结论亲手验证:压缩的空间全部来自概率的不均匀;符号越「有偏」,省得越多。这正对应 p.22 的英语:等概是 4.70,实际约 1.3——中间的差全是可省的冗余。

任务三(挑战):八个符号等概。熵是 log28 = 3 比特,编三位码 000 到 111。验证:任何一串 0/1 都有唯一的切法,每符号恰 3 比特——此时码已顶到熵,绝无再压的余地。把三道题的结果连成一句话:码长的下界由概率决定,短码配高概率就是全部诀窍。

做完三题,无损压缩的全部原理就体验完了:概率、分组、短码。今天每一份压缩文件的祖先,就是这张纸上这三道题。

动手做亲手纠一次错p.45

器材:一枚骰子、纸笔。约定:掷出 1 点,表示「这一位被噪声翻转」——单位出错率 p = 1/6 ≈ 0.167。

任务一:跑一个三连码。任取一段 0/1(或让同伴随机报八位),每位连发三遍;发每位之前掷一次骰子,掷出 1 就把发出去的三位里随机一位翻转。收端按多数表决。对照:单发错误率 1/6;三连表决的理论错误率 3p2−2p3 = 3×(1/36)×(5/6) − 2×(1/216) = 15/216 − 2/216 = 13/216 ≈ 0.060。跑八位,出错次数通常在零与一之间——少跑几轮看不出优势,多跑几十轮才见统计的分量。

任务二:算五连码,比速率。每位发五遍、多数表决:出错概率 = C(5,3)p3(1−p)2 + C(5,4)p4(1−p) + p5 = 10×(1/216)×(25/36) + 5×(1/1296)×(5/6) + 1/7776 = 276/7776 ≈ 0.036。速率只剩 1/5——比三连码的 1/3 更稳,也更慢。「稳与快不可兼得」在这两个数里看得见;好码的任务正是同时改善两者。

任务三(挑战):哈明码跑一遍。取 p.30 的码字 0110011,请同伴瞒着翻转其中任何一位。收端按三条校验重算,报错组合读成二进制即是坏位的位置——一次翻转,一步定位,数据完璧。做完对照:哈明码速率 4/7,比五连码快一倍还多,同样纠单错。

跑完三题,纠错的全貌就体验完了:冗余买可靠,设计省冗余。理论(香农的界)画天花板,工程(哈明的码)搭楼梯——两层缺一不可。

小典术语十条p.46

开关代数 通断记 1 与 0、串联乘并联加的代数;电路设计的语言(p.7)。

综合 由真值表反解出代数式与线路的设计程序;与「分析」互逆(p.8)。

一次一密 密钥真随机、与明文等长、只用一次的密码;完全保密(p.14)。

采样定理 带宽 B 赫的信号每秒 2B 个样点即可无损重建(p.15)。

熵 不确定的平均计量 H = −Σp log2p,单位比特(p.21)。

冗余度 等概信息量与实际信息量之差所占的比例;抗噪的铠甲(p.22)。

信道容量 无错传输的速率上限 C = B log2(1+S/N)(p.23)。

香农–法诺编码 按概率对分递归赋码;短码配高概率(p.23、p.44)。

信道编码定理 速率低于容量即可使错误任意小的存在性定理(p.27、p.29)。

哈明码 校验位覆盖定位的纠错码;(7,4)码单错全纠,速率 4/7(p.30)。

小典人物十位p.47

莱布尼茨(1646—1716) 梦想「把推理变成计算」的先声;三棒接力的第一棒(p.11)。

布尔(1815—1864) 把逻辑写成代数的数学家;那门代数以他命名(p.6、p.11)。

布什(1890—1974) 微分分析仪的主持者、香农硕士论文的导师;战时科技总调度(p.4、p.6)。

哈特利(1885—1959) 1928 年先给信息量立尺的贝尔实验室工程师;容量公式里留了他的名字(p.23)。

奈奎斯特(1889—1976) 1928 年采样关键结果的第一作者(p.15)。

科捷利尼科夫(1908—2005) 1933 年在苏联独立证明采样定理(p.15)。

图灵(1912—1954) 1943 年与香农长谈的同代人;破译密码、追问机器(p.13、p.18)。

维纳(1894—1964) 滤波预测与《控制论》的作者;与香农同源而不同向(p.13、p.16、p.25)。

哈明(1915—1998) 第一批纠错码的作者;「机器自己纠错」的工程师(p.27、p.30)。

凯利(1923—1965) 把信息论读进赌局的物理学家;最优押注比例以他命名(p.36)。

延伸信息论后来长成了什么p.48

1948 年那篇论文之后,信息论沿三个方向生长。

其一,编码的家谱。哈明(1950)→ 里德–所罗门(1960)→ 低密度奇偶校验与涡轮(1990 年代)→ 极化(2009)。从代数构造到迭代译码,终点是香农极限本身——「逼近容量」成了整门学科半个多世纪的进度条。

其二,有损的一翼。声音与图像不必一丝不差地传——差多少算「听不出、看不出」?率失真理论给出答案:在允许失真的前提下,压缩的下界仍然由熵的推广量决定。音乐与影像文件的每一段格式,都站在这条线上。

其三,计量的哲学边界。「一段序列的复杂度,是能生成它的最短程序的长度」——这个与香农熵互补的度量(柯尔莫哥洛夫复杂度)把「随机」定义得干脆:不可压缩即随机。它与香农的熵在长序列上重合,在单件对象上各有天地——计量的地盘扩到了意义的门前。

一句话收拢:香农给出的是一张边界地图:哪里压不动(熵),哪里传不过(容量),哪里必有错(超容量)。后世的全部工作,是把地图填成产业。

延伸数字时代的接力p.49

从 1948 到今天,三个阶段可辨。

第一阶段:理论定型(1950—1970)。哈明的码进了交换机与存储器;采样与量化把电话、录音逐段数字化;容量公式成了线路设计的通用的尺。理论先行、工程缓步——两定理悬在头顶像两颗北极星。

第二阶段:极限可及(1970—2000)。光纤把带宽做大,移动通信把噪声做小,迭代译码把错误压到极限附近;压缩格式把音乐、图像、文件逐段瘦身。1948 年的两条定理第一次从「存在」变成「在手」。

第三阶段:无处不在(2000 年至今)。扫码、导航、流媒体、移动宽带、深空通信、基因测序的存储与比对——每一条链路的可行性证明都写在 1948 年。连语言模型训练用的「词元」,也仍然是比特的近亲:先切成离散符号,再交给统计。

同时要带着香农自己的分寸读这三阶段。他划下的界线没有移动:工程能算的是不确定,工程不算的是意义。机器越能干,这条界线越值得记着——它当年是清醒,如今是路标。

家长导读怎样陪孩子读这一册p.50

本册的三层各有入口。小学低年级:只读故事页,配 p.44 的编码游戏——一张纸条一支铅笔就能玩,「短码给常用字」的玩法孩子一学就会,顺便把「为什么手机打字常用字排在前面」讲通。

小学高年级到初中:加读 p.21 与 p.28 的实算。熵的算例只用到对数换底的一小步,家长可以陪孩子把 1.75 这笔账逐项列出来;p.45 的掷骰表决是全家能玩的概率游戏——掷得越多,理论数字越显形,统计的味道自己就出来了。

高中及以上:全册可读。p.23 的两条定理、p.29 的存在性直觉、p.30 的哈明码,是大学通信课程第一周的完整预告;注疏层的文献路径(p.2 注起)可供检索。

三处提示给家长。其一,p.34 的晚年病痛,孩子若问起,如实讲即可——一位被病痛收走记忆的人,留下的结构至今在运行,这本身就是诚实教育的一课。其二,p.24 的「与意思无关」容易被听成「信息论冷血」,请把 p.43 的语义悬题一并讲掉:切出去不是不管,是先管能管的。其三,p.45 的表决游戏可以换成硬币与杯子的实体版:全家轮流当「噪声」,比屏幕更有体感。

读完这一册,值得留下一句话给孩子:把说不清的东西先分成两半,再给每一半记账——香农一生用的就是这一种本事。

家长导读五个常见误区p.51

一、「比特是机器里的电平。」比特是信息的单位,不是任何实物——纸上的一串符号、一个开关的位置、一段基因的字母,都可以论比特(p.21)。

二、「信息论能量出一段话的意思。」它量的是不确定的消减,不量价值与含义——香农在论文第一段就把语义切了出去(p.24)。

三、「采样定理说采样越多越好。」它说的是恰好够的下限:每秒 2B 个即可无损;少于它必失真,多于它是浪费(p.15)。

四、「重复码是好码。」它只是最笨的纠错码——速率掉到三分之一才纠单错。好码(哈明起家,极化收官)能在速率不降的同时逼近极限(p.28、p.30、p.32)。

五、「一次一密是『几乎破不了』的密码。」它在数学上不可破——前提是密钥真随机、等长、只用一次;三个条件缺一,安全等级立刻跌回普通密码(p.14)。

五条误区有一致的解药:把「谁说的」换回「在哪一页、依据什么」。这本册子每一处重要断言都留了页码与文献——这正是计量这门学问自己立身的规矩。

版权与编目版权页p.52

《数学家的故事》第四辑 第 40 册
香农 · 比特与通信

体例:五幕 · 52 页 · 三层可读(故事/数学/注疏)
插画:40 幅(留白线体)
数值:全册关键数值实算复核

本册为「格物致知」系列数学通识读物之一,面向全龄读者。
故事层无需预备知识;数学层对应高中至大学初年级;注疏层供检索与延伸。

格式 · 格物致知 · JUST FOR FUN