海明码校验与纠错

2026 大纲 三（三）2 纠错编码（海明码）。码距 $d_{min}$ 与检错/纠错能力的关系集中在本篇；模 2 除法与生成多项式属于 CRC 的机制，在《差错检测》。

一、检出来了只能丢弃，能不能直接改

上一节的 CRC 只回答"是/否有错"——余数非 0 就整帧丢弃，连错在哪一位都不知道。丢弃意味着要等对方重传，而有些场景根本没有"对方"可等：光盘和闪存读出来一位错了，找谁重传？深空探测器的信号跑了几个小时才到，重传一次要再等几个小时。

所以要问：能不能让接收端自己把错位找出来、就地改回去？ 能，代价是多带冗余。这一节讲的海明码就是最基本的一种纠错码。

要理解它为什么行、能行到哪一步，得先建立一个几何直觉。

二、码距：一切能力的来源

码距是两个等长码字对应位不同的比特数； $d_{min}$ 是所有合法码字两两码距的最小值。

把每个合法码字想象成空间中的一个点，出错就是从这个点往外走若干步（走一步 = 翻一位）。三条能力于是全部变成距离条件：

检测 $e$ 位错误＝从任何合法码字走 $e$ 步以内绝不踩到另一个合法码字（踩到就会被误判成"没错"），故 $d_{min} \geq e + 1$ ；
纠正 $t$ 位错误还要能唯一判断出发点：以合法码字为心、半径 $t$ 的球必须互不相交，否则落在交叠区的码字无从归属，故 $d_{min} \geq 2 t + 1$ ；
两者兼得（ $e > t$ ）则 $d_{min} \geq e + t + 1$ 。

$d_{min}$	能力
2	检 1 位（奇偶校验）
3	检 2 位或纠 1 位（二选一）
4	检 2 位且纠 1 位

检 2 与纠 1 为什么不能兼得，值得说透，因为这是最容易被当成记忆项的一条。设 $d_{min} = 3$ ，合法码字 $A$ 、 $B$ 相距 3。若收到的码字距 $A$ 为 2、距 $B$ 为 1，你要么按"纠 1 位"把它纠成 $B$ （错了，本来是 $A$ 发出的），要么按"检 2 位"报告"出错但不纠"——同一个接收码字不能既被判为 2 位错、又被判为离 $B$ 只差 1 位，两套判据在这里打架。距离拉到 4，2 位错的接收码字与任何合法码字的距离都是 2，就不可能与 1 位错混淆了。

三、校验位要几个

$r$ 个校验位在接收端会算出 $r$ 个校正因子（每个取 0 或 1），拼起来共 $2^{r}$ 种取值，要一一对应地区分：1 种"无错" + $n = k + r$ 种"第 $j$ 位错"。于是

2^{r} \geq n + 1 = k + r + 1

式子里两个加项各有来历，漏掉任一项都会把 $r$ 算小： $+ r$ 是"校验位自己也要被保护"（所以是 $n$ 种而不是 $k$ 种）， $+ 1$ 是"留一个编号表示无错"。

取满足不等式的最小 $r$ ：

数据位 $k$	校验位 $r$	总位数 $n$	验算
1	2	3	$2^{2} = 4 \geq 1 + 2 + 1 = 4$ ✓
2 – 4	3	5 – 7	$2^{3} = 8 \geq 4 + 3 + 1 = 8$ ✓
5 – 11	4	9 – 15	$2^{4} = 16 \geq 11 + 4 + 1 = 16$ ✓
12 – 26	5	17 – 31	$2^{5} = 32 \geq 26 + 5 + 1 = 32$ ✓
27 – 57	6	33 – 63	$2^{6} = 64 \geq 57 + 6 + 1 = 64$ ✓

边界自己会算，不要背表： $k = 5$ 时试 $r = 3$ 得 $8 \geq 9$ 不成立，试 $r = 4$ 得 $16 \geq 10$ 成立。每段右端点都取等号，那是校正因子刚好用完、一个不浪费的位置。

