海明码详解

考情分析

海明码是 408 数据表示章节的高频考点，大题和选择题都会出。常考题型：给定数据位求校验位数量、写出各校验位的值、给定接收码判断是否出错并纠正，以及 SEC-DED 方案的判断逻辑。

海明码的核心思想

海明码在数据位之间插入若干校验位，使码距 $d = 3$ ，从而可以纠正 1 位错误或检测 2 位错误。

精妙之处在于：每个数据位被分配到多个校验组中，出错时各校验组的结果拼起来直接给出出错位的编号。

校验位数量

设数据 $k$ 位，校验位 $r$ 位，总码长 $n = k + r$ 。校验位数量满足：

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

$+ 1$ 是为了表示"无错误"的情况（故障字全 0）。

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

校验位的位置

校验位放在编号为 $2^{i}$ 的位置（ $i = 0, 1, 2, \dots$ ），即第 1、2、4、8、16... 位。其余位置存放数据位。

以 $k = 4$ （数据 $D_{4} D_{3} D_{2} D_{1}$ ）， $r = 3$ 为例：

位编号	7	6	5	4	3	2	1
内容	$D_{4}$	$D_{3}$	$D_{2}$	$P_{3}$	$D_{1}$	$P_{2}$	$P_{1}$

分组规则

校验位 $P_{j}$ （位于第 $2^{j - 1}$ 位）负责校验所有位编号的二进制表示中第 $j$ 位为 1的位。

7 位海明码中，各位编号的二进制表示：

位编号	二进制	属于校验组
1	`001`	$P_{1}$
2	`010`	$P_{2}$
3	`011`	$P_{1}, P_{2}$
4	`100`	$P_{3}$
5	`101`	$P_{1}, P_{3}$
6	`110`	$P_{2}, P_{3}$
7	`111`	$P_{1}, P_{2}, P_{3}$

各校验组的覆盖范围：

校验位	覆盖位编号	覆盖的数据/校验位
$P_{1}$	1, 3, 5, 7	$P_{1}, D_{1}, D_{2}, D_{4}$
$P_{2}$	2, 3, 6, 7	$P_{2}, D_{1}, D_{3}, D_{4}$
$P_{3}$	4, 5, 6, 7	$P_{3}, D_{2}, D_{3}, D_{4}$

编码过程

对每个校验组做偶校验（该组所有位含校验位自身的异或为 0）：

P_{1} = D_{1} \oplus D_{2} \oplus D_{4}

P_{2} = D_{1} \oplus D_{3} \oplus D_{4}

P_{3} = D_{2} \oplus D_{3} \oplus D_{4}

检错与纠错

接收端对每个校验组重新计算偶校验，得到故障字（syndrome） $S_{3} S_{2} S_{1}$ ：

S_{1} = P_{1} \oplus D_{1} \oplus D_{2} \oplus D_{4}

S_{2} = P_{2} \oplus D_{1} \oplus D_{3} \oplus D_{4}

S_{3} = P_{3} \oplus D_{2} \oplus D_{3} \oplus D_{4}

故障字的值 = 出错位的编号：

故障字 $S_{3} S_{2} S_{1}$	含义
`000`	无错误
`001`	第 1 位（ $P_{1}$ ）出错
`010`	第 2 位（ $P_{2}$ ）出错
`011`	第 3 位（ $D_{1}$ ）出错
`100`	第 4 位（ $P_{3}$ ）出错
`101`	第 5 位（ $D_{2}$ ）出错
`110`	第 6 位（ $D_{3}$ ）出错
`111`	第 7 位（ $D_{4}$ ）出错

将对应位取反即完成纠错。

为什么 syndrome 恰好等于出错位编号？ 因为出错位参与了哪些校验组，那些组的 syndrome 就为 1。把各组的 syndrome 拼起来，正好是该位编号的二进制表示——这就是海明码位置编排的巧妙之处。

SEC-DED：全校验位扩展

标准海明码只能纠 1 位错。如果 2 位同时出错，故障字非零但指向一个错误的位置，"纠正"反而引入第 3 个错误。

解决方案：增加 1 位全校验位 $P_{0}$ ，对所有 $n$ 位做整体偶校验。

$P_{0}$ 校验	故障字	判断	处理
正确（0）	全 0	无错误	无需处理
出错（1）	非 0	1 位错	按故障字纠正
正确（0）	非 0	2 位错	报告错误，不纠正
出错（1）	全 0	$P_{0}$ 自身出错	纠正 $P_{0}$

这就是 SEC-DED（Single Error Correction, Double Error Detection）方案。实际内存的 ECC 就是基于这个原理——72 位码字（64 位数据 + 8 位校验）实现 SEC-DED。

交互可视化

加载可视化中...

例题

例 1：对数据 $D_{4} D_{3} D_{2} D_{1} = 1011$ 编写 7 位海明码（偶校验）。

P_{1} = D_{1} \oplus D_{2} \oplus D_{4} = 1 \oplus 1 \oplus 1 = 1

P_{2} = D_{1} \oplus D_{3} \oplus D_{4} = 1 \oplus 0 \oplus 1 = 0

