汉明，1950年：用三个校验位修复一个错误

本文由AI系统依据所引资料撰写并翻译，按News编辑方法进行了自动检查。

维护更新 — 2026年10月7日。 由于无法通过现有访问权限找回旧封面的原始文件和生成凭据，封面已更换。新图像由原生图像工具返回并经过视觉检查；文件、生成指令和参考来源保存在非公开编辑记录中。旧封面及其未经核实的来历仍保留在历史记录中。这是一幅插画，并非实验证据；核心科学结果保持不变。

AI生成的概念插画：汉明码（7,4）用4个数据位和3个校验位，纠正每个码块中的单比特翻转。方块是象征性表达，并非实际电路。

阅读公式之前

比特的值是0或1。翻转就是将一个值变成另一个。奇偶校验关注一组比特中1的个数是偶数还是奇数。例如101含有两个1，因此具有偶校验性质。冗余是为接收方检查数据而额外传送的信息。这里，三组相互重叠的检查能够定位一个翻转的比特，前提是七位块中至多发生一次翻转。

理解思路可以先看第3节的例子，再回到第2节的公式。要验证结果，可使用下方完整程序。请先想一想：检查通过，是否就证明没有任何比特发生变化？第5节解释为什么答案取决于错误模型。

1. 用有结构的冗余提高可靠性

1950年4月，Richard W. Hamming在Bell System Technical Journal发表了《Error Detecting and Error Correcting Codes》。问题来自实际计算：无人值守时，发现故障可能意味着停机；若能定位并修复，计算就可能继续。论文给出的是明确的二进制构造，并不承诺修复任意损坏。[1,2]

进步在于让冗余携带诊断信息。将四个比特各重复三遍，需要传输十二位；汉明码用七位保护同样的四个数据位，使其能够抵抗该块中任意一个比特翻转。这是组织冗余的不同方式，并不证明一种码适用于所有信道。压缩减少冗余，纠错则有控制地增加冗余。

2. 七个位置，三项检查

把传输位置编号为1至7。位置1、2、4放校验位，位置3、5、6、7放数据d₁、d₂、d₃、d₄。符号⊕表示异或，即模2加法，所以1 ⊕ 1 = 0。下式设置偶校验。p的下标指位置，而不是校验的先后顺序。[1, §3]

$p_1=d_1\oplus d_2\oplus d_4$p1​=d1​⊕d2​⊕d4​

$p_2=d_1\oplus d_3\oplus d_4$p2​=d1​⊕d3​⊕d4​

$p_4=d_2\oplus d_3\oplus d_4$p4​=d2​⊕d3​⊕d4​

接收端检查{1,3,5,7}、{2,3,6,7}和{4,5,6,7}。校验不满足时得到伴随式位1，满足时为0，分别记作s₁、s₂、s₄。在至多一个比特翻转的假设下，错误位置j为：

$j=s_1+2s_2+4s_4$j=s1​+2s2​+4s4​

只有在这一假设下，伴随式为零才意味着没有错误；它不是普遍的完整性保证。

3. 可以复算的纠错过程

取数据1010，算得p₁ = 1、p₂ = 0、p₄ = 1。按位置从左向右写，发送码字为1011010。若第6位翻转，接收字就是1011000。第一项校验为偶数，第二和第三项为奇数。因此(s₁,s₂,s₄) = (0,1,1)，j = 0 + 2 + 4 = 6。把第6位翻转回来，再读位置3,5,6,7，恢复数据1010。

用代码制作的科学示意图；比特串精确，不是实验数据。

这是为本文设计的计算示例，不是实验测量。校验位本身翻转也能纠正。前提是块边界和比特位置已知；插入或删除比特属于另一种错误模型。

4. 为什么这种构造有效

三个二进制校验结果共有八种，恰好可以区分七个单错位置和无错状态。一般而言，含r个校验位、总长n位的二进制码，为纠正一个翻转至少需要n + 1种不同的伴随式：

$2^r\ge n+1$2r≥n+1

汉明构造在n = 2ʳ − 1、数据位数k = n − r时达到这一计数。r = 3时，n = 7、k = 4。最小汉明距离，即两个不同合法码字之间不同位置数的最小值，为3。如果某接收字与两个合法码字都只差一位，那两个码字最多相差两位，产生矛盾。

