第二季 · 第 47 章

一个错误也不能放过

《算法的故事》第二季 · 第四篇：穿越噪声的信息——理查德·汉明、贝尔实验室与让计算机自行纠错的数学革命

1947年，美国纽约。星期一早晨，一位数学家来到计算机旁，准备领取自己的计算结果。这些计算不是几分钟就能完成的工作。它们被安排在整个周末进行。星期五傍晚，研究人员将一批计算任务装入设备。机器将在星期五夜里、星期六、星期日，以及星期日夜里，尽可能持续工作。到了星期一早晨，研究者就可以取回答案。这名数学家已经习惯了这样的工作方式。因为当时大型计算设备十分稀缺。机器远不像今天的个人电脑那样，可以随时为每个人提供充足的算力。因此，漫长的周末反而是一段宝贵的计算时间。但是，那天早晨，情况不对。机器没有交出他需要的结果。某些计算发生了错误。设备能够检测到异常。它尝试重试。但如果多次重试仍不能通过检查，就会放弃当前任务，转而处理其他工作。于是，研究者精心安排的部分计算，就这样丢失了。他只能再等一个星期。更令人恼火的是，类似的事情第二个周末又发生了。他再次来到机器旁。再次没有得到需要的答案。这一次，他开始认真思考一个问题。既然计算机已经能够判断自己发生了错误，为什么它不能进一步找到错误的位置，并自动修正？如果某个二进制位原来是0，却错误地变成了1，只要知道错误发生在哪一位，就能够把它重新改回0。如果原来是1，却错误地变成了0，也一样。所以，真正的困难，也许并不在于怎样修复一个已经定位的单比特错误。而是：怎样只利用少量额外信息，确定究竟是哪一个比特出了错？这位感到恼火的数学家，就是：理查德·韦斯利·汉明（Richard Wesley Hamming）。多年以后，1995年4月21日，已经八十岁的汉明在美国海军研究生院授课时，亲自回忆了这段经历。他清楚记得两个连续的周末。也记得自己当时的愤怒。正是在那份课堂回忆里，他解释了自己怎样从原有的错误检测技术，逐步走向能够定位并纠正错误的编码方法。 ^{[savage.nps.edu]}1950年4月，汉明在《贝尔系统技术期刊》发表了经典论文：Error Detecting and Error Correcting Codes《错误检测与错误纠正编码》。论文第147—160页。

1950年4月原始论文首页。汉明明确指出，研究动机来自大型数字计算机对可靠计算的需求。^{[Wiley Online Library][zoo.cs.yale.edu]}论文提出了能够进行单错误纠正，以及单错误纠正加双错误检测的编码构造。它并没有让计算机从此永远不会发生错误。而是让某些原本只能被发现、随后迫使任务中断的错误，第一次拥有了系统化的自动修复方法。这项研究后来产生了一个著名的名字：汉明码（Hamming Code）。而今天，我们要亲手构造其中最经典的一种：

\boxed{(7,4)\text{ 汉明码}}

四个原始信息比特。三个额外校验比特。总共七个比特。它竟然能够自动判断：如果七个比特里恰好只有一个发生翻转，究竟是哪一位出了错。然后，将它改回来。最有意思的是，这个过程不需要发送端重新传输消息。也不需要接收端事先知道原来的四个数据比特是什么。只需要七个收到的比特本身。那么，三个校验比特为什么就足够？这是本章的数学核心。

第一幕：那个连续两次毁掉周末计算的错误

贝尔实验室1940年代的继电器计算设备。与汉明早期研究直接相关的是贝尔为阿伯丁试验场制造的Model 5继电器计算机，而不是现代意义上的存储程序PC。^{[zoo.cs.yale.edu]}1940年代的计算机，与今天的计算机存在巨大的差异。当时，某些大型计算机依靠大量继电器工作。继电器是一种能够通过电信号控制开合的电气器件。在计算设备中，许多继电器可以组成开关逻辑，实现数字表示与计算。但继电器具有机械结构。它们可能出现接触不良、动作失败或者其他异常。而当一台设备拥有成千上万个继电器时，即使每个继电器都相对可靠，整个系统仍然可能偶尔发生故障。

一个不能被忽略的数字：8900

在1950年的原始论文中，汉明提到了贝尔实验室为美国阿伯丁试验场制造的Model 5继电器计算机。论文记录：两台机器合计拥有约8900个继电器。早期观察中，平均每天会发生约两到三次继电器故障。按照当时的统计，相当于每两三百万次继电器操作，大约出现一次故障。^{[zoo.cs.yale.edu]}这看起来并不算非常糟糕。但如果一项计算需要执行大量连续操作，问题就变得严重了。假设一项计算涉及数百万、数千万次操作。那么，即使单次操作出错的概率很小，整项长时间计算中遭遇至少一次故障的可能性，也可能不容忽视。特别是，当计算必须依赖前面的结果继续进行时，一次错误就可能影响后面整个计算过程。

设备已经具有错误检测能力

Model 5有一项很重要的功能。它能够利用特殊的数字编码检测某些异常。其中一项技术叫作：2-out-of-5 Code。中文可以理解为：“五位中恰好两位为1的编码”。例如：110001010010010这些序列，都有一个共同特点。五个位置中恰好有两个1。如果某个位置发生单比特翻转，结果就可能变成只有一个1，或者拥有三个1。这样，机器就能发现：收到的状态不符合合法编码规则。于是，它知道某些事情出了问题。但它还不知道，正确的结果究竟是什么。因此，机器只能重试，或者放弃当前任务。

汉明真正不满意的是什么？

在1995年的亲自回忆中，汉明讲述了当时设备的处理方式。如果出现无法通过校验的异常，机器可以尝试重新执行。如果三次尝试仍然不能通过，便放弃相应任务，继续处理下一项工作。他曾依靠周末的无人值守时间，完成大量白天难以取得计算资源的任务。于是，连续两次在星期一拿不到结果，让他十分恼火。^{[savage.nps.edu]}但这里必须区分两件事。已经存在的技术能够发现：某些数据或计算结果不合法。汉明希望进一步实现：知道它错在哪里，并在允许的错误模型下恢复正确结果。这是从错误检测（Error Detection），迈向错误纠正（Error Correction）。它们不是同一件事。

图47-1：检测错误与纠正错误的区别

错误检测

可能需要重试、丢弃或重新传输。

错误纠正

在规定错误数量内，可以自动修复。

一个真实故事里的细节

我们很容易把这段历史编成：“某个周末，汉明看见一张错误的穿孔卡片，突然想到三个校验位。”但这个说法没有充分依据。汉明在回忆里讲的，是使用继电器计算机进行周末批处理计算时，发生自动放弃任务的问题。而且，他后来还强调：自己并不是第一次思考容错计算。在此之前，他已经考虑过使用三台机器并行运行、通过多数表决抵抗单机错误的办法。他也对校验技术非常熟悉。所以，这项发明并非完全没有准备的瞬间灵感。恰恰相反：他早已掌握了大量相关知识，而连续失败的计算任务，使他迫切需要寻找一种更好的办法。

第二幕：一张来自洛斯阿拉莫斯的履历，为什么通向贝尔实验室？

理查德·汉明站在黑板旁的历史照片。他的研究横跨纠错编码、数值计算、数字信号处理及计算机科学教育。1915年2月11日，汉明出生于美国芝加哥。他早年学习数学。1937年，在芝加哥大学取得学士学位。1939年，在内布拉斯加大学取得硕士学位。1942年，在伊利诺伊大学获得数学博士学位。他的博士研究涉及线性微分方程边值问题。这些经历，与后来成为信息论和计算机科学经典的纠错编码，看起来并没有直接联系。但第二次世界大战改变了他的研究方向。

1945年，洛斯阿拉莫斯

战争期间，汉明进入洛斯阿拉莫斯实验室工作。在那里，他参与了曼哈顿计划相关的数值计算工作。他管理和使用当时的计算设备，协助科学家处理大量数值任务。在1982年的一篇回忆中，他明确谈到：这段工作经历让他认识到，大规模数值计算对于某些科学问题不可替代。^{[加菲尔德图书馆][Nuclear Museum]}这段经历还让他亲眼看到：计算结果的可靠性，不只是工程维护中的小问题。如果大量计算依赖前一个结果继续进行，某次错误就可能让后面的工作失去意义。

1946年，进入贝尔实验室

1946年，汉明加入贝尔实验室。这里汇集了通信、电路、数学和计算机领域的大量研究者。贝尔实验室已经在继电器计算机和自动电话交换系统中积累了丰富经验。汉明开始继续使用模拟与数字计算设备。他逐渐把注意力集中到一个问题：如果计算量越来越庞大，怎样让计算机在偶尔发生故障时仍然得到正确结果？这与当时快速发展的计算技术具有直接关系。随着电子计算机速度越来越快，机器能够在短时间内执行的操作数量大幅增加。但操作次数越多，可靠性要求也越高。在1950年论文开头，汉明明确指出，长而相互依赖的数字计算，与电话交换系统中较为独立的多条通路有所不同。前者的一次错误，可能破坏后续许多计算。^{[zoo.cs.yale.edu]}

