海明码校验与纠错

考情分析

海明码是 408 中数据链路层和计算机组成原理都可能涉及的知识点，考查频率中等偏高。常见考法是给定一组数据位，要求写出完整的海明码，或者给定一个收到的码字，要求判断并纠正错误位。

考频：★★★

海明距离

海明距离是指两个等长码字之间对应位置上不同比特的个数。例如：

$$d(0100,1110)=2\text{（第1位和第3位不同）}$$

编码方案的最小海明距离 $d_{min}$ 决定了检错和纠错能力：

最小海明距离 $d_{min}$	能力
$d_{min}\ge e+1$	检测 $e$ 位错误
$d_{min}\ge 2t+1$	纠正 $t$ 位错误
$d_{min}\ge e+t+1$（$e>t$）	检测 $e$ 位错误同时纠正 $t$ 位错误

海明码的 $d_{min}=3$，所以可以检测 2 位错误或纠正 1 位错误（二选一，不能同时做到）。如果加上全局校验位，$d_{min}=4$，可以检测 2 位错误并纠正 1 位错误。

校验位的个数

设数据位有 $k$ 位，校验位有 $r$ 位，则总码字长度为 $n=k+r$。校验位的个数 $r$ 需要满足：

$$2^r\ge k+r+1$$

这个不等式的含义：$r$ 个校验位能表示 $2^r$ 种状态，其中 1 种表示"无错"，其余 $k+r$ 种分别对应每一位出错。

常见对应关系：

数据位 $k$	校验位 $r$	总位数 $n$
1	2	3
2-4	3	5-7
5-11	4	9-15
12-26	5	17-31

校验位的位置

海明码中，校验位放在第 $2^i$ 位（$i=0,1,2,\dots$），也就是第 1、2、4、8、16... 位。其余位置放数据位。

以 $k=4,r=3$ 为例（总共 7 位）：

位置	7	6	5	4	3	2	1
内容	$d_4$	$d_3$	$d_2$	$p_3$	$d_1$	$p_2$	$p_1$

其中 $d_1\sim d_4$ 是数据位，$p_1,p_2,p_3$ 是校验位。

校验位的计算

每个校验位 $p_i$ 负责校验一组特定的位。判断某个位置 $j$ 是否被 $p_i$ 校验的规则：将 $j$ 写成二进制，如果第 $i$ 位（从第 0 位开始）为 1，则 $j$ 被 $p_i$ 校验。

对于 7 位海明码：

位置	二进制	被哪些校验位校验
1 = 001	$p_1$	$p_1$
2 = 010	$p_2$	$p_2$
3 = 011	$d_1$	$p_1,p_2$
4 = 100	$p_3$	$p_3$
5 = 101	$d_2$	$p_1,p_3$
6 = 110	$d_3$	$p_2,p_3$
7 = 111	$d_4$	$p_1,p_2,p_3$

因此：

• $p_1$ 校验第 1, 3, 5, 7 位 → $p_1=d_1\oplus d_2\oplus d_4$（使这些位的异或为 0）
• $p_2$ 校验第 2, 3, 6, 7 位 → $p_2=d_1\oplus d_3\oplus d_4$
• $p_3$ 校验第 4, 5, 6, 7 位 → $p_3=d_2\oplus d_3\oplus d_4$

编码例题

已知： 数据 $D=1011$（$d_1=1,d_2=0,d_3=1,d_4=1$）

第 1 步： 放入数据位

位置	7	6	5	4	3	2	1
内容	1	1	0	?	1	?	?

第 2 步： 计算校验位

$$p_1=d_1\oplus d_2\oplus d_4=1\oplus 0\oplus 1=0$$$$p_2=d_1\oplus d_3\oplus d_4=1\oplus 1\oplus 1=1$$$$p_3=d_2\oplus d_3\oplus d_4=0\oplus 1\oplus 1=0$$

第 3 步： 完整的海明码

位置	7	6	5	4	3	2	1
内容	1	1	0	0	1	1	0

海明码为 $1100110$。

检错与纠错过程

接收方收到码字后，分别计算每组校验的结果：

$$S_1=\text{第 1, 3, 5, 7 位的异或}$$$$S_2=\text{第 2, 3, 6, 7 位的异或}$$$$S_3=\text{第 4, 5, 6, 7 位的异或}$$

将 $S_3{S}_2{S}_1$ 组合成二进制数：

• 如果 $S_3{S}_2{S}_1=000$：无错
• 如果 $S_3{S}_2{S}_1\ne 000$：对应的十进制数就是出错位的位置，将该位取反即可纠正

示例： 假设收到 $1\mathbf{0}00110$（第 6 位出错，从 1 变成了 0）。

$$S_1=0\oplus 1\oplus 0\oplus 1=0$$$$S_2=1\oplus 1\oplus 0\oplus 1=1$$$$S_3=0\oplus 0\oplus 0\oplus 1=1$$

$S_3{S}_2{S}_1={110}_2=6$，说明第 6 位出错。将第 6 位从 0 翻转为 1，恢复正确码字 $1100110$。

交互可视化

加载可视化中...

全局校验位

基本海明码的 $d_{min}=3$，只能在"检测 2 位错"和"纠正 1 位错"之间二选一。如果加一个全局校验位 $p_0$（对所有位做异或），$d_{min}$ 变为 4，可以同时做到：

• 1 位错误：$S_3{S}_2{S}_1\ne 0$ 且 $p_0$ 异或结果 $\ne 0$ → 定位并纠正
• 2 位错误：$S_3{S}_2{S}_1\ne 0$ 且 $p_0$ 异或结果 $=0$ → 检测到错误但无法纠正

408 考试中如果题目说"海明码能检测 2 位并纠正 1 位错误"，指的就是带全局校验位的情况。

易错点

1. 校验位位置是 $2^i$，不是第 $i$ 位

$p_1$ 在第 1 位，$p_2$ 在第 2 位，$p_3$ 在第 4 位（不是第 3 位）。第 3 位是数据位。

2. 计算校验位时要把自身位置也算进去

$p_1$ 校验第 1, 3, 5, 7 位，其中第 1 位就是 $p_1$ 自己。计算 $p_1$ 时用其余位的异或结果，使整组异或为 0。

3. 纠错指针的组合顺序

$S_3{S}_2{S}_1$ 的顺序是从高位到低位，对应 $p_3,p_2,p_1$。不要搞反。

高频考点清单

• 海明距离与检错/纠错能力的关系
• 校验位个数的计算：$2^r\ge k+r+1$
• 校验位的位置（$2^i$ 位）和每个校验位覆盖的范围
• 给定数据位，计算完整的海明码
• 给定收到的码字，判断并纠正出错位
• 基本海明码 vs 带全局校验位的海明码

相关文章

• 封装成帧与透明传输
• 差错检测（CRC校验）
• 海明码
• 停止-等待协议
• GBN 后退N帧协议
• SR 选择重传协议
• 滑动窗口协议对比
• PPP 点对点协议
• HDLC 高级数据链路控制
• ALOHA 协议
• CSMA/CD 协议
• CSMA/CA 协议
• 以太网
• 交换机自学习算法
• VLAN 虚拟局域网
• 令牌传递协议

交互体验

前往完整可视化页面 →

真题练习

相关真题（1题）

2025Q34选择题2分

详解

编码集的海明距离决定检错和纠错能力

CRC校验海明码