共有16个合法码字，每个码字连同其七个单次翻转邻居组成一个集合。这些集合互不重叠，覆盖全部128种七位字：16 × 8 = 128。“完美码”描述的是这种填充性质，并不表示在任意噪声下都不会出错。[1, §§5,7]

5. 两个错误造成的陷阱

两个比特翻转总会产生非零伴随式，所以只负责标记非法字的检测器能够发现它们。但若译码器把每个非零伴随式都解释为单错，就可能误纠。位置2和5同时翻转，与仅位置7翻转产生相同的伴随式。再“纠正”第7位，便留下三个错误位，并得到另一个合法码字。

增加第八位，使八位整体保持偶校验，最小距离就提高到4。这种扩展码支持单错纠正、双错检测，即SECDED。下表的判断以至多两个翻转为前提。q是八个接收位的整体奇偶校验值。[1, §4]

三个及以上错误超出了这一保证。SECDED译码器可能对其中一些情况误纠；“双错检测”不等于能诊断所有更严重的故障。

6. 明确假设下的数值收益

假设每个传输比特独立地以p = 0.01的概率翻转，对0和1相同；编码和译码均无误，块边界已知。对这里的七位码和译码器，恢复出的四位消息出错，当且仅当块中至少有两位翻转：

$\begin{aligned} P_{\rm fail}&=1-(1-p)^7\\ &\quad-7p(1-p)^6. \end{aligned}$Pfail​​=1−(1−p)7−7p(1−p)6.​

结果约为0.002031，即0.2031%的块。若直接发送四个数据位，则1 − (1 − p)⁴ = 0.039404，即3.9404%的消息含错。这是消息错误概率，不是残余比特错误率，也不是设备性能的实测值。

代价是每四个数据位增加三位，传输位数增加75%，码率为4/7 ≈ 0.5714数据位／传输位。比较固定了p，但没有同时固定带宽、传输时间和每条消息的能耗。

7. 结果保证什么，不保证什么

这一工作的持久贡献，是把代数与可靠性以可构造的方式连接起来：让合法码字保持距离，计算简短校验，再定位有限范围内的故障。七位例子可以穷举验证。本文检查了16条消息及其无错或单错的128种情况，还检查了扩展码中448种双错情况。

它不能修复任意突发错误、损坏的软件、恶意篡改或同步丢失。真实系统必须使编码适合故障模型，并保护编码器、译码器与周边逻辑。汉明论文没有给出现代硬件的测量数据，本文的数值例子也不作这种主张。它用一个明确的有限构造补充香农的通信极限理论，而不是提供在所有条件下都达到信道容量的万能方案。

8. 复现有限计算

步骤HAMMING-REPRO-1。将完整Python代码复制到reproduce_hamming.py，然后运行python3 reproduce_hamming.py。程序只使用Python标准库，无需网络、下载数据或随机种子。本次编辑修订使用CPython 3.12.14执行。位置从1开始编号，第八位使整体保持偶校验。程序枚举全部16条消息，另行通过奇偶校验约束构造所有合法七位字，再与编码器输出比较。

预期输出为status PASS、codewords 16、minimum_distances [3, 4]。计数依次为：七位码无错或单错时正确恢复128例；八位码对应144例；扩展码检测双错448例；七位译码器误纠双错336例；本文八位译码器误纠三错896例。最后两项是阴性对照，展示的是边界而非纠错成功。p = 0.01时，coded_message_error约为0.00203104163494，uncoded_message_error为0.03940399。这些概率假设固定p下的独立翻转，并非在相同能耗或带宽下比较。

"""News HAMMING-REPRO-1: finite mathematical check, not hardware validation."""
from itertools import combinations, product
import json
import platform


def encode(data):
    a, b, c, d = data
    return (a ^ b ^ d, a ^ c ^ d, a, b ^ c ^ d, b, c, d)


def syndrome(word):
    a, b, c, d, e, f, g = word[:7]
    return (a ^ c ^ e ^ g) + 2 * (b ^ c ^ f ^ g) + 4 * (d ^ e ^ f ^ g)


def flip(word, positions):
    result = list(word)
    for position in positions:
        result[position - 1] ^= 1
    return tuple(result)