1982年，汉明怎样回望自己的发明？

1982年，他在一份经典论文回顾中指出：实际的纠错码研究大约用了三个月。但由于专利方面的原因，成果发表推迟了两年多。在这段期间，管理层要求他将论文写得更加清晰而严谨。^{[加菲尔德图书馆]}所以，我们可以把这项研究的发展过程理解为：1946年以后，汉明在贝尔实验室持续思考计算机可靠性。1947年前后，实际计算中反复遭遇的错误激发了更明确的纠错需求。随后，他逐渐发展出相关数学构造。1950年，论文正式公开发表。这比“一次周末事故瞬间发明汉明码”的故事更加接近真实历史。

一项关于科学发现的自我反思

1995年，汉明还回忆了一段很有趣的思考过程。起初，他想过使用二维表格进行行校验和列校验。如果某个数据位出现错误，那么对应的一行和一列都会显示异常。于是，错误位置就能由行号和列号共同确定。接着，他又思考：能不能换一种几何排列方式，让校验位的数量更少？他从矩形想到三角形。又进一步想到更高维结构。最后，他逐渐认识到：比起把数据物理地排成某个图案，更重要的是让不同位置具有不同的校验标识。这段从二维表格走向更抽象校验结构的思考，来自汉明1995年保留下来的课堂讲述。^{[savage.nps.edu]}我们接下来，就沿着这条思路重新推导。不过先不要急着使用三个校验位。先从最简单的一位校验开始。

第三幕：一个额外的比特，竟然能够发现错误

继电器与二进制开关状态构成了早期数字计算设备的重要基础。在数据中加入特殊校验位，可以让某些原本无法辨识的错误变得可检测。假设我们需要传输四个信息比特：

\boxed{1011}

如果直接传输，接收端收到：1011它就认为消息正确。但假设传输过程中，第三位从1变成0。收到：1001接收端怎么办？如果没有任何额外信息，它无法判断：发送端原本就要发送1001。还是原本发送1011，只是某一位出错了。因为这两个字符串都可能是合法消息。

加入一个偶校验位

我们可以制定一项规则：每组数据必须包含偶数个1。例如：1011有三个1。所以，增加一个1作为校验位。变成：10111总共四个1。符合偶校验规则。如果传输时发生一个比特翻转：10111变成：10011那么1的总数变成三个。奇数。接收端立刻知道：数据不符合偶校验规则。因此，至少发生了某种异常。

但它知道哪一位错了吗？

不知道。假设接收端收到：10011它知道当前总共有奇数个1。但究竟是：第1位错了？第2位错了？第3位错了？第4位错了？还是校验位自己错了？仅凭这一项偶校验结果，无法区分。这就是单个校验位的局限。

图47-2：一个偶校验位能做什么？

原始信息1011

追加偶校验位10111

传输时第三位翻转10011

收到的1的数量3（奇数）

能够判断数据不符合偶校验规则，但无法仅凭这一个检查结果确定错误位置。

如果同时有两个比特发生翻转呢？

假设原始数据为：10111两个比特同时发生翻转后，得到：01111你会发现，1的数量仍然可能是偶数。因此，偶校验没有发现异常。从数学上讲：每次比特翻转，都会改变整体奇偶性。翻转奇数次，奇偶性改变。翻转偶数次，奇偶性保持不变。所以，单个偶校验位能够检测任意奇数数量的翻转错误。但不能检测偶数数量的翻转错误。它能够检测一个错误，却不能保证检测两个错误。更无法自动定位单个错误的位置。

汉明的关键问题

现在，假设我们不只做一项校验。而是设计多项互相重叠的校验。第一项检查某些位置。第二项检查另一组位置。第三项再检查另一组位置。如果每一个比特位置，参与校验的组合都不同，那么：当某一位出错时，出现异常的校验组合，也可能独一无二。例如：第3位出错。第一项校验失败，第二项也失败，第三项却正确。第5位出错。第一项与第三项失败，第二项正确。只要这些结果能够区分全部位置，就可以判断是哪一位发生错误。这才是汉明码真正的核心。不是多加几个校验位那么简单，而是让每一位数据拥有一组独一无二的校验身份。下一幕，我们将看到：为什么对七个比特而言，恰好只需要三个校验位。

第四幕：为什么四位信息，只需要再增加三个校验位？

汉明(7,4)码把4个信息位与3个校验位组合成7位码字。传统位置编号采用1至7，其中1、2、4为校验位。让我们暂时不考虑怎么计算校验位的数值。先问一个更基础的问题。如果我们想定位七个比特中的任意一个单比特错误，需要区分多少种情况？答案是八种。第一种：没有错误。第二种：第1位出错。第三种：第2位出错。……第八种：第7位出错。所以，一共：

7+1=8

种状态。

三个校验结果，最多能够区分八种情况

每项二元校验，只能产生两种结果。通过。不通过。如果有：

r

项独立的二元校验，最多可以形成：

2^r

种不同的结果组合。因此，为了区分：没有错误，以及七个可能的错误位置。我们至少需要：

2^r\ge8

当：

r=2

时：

2^2=4

不够。当：

r=3

时：

2^3=8

刚好足够。所以：

\boxed{r=3}

但要注意：这个计算仅仅证明，在结果数量上三个校验位有可能足够。它还没有证明：我们真的能找到一种校验结构，使八种情况都有不同的结果。汉明真正重要的贡献，正是构造出这样一种结构。

一般情况下，需要多少个校验位？

假设有：

m

个信息位。增加：

r

个校验位。总长度：

n=m+r

如果想纠正码字中任意一个单比特翻转，那么必须区分：

n

个错误位置，加上“没有错误”这一种情况。因此：

\boxed{2^r\ge m+r+1}

这个不等式，可以帮助我们判断需要的最少校验位数量。它也直接出现在汉明1950年的原始论文中。^{[zoo.cs.yale.edu]}例如：

m=4

如果：

r=3

则：

2^3=8

右边：

4+3+1=8

恰好相等。也就是说，三个校验位所能表达的全部八种结果，都被充分利用。

为什么选择第1、2、4位作为校验位？

在七个位置中：

1,2,3,4,5,6,7

汉明选择：

1,\ 2,\ 4

作为校验位。剩下：

3,\ 5,\ 6,\ 7

用来放数据。为什么偏偏是1、2、4？因为它们是2的整数次幂：

1=2^0

2=2^1

4=2^2

而所有数字1到7，都可以表示成三位二进制数。

图47-3：七个比特位置的三位二进制身份

位置	二进制编号	用途	参与哪些校验
1	001	P1	1
2	010	P2	2
3	011	D1	1、2
4	100	P4	4
5	101	D2	1、4
6	110	D3	2、4
7	111	D4	1、2、4

你会发现，每个位置都有独一无二的二进制编号。第1位：001第2位：010第3位：011……第7位：111如果我们能让校验失败的组合，恰好对应这个二进制编号，那么错误位置就可以直接算出来。

三组校验究竟怎样安排？

规定：P1检查组：

\boxed{\{1,3,5,7\}}

这些位置的二进制编号，最低位都是1。P2检查组：

\boxed{\{2,3,6,7\}}

这些位置的二进制编号，第二位都是1。P4检查组：

\boxed{\{4,5,6,7\}}

这些位置的二进制编号，第三位都是1。我们要求每一组的所有比特异或结果为0。也就是满足偶校验。于是，某个位置发生翻转时：凡是包含该位置的校验组，结果都会从通过变成失败。而那些不包含该位置的校验组，结果保持不变。因此，三项校验失败与否形成的三位二进制数，恰好就是错误位置。这便是整个算法的关键机制。

用一幅图看懂三组校验

图47-4：三组重叠校验与七个位置

查看 SVG 配图原件

47-007-7f4da8cb326d.svg · 点击查看大图

这是校验关系的教学结构图，而不是物理电路。七个位置各自对应一种独特的三组校验参与方式。

这其实与汉明早期考虑的“行列校验”很相似。但汉明码进一步利用了二进制编号，让不同位置的错误拥有不同的校验签名。如果用现代计算机术语描述：错误位置的编号，被直接编码进了校验结果。这一点在1950年的论文中写得非常明确：校验结果构成的二进制数，应当等于发生单错误的位置；零值则表示没有检测到错误。^{[zoo.cs.yale.edu]}现在，我们已经拥有了完整的设计规则。接下来，将四个具体信息比特填进去，看看会发生什么。

第五幕：从1011到0110011——第一次完整编码

汉明(7,4)码的编码过程：先将四个原始信息比特放入第3、5、6、7位，再分别计算第1、2、4位的偶校验值。现在，假设我们需要发送：

\boxed{1011}

为了避免混淆，我们将四个信息比特写成：

D_1=1

D_2=0

D_3=1

D_4=1

然后，把它们放入第3、5、6、7位。

位置	1	2	3	4	5	6	7
类型	P1	P2	D1	P4	D2	D3	D4
数值	?	?	1	?	0	1	1

现在，只需要计算三个问号。

第一项：求P1

P1负责位置：