P_{3} = D_{2} \oplus D_{3} \oplus D_{4} = 1 \oplus 0 \oplus 1 = 0

位编号	7	6	5	4	3	2	1
内容	1	0	1	0	1	0	1

海明码 = 1010101。

例 2：接收到 1010001（原发送 1010101，位 3 出错），检错并纠正。

位编号	7	6	5	4	3	2	1
收到	1	0	1	0	0	0	1

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

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

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

故障字 $S_{3} S_{2} S_{1} = 011_{2} = 3$ ，第 3 位出错。

将第 3 位取反： $0 \to 1$ ，纠正后 1010101，恢复正确。

例 3：8 位数据至少需要多少位海明校验位？SEC-DED 方案呢？

$2^{r} \geq 8 + r + 1$ ： $r = 4$ 时 $16 \geq 13$ ，满足。

标准海明码：4 位校验位，总码长 12。

SEC-DED：加 1 位全校验位 $P_{0}$ ，共 5 位校验，总码长 13。

端到端大例：8 位数据的完整编码—传错—纠错

真题可能给 8 位数据，规模一大最容易在分组上数错位，完整走一遍。

编码：数据 $D = 10011010$ （8 位，记 $D_{1} \dots D_{8}$ 从左到右）。校验位数： $2^{r} \geq 8 + r + 1$ ， $r = 4$ 。校验位放第 1、2、4、8 位，数据位依次填入其余位置：

位编号	1	2	3	4	5	6	7	8	9	10	11	12
内容	$P_{1}$	$P_{2}$	$D_{1}$ =1	$P_{3}$	$D_{2}$ =0	$D_{3}$ =0	$D_{4}$ =1	$P_{4}$	$D_{5}$ =1	$D_{6}$ =0	$D_{7}$ =1	$D_{8}$ =0

按偶校验逐组计算（组内数据位异或）：

$P_{1}$ （管 1,3,5,7,9,11） $= 1 \oplus 0 \oplus 1 \oplus 1 \oplus 1 = 0$
$P_{2}$ （管 2,3,6,7,10,11） $= 1 \oplus 0 \oplus 1 \oplus 0 \oplus 1 = 1$
$P_{3}$ （管 4,5,6,7,12） $= 0 \oplus 0 \oplus 1 \oplus 0 = 1$
$P_{4}$ （管 8,9,10,11,12） $= 1 \oplus 0 \oplus 1 \oplus 0 = 0$

码字（第 1 → 12 位）：0 1 1 1 0 0 1 0 1 0 1 0

传错：接收方收到的码字第 10 位由 0 变 1。

纠错：对四个组重新做偶校验，违例记 1：

$S_{1}$ ：组 {1,3,5,7,9,11} 不含第 10 位 → 校验通过， $S_{1} = 0$
$S_{2}$ ：组 {2,3,6,7,10,11} 含第 10 位 → 违例， $S_{2} = 1$
$S_{3}$ ：组 {4,5,6,7,12} 不含 → $S_{3} = 0$
$S_{4}$ ：组 {8,9,10,11,12} 含 → $S_{4} = 1$

故障字 $S_{4} S_{3} S_{2} S_{1} = 1010_{2} = 10$ ，直接指向第 10 位，取反即纠正。✓

规模变大后分组别靠背——用"位编号二进制里第 $j$ 位是否为 1"现场推： $10 = 1010_{2}$ ，第 2、4 位为 1，所以它恰好属于 $P_{2}$ 、 $P_{4}$ 两组，与上面违例的两组完全吻合。

考点清单

[ ] 校验位数量公式： $2^{r} \geq k + r + 1$
[ ] 校验位放在第 $2^{0}, 2^{1}, 2^{2}, \dots$ 位
[ ] 分组规则：位编号二进制中第 $j$ 位为 1 则归入 $P_{j}$ 组
[ ] 编码时对各组做偶校验求校验位
[ ] 故障字 = 出错位编号（全 0 表示无错）
[ ] 标准海明码： $d = 3$ ，纠 1 位或检 2 位（二选一）
[ ] SEC-DED：加全校验位 $P_{0}$ ， $d = 4$ ，同时检 2 纠 1

海明码详解

考情分析

海明码的核心思想

校验位数量

校验位的位置

分组规则

编码过程

检错与纠错

SEC-DED：全校验位扩展

交互可视化

例题

端到端大例：8 位数据的完整编码—传错—纠错

考点清单

相关文章

真题练习

海明码详解 ​

考情分析 ​

海明码的核心思想 ​

校验位数量 ​

校验位的位置 ​

分组规则 ​

编码过程 ​

检错与纠错 ​

SEC-DED：全校验位扩展 ​

交互可视化 ​

例题 ​

端到端大例：8 位数据的完整编码—传错—纠错 ​

考点清单 ​

相关文章

真题练习 ​

海明码详解

考情分析

海明码的核心思想

校验位数量

校验位的位置

分组规则

编码过程

检错与纠错

SEC-DED：全校验位扩展

交互可视化

例题

端到端大例：8 位数据的完整编码—传错—纠错

考点清单

真题练习