海明码详解

2026 大纲的「二、数据的表示和运算」与「三、存储器层次结构」均已不含校验码，本篇不对应任何条目编号；但纠错编码在 408 计算机网络「三（三）差错控制」 中仍是纲内内容，海明码正属此列。内存 ECC 用的就是它的 SEC-DED 变体。

怎么分配时间：备考 CN 差错控制的按纲内内容读；只复习 CO 的把编码与纠错的流程走一遍即可，不必做题训练。

让每一位留下互不相同的"指纹"

奇偶校验只能告诉你"有错"，因为整个码字只归入一个校验组，失配时无从分辨是哪一位坏了。海明码的做法是：

🔴 把每一位分配到多个校验组里，且每一位所属组的组合各不相同。 某一位出错时，包含它的那些组全部失配、不含它的组不受影响——这个失配模式就是这一位的"指纹"。再把指纹设计成"位编号的二进制"，读出失配模式就直接读出了出错的位置。

这一句话解释了海明码的每一处设计。三条最容易被当成"规定"来背的，其实都是它的必然推论：

🔴 位编号从 1 开始，不是从 0。 编号 0 的二进制是全 0、不属于任何校验组，出错时故障字仍为 0，与"无错"无法区分。全 0 这个状态必须留给无错。

🔴 校验位必须占 $2^j$ 号位（1、2、4、8……）。 只有这些编号的二进制只含一个 1，即各自只属于一个组。校验位 $P_{2^j}$ 由第 $j$ 组其余成员算出；若它同时还属于别的组，算 $P_1$ 要用 $P_2$、算 $P_2$ 又要用 $P_1$，互相依赖就解不出来了。

🔴 分组规则：位编号的二进制第 $j$ 位为 1，该位就归入第 $j$ 组（由 $P_{2^j}$ 校验）。数据位填进剩下那些编号（3、5、6、7、9……），它们含两个及以上的 1、因而横跨多个组——这正是"让指纹互不相同"所需要的。

交互可视化

加载可视化中...

一、校验位数量：$2^r\ge k+r+1$

$r$ 个校验组的失配情况拼成一个 $r$ 位的故障字（也叫校验和），它一共能表达 $2^r$ 种状态。这些状态必须够用：

$$\underset{\text{每一位各占一种状态}}{\underbrace{n}}+\underset{\text{“无错”也要占一种}}{\underbrace{1}}\le 2^r$$

数据位 $k$	校验位 $r$	总码长 $n$
1	2	3
4	3	7
8	4	12
16	5	21
32	6	38
64	7	71

以 $k=8$ 为例：$r=3$ 时 $2^3=8<8+3+1=12$，不够；$r=4$ 时 $2^4=16\ge 8+4+1=13$，成立。所以取 $r=4$。

🔴 $r$ 在不等式两边都出现，不能直接解，只能从小到大逐个试。 好在 $r$ 增大时左边指数增长、右边线性增长，第一个成立的就是答案。

🔴 那个 $+1$ 不能省。 它是"无错"状态的名额，通常约定用全 0 的故障字表示。省掉的话 $2^r$ 个状态刚好被 $n$ 个出错位占满，接收端就无法表达"什么都没错"。

二、位置与分组

把 $n$ 位码字从左到右编号为 $1,2,3,\dots ,n$，以 7 位码字为例：

编号	二进制	属于哪些组
1	001	$P_1$
2	010	$P_2$
3	011	$P_1,P_2$
4	100	$P_4$
5	101	$P_1,P_4$
6	110	$P_2,P_4$
7	111	$P_1,P_2,P_4$

于是三个校验组分别是

$$P_1:\{1,3,5,7\}{P}_2:\{2,3,6,7\}{P}_4:\{4,5,6,7\}$$

对每组做偶校验，由于每组只含一个校验位，直接令它等于组内其余各位的异或：

$$P_1=b_3\oplus b_5\oplus b_7,P_2=b_3\oplus b_6\oplus b_7,P_4=b_5\oplus b_6\oplus b_7$$

三、故障字为什么直接等于出错位编号

接收端对每一组连同校验位一起重新做偶校验，把结果记为 $S_j$（相符为 0，失配为 1），拼成故障字 $S=S_4{S}_2{S}_1$（高位在左）。

第 $i$ 位参与的组，恰好是 $i$ 的二进制中为 1 的那几位对应的组（这正是分组规则）。第 $i$ 位翻转时，这些组全部由偶变奇（$S_j=1$），其余组不含它、丝毫不受影响（$S_j=0$）。于是 $S$ 的第 $j$ 位为 1 $⟺$ $i$ 的第 $j$ 位为 1，即

$$\boxed{{\displaystyle S=i}}$$

没有出错时所有组都相符，$S=0$——这正是那个 $+1$ 预留的状态。

编码与纠错各走一遍：从数据位填格到故障字定位（想核对自己算校验位、算故障字的每一步时展开）

编码。 $k=4$，数据 $D_1{D}_2{D}_3{D}_4=1001$，依次填入编号 3、5、6、7 号位。

编号	1	2	3	4	5	6	7
内容	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
值	?	?	1	?	0	0	1

逐个算：

$$P_1=b_3\oplus b_5\oplus b_7=1\oplus 0\oplus 1=0$$$$P_2=b_3\oplus b_6\oplus b_7=1\oplus 0\oplus 1=0$$$$P_4=b_5\oplus b_6\oplus b_7=0\oplus 0\oplus 1=1$$