1,3,5,7

要求这些位置的异或值为0。因此：

P_1\oplus D_1\oplus D_2\oplus D_4=0

所以：

P_1=D_1\oplus D_2\oplus D_4

代入：

P_1=1\oplus0\oplus1

异或运算中：

1\oplus0=1

1\oplus1=0

因此：

\boxed{P_1=0}

第二项：求P2

P2负责：

2,3,6,7

所以：

P_2=D_1\oplus D_3\oplus D_4

代入：

P_2=1\oplus1\oplus1

得到：

\boxed{P_2=1}

第三项：求P4

P4负责：

4,5,6,7

所以：

P_4=D_2\oplus D_3\oplus D_4

代入：

P_4=0\oplus1\oplus1

得到：

\boxed{P_4=0}

于是，完整的七位码字是：

位置	1	2	3	4	5	6	7
类型	P1	P2	D1	P4	D2	D3	D4
值	0	1	1	0	0	1	1

最终：

\boxed{1011\longrightarrow0110011}

四位信息，变成了七位码字。编码率为：

R=\frac47

约等于：

\boxed{57.14\%}

也就是说，每发送7个编码比特，其中有4个是真正的原始信息位。另外3个比特承担纠错所需的冗余。这与上一章的压缩存在鲜明对比。压缩尽量减少统计上不必要的冗余。汉明码则主动加入具有特定结构的冗余，帮助接收端抵抗错误。

为什么三个校验位之间不需要互相求解？

注意我们选择的位置：1、2、4。P1只检查包含第1位，但不依赖另外两个校验位。P2也不依赖P1或P4。P4同样如此。这是使用2的幂次位置作为校验位的一项便利之处。因此，三个校验比特可以直接从原始信息位独立计算。这使编码逻辑非常简单。在数字电路里，它们可以使用异或门组合实现。

一个真实的历史对应

汉明在1950年的论文中，确实使用了七位码、四位信息、三位校验这一具体例子。原始论文中的表格列出了全部16种合法七位码字。它还给出了一次第五位错误的示范：接收端通过校验结果得到二进制101，也就是十进制位置5，因此将第5位翻转，恢复原始码字。^{[zoo.cs.yale.edu]}我们现在所使用的1011 → 0110011，则是按照相同规则重新设计的教学例子。它不是对汉明原文具体数字的一字不差复述。但数学方法完全一致。接下来，我们将人为破坏刚才生成的七位码字。看看它如何自己暴露错误位置。

第六幕：第六位错了，为什么校验结果恰好是数字六？

伴随式（syndrome）计算示意。三个校验结果可以组成一个二进制编号，在恰好发生一次比特翻转时直接指出错误位置。刚才我们构造了合法码字：

\boxed{0110011}

现在，假设传输时，第6位发生翻转。原来第6位是：

1

但接收端收到：

0

于是，收到的七位序列变成：

\boxed{0110001}

接收端并不知道原始消息是1011。它也不知道到底有没有比特发生错误。它只能根据收到的七位数据，重新执行三个校验。

检查P1组

P1组包括位置：

1,3,5,7

收到的数值分别为：

0,1,0,1

异或：

s_1=0\oplus1\oplus0\oplus1

得到：

\boxed{s_1=0}

这意味着：P1组校验通过。

检查P2组

P2组包括：

2,3,6,7

收到的数值：

1,1,0,1

所以：

s_2=1\oplus1\oplus0\oplus1

得到：

\boxed{s_2=1}

第二组校验失败。

检查P4组

P4组包括：

4,5,6,7

收到：

0,0,0,1

所以：

s_4=0\oplus0\oplus0\oplus1

得到：

\boxed{s_4=1}

第三组校验也失败。

将三个结果合成二进制数

按照高位到低位的顺序：

s_4s_2s_1

得到：

\boxed{110_2}

换成十进制：

110_2=6

或者直接计算：

s=s_1+2s_2+4s_4

s=0+2+4

于是：

\boxed{s=6}

这意味着：在恰好只有一个比特发生错误的前提下，错误位置就是第6位。接收端只需要将第6位再翻转一次：0110001恢复成：0110011然后提取第3、5、6、7位：

1,\ 0,\ 1,\ 1

原始消息恢复为：

\boxed{1011}

整个过程，不需要重新传输。也不需要事先保存原来的四位消息。

图47-5：第6位错误的完整恢复过程

原始4位信息1011

编码后7位0110011

传输中第6位翻转0110001

第一组校验s₁ = 0

第二组校验s₂ = 1

第三组校验s₄ = 1

合成错误位置

110₂ = 6

定位第6位

纠正后提取数据位

1011

这种结果为什么如此漂亮？

因为我们刚才并没有做七次独立的错误位置检测。我们只计算了三项校验。而三项校验结果，本身组成了一个三位二进制数字。这个数字恰好表示出错的位置。这种计算结果，后来在编码理论中通常称为：伴随式（Syndrome）。有些中文教材也将它称为“校验子”或“症状”。在1950年的原始论文里，汉明使用了 checking number 这样的表述，并要求它直接给出单错误位置。现代线性码理论则使用统一的矩阵语言，将它表达为伴随式。^{[zoo.cs.yale.edu]}现在，我们已经掌握了汉明(7,4)码的基本编码与解码。但仍然有一个更加深刻的问题。为什么这种方法的数学保证是：纠正一个错误。而不是两个、三个或者任意多个错误？这需要引入另一个以汉明命名的概念。汉明距离（Hamming Distance）。

第七幕：汉明距离——两个正确答案，最少必须相隔多远？

编码理论可以将码字看成高维二进制空间中的点。两个码字相差多少个比特位置，就决定了它们在汉明距离下相隔多远。回想一下，我们刚才通过三个校验结果，定位了一次比特错误。但为什么它不能无条件纠正两个错误？要回答这个问题，我们需要先知道：不同合法码字之间，到底有什么几何关系？虽然码字只是一串0和1，但我们可以把它们看作某种特殊空间中的点。例如：000对应三维二进制空间中的点：

(0,0,0)

101对应：

(1,0,1)

这两个点在两个坐标位置上不同。于是，我们说：它们的汉明距离是2。

汉明距离的定义

对于两个长度相等的二进制字符串：

x=(x_1,\ldots,x_n)

y=(y_1,\ldots,y_n)

定义：

\boxed{ d_H(x,y)= |\{i:x_i\ne y_i\}| }

也就是：两串数据在多少个位置上不同。例如：10110011001101逐位比较：

位置	1	2	3	4	5	6	7
第一串	1	0	1	1	0	0	1
第二串	1	0	0	1	1	0	1
是否不同	否	否	是	否	是	否	否

只有第3位和第5位不同。因此：

\boxed{d_H=2}

汉明距离不仅可以用于纠错码。在位串比较、某些数据相似性计算和密码学分析中，它也很有用途。但在纠错码里，最重要的是：合法码字之间，至少相差多少位？

最小码距

设某种编码的所有合法码字构成集合：

\mathcal C

定义最小码距：

\boxed{ d_{\min}= \min_{\substack{x,y\in\mathcal C\\x\ne y}} d_H(x,y) }

也就是任意两个不同合法码字之间，最小的汉明距离。这个数字能够告诉我们：编码究竟能抵抗多少个错误。例如，如果：

d_{\min}=3

那么任意两个合法码字，至少相差三个比特位置。假设发送的是码字A。在传输时只有一个位置翻转。那么，接收结果距离A为1。它不可能同时距离另一个不同的合法码字B也为1。否则，根据距离的三角不等式：

d_H(A,B)\le1+1=2

就与：

d_{\min}=3

发生矛盾。所以，当至多一个比特发生错误时，最近的合法码字是唯一的。这就是单比特纠错的几何基础。

汉明(7,4)码的最小码距恰好是3

我们可以证明：

\boxed{d_{\min}=3}

首先，任何合法码字都必须通过全部三项偶校验。而七个比特位置的校验身份各不相同，且没有任何一个位置的校验身份为零。如果某个非零码字只有一个1，那么它不能通过全部校验。如果某个非零码字恰好只有两个1，因为它们对应不同的校验身份，两者异或也不会为零。因此，不存在重量为1或2的非零合法码字。另一方面，我们确实可以找到一个仅包含三个1的合法码字。例如，原始信息：

1000

按照前面的编码规则，会得到：

\boxed{1110000}

它与全零合法码字：

0000000

恰好相差三个位置。所以：

d_{\min}\ge3

并且：

d_{\min}\le3

最终：

\boxed{d_{\min}=3}

最小码距给出了纠错能力的界限

一般地，对于最小码距为：

d_{\min}

的编码，如果采用适当的译码策略：

最多能够保证纠正 $\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor$ 个错误。
如果只要求判断收到的数据是否为合法码字，则能够保证检测最多 $d_{\min}-1$ 个比特翻转错误。

对于汉明(7,4)码：

d_{\min}=3

因此：

t=\left\lfloor\frac{3-1}{2}\right\rfloor=1

所以它能保证：

\boxed{\text{纠正1个比特错误}}