编码效率随 $k$ 增大而提高（ $4 / 7$ 、 $11 / 15$ 、 $26 / 31$ ），因为 $r$ 按对数增长而 $k$ 线性增长。代价是长码字里出现 2 位错的概率也随之上升，而海明码只能纠 1 位——所以 $k$ 不能无限放大。

四、位置与分组

校验位放在第 $2^{i}$ 位，即第 1、2、4、8 位。注意 $p_{3}$ 在第 4 位不是第 3 位（第 3 位是数据位），位置号从 1 开始、没有第 0 位。

分组规则：位置号写成二进制，第 $i$ 位（从第 0 位算起）为 1 的所有位置归 $p_{i + 1}$ 管，每组取偶校验。每组含它自己—— $p_{1}$ 管第 1,3,5,7 位，第 1 位就是 $p_{1}$ 。

以 $k = 4, r = 3$ 、共 7 位为例：

位置	1	2	3	4	5	6	7
二进制	001	010	011	100	101	110	111
内容	$p_{1}$	$p_{2}$	$d_{1}$	$p_{3}$	$d_{2}$	$d_{3}$	$d_{4}$
被谁覆盖	$p_{1}$	$p_{2}$	$p_{1}, p_{2}$	$p_{3}$	$p_{1}, p_{3}$	$p_{2}, p_{3}$	$p_{1}, p_{2}, p_{3}$

于是 $p_{1} = d_{1} \oplus d_{2} \oplus d_{4}$ （第 1,3,5,7 位）、 $p_{2} = d_{1} \oplus d_{3} \oplus d_{4}$ （第 2,3,6,7 位）、 $p_{3} = d_{2} \oplus d_{3} \oplus d_{4}$ （第 4,5,6,7 位）。

校验位为什么非放 $2^{i}$ 位不可，有三条理由，缺一不可：

$2^{i}$ 的二进制里只有 1 个 1，所以第 $2^{i}$ 位只被 $p_{i + 1}$ 一个校验位覆盖。这样每个校验位的值可由"自己那一组里的数据位"直接算出，不依赖别的校验位——编码时不会出现循环依赖。若把校验位放末尾连成一片，比如 7 位码字里 $p_{1}, p_{2}, p_{3}$ 占第 1,2,3 位，那么第 3 位（二进制 011）会同时被 $p_{1}$ 和 $p_{2}$ 覆盖，算 $p_{1}$ 要先知道 $p_{2}$ 、算 $p_{2}$ 又要先知道 $p_{1}$ ，解不开。
每个位置的"被覆盖集合"互不相同，且恰好等于该位置号的二进制展开。这是下一节"校正因子拼起来就是错位编号"的前提。
覆盖集合的并集是全部位置（1 到 $n$ 中没有任何一个位置的二进制是全 0），所以每一位都在保护之下，包括校验位自己。

⚠️ 有两种书写顺序。 本篇把位 1 写在最右端；另一种按 $H_{1} H_{2} \dots H_{n}$ 从左往右排。位号与分组规则完全相同，只是落笔顺序互为逆序。找 $p_{1}$ 在哪一端即可判断——它永远在位号 1 那一侧。

五、纠错：校正因子拼起来为什么就是错位编号

发送时每一组的异或都被配成 0。设第 $j$ 位翻转、其余位都对，对任意一组：第 $j$ 位在这组里则异或从 0 变 1（ $S = 1$ ），不在则这组仍全对（ $S = 0$ ）。而"第 $j$ 位在不在第 $i$ 组"的判据，正是位置号 $j$ 的二进制第 $i$ 位是不是 1，即

S_{i} = (j 的二进制第 i - 1 位)

