1.2.4 海明校验码

本课核心知识点整理

本节导学

海明码是本组三类校验方式中唯一需要重点掌握“纠错机制”的内容。字幕给出的核心非常明确：海明码通过多组分组校验形成交叉关系，当若干校验组同时报告异常时，交叉点就指向出错位；二进制位一旦定位，取反即可修正。

软件设计师考试不要求你完整推导每一个校验位的取值，但必须掌握两个入口规则：

内容	规则
校验位个数	$2^r\ge m+r+1$，取满足条件的最小 r
校验位位置	放在第 1,2,4,8,16,... 位，也就是 $2^0,2^1,2^2,\dots$

为什么海明码能纠错

奇偶校验只有一条约束，发现错误时不知道是哪一位错。海明码把数据位放入多个校验组中，让同一个数据位同时参与若干组校验。这样一来，某一位出错时，会影响一组特定的校验位；这些异常校验位组合起来，就像坐标一样指向出错位置。

可以把它理解成“多组奇偶校验的交叉定位”。如果只知道“某一行出错”，不能定位；只知道“某一列出错”，也不够；但同时知道“第 2 行”和“第 4 列”出错，交叉点就出来了。海明码正是用二进制位序把这种交叉关系编码起来。

定位后，纠错动作很简单：错误位如果是 0 就改成 1，如果是 1 就改成 0。所以海明码的关键不是取反，而是通过校验结果找位置。

校验位个数公式

设信息位个数为 m，校验位个数为 r，海明码要满足：

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

取满足条件的最小 r。

r 个校验位能产生 2r 种校验结果。除了指示每一个可能出错的位置，还要能表示“没有错误”的情况，所以需要覆盖 m + r + 1 种状态。

从小到大试 r，只要第一次满足公式就停止。

例如 m = 32：r = 5 时左边 32，右边 38，不满足；r = 6 时左边 64，右边 39，满足，所以至少需要 6 位校验位。

再看字幕中的 m=16 示例：r=4 时 $2^4=16$，但右侧为 $16+4+1=21$，不满足；r=5 时 $2^5=32$，右侧为 $16+5+1=22$，满足，所以至少需要 5 位校验位。

校验位插入位置

校验位放在位序为 2 的幂次的位置：第 1、2、4、8、16 位……其余位置依次放信息位。

这些位置的二进制编号只有一个 1，天然对应一个校验组。这样每个普通数据位都可以用自己的二进制位序同时落入若干校验组。

编号从 1 开始。先把第 1、2、4、8、16 位留给校验位，再把信息位按顺序填入剩余位置。注意：海明码的校验位是插入在数据中间，不是简单拼到末尾。

位序	1	2	3	4	5	6	7	8	9	10
内容	P1	P2	D1	P4	D2	D3	D4	P8	D5	D6

这正是海明码和 CRC、奇偶校验的结构差异：奇偶校验和 CRC 多是把校验位拼接在信息位前后；海明码的校验位插入在信息位之间，形成交叉覆盖关系。

位序二进制分解

某一位参与哪些校验组，可以通过它的位序二进制表示来判断：二进制中哪一位为 1，就参与对应的校验位。

这种设计让多个校验组的结果能够组合成一个二进制数，而这个二进制数正好是错误位的位置。

把该位置的位序拆成 2 的幂次之和。比如第 14 位：

$$14=8+4+2$$

所以它由 P8、P4、P2 参与校验。题目里也可能写成 P4、P3、P2 这种下标命名，本质仍然对应 8、4、2 这些位置。

再举第 10 位：

$$10=(1010{)}_2=8+2$$

所以第 10 位参与 P8 和 P2 两个校验组。

与奇偶校验、CRC 的分工

对比项	规则	高频考法
校验位个数 r	2r >= m+r+1	给信息位 m 求最小 r
校验位位置	1,2,4,8,...	判断某位是信息位还是校验位
覆盖关系	按位号二进制展开分组	判断某校验位参与哪些位
能力边界	经典海明码单错纠正、双错检测	与 CRC/奇偶能力对比

技术	位置组织	能力	为什么没有被简单替代
奇偶校验	校验位通常拼接	检奇数位错，不纠错	成本极低，适合简单检查
CRC	余数拼接在尾部	强检错，不纠错	通信中发现错误后可重传，不一定要本地修复
海明码	校验位插入 2 的幂次位	可检错、可纠错	冗余和规则更复杂，适合需要自动纠错的场景

做题路线

1. 给出信息位 m 时，从 r=1 开始试 $2^r\ge m+r+1$，取最小 r。
2. 判断校验位位置时，牢记从 1 开始编号，位置是 1,2,4,8,16,...。
3. 判断某个位置参与哪些校验组时，把位序写成二进制或拆成 2 的幂次之和。
4. 能力对比题中，海明码是三者里唯一通常可纠错的；CRC 可检错但不可纠错；奇偶校验能力最弱。

🧪 例题（按难度）

简单（3题）

单选

海明码中校验位的典型插入位置规律是：

AP 位全部放在末尾BP 位放在 3、6、9... 等位置CP 位放在 1、2、4、8、16... 等 2 的幂次位置DP 位位置由题目随机决定，无法总结规律

单选

对 8 位数据采用海明码，至少需要多少位校验位 r？

A3B4C5D6

单选

在位序从 1 开始的海明码中，第 14 位参与哪些校验位的校验？

AP1、P2BP1、P4、P8CP2、P4、P8DP1、P2、P4

中级（3题）

例题1（求校验位个数）

对 32 位数据采用海明码，至少需要增加多少位校验位？

单选

选择至少需要的校验位个数：

A5B6C7D8

例题2（找规律：某位由哪些校验位校验）

某海明码位序从 1 开始计数，问第 10 位数据位参与哪些校验位的校验？

单选

选择参与校验的校验位：

AP1、P2BP2、P8CP4、P8DP1、P8

例题3（概念题）

下列关于海明码的叙述正确的是：

单选

选择正确叙述：

A海明码可纠错但不可检错B海明码数据位长度与校验位长度相同C海明码利用分组奇偶校验实现检错与纠错D海明码码距一定为 1

困难（1题）

单选

海明码在接收端计算得到综合校验（syndrome）为 `0110`（二进制）。若采用 1-based 位序，则错误位最可能在：

A第 3 位B第 6 位C第 9 位D无法定位错误位

📚 本课小结

• r 的求法：2r >= m+r+1（取最小 r）
• 校验位位置：1/2/4/8/16...
• 位序二进制分解：决定参与哪些校验组