从纯错误检测角度，它还能保证检测最多两个翻转错误。但这里存在一个非常重要的陷阱。能够检测两个错误，并不意味着同时拥有“自动纠正一个错误”和“可靠报告两个错误”的完整能力。因为如果我们总是假设只有一个错误，并看到非零伴随式就直接翻转对应位置，那么两个错误也可能被错误地当成一个错误来纠正。这正是下一幕将要解决的问题。

第八幕：当两个比特同时出错，汉明码为什么可能修错第三位？

基础汉明码的伴随式能够在单错误情况下准确定位错误。但两个错误的校验结果，可能恰好与另一个单错误的校验结果相同。继续使用我们已经构造出的合法码字：

0110011

现在假设，不是一个比特出错。而是两个位置同时发生翻转。例如：第3位。第5位。原始：0110011同时翻转第3和第5位：0100111现在，接收端重新计算伴随式。

两次错误怎样影响伴随式？

第3位的二进制位置编号是：

3=011_2

第5位的编号是：

5=101_2

如果两者同时翻转，那么校验结果会进行异或组合：

011_2\oplus101_2

得到：

\boxed{110_2}

也就是：

6

你会发现：这与“第6位发生单错误”的伴随式完全相同！因此，如果接收端没有额外信息，只按照单比特纠错规则处理，就会认为：第6位出错。然后将第6位也翻转。最终，接收端不但没有修复原来的第3、5位错误，反而又改坏了第6位。原本有两个位置不同。现在可能有三个位置不同。

这并不是偶然

对于基础汉明(7,4)码，每个非零三位伴随式都被分配给某个单比特错误位置。总共有：

2^3-1=7

种非零伴随式。而错误位置也恰好有七个。因此，全部非零结果都已经用来表示一种单比特错误。假设错误发生在：

i,\quad j

两个不同位置。伴随式就是：

s=i\oplus j

对于1到7的不同非零编号：

i\oplus j

依然是一个非零的三位数。因此，它总能对应另一个位置。所以，基础(7,4)码的单错误纠正器，无法仅凭三个校验结果区分：究竟是某一位出错。还是两个位置同时出错，组合起来形成了同样的伴随式。

不要混淆两个不同的程序

我们可以设计两个不同的接收策略。第一种是纯检测器。它只检查：

s=0?

如果非零，就报告检测到了错误。这种策略能够发现任意一个或两个比特翻转。第二种是单错误纠正器。它假设：错误数量最多为1。如果：

s\ne0

就将第

s

位翻转。在确实最多只有一个错误时，它能够正确恢复。但如果已经发生两个错误，那么它可能执行错误修复。这说明，代码必须明确自己的能力范围。如果不知道错误是否已经超出纠错能力，就不能把一次伴随式定位当成对错误数量的完整诊断。

那么能不能再增加一个校验位？

可以。而且，这正是汉明1950年原始论文里已经明确讨论的扩展方案。我们在原来的七位码字之外，再增加一个：整体偶校验位（Overall Parity Bit）。这样，原来的七位汉明码就扩展成八位。这种常见结构可以实现：SECDED：Single Error Correction, Double Error Detection。也就是：单错误纠正、双错误检测。它不仅能够在恰好发生一个错误时进行定位与修复。还能够在恰好发生两个错误时，判断当前并不是可以安全修复的单错误情况。但是，如何利用这第八位来做出判断？

第九幕：只增加第八位，为什么就能区分一个错误和两个错误？

扩展汉明码增加一个整体偶校验位。接收端将七位汉明伴随式与八位整体奇偶性共同判断，从而区分无错误、单错误和双错误情况。我们继续使用原始消息：

1011

它对应的七位汉明码：

0110011

现在数一数其中的1。它有四个1。已经是偶数。所以，我们添加的整体偶校验位是：

P_0=0

将它放在第8位。得到：

\boxed{01100110}

这是一种八位扩展码字。现在，我们拥有了两类不同的检查。第一类：原来的三项汉明校验。它们负责计算：

s

用于定位七位主体里的单错误。第二类：整个八位码字的偶校验。它负责判断所有八个位置中的1的总数，是否仍然为偶数。

如果没有错误

全部七位汉明校验通过。所以：

s=0

整体偶校验也通过。因此：

P_{\mathrm{all}}=0

接收端认为：没有检测到错误。

如果第6位发生单错误

第6位参与：P2检查。P4检查。因此：

s=6

同时，整个八位码字发生奇数次翻转。所以整体偶校验失败：

P_{\mathrm{all}}=1

于是，接收端看到：

s\ne0

而：

P_{\mathrm{all}}=1

在至多两位出错的假设下，这表示主体七位中有一个比特出错。因此可以根据

s

定位并修复。

如果第8位整体校验位出错

由于第8位不属于原来的三项汉明校验组，所以：

s=0

但是整体奇偶性被破坏：

P_{\mathrm{all}}=1

于是，接收端知道：不是原来的七位主体发生了单错误。而是整体校验位本身出了错。因此，将第8位翻转即可。

如果有两个比特同时出错

两个比特同时翻转，会让整体奇偶性保持不变。所以：

P_{\mathrm{all}}=0

但原来的三项汉明校验仍然能够发现异常。因此：

s\ne0

于是，接收端看到：

s\ne0,\qquad P_{\mathrm{all}}=0

在至多两位出错的前提下，就可以判断：发生了双错误。而且，它不会错误地把它当成单错误去修复。

图47-6：扩展汉明码的四种判断

汉明伴随式	整体偶校验	接收端操作
$s=0$	通过	未检测到错误
$s\ne0$	失败	纠正七位主体中的单错误
$s=0$	失败	纠正第8位整体校验位
$s\ne0$	通过	检测到双错误，不自动纠正

表中“无错误、单错误、双错误”的明确分类，依赖实际翻转数不超过2的前提。出现3个或更多错误时，某些组合可能导致误判或未检出。

为什么它的最小码距变成了4？

原来的汉明(7,4)码最小码距为：

d_{\min}=3

增加整体偶校验位之后，所有合法八位码字的1的数量都是偶数。如果两个合法码字之间原本相差三个位置，那么增加整体校验位之后，还必须在第8位出现一个差异，以保持两者整体的偶校验结构。于是，它们的距离从3增加到4。如果原本相差四个位置，新增校验位不需要再增加差异。因此，扩展汉明(8,4)码的最小距离为：

\boxed{d_{\min}=4}

这使它能够保证：纠正一个错误。检测两个错误。事实上，从纯检测角度，最小码距4意味着最多三个比特翻转也不能把一个合法码字直接变成另一个合法码字。但SECDED通常使用的自动诊断规则，明确保证的是：在最多两位出错的情况下，能够安全区分并处理单错误与双错误。如果出现三个错误，整体奇偶校验会失败，伴随式也可能非零，于是接收端可能将三个错误误认为一个错误并进行不正确的修复。因此，不能把SECDED说成：“任何三个错误都能正确识别并处理。”

第八位究竟改变了什么？

原来的七位码，已经拥有定位单错误的全部七种非零校验组合。但它缺少对错误数量奇偶性的额外判断。增加整体偶校验位之后，接收端获得了另一项独立信息。它能判断：本次错误翻转次数是奇数，还是偶数。于是，三个定位校验与一个整体校验联合起来，便能够完成更加可靠的分类。这就是SECDED的基本思想。更重要的是：这并不是后来人为附加给汉明研究的现代技巧。汉明在1950年原始论文中，就已经专门讨论了单错误纠正加双错误检测的编码，并通过增加一个整体偶校验位来构造它。 ^{[zoo.cs.yale.edu]}从一个校验位。到三个交叉校验位。再到四个联合校验位。我们终于理解了：冗余为什么不仅能表示“有错误”。还可以逐步获得更多关于错误模式的信息。接下来，就是本章最重要的互动实验。

第十幕：互动实验室——亲手把任意一个比特改坏，再让汉明码找出它

纠错实验的关键，不是让接收端知道正确答案，而是让接收端只根据收到的码字和既定校验规则，计算出错误位置。现在，我们已经拥有完成整个实验所需要的全部理论。下面是一台真正执行汉明码编码与校验运算的教学模拟器。你可以先选择四位原始消息。程序会自动生成七位汉明码。然后，你可以点击任何一个编码比特，将它人为翻转。接收端会重新计算三个校验结果。如果启用扩展模式，程序还会计算第8位整体校验。请特别注意：接收端的纠错判断只根据收到的比特计算，不会用原始消息偷偷修复答案。原始消息只用于实验结束后的正确性验证。

实验一：从`1011`开始

图47-7：汉明码与SECDED纠错实验台选择一组4位消息，再点击下面的编码比特，模拟它们在传输或存储过程中发生翻转。

四位原始消息

增加第8位整体偶校验，启用SECDED模式

发送端Hamming (7,4) · 单错纠正

原始消息 → 编码码字

1011

0110011

点击要翻转的位置已翻转 0 位

红色表示该位置被你人为翻转。单击红色位置可恢复；程序实际根据收到的0/1重新计算校验，而不是根据红色标识确定错误。

接收端：重新执行三项校验