码字（编号 1→7）= 0011001。 自查：$P_1$ 组 $\{0,1,0,1\}$ 两个 1，偶 ✓；$P_2$ 组 $\{0,1,0,1\}$ 偶 ✓；$P_4$ 组 $\{1,0,0,1\}$ 偶 ✓。

纠错。 发送 0011001，传输中第 5 位由 0 翻成 1，接收到 0011101。

组	成员编号	收到的值	异或	$S_j$
$P_1$	1, 3, 5, 7	0, 1, 1, 1	1	1
$P_2$	2, 3, 6, 7	0, 1, 0, 1	0	0
$P_4$	4, 5, 6, 7	1, 1, 0, 1	1	1

$$S=S_4{S}_2{S}_1={101}_2=5$$

第 5 位出错，把它翻回去即得 0011001，与发送的一致。海明码的全部工作量都在分组的设计上，运行时开销极小——这正是它能被做进内存 ECC 硬件的原因。

四、SEC-DED：再加一位换来"且"

标准海明码 $d=3$，按 校验码总述 里的公式只能"纠 1 或 检 2"。SEC-DED（Single Error Correction, Double Error Detection）再加一个校验位 $P_0$，覆盖全部位（包括其他所有校验位），对整个码字做一次偶校验。最小码距增大到 $d=4$，满足 $d\ge e+t+1=2+1+1$，于是可以同时"检 2 纠 1"。

判别逻辑变成两个信号的组合：

$P_0$ 校验	故障字 $S$	结论
相符	$=0$	无错
失配	$\ne 0$	1 位错，位置为 $S$，可纠正
相符	$\ne 0$	2 位错，只能报错，无法定位
失配	$=0$	$P_0$ 自身出错

判据来自奇偶性：错 1 位时全局 1 的个数奇偶性改变（$P_0$ 失配），错 2 位时奇偶性不变（$P_0$ 相符）——而故障字 $S$ 在两种情况下都非零。两个信号一组合，就把"1 位错"和"2 位错"区分开了。

考点速记

1. 海明码把每一位分配到若干个校验组中，让每一位所属组的组合互不相同，失配模式即"指纹"；校验位数量满足 $\boxed{{\displaystyle 2^r\ge k+r+1}}$，$+1$ 是"无错"状态的名额，$r$ 只能从小到大逐个试。
2. 位编号从 1 开始；校验位放在 $2^0,2^1,2^2,\dots$ 号位，因为这些编号的二进制只含一个 1、每个校验位只属于一组，$r$ 个校验位才能彼此独立算出。分组规则是"位编号二进制第 $j$ 位为 1 则归入第 $j$ 组"。
3. 纠错时各组重新校验得故障字，它直接等于出错位的码字编号，全 0 表示无错；标准海明码 $d=3$ 只能"纠 1 位或检 2 位"，SEC-DED 再加一位覆盖全码字的 $P_0$ 使 $d=4$。

这一节在真题里被考过的形式（下方「真题练习」里那道就是本篇的）：

• 给数据位数，问纠一位错至少需要几位校验位：套 $2^r\ge k+r+1$ 逐个试 $r$。8 位数据：$r=3$ 时 $8<12$ 不够，$r=4$ 时 $16\ge 13$ 成立，答 4。⚠️ 两处常错——把 $+1$ 漏掉，或者拿 $2^r\ge k$ 去算（那样 8 位数据会得出 3，正是准备好的错误选项）。

易错：漏掉不等式里的 $+1$。它是"无错"状态的名额。

易错：把 $2^r\ge k+r+1$ 当成可以直接解的方程。$r$ 在两边都有，只能逐个试。

易错：把故障字 $S$ 当成数据位的序号。$S$ 给的是码字位编号——7 位海明码里 1、2、4 是校验位，3、5、6、7 才是 $D_1\sim D_4$，所以 $S=5$ 对应的是 $D_2$。校验位自己出错时故障字同样非零（$S$ 是 1、2 或 4），这种情况数据其实完好。

易错：认为海明码能纠 2 位错。$d=3$ 只支持 $t=1$；发生 2 位错时故障字通常非零，但它指向的是第三个无关的位置，按它去"纠正"反而把数据改得更错——这正是 SEC-DED 存在的理由。

教材出处

• 汉明码的一位纠错能力、检测位数满足 $2^k\ge n+k+1$、代码长度与检测位位数的关系表（表 4.2）、检测位安插在第 $1,2,4,8,\dots ,2^{k-1}$ 位上及各小组的划分（$g_1$ 含 1,3,5,7…，$g_2$ 含 2,3,6,7…，$g_3$ 含 4,5,6,7…）：唐朔飞《计算机组成原理》第 3 版 第 4 章 存储器·汉明码，印刷页 p100–p101
• 纠错过程：接收后重新形成检测位 $P_i$，由 $P_i$ 的状态直接指出错误位置：同书，印刷页 p101

相关知识

校验码总述：码距、奇偶校验与 CRC｜计算机网络博客的海明码

真题练习

相关真题（1题）

2013Q152分

上一篇校验码与码距（纲外）下一篇存储器的分类

相关文章

• 进位计数制与转换
• 真值与机器数：四种编码
• 定点数编码的转换与书写
• 算术逻辑单元（ALU）
• 补码加减运算与溢出判别
• 乘除运算的基本原理与实现结构
• Booth 乘法（补码一位乘）
• 恢复余数除法
• 不恢复余数除法（加减交替法）
• 定点数的移位运算
• C 语言中的数据类型与转换
• 浮点数表示（IEEE 754）
• 浮点数的加减运算
• 数据对齐与大小端（属指令系统章）
• 校验码与码距（纲外）