汉明码：三个校验位，纠一个错
一个被穿孔卡片折磨到崩溃的工程师，在 1947 年一个周末想出来的东西。它的构造漂亮到会让你想立刻讲给别人听——而且它顺便定义了「码距」这个此后所有纠错码都要用的概念。
汉明 (7,4) 码能纠 1 个错。那么如果一个 7 位码字里错了 2 位，会发生什么？
一个周末的怒火
1947 年，理查德·汉明（Richard Hamming）在贝尔实验室用一台继电器计算机。机器只在周末给他跑批处理，而它有一个检错电路——发现错误就停机，跳过这个任务。
于是汉明周一早上经常收到的是：「你的任务出错了，没跑。」等下一个周末。
他后来写道，他当时的想法是：「既然机器能发现哪里错了，为什么它不能自己改过来？」
这个「凭什么」造出了世界上第一个纠错码。
从一个校验位开始
先看最简单的检错：奇偶校验位。
数据： 1 0 1 1
1 的个数是 3，奇数
校验位：1 ← 补一个 1，让总数变成偶数
发出： 1 0 1 1 1
# 收方数一下 1 的个数：
# 偶数 → 大概没错
# 奇数 → 【一定有错】，但不知道错在哪
一个校验位给了你一个是非问题的答案：「1 的个数是偶数吗？」一个问题只能区分两种情况：没错 / 有错。
汉明的想法是：那就多问几个问题，而且让这些问题的答案能拼出位置。
把 7 个位置编号 1 到 7。让位置是 2 的幂的那几位（1、2、4）当校验位，其余（3、5、6、7）放数据。
位置： 1 2 3 4 5 6 7
内容： p1 p2 d1 p4 d2 d3 d4
↑ ↑ ↑ ↑
数据位在 3, 5, 6, 7
然后规定每个校验位管哪些位置——看位置编号的二进制：
位置 二进制 第1位 第2位 第4位 1 001 ✓ 2 010 ✓ 3 011 ✓ ✓ 4 100 ✓ 5 101 ✓ ✓ 6 110 ✓ ✓ 7 111 ✓ ✓ ✓ p1（位置1）管所有【二进制最低位是 1】的位置：1, 3, 5, 7 p2（位置2）管所有【二进制第二位是 1】的位置：2, 3, 6, 7 p4（位置4）管所有【二进制第三位是 1】的位置：4, 5, 6, 7
每个校验位让自己管的那一组的 1 的个数变成偶数。
魔术在解码这一步
收方对三组各数一次，得到三个答案（0 = 偶数，正常；1 = 奇数，这组有问题）：
s1 = 第 1,3,5,7 位的异或 s2 = 第 2,3,6,7 位的异或 s4 = 第 4,5,6,7 位的异或 把它们拼成一个二进制数： s4 s2 s1 【这个数就是出错的位置。】 # 为什么？ # 假设第 5 位错了。5 的二进制是 101。 # → 它在 p1 管的组里（101 最低位是 1）→ s1 = 1 # → 它不在 p2 管的组里（101 第二位是 0）→ s2 = 0 # → 它在 p4 管的组里（101 第三位是 1）→ s4 = 1 # → s4 s2 s1 = 101 = 5 ✓ 就是它 # 如果没错：三组都正常，s4s2s1 = 000 = 0。
因为 1、2、4 各自只出现在一个组里（1 = 001 只有最低位，2 = 010 只有第二位，4 = 100 只有第三位）。
这样每个校验位可以独立地被算出来——它管的那一组里只有它自己是校验位，其余全是数据位。
如果校验位放在别处，几个校验位会互相依赖，你得解方程组。汉明这个编号方案让整件事变成了三次独立的异或。
下面这台是真的。点任意一格把那一位翻掉，看三个问题的答案怎么把它指认出来：
112 / 112
点 demo 里那个「把所有 16 × 7 = 112 种单错全试一遍」的按钮。结果是：
| 测试 | 结果 | 说明 |
|---|---|---|
| 16 个码字 × 7 个位置 = 单错 | 112 / 112 全部纠对 | 一个不漏 |
| 16 个码字 × C(7,2) = 双错 | 336 / 336 全部纠错 | 一个也救不了 |
| 最小码距 | 3 | 任意两个码字至少差 3 位 |
| 汉明界 | 16 = 2⁴ | 完美码 |
第二行就是开头那道题的答案，而且它不是缺陷，是必然。
两个码字的汉明距离 = 有多少位不同。
一个码的最小距离 d = 所有码字两两之间距离的最小值。
而这一个数决定了这个码的全部能力：
能【检出】的错误位数： d − 1 能【纠正】的错误位数： ⌊(d − 1) / 2⌋ 汉明 (7,4)：d = 3 → 能检出 2 个错 → 能纠正 1 个错 → 但【不能同时做到】
为什么不能同时？因为「检出 2 个错」的意思是「发现它不是任何一个码字」，而「纠正 1 个错」的意思是「把它归到最近的那个码字」。当真的错了 2 位时，它已经落进了另一个码字的势力范围，译码器分不出这是「离 A 两步」还是「离 B 一步」——它会毫不犹豫地判成 B。
所以答案是 D：纠到第三个位置去，越纠越坏。它不但没救回来，还多引入了一个错。
「完美码」是什么意思
7 位一共有 2⁷ = 128 种可能的比特串。
每个码字要能纠 1 个错，就得独占一个「势力范围」：它自己 + 它翻 1 位能到的 7 个串 = 8 个串。
能塞下的码字数 ≤ 128 / 8 = 【16】 而汉明 (7,4) 恰好有 2⁴ = 【16】 个码字。
不多不少，一个位置都没浪费。这种「取到界」的码叫完美码（perfect code）。
完美码极其罕见。除了平凡的情况，二元完美码只有三族：汉明码、重复码（奇数长度）、以及 Golay(23,12) 码。就这些，1973 年被证明再没有别的了。
（Golay(23,12) 是个奇迹般的存在：23 位纠 3 个错，C(23,0)+C(23,1)+C(23,2)+C(23,3) = 1+23+253+1771 = 2048 = 2¹¹，而码字数 2¹² × 2¹¹ = 2²³。四个二项式系数加起来正好是 2 的幂——这个巧合没有已知的深层原因。NASA 的旅行者号用它传回了木星和土星的照片。）
ECC 内存用的是汉明码的一个变种：SECDED（Single Error Correct, Double Error Detect）。
做法是在汉明码上再加一个总体奇偶位，把最小码距从 3 提到 4。于是：
校验子 = 0，总奇偶正确 → 没错 校验子 ≠ 0，总奇偶【错】 → 错了 1 位，位置就是校验子，纠回来 校验子 ≠ 0，总奇偶【对】 → 错了 2 位，【报错，别乱纠】 # 那个多出来的 1 位，买到的是「知道自己救不了」这个能力。 # 而对服务器来说，「知道自己错了」比「悄悄给出错数据」重要得多。
典型规格是 (72, 64)：64 位数据 + 8 位校验。这就是为什么 ECC 内存条上的芯片是 9 的倍数而不是 8 的倍数。
宇宙射线和 α 粒子确实会翻内存的位——这叫软错误。在数据中心的规模上，这不是理论风险：没有 ECC 的大规模集群会稳定地产生莫名其妙的崩溃和数据损坏。这也是为什么服务器内存和消费级内存价格差那么多。
顺带一提这个设计哲学：SECDED 宁可花一位去买「知道自己救不了」，也不肯冒「自信地给出错误答案」的风险。这是一条很好的工程原则，远不止用在内存上。
这是纠错码最危险的性质，也是它和「检错」的根本区别：
- 检错失败的方式是「没发现」——你拿到坏数据，但至少系统没骗你说它是好的。
- 纠错失败的方式是「纠到别处」——你拿到一份看起来完全正常、校验全部通过的错误数据。
所以严肃的系统会分层：底层纠错（尽量救），上层再加一个独立的完整性校验（比如 CRC 或者哈希）来兜底。ZFS、Btrfs 这类文件系统的端到端校验和，防的就是这个——硬盘的 ECC 说「我修好了」，但它可能修错了。
336 种双错，336 种全部纠错。这不是实现的 bug，是最小码距为 3 的数学后果。
如果你选了 A，那是把汉明码当成 SECDED 了——要做到「检出双错并报警」，必须再多花一个校验位。那一位不提高纠错能力，只买「知道自己不行」这一件事。
而这件事值不值一位？在服务器内存里，值。因为一份被自信地纠错的坏数据，可能会一路写进数据库。
这一章的一句话
三个校验位问三个「这几位里 1 是偶数个吗」，三个答案拼成的二进制数正好是出错的位置。112 种单错全纠对，336 种双错全纠坏——而这两句话是同一个「最小码距 3」的两面。
下一章把这卷收尾，从汉明码一路走到你今天用的东西：为什么二维码盖住三成还能扫、为什么 SSD 的原始错误率高得吓人却看起来从不出错、以及为什么 WiFi 提速靠加带宽而不是靠让路由器喊得更大声。最后那个问题有一个只有一行的答案，而它藏在 log 的括号里外。