校验组	检查位置	结果
P1	1、3、5、7	0 · 通过
P2	2、3、6、7	0 · 通过
P4	4、5、6、7	0 · 通过

伴随式：s₄s₂s₁

000

十进制

0

译码器采取的动作全部校验通过；未检测到异常

处理后的码字0110011

提取出的原始信息

1011

本次实验的原始消息已恢复

正确性验证使用实验已知的原始消息；真实接收端没有这一信息。若出现3位及以上错误，即使启用SECDED，也可能被误判为单错或未发现，因此不能将这套诊断解释成任意多错误下都可靠。

实验观察一：只翻转第6位

首先关闭SECDED。选择：1011然后点击：“翻转第6位”。你会得到：

s=6

译码器将第6位翻转回来。最终恢复：

1011

然后，你可以分别尝试第1到第7位。只要每次恰好翻转一个位置，程序都能够恢复。这验证了：

\boxed{d_{\min}=3\Rightarrow\text{保证纠正1个错误}}

实验观察二：同时翻转第3、5位

继续保持普通(7,4)模式。点击：“翻转第3、5位”。你会发现：

3\oplus5=6

接收端错误地认为第6位发生了单错误。于是，它会进一步改动第6位。最终恢复的消息可能与原始消息不同。这不是程序错误。而是我们故意让错误数量超出基础汉明码的单错误纠正能力。

实验观察三：打开SECDED

现在，勾选：“增加第8位整体偶校验”。再次翻转第3、5位。原来的三项汉明校验仍然得到：

s=6

但整体偶校验通过。所以，接收端知道：它不能把这次异常简单当成单错误修复。在最多两位错误的条件下，这应当被判定为双错误。于是，它会拒绝自动修复。这正是SECDED相比基础(7,4)码的重要进步。

实验观察四：一次翻转三个比特

保持SECDED模式。点击：“翻转第1、2、3位”。你会观察到一个令人警惕的结果。第1、2、3位的错误位置编号分别是：

001_2,\quad010_2,\quad011_2

三者异或：

001\oplus010\oplus011=000

所以：

s=0

而三次翻转破坏了整体偶校验。于是，译码器可能以为：只有第8位整体校验位发生了错误。它会错误地修复第8位。实际上，第1、2、3位仍然是错误的。这证明：SECDED也不是万能纠错技术。它的可靠诊断能力，是建立在明确错误数量约束之上的。

第十一幕：128个七位字符串，为什么恰好被16个码字全部占满？

完美码的几何直觉：每个合法码字周围都有一组可以通过单次比特翻转到达的接收结果。这些集合互不重叠，而且恰好覆盖全部可能的七位字符串。我们已经完成了具体的编码与纠错。但汉明在1950年论文里，还研究了一个更加深刻的问题。他构造出的编码，在冗余利用方面是否已经足够好？如果有更聪明的校验安排，能不能用更少的比特完成同样的单错误纠正？要回答这个问题，我们需要回到第七幕的汉明距离。

七位空间一共有多少个点？

每个位置可以是0或1。七个位置，共有：

\boxed{2^7=128}

种不同的二进制字符串。例如：00000000000001一直到：1111111这128个字符串，可以视为七维二进制空间里的128个点。而汉明(7,4)码只有：

2^4=16

种不同的原始消息。每条消息对应一个合法码字。因此，合法码字共有：

16

个。其他：

128-16=112

个七位字符串，不是合法码字。但它们并不是毫无用途。相反，它们可以被看作合法码字发生单比特错误后的结果。

每个合法码字周围有八种允许接收结果

假设发送的合法码字是：

c

如果没有错误，接收端收到：

c

这是一种情况。如果发生一次比特翻转，错误位置可以是：第1位。第2位。……第7位。因此共有七种单错误结果。加上没有错误，总共：

\boxed{1+7=8}

种接收结果。这些结果，构成以合法码字

c

为中心、汉明距离不超过1的集合：

B_1(c)=\{x:d_H(x,c)\le1\}

它通常被称为：半径为1的汉明球（Hamming Ball）。注意，这不是真实三维空间中的圆球。而是二进制字符串空间中，按照汉明距离定义的邻域。

不同合法码字的汉明球不能重叠

如果两个合法码字的半径1汉明球存在共同的接收结果，就意味着：某个七位字符串距离两个不同合法码字都不超过1。那么，接收端无法唯一判断原来的消息是哪一条。这与单错误纠正的要求矛盾。所以，如果希望保证纠正一个错误，不同合法码字的半径1汉明球必须互不重叠。对于汉明(7,4)码：合法码字数量为16。每个汉明球包含8个字符串。因此：

16\times8=128

而整个七位空间，也恰好包含：

2^7=128

个字符串。于是：

\boxed{16(1+7)=2^7}

每个字符串，都被某个合法码字的半径1汉明球覆盖。没有剩余。也没有重叠。

图47-8：16个汉明球，恰好填满128种可能

16组，每组8个字符串合计128种

2^4\left(\binom70+\binom71\right)=2^7

颜色只是将128种字符串按16个不重叠的纠错邻域分组，并不表示七维空间中的真实几何布局。

这说明了什么？说明汉明(7,4)码在单错误纠正的空间利用方面，达到了一项非常漂亮的极限。它被称为：完美码（Perfect Code）。这里的“完美”，有严格的数学含义。它是指纠错球恰好填满整个码字空间，达到对应的汉明球填充界。不是说：这个编码没有缺点。更不是说：它能纠正所有错误。

一般的汉明界

对于长度为：

n

的二进制码。如果合法码字有：

M

个。并且希望纠正最多：

t

个比特翻转，那么每个合法码字周围半径

t

的汉明球包含：

\sum_{j=0}^{t}\binom nj

个字符串。这些球必须互不重叠。但整个二进制空间只有：

2^n

个字符串。所以：

\boxed{ M\sum_{j=0}^{t}\binom nj\le2^n }

这就是二进制编码中的汉明界（Hamming Bound），也称球填充界。如果是二元线性：

(n,k)

码，那么：

M=2^k

于是：

\boxed{ 2^k\sum_{j=0}^{t}\binom nj\le2^n }

对汉明(7,4)码，取：

n=7,\quad k=4,\quad t=1

得到：

2^4\left(1+7\right)\le2^7

两边都是128。所以等号成立。这项结果告诉我们：汉明(7,4)码不只是偶然能纠正一位错误。它还在相应参数下，极其充分地利用了七位二进制空间。

一个非常深刻的推论

对于任意收到的七位字符串，只要使用汉明(7,4)码的最近码字解码规则，都能够找到唯一一个距离不超过1的合法码字。这解释了为什么：当收到两个错误时，基础单错误译码器经常仍然会给出一个看起来非常明确的答案。因为它总能找到某个距离1的合法码字。问题并不是它“找不到答案”。而是它找到的那个合法码字，可能不是发送端真正发送的码字。这也是编码理论中一个非常重要的认识：能够把收到的数据映射回某个合法码字，不等于能够证明这个码字就是原始消息。正确性始终需要与错误数量的假设一起理解。

第十二幕：三项校验，为什么可以写成一个矩阵？

现代线性编码理论使用二进制矩阵描述校验关系。汉明码的三个校验结果可以统一表示为一个矩阵乘法。到这里，我们已经可以用普通的异或运算，实现完整的汉明(7,4)码。但如果消息长度不再只有四位呢？假设需要保护：64位。128位。甚至更长的数据块。我们显然不能只依靠手写七位示例中的三条校验公式。数学家需要一种统一的表达方式。这就引出了：线性分组码（Linear Block Code）。

在二元域上进行计算

我们现在只考虑0和1。加法采用模2运算：

0+0=0

0+1=1

1+0=1

1+1=0

这与异或运算一致。因此：

a+b\pmod2=a\oplus b

我们可以在二元有限域：

\mathbb F_2

上进行矩阵计算。

汉明码的校验矩阵

对于前面使用的七位布局：

c=(c_1,c_2,\ldots,c_7)

三项校验分别是：

c_1+c_3+c_5+c_7=0

c_2+c_3+c_6+c_7=0

c_4+c_5+c_6+c_7=0

全部加法都在模2意义下进行。我们将这三条约束写成矩阵：

\boxed{ H= \begin{bmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix} }

合法码字必须满足：

\boxed{Hc^T=0}

其中：

c^T

是七位码字的列向量。所有计算仍然在

\mathbb F_2

中进行。

为什么矩阵的七列这么特别？

观察矩阵H的每一列。第1列：

\begin{bmatrix}1\\0\\0\end{bmatrix}

第2列：

\begin{bmatrix}0\\1\\0\end{bmatrix}

第3列：

\begin{bmatrix}1\\1\\0\end{bmatrix}

……第7列：

\begin{bmatrix}1\\1\\1\end{bmatrix}

它们恰好是全部七种非零三位二进制向量。只是我们将：

s_1,s_2,s_4

按低位到高位的顺序放入列向量。如果第6位出错，那么错误向量为：

e= \begin{bmatrix} 0&0&0&0&0&1&0 \end{bmatrix}^T

接收码字：

r=c+e

由于合法码字满足：