把所有 $S_{i}$ 由低位到高位拼起来，得到的就是 $j$ 本身的二进制表示。分组规则用位置号的二进制来定，读出来的自然也是位置号的二进制——同一件事说了两遍。 $S_{1}$ 来自"位置号第 0 位为 1 的那一组"，当然对应最低位；顺序是推出来的，想不起来回分组表验算一次即可。

全 0 能表示"无错"，是因为位置编号从 1 开始，编号 0 被空了出来——这正是 $2^{r} \geq n + 1$ 里那个 $+ 1$ 的来历。

编码与纠错各走一遍

编码：数据 $D = 1011$ ，即 $d_{1} = 1, d_{2} = 0, d_{3} = 1, d_{4} = 1$ 。

第 1 步定 $r$ ：试 $r = 3$ ， $2^{3} = 8 \geq 4 + 3 + 1 = 8$ ✓，故 $r = 3$ 、 $n = 7$ 。

第 2 步把数据位填进非 $2^{i}$ 的位置（按位置号从小到大依次放 $d_{1} \sim d_{4}$ ）。先占好数据位，是因为校验位的值必须等数据位全部就位后才能算——它们是数据位的函数。

第 3 步算校验位（每组异或为 0）：

p_{1} = 1 \oplus 0 \oplus 1 = 0 p_{2} = 1 \oplus 1 \oplus 1 = 1 p_{3} = 0 \oplus 1 \oplus 1 = 0

第 4 步拼出码字：

位置	7	6	5	4	3	2	1
内容	$d_{4}$ =1	$d_{3}$ =1	$d_{2}$ =0	$p_{3}$ =0	$d_{1}$ =1	$p_{2}$ =1	$p_{1}$ =0

海明码 $= 1100110$ 。自查：第 1,3,5,7 位是 $0, 1, 0, 1$ 异或为 0 ✓；第 2,3,6,7 位是 $1, 1, 1, 1$ 异或为 0 ✓；第 4,5,6,7 位是 $0, 0, 1, 1$ 异或为 0 ✓。三组全为 0 才算编对。

纠错：接收到 $1000110$ （位 7 到位 1 依次为 $1, 0, 0, 0, 1, 1, 0$ ）：

S_{1} = b_{1} \oplus b_{3} \oplus b_{5} \oplus b_{7} = 0 \oplus 1 \oplus 0 \oplus 1 = 0

S_{2} = b_{2} \oplus b_{3} \oplus b_{6} \oplus b_{7} = 1 \oplus 1 \oplus 0 \oplus 1 = 1

S_{3} = b_{4} \oplus b_{5} \oplus b_{6} \oplus b_{7} = 0 \oplus 0 \oplus 0 \oplus 1 = 1

$S_{3} S_{2} S_{1} = 110_{2} = 6$ → 第 6 位出错。把第 6 位由 0 翻回 1，恢复出 $1100110$ ，与发送的一致。

为什么可以直接翻转：在"至多 1 位错"的前提下，校正因子给出的编号是唯一的候选。若实际错了 2 位，这个前提不成立，得到的编号会指向一个无辜的位置——这就是误纠。

交互可视化

加载可视化中...

六、加全局校验位：把"二选一"变成"兼得"

在码字最前（或最后）加一个全局校验位 $p_{0}$ ，让整个码字的异或为 0。原来相距 3 的两个合法码字，1 的个数奇偶性必然相反，加上全局偶校验位后 $p_{0}$ 必然不同，距离从 3 变成 4；原本距离为偶数的码字对不受影响。

$S$	$P$	判定	动作
$= 0$	$= 0$	无错	接受
$\neq 0$	$= 1$	1 位错	按 $S$ 定位并纠正
$\neq 0$	$= 0$	2 位错	只能检出，不可纠（纠了必错）
$= 0$	$= 1$	全局校验位自己错了	数据无损，接受

$P$ 记录错误位数的奇偶性， $S \neq 0$ 说明确实有错；两个信号交叉才把 1 位错与 2 位错分开。基本海明码分不开，正是因为它只有 $S$ 这一路信号。