def decode7(word):
    position = syndrome(word)
    return flip(word, (position,)) if position else word


def decode8(word):
    position, parity = syndrome(word), sum(word) % 2
    if parity:
        return flip(word, (position or 8,))
    return None if position else word


def distance(a, b):
    return sum(x != y for x, y in zip(a, b))


def require(condition, label):
    if not condition:
        raise RuntimeError(label)


messages = list(product((0, 1), repeat=4))
code7 = [encode(data) for data in messages]
code8 = [word + (sum(word) % 2,) for word in code7]
# Independent enumeration uses parity sums rather than the encoder equations.
groups = ((1, 3, 5, 7), (2, 3, 6, 7), (4, 5, 6, 7))
oracle = {
    word for word in product((0, 1), repeat=7)
    if all(sum(word[p - 1] for p in group) % 2 == 0 for group in groups)
}
require(len(set(code7)) == 16 and set(code7) == oracle, "codebook")
min7 = min(distance(a, b) for a, b in combinations(code7, 2))
min8 = min(distance(a, b) for a, b in combinations(code8, 2))
require((min7, min8) == (3, 4), "minimum distances")
counts = {"seven_zero_or_one": 0, "eight_zero_or_one": 0,
          "eight_double_detected": 0, "seven_double_miscorrected": 0,
          "eight_triple_miscorrected": 0}
for word in code7:
    for positions in [()] + [(i,) for i in range(1, 8)]:
        require(decode7(flip(word, positions)) == word, "seven-bit recovery")
        counts["seven_zero_or_one"] += 1
    for positions in combinations(range(1, 8), 2):
        received = flip(word, positions)
        require(syndrome(received) != 0, "double error detectable")
        require(decode7(received) != word, "double error outside correction guarantee")
        counts["seven_double_miscorrected"] += 1
for word in code8:
    for positions in [()] + [(i,) for i in range(1, 9)]:
        require(decode8(flip(word, positions)) == word, "eight-bit recovery")
        counts["eight_zero_or_one"] += 1
    for positions in combinations(range(1, 9), 2):
        require(decode8(flip(word, positions)) is None, "double error must be flagged")
        counts["eight_double_detected"] += 1
    for positions in combinations(range(1, 9), 3):
        result = decode8(flip(word, positions))
        require(result is not None and result != word and result in code8,
                "triple error counterexample")
        counts["eight_triple_miscorrected"] += 1
require(list(counts.values()) == [128, 144, 448, 336, 896], "case counts")
require(encode((1, 0, 1, 0)) == (1, 0, 1, 1, 0, 1, 0), "worked example")
require(syndrome((1, 0, 1, 1, 0, 0, 0)) == 6, "worked syndrome")
p = 0.01
failure = 1 - (1-p)**7 - 7*p*(1-p)**6
uncoded = 1 - (1-p)**4
require(abs(failure - 0.00203104163494) < 1e-12, "probability")
print(json.dumps({"protocol": "HAMMING-REPRO-1", "python": platform.python_version(),
                  "codewords": len(code7), "minimum_distances": [min7, min8],
                  "counts": counts, "p": p, "coded_message_error": failure,
                  "uncoded_message_error": uncoded, "status": "PASS"}, indent=2))

PASS表示这些有限数学检查通过，不代表硬件性能、对其他错误模型的稳健性或独立复现。python字段记录你的解释器版本，可能不同。若出现RuntimeError，请保留脚本与完整输出，检查报错所指项目；部分执行不能视为验证通过。

本文的News编辑方法

2026-10-03 — 修订HAMMING-EN-2增加了循序渐进的导读和完整复现步骤。科学正文与代码绘图保留自HAMMING-EN-1。本次更新在1950年论文及MIT第5.6–5.7节中重新核对了构造与边界，并执行了有限计算程序。撰写和翻译由AI完成，未经独立专家评审或人工验证。

资料来源

[1] R. W. Hamming — Error Detecting and Error Correcting Codes — DOI: 10.1002/j.1538-7305.1950.tb00463.x.

[2] Nokia Bell Labs — Error Detecting and Error Correcting Codes.

[3] MIT 6.02 — Coping with Bit Errors using Error Correction Codes.