Hc^T=0

所以：

Hr^T=H(c+e)^T

即：

Hr^T=Hc^T+He^T

得到：

\boxed{Hr^T=He^T}

而

e

只有第6位为1，因此：

He^T

直接等于H的第6列：

\begin{bmatrix} 0\\1\\1 \end{bmatrix}

如果我们按：

s_4s_2s_1

写成二进制，就是：

110_2=6

于是，整个纠错机制获得了一种极其简洁的数学表达：

\boxed{s=Hr^T}

其中

s

就是伴随式。

一个矩阵，统一了所有校验

这项方法之所以重要，是因为它不再要求我们为每一种码字布局，单独发明一套人工规则。只要给定相应的校验矩阵：

H

就可以计算收到的码字是否满足约束。对于更一般的线性分组码，也可以使用类似的矩阵语言研究：合法码字空间。校验约束。错误向量。伴随式。以及译码方法。因此，汉明码不仅是一套七位小技巧。它还是线性编码理论中最容易理解、又非常具有代表性的例子。从三个异或公式，到一个矩阵方程：

Hr^T=s

这是一项数学抽象带来的巨大简化。

第十三幕：Python实战——让程序纠正全部128种单错误情况

汉明(7,4)码规模很小，因此我们不仅能够测试几个案例，还能够穷举验证全部16种原始消息及所有单错误位置。现在，我们将前面十一幕的数学推导，写成一份真正可以运行、可以自动验证的Python程序。这次程序包含：汉明(7,4)编码。伴随式计算。单错误纠正。扩展汉明(8,4)编码。SECDED译码。以及自动化穷举测试。我们不调用任何专业纠错库。只使用Python标准库。

第一部分：四位信息，生成七位码字


from itertools import product, combinations


def encode74(data: str) -> list[int]:
    """
    Hamming(7,4) 偶校验编码。

    位置编号：
      1  2  3  4  5  6  7
      P1 P2 D1 P4 D2 D3 D4
    """

    if len(data) != 4 or set(data) - {"0", "1"}:
        raise ValueError("请输入恰好4个二进制字符")

    d1, d2, d3, d4 = map(int, data)

    # 使用1起始下标，位置0不使用
    c = [0] * 8

    c[3] = d1
    c[5] = d2
    c[6] = d3
    c[7] = d4

    # 三项偶校验
    c[1] = c[3] ^ c[5] ^ c[7]
    c[2] = c[3] ^ c[6] ^ c[7]
    c[4] = c[5] ^ c[6] ^ c[7]

    return c[1:]


def syndrome74(received: list[int]) -> int:
    """按s4 s2 s1形成错误位置编号。"""

    if len(received) != 7:
        raise ValueError("必须输入7个比特")

    r = [0] + list(received)

    s1 = r[1] ^ r[3] ^ r[5] ^ r[7]
    s2 = r[2] ^ r[3] ^ r[6] ^ r[7]
    s4 = r[4] ^ r[5] ^ r[6] ^ r[7]

    return s1 + 2*s2 + 4*s4


def decode74(received: list[int]):
    """
    基础汉明码单错误译码。

    注意：自动纠正隐含“最多1位出错”假设。
    两位或更多位错误时不能保证恢复正确消息。
    """

    corrected = list(received)
    s = syndrome74(corrected)

    if s != 0:
        corrected[s - 1] ^= 1

    data = "".join(
        str(corrected[i])
        for i in (2, 4, 5, 6)
    )

    return data, s, corrected


message = "1011"

encoded = encode74(message)

print("原始消息:", message)
print("七位编码:", "".join(map(str, encoded)))

# 人为翻转第6位
received = encoded.copy()
received[5] ^= 1

print("收到消息:", "".join(map(str, received)))

decoded, position, corrected = decode74(received)

print("伴随式定位:", position)
print("纠正后码字:", "".join(map(str, corrected)))
print("恢复原始信息:", decoded)

assert decoded == message

预期结果：

原始消息: 1011
七位编码: 0110011
收到消息: 0110001
伴随式定位: 6
纠正后码字: 0110011
恢复原始信息: 1011

这里的关键是：接收端并没有读取原来的1011参与解码。它只接收：0110001然后重新计算三个校验。最终定位第6位。

第二部分：扩展为SECDED

现在，增加一个整体偶校验位。同时，译码器必须根据汉明伴随式和整体偶校验结果，区分错误类型。


def encode84(data: str) -> list[int]:
    """扩展汉明(8,4)：7位主体+1位整体偶校验。"""

    code = encode74(data)

    overall = sum(code) % 2

    return code + [overall]


def decode84(received: list[int]):
    """
    SECDED译码。

    返回：
      (状态, 恢复的数据或None, 伴随式)

    在最多2个比特发生错误的假设下：
      - 0错：正常
      - 1错：修复
      - 2错：检测并拒绝自动修复
    """

    if len(received) != 8:
        raise ValueError("SECDED需要8位码字")

    r = list(received)

    s = syndrome74(r[:7])

    overall = sum(r) % 2

    if s == 0 and overall == 0:
        status = "no_error"

    elif s != 0 and overall == 1:
        r[s - 1] ^= 1
        status = "single_error_corrected"

    elif s == 0 and overall == 1:
        r[7] ^= 1
        status = "overall_parity_corrected"

    else:
        return "double_error_detected", None, s

    data = "".join(
        str(r[i])
        for i in (2, 4, 5, 6)
    )

    return status, data, s


original = encode84("1011")

# 模拟第3位和第5位同时出错
damaged = original.copy()
damaged[2] ^= 1
damaged[4] ^= 1

status, decoded, syndrome = decode84(damaged)

print("原始8位码字:", "".join(map(str, original)))
print("受损8位码字:", "".join(map(str, damaged)))
print("诊断状态:", status)
print("伴随式:", syndrome)
print("是否交付数据:", decoded is not None)

预期结果：

原始8位码字: 01100110
受损8位码字: 01001110
诊断状态: double_error_detected
伴随式: 6
是否交付数据: False

注意最后一行。程序没有试图恢复出一组看起来合理但未经保证的数据。它明确报告：本次错误超出了安全单错误纠正能力。因此，不交付译码结果。这对于真实可靠性系统十分重要。有些错误可以修复。有些错误只能检测。如果程序无法安全纠正，就应该将状态明确报告给更高层，而不是假装一切正常。

第三部分：穷举测试全部合法消息

汉明(7,4)码只有：

2^4=16

种原始消息。因此，我们能够穷举全部合法码字。对于每个七位码字，分别翻转其中的七个位置。然后验证：是否总能恢复正确的四位原始信息。测试数量：

16\times7=112

另外，还可以将没有错误的16种情况也加入测试。一共128种。


def all_messages():
    return (
        "".join(bits)
        for bits in product("01", repeat=4)
    )


# 测试所有合法原始消息的全部单错误情况
tested = 0

for message in all_messages():
    encoded = encode74(message)

    # 没有错误
    decoded, _, _ = decode74(encoded)

    assert decoded == message
    tested += 1

    # 任意一个位置发生翻转
    for position in range(7):
        damaged = encoded.copy()
        damaged[position] ^= 1

        decoded, syndrome, _ = decode74(damaged)

        assert decoded == message
        assert syndrome == position + 1

        tested += 1

print("Hamming(7,4)测试通过:", tested)


# 测试SECDED的全部单错误和双错误
single_tests = 0
double_tests = 0

for message in all_messages():
    encoded = encode84(message)

    # 测试任意单错误，包括整体校验位
    for position in range(8):
        damaged = encoded.copy()
        damaged[position] ^= 1

        status, decoded, _ = decode84(damaged)

        assert status in (
            "single_error_corrected",
            "overall_parity_corrected",
        )

        assert decoded == message
        single_tests += 1

    # 测试任意双错误
    for i, j in combinations(range(8), 2):
        damaged = encoded.copy()
        damaged[i] ^= 1
        damaged[j] ^= 1

        status, decoded, _ = decode84(damaged)

        assert status == "double_error_detected"
        assert decoded is None

        double_tests += 1

print("SECDED单错误测试:", single_tests)
print("SECDED双错误测试:", double_tests)
print("全部自动测试通过")

这段程序的预期结果：

Hamming(7,4)测试通过: 128
SECDED单错误测试: 128
SECDED双错误测试: 448
全部自动测试通过

为什么双错误测试是448种？因为每个八位码字有：

\binom82=28

种不同的双错误位置组合。而原始消息一共有16种。所以：

16\times28=448

这项测试非常有价值。因为它不只是拿某两个例子证明程序似乎正确。而是穷举了：全部16种原始消息。全部128种单错误情况。全部448种双错误情况。对于这种规模很小的编码，穷举测试是一种极为有效的验证方式。当然，我们验证的是代码对所列错误模式的行为。它并没有证明：当出现三位、四位或更多错误时，SECDED仍然能够正确诊断。这些情况本来就超出了它的保证范围。

为什么这份程序与真实ECC控制器仍然不同？