第三行要特别记住： $S \neq 0$ 且 $P = 0$ 时， $S$ 指向的一般是无辜的第三位，纠下去会把 2 位错扩大成 3 位错。正确动作是报错并丢弃，不是纠正。

七、边界：海明码不擅长什么

只能纠 1 位。 实际链路上的差错以突发错误为主，一次影响连续多位；对突发错误 $d_{min} = 3$ 的海明码不但纠不了，2 位以上还会误纠。经典对策是交织：把连续 $P$ 个码字排成矩阵、每行一个码字、按列的顺序发送，线路上连续的 $P$ 个比特分别来自 $P$ 个不同码字，只要突发长度 $\leq P$ ，每个码字最多摊到 1 位错。

冗余开销大于检错码。 海明码 $k = 4$ 时效率只有 $4 / 7$ ，而 CRC-32 给 1500 字节数据只加 4 字节、效率约 99.7%——这就是有线链路层普遍选"CRC 检错 + 丢弃 + 上层重传"、把海明码留给内存 ECC 这类重传不可得的场景的原因。

两者不是替代关系，选谁取决于一句话：重传一次贵，还是每帧多带冗余贵。

本节小结

能力全来自码距：检 $e$ 位要 $d_{min} \geq e + 1$ ，纠 $t$ 位要 $d_{min} \geq 2 t + 1$ ，兼得要 $d_{min} \geq e + t + 1$ 。海明码 $d_{min} = 3$ ，故检 2 与纠 1 只能二选一；加全局校验位提到 4，多出"错误位数奇偶性"信号 $P$ 才兼得，且 $S \neq 0$ 且 $P = 0$ 时只报不纠。
$2^{r} \geq k + r + 1$ 中 $+ r$ 是校验位自己也在保护范围内、 $+ 1$ 是给"无错"留的编号。校验位放第 $2^{i}$ 位最要紧的理由是该位只被一个校验位覆盖，编码时不会循环依赖。
分组规则与纠错读法是同一条规则正反用两遍：按位置号二进制分组，所以校正因子拼起来读出的就是出错位的位置编号。边界上海明码只纠 1 位，对突发错误要靠交织摊开，效率也不及检错码。

考点速记

本节在真题里被考过的形式，考的不是海明码的编码流程，而是它背后那三条不等式——给一个编码集，问它的检错与纠错能力（cn-2025-34，编码集 {1001 1010, 0101 1100, 1111 0000, 0000 1111}）。三步：

两两算码距（对应位不同的比特数）。4 个码字有 6 对，逐对异或数 1 的个数即可。本题除了后两个码字相距 8，其余各对都是 4。
取最小值得 $d_{min}$ ——本题 $d_{min} = 4$ 。
代两条不等式：检 $e$ 位需 $d_{min} \geq e + 1 \Rightarrow e \leq 3$ ；纠 $t$ 位需 $d_{min} \geq 2 t + 1 \Rightarrow 4 \geq 2 t + 1 \Rightarrow t \leq 1.5 \Rightarrow t = 1$ 。答"不超过 3 位错的 100% 检错、不超过 1 位错的纠错"。

第 3 步是四个选项唯一的分岔口：选项通常在检 2/检 3、纠 1/纠 2 之间排列组合，算错 $d_{min}$ 或用错不等式都会落进干扰项。 $t$ 要向下取整—— $d_{min} = 4$ 时 $t \leq 1.5$ 只能取 1，不能凑成 2。

海明码本身的编码与纠错流程（定 $r$ 、填位置、算校验位、读校正因子）在 cn 真题里不单独成题，但它在计算机组成原理里是考过的，而且第二部分那三条不等式正是这类题的公共依据。