真实硬件里的ECC逻辑，可能使用：更长的数据块。经过优化的校验矩阵。硬件并行异或网络。存储控制器状态寄存器。纠错事件计数器。以及中断与错误上报机制。但它们仍然使用了许多相同的核心思想：写入时计算校验信息。读取时重新执行校验。根据校验结果判断数据状态。如果能够安全修复，就返回修复后的数据。如果错误不可纠正，就向系统报告。所以，虽然本章的七位和八位程序很小，却已经能够解释现代ECC中一些非常重要的基本原理。

第十四幕：从七位汉明码，到现代计算机内存的纠错机制

现代服务器和某些嵌入式系统使用ECC机制，提高数据存储和读取的可靠性。实际ECC方案通常保护远大于4位的数据块，且不一定与教学版(8,4)码完全相同。如果我们只停留在七位码字的数学推导上，很容易产生一个误解。汉明码似乎只是早期计算机时代的一项小技巧。但事实并非如此。它建立的思想，直到今天仍然出现在很多硬件与软件系统中。

第一种应用：计算机内存

现代计算机内存，可能由于多种原因出现比特错误。例如：电气干扰。硬件缺陷。某些辐射相关的软错误。以及其他物理机制。这些问题可能导致原本保存为0的某个位置，读取时变成1。或者原本保存为1，却读取成0。如果一项重要程序长期运行、依赖大量内存数据，那么这些错误可能具有严重影响。因此，某些服务器、工作站和嵌入式系统采用ECC内存机制。ECC通常是：Error-Correcting Code。即错误纠正编码。

现代内存控制器怎样使用ECC？

可以将其简化成以下过程。写入数据时：控制器根据原始数据，计算额外的ECC校验位。然后将数据与校验信息一起保存。读取数据时：控制器取回数据和校验信息。重新执行校验。如果发现可纠正的单比特错误，就按编码规则恢复。如果检测到无法修复的多比特错误，就向系统报告。这与我们刚才编写的SECDED程序，在思想上高度一致。不过，真实ECC系统使用的数据块通常更长。例如，AMD的内存控制器技术文档中，就明确描述了采用SECDED进行DRAM保护的方案：能够纠正全部单比特错误。检测全部双比特错误。对于超过两个比特的错误，则不保证全部检测到。^[UG586]

为什么常见ECC内存会有64位数据、8位校验？

这是一个很有代表性的工程例子。假设我们需要保护：

m=64

个原始数据比特。如果只要求单错误纠正，先计算最少需要多少个校验位。根据汉明码的计数条件：

2^r\ge64+r+1

当：

r=6

时：

2^6=64

但右边：

64+6+1=71

所以不够。当：

r=7

时：

2^7=128

右边：

64+7+1=72

满足要求。因此，理论上可以使用7个适当的校验位，构造保护64位数据的单错误纠正线性码。如果再增加一个整体偶校验位：

7+1=8

那么总共需要：

64+8=72

个比特。这就是很多64位数据加8位ECC冗余的SECDED方案，在数学上非常自然的原因。

图47-9：教学版与常见长字SECDED方案

方案	数据位	校验位	总位数
Hamming(7,4)	4	3	7
扩展Hamming(8,4)	4	4	8
一种64位SECDED布局	64	8	72

不同厂商和控制器可能采用不同的ECC编码矩阵、数据组织及硬件传输方式。64+8只是很有代表性的布局，并不意味着全部ECC实现都完全相同。

AMD与Microchip的官方文档中，均可找到64位数据配合8位ECC校验的SECDED硬件实例。^{[PG313][Microchip 文档]}

第二种应用：微控制器与嵌入式存储

部分微控制器的片内RAM或Flash采用ECC保护机制，以减少某些偶发位错误对运行结果的影响。在工业设备和嵌入式系统中，ECC也具有重要价值。例如，STMicroelectronics 的应用文档明确介绍了其部分STM32微控制器使用的ECC机制。其中包括基于汉明编码原理、增加整体校验位的SECDED方案。文档还讨论了SRAM软错误、Flash数据保持问题，以及系统应如何处理可纠正和不可纠正的错误。^[AN5342]这类系统的实际行为，可能不只是悄悄把一个错误比特修复。它还可能：记录错误地址。设置错误状态寄存器。触发中断。向系统软件报告不可纠正错误。或者由安全机制采取进一步动作。因为在关键应用中，错误被纠正了，并不代表我们应该忽略它。如果某个内存区域频繁发生可纠正错误，它可能提示硬件状况需要进一步检查。

第三种应用：长距离通信与数字存储

空间通信与数字存储都需要面对噪声或数据损坏，但具体采用的纠错编码不一定是简单汉明码。它们共享的是利用编码冗余恢复可靠信息的基本思想。在更广泛的通信和存储领域，纠错码同样发挥着重要作用。但我们不能简单地说：“所有卫星、所有光盘、所有现代无线网络都在直接使用汉明(7,4)码。”现代系统可能采用更加复杂的编码方法。例如：卷积码。里德—所罗门码。BCH码。LDPC码。Polar码。以及多种组合编码与交织技术。它们的编码长度、纠错能力和解码算法都可能与最初的汉明码明显不同。然而，这些技术都继承了一项共同的思想：不必要求每个物理信号和存储单元永远正确，而是通过数学编码，为一定范围内的错误提供检测或纠正能力。这项思想与1948年的香农理论密切相关。香农告诉我们可靠通信存在理论可能性与容量极限。汉明则展示了怎样用非常明确的代数规则，构造可以自动修复错误的实际编码。二者的研究动机并不完全相同。但后来共同成为现代编码理论的重要基础。

尾声：一台会停下来的计算机，终于学会了先修复自己

让我们回到那个星期一早晨。汉明走进计算机房。他原本希望领取整个周末积累的计算结果。但设备没有交出答案。因为某些计算出现了错误。系统知道自己遇到了异常。却无法判断正确结果究竟应该是什么。于是，它放弃任务。而汉明，失去了宝贵的计算时间。这样的经历重复发生后，他开始思考：为什么机器只能发现错误，却不能自己纠正？如果错误发生在二进制数据中的一个位置，那么：0可以改成1。1可以改成0。问题只剩下：怎样知道究竟应该修改哪一个位置？从这个简单的问题出发，他逐渐发展了一套极其优美的数学结构。为每个比特位置分配一组不同的校验身份。让多个校验条件彼此重叠。当某个位置发生错误时，参与它的校验条件就会失败。而这些失败结果，恰好组合成错误位置的二进制编号。于是：

\boxed{\text{校验结果}=\text{错误位置}}

对于汉明(7,4)码，这个过程只需要三个校验比特。四个原始信息比特，可以被编码成七位。只要七位中最多出现一次比特翻转，接收端就能够恢复原始数据。进一步增加一个整体偶校验位，还可以在最多出现两个错误的模型下，实现：单错误纠正。双错误检测。这便是我们今天所说的SECDED。

从三个校验结果，到整个线性编码理论

汉明码的数学思想，还可以通过矩阵表示：

\boxed{Hr^T=s}

其中：

H

是校验矩阵。

r

是接收到的码字。

s

是校验结果，也就是伴随式。在单错误情况下，伴随式直接指出错误位置。这使编码与解码拥有了一种可推广的代数语言。而最小码距：

\boxed{d_{\min}}

则告诉我们，编码对于不同数量的错误能够提供什么保证。汉明(7,4)码的：

d_{\min}=3

解释了它为什么能够纠正一个错误。扩展汉明(8,4)码的：

d_{\min}=4

则解释了为什么它可以安全区分单错误与双错误。更令人惊叹的是，汉明(7,4)码还属于一类特殊的完美码。它的16个合法码字，每个都有8种距离不超过1的可能接收结果。而：

16\times8=128=2^7

恰好覆盖全部七位二进制字符串。这说明，汉明码并不是凭经验增加了几个校验位。它在数学上达到了一个非常漂亮的组合极限。

这项发明的意义，远远超出了七个比特

1950年的原始论文只有14页。但它引出了许多后来成为编码理论基础的概念。错误检测。错误纠正。冗余。最小码距。伴随式。以及纠错能力与码字空间之间的关系。这些概念后来进入现代计算机硬件。ECC内存。嵌入式系统。以及各种数字通信与存储技术。但我们也必须承认：汉明码没有彻底解决世界上的全部数据错误。现实中的错误可能一次破坏多个比特。可能以连续成片的形式出现。也可能涉及更复杂的信道统计与存储故障模型。因此，后来的研究者继续发展更加复杂的编码方案。汉明建立的数学语言，成为他们研究这些问题的一项重要基础。

汉明的晚年与研究遗产

汉明在1976年离开贝尔实验室，进入美国海军研究生院从事教学。他不仅研究纠错编码，还长期关心科学方法、数值分析与如何开展具有重要价值的研究。^{[Naval Postgraduate School]}1968年，汉明获得ACM图灵奖。获奖理由包括数值方法、自动编码系统，以及错误检测与纠正编码方面的贡献。1976年，他离开贝尔实验室，进入美国海军研究生院工作。此后，他继续从事计算机科学教育。1995年，他仍在课堂上亲自向学生讲述自己几十年前的研究过程。1998年1月7日，汉明在加利福尼亚州蒙特雷去世，享年82岁。^{[MacTutor History of Mathematics][国家科学院]}我们今天能够读到那段关于连续两个周末计算失败的回忆，是一项很幸运的事情。因为它让我们看到：一项看起来极其抽象的数学结构，最初可能来自一个非常实际的问题。一台计算机不够可靠。一次计算任务失败了。一位研究者感到恼火。但他没有仅仅要求：能不能换一台更好的机器？能不能增加工作人员？能不能让设备再多重试几次？他提出了一个不同的、更具有一般性的问题。为什么不让系统利用少量额外信息，在一定的错误范围内自行恢复？这个问题最终变成了一套可以被证明、实现与推广的数学方法。

第四篇的前两章，已经形成了一条清晰的研究道路

《穿越噪声的信息》· 第46—47章

第46章

香农：可靠通信的数学极限信息熵量化不确定性，信道容量描述在给定噪声模型下能够实现的可靠通信速率极限。

第47章

汉明：具体的错误检测与纠正方法利用交叉校验、二进制位置编号与最小码距，让接收端能够定位并修复特定范围内的错误。

香农告诉我们：可靠通信在什么条件下可以实现？它的理论极限在哪里？汉明进一步告诉我们：怎样用一种具体的数学构造，让计算机自动纠正单比特错误？这两项研究并非完全相同的问题。却共同支撑起了现代纠错编码理论。而我们下一章，将面对更加棘手的一类错误。不是某一个比特偶然翻转。而是一整片连续的数据受到损坏。例如：一张光盘被划出一道伤痕。某些连续的存储符号，再也无法被正确读取。这时候，简单的单比特纠错可能远远不够。研究者需要一种能够处理多符号错误、甚至成片错误的数学编码。故事将带我们走向：里德—所罗门码（Reed–Solomon Code）。

历史档案：从1947年的计算失败，到1950年的经典论文

年份	人物或事件	历史意义
1915年	Richard Wesley Hamming出生	后来的纠错编码先驱
1945年	汉明在洛斯阿拉莫斯工作	深入接触大规模数值计算及可靠性问题
1946年	加入贝尔实验室	继续研究数值计算、数字系统及纠错问题
1947年前后	研究自动错误纠正	与继电器计算机的错误检测和计算中断经历密切相关
1950年4月	发表纠错编码经典论文	系统阐述单错检测、单错纠正及单错纠正加双错检测的编码构造
1968年	获得ACM图灵奖	认可其对计算科学与纠错编码的长期贡献
1976年	转至美国海军研究生院	继续进行教学与计算机科学研究
1995年4月21日	亲自讲述纠错码发明过程	留下有关周末计算失败与研究探索的第一手课堂资料
1998年1月7日	在蒙特雷去世	享年82岁

主要参考文献与一手资料

1950年 · 汉明原始论文Error Detecting and Error Correcting Codes — 原文PDF第一手核心史料。包含Model 5继电器计算机、校验位构造、七位汉明码、错误位置编号以及扩展为单错纠正加双错检测码的方法。

1950年 · 期刊官方书目Bell System Technical Journal — Hamming (1950)第29卷第2期，第147—160页，1950年4月正式发表。用于核查论文的准确题目、作者、日期和页码。

1995年 · 汉明亲自讲述发明过程Error Correcting Codes — Naval Postgraduate School 讲课实录非常重要的一手口述史。详细记录连续两个周末计算失败、原有2-out-of-5错误检测、行列校验思路，以及随后发展的更抽象结构。

1982年 · 汉明回顾1950年论文This Week's Citation Classic — R. W. Hamming汉明本人回忆洛斯阿拉莫斯、贝尔计算机、纠错研究约三个月的工作过程，以及专利事务造成的发表延迟。

汉明的教育经历与生平MacTutor — Richard Hamming 美国国家工程院：Richard W. Hamming纪念传记用于核查出生日期、学位、洛斯阿拉莫斯与贝尔实验室工作经历、图灵奖和晚年教学。

现代ECC硬件的官方技术文档AMD — DRAM Error Correcting Code STMicroelectronics — ECC应用说明用于核查现代SECDED能够纠正单错误、检测双错误的具体应用及其超出保证范围时的局限。

**史实与教学重构说明：**本章开篇的两个周末计算失败，来自汉明1995年的亲自回忆；相关设备的错误检测能力则可由1950年论文交叉核查。场景中的心理活动是根据其回忆组织的文学化叙事，不是逐字还原的现场记录。汉明(7,4)码的编码规则与校验位置来自1950年原始论文。本章使用1011 → 0110011作为重新设计的教学例子。互动实验、矩阵图、码距推导及Python程序均为现代教学内容。实验中翻转的比特数量由用户明确设定，因此我们可以额外验证程序是否真正修复成功；现实接收端通常没有这份“标准答案”，其安全诊断依赖编码本身的错误检测与纠正保证。

下一章预告 · 第48章

《被划伤的光盘为什么还能读：里德—所罗门码》

1960年，两位数学家发表了一篇只有几页的论文。一位叫欧文·里德（Irving S. Reed）。另一位叫古斯塔夫·所罗门（Gustave Solomon）。论文的标题是：Polynomial Codes Over Certain Finite Fields《某些有限域上的多项式编码》。它发表于《Journal of the Society for Industrial and Applied Mathematics》第8卷第2期，第300—304页。 ^{[SIAM Journal on Applied Mathematics]}与汉明码不同，他们将信息表示为有限域上的多项式。通过在多个不同位置计算多项式的值，形成一组具有数学冗余的编码符号。于是，即使某些符号受到损坏，只要错误数量处在规定范围内，接收端仍然有机会恢复原来的多项式。后来，这项思想进入数字通信与存储设备。例如，经典音频CD系统使用了交叉交织里德—所罗门编码（CIRC），帮助处理随机错误和连续的突发错误。因此，一张表面出现划痕的光盘，并不一定马上无法读取。但是，划痕过于严重时，纠错能力同样存在极限。下一章，我们将从光盘上的一条真实划痕出发，研究为什么把数据分散、交织和多项式编码之后，可以抵抗某些连续损坏。还会学习有限域、编码多项式、错误与擦除的区别，以及如何使用 Python 在受损符号中恢复原始消息。汉明教会机器寻找单个错误的位置；里德与所罗门，则将带我们研究怎样从多处受损的数据中恢复整个消息。

——《算法的故事》第二季 · 第47章完

第一幕：那个连续两次毁掉周末计算的错误

一个不能被忽略的数字：8900

设备已经具有错误检测能力

汉明真正不满意的是什么？

一个真实故事里的细节

第二幕：一张来自洛斯阿拉莫斯的履历，为什么通向贝尔实验室？

1945年，洛斯阿拉莫斯

1946年，进入贝尔实验室

1982年，汉明怎样回望自己的发明？

一项关于科学发现的自我反思

第三幕：一个额外的比特，竟然能够发现错误

加入一个偶校验位

但它知道哪一位错了吗？

如果同时有两个比特发生翻转呢？

汉明的关键问题

第四幕：为什么四位信息，只需要再增加三个校验位？

三个校验结果，最多能够区分八种情况

一般情况下，需要多少个校验位？

为什么选择第1、2、4位作为校验位？

三组校验究竟怎样安排？

用一幅图看懂三组校验

第五幕：从1011到0110011——第一次完整编码

第一项：求P1

第二项：求P2

第三项：求P4

为什么三个校验位之间不需要互相求解？

一个真实的历史对应

第六幕：第六位错了，为什么校验结果恰好是数字六？

检查P1组

检查P2组

检查P4组

将三个结果合成二进制数

110₂ = 6

1011

这种结果为什么如此漂亮？

第七幕：汉明距离——两个正确答案，最少必须相隔多远？

汉明距离的定义

最小码距

汉明(7,4)码的最小码距恰好是3

最小码距给出了纠错能力的界限

第八幕：当两个比特同时出错，汉明码为什么可能修错第三位？

两次错误怎样影响伴随式？

这并不是偶然

不要混淆两个不同的程序

那么能不能再增加一个校验位？

第九幕：只增加第八位，为什么就能区分一个错误和两个错误？

如果没有错误

如果第6位发生单错误

如果第8位整体校验位出错

如果有两个比特同时出错

为什么它的最小码距变成了4？

第八位究竟改变了什么？

第十幕：互动实验室——亲手把任意一个比特改坏，再让汉明码找出它

实验一：从1011开始

1011

0110011

0

1

1

0

0

1

1

000

0

1011

实验观察一：只翻转第6位

实验观察二：同时翻转第3、5位

实验观察三：打开SECDED

实验观察四：一次翻转三个比特

第十一幕：128个七位字符串，为什么恰好被16个码字全部占满？

七位空间一共有多少个点？

每个合法码字周围有八种允许接收结果

不同合法码字的汉明球不能重叠

一般的汉明界

一个非常深刻的推论

第十二幕：三项校验，为什么可以写成一个矩阵？

在二元域上进行计算

汉明码的校验矩阵

为什么矩阵的七列这么特别？

实验一：从`1011`开始