易错：纠 $t$ 位要向下取整。 $d_{min} = 4$ 时 $2 t + 1 \leq 4$ 给出 $t \leq 1.5$ ，只能纠 1 位。 $d_{min}$ 是偶数时，多出来的那一格用在检错上而不是纠错上。

易错："检 $e$ 位"与"纠 $t$ 位"是两套独立的不等式，不能相加使用。 同时要求检 $e$ 纠 $t$ （ $e > t$ ）时用第三条 $d_{min} \geq e + t + 1$ ，比单看两条都严。

易错： $d_{min}$ 是所有码字对里的最小值，不是随便挑一对算出来的值。漏算某一对就可能把 $d_{min}$ 取大。

易错： $2^{r} \geq k + r + 1$ 里的 $+ r$ 和 $+ 1$ 都不能漏——校验位自己也要被保护，还要留一个编号表示无错。写成 $2^{r} \geq k + 1$ 会把 $r$ 算小。

易错：校验位在第 $2^{i}$ 位（1、2、4、8），不是第 1、2、3、4 位。 $p_{3}$ 在第 4 位，第 3 位是数据位。

易错：加了全局校验位之后， $S \neq 0$ 且 $P = 0$ 判为 2 位错，此时只能报错不能纠。按 $S$ 去纠会把 2 位错变成 3 位错。

教材出处

谢希仁《计算机网络》（第 8 版）全书未涉及海明码，因此本篇的编码原理部分无该书可引；此处只引与"链路层要不要纠错"这一判断直接相关的段落，其余结论未在正文中标注页码出处。

谢希仁《计算机网络》（第 8 版）p79（3.2.1 PPP 协议应满足的需求，第 1 条"简单"）：说明为什么 TCP/IP 体系的链路层不采用纠错编码——"IETF 在设计互联网体系结构时把其中最复杂的部分放在 TCP 协议中……在这种情况下，数据链路层没有必要提供比 IP 协议更多的功能。因此，对数据链路层的帧，不需要纠错，不需要序号，也不需要流量控制"；同页给出链路层的实际动作："接收方每收到一个帧，就进行 CRC 检验。如 CRC 检验正确，就收下这个帧；反之，就丢弃这个帧，其他什么也不做。"
同书 p80：再次确认这一分工——"在 TCP/IP 协议族中，可靠传输由运输层的 TCP 协议负责，因此数据链路层的 PPP 协议不需要进行纠错，不需要设置序号，也不需要进行流量控制。"
同书 p78：链路层用 CRC 只能实现"无比特差错"而非可靠传输，是理解"检错 + 重传"路线与"纠错编码"路线分野的前提。

真题练习

2025Q342分 2023Q372分

海明码校验与纠错

一、检出来了只能丢弃，能不能直接改

二、码距：一切能力的来源

三、校验位要几个

四、位置与分组

五、纠错：校正因子拼起来为什么就是错位编号

编码与纠错各走一遍

交互可视化

六、加全局校验位：把"二选一"变成"兼得"

七、边界：海明码不擅长什么

本节小结

考点速记

相关知识

相关文章

交互体验

真题练习

相关真题（2题）

海明码校验与纠错 ​

一、检出来了只能丢弃，能不能直接改 ​

二、码距：一切能力的来源 ​

三、校验位要几个 ​

四、位置与分组 ​

五、纠错：校正因子拼起来为什么就是错位编号 ​

编码与纠错各走一遍 ​

交互可视化 ​

六、加全局校验位：把"二选一"变成"兼得" ​

七、边界：海明码不擅长什么 ​

本节小结 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

相关真题（2题）

海明码校验与纠错

一、检出来了只能丢弃，能不能直接改

二、码距：一切能力的来源

三、校验位要几个

四、位置与分组

五、纠错：校正因子拼起来为什么就是错位编号

编码与纠错各走一遍

交互可视化

六、加全局校验位：把"二选一"变成"兼得"

七、边界：海明码不擅长什么

本节小结

考点速记

相关知识

真题练习