校验码总述：码距、奇偶校验与 CRC

2026 大纲的「二、数据的表示和运算」与「三、存储器层次结构」均已不含校验码，本篇不对应任何条目编号；但检错编码（奇偶校验、CRC）与纠错编码（海明码）在 408 计算机网络「三（三）差错控制」 中仍是纲内内容，原理完全通用。

怎么分配时间：备考 CN 差错控制的按纲内内容读；只复习 CO 的读一遍建立概念即可，不必做题训练。

冗余买的是一块"非法位串"缓冲区

$n$ 位串一共有 $2^n$ 种，如果全都合法，那么任何一位出错之后得到的仍是一个合法码字——接收端根本无从察觉。校验码的全部做法就是：只让其中 $2^k$ 种合法，其余全部非法。冗余位买来的正是这块"非法位串"缓冲区，它越厚，能识别的错误就越多。

衡量这块缓冲区厚度的量叫码距：两个等长码字对应位不同的个数（1011 与 1101 的码距是 2）；最小码距 $d$ 是所有合法码字两两码距的最小值。

🔴 谈能力时说的永远是最小码距——整套编码的能力由最弱的那一对码字决定。

而全部能力只需要一个式子：

🔴 同时检 $e$ 位、纠 $t$ 位（$e\ge t$）需要 $\boxed{{\displaystyle d\ge e+t+1}}$。令 $e=t$ 就退化成"纠 $t$ 位"的 $d\ge 2t+1$；令 $t=0$ 就退化成"只检 $e$ 位"的 $d\ge e+1$。另外两个式子不用背。

由它立刻能读出一条常被弄混的结论：

🔴 $d=3$ 是"检 2 位"或"纠 1 位"，不能兼得——兼得要求 $d\ge 2+1+1=4$。根源在于：检错只要求出错后的串落在球外，纠错却要求它落在正确那个球内，同一份距离预算一次只能满足一种解释。推论：纠错能力恒不大于检错能力。

一、冗余的本质：让合法码字变稀疏

$n$ 位二进制串一共有 $2^n$ 种。如果这 $2^n$ 种全部合法，那么任何一位出错之后得到的仍是一个合法码字——从结果上根本看不出发生过错误。

所以有 $k$ 位信息要传时，我们不发 $k$ 位，而是发 $n=k+r$ 位。$2^k$ 个合法码字散布在 $2^n$ 个位串里，其余 $2^n-2^k$ 个位串一旦出现，接收端立刻知道传输出了错。冗余越多，合法码字越稀疏，缓冲区越厚。

二、码距决定的能力

最小码距 $d$	能力
1	无（任何一位错都变成另一个合法码字）
2	检 1 位
3	检 2 位 或 纠 1 位
4	检 2 位 且 纠 1 位
$2t+1$	纠 $t$ 位
$e+t+1$（$e\ge t$）	检 $e$ 位且纠 $t$ 位

三个不等式各自是怎么推出来的：从"落进非法区"到"半径 t 的球互不相交"（想弄清为什么纠错要 2t+1 而不是 t+1 时展开）

检错 $d\ge e+1$。 合法码字 $C$ 发生 $e$ 位错误后变成 $C^{\prime }$，两者码距恰好是 $e$。只要 $C^{\prime }$ 不是另一个合法码字，接收端就能发现异常；而任意两个合法码字之间的距离至少是 $d$，所以只要

$$e<d⟺d\ge e+1$$

错误就"走不到"另一个合法码字上，一定落进非法区。

纠错 $d\ge 2t+1$。 纠错比检错多要求一件事：不仅要知道错了，还要知道原来是谁。 做法是"就近归属"——把收到的串归给离它最近的那个合法码字。要保证判断唯一，就要求以每个合法码字为球心、半径 $t$ 的"球"互不相交。

设 $C$ 是发送的码字、$R$ 是收到的串，$d(C,R)\le t$。对任意另一个合法码字 $C_2$，由三角不等式 $d(C,C_2)\le d(C,R)+d(R,C_2)$，若 $d(C,C_2)\ge 2t+1$ 则

$$d(R,C_2)\ge (2t+1)-t=t+1>t$$

即 $R$ 一定落在 $C_2$ 的球外，归属没有歧义。

同时检纠 $d\ge e+t+1$。 两个要求会互相干扰：错了 $e$ 位得到的串 $R$，如果恰好掉进别的合法码字的半径 $t$ 球里，接收端不但不报警，还会把它"纠"成那个错的码字——比不纠更糟。要杜绝的正是这一种情形，即 $R$ 与任何其他合法码字 $C_2$ 的距离都必须大于 $t$。反设 $d(R,C_2)\le t$，由三角不等式

$$d(C,C_2)\le d(C,R)+d(R,C_2)\le e+t$$

即只要存在一对合法码字距离 $\le e+t$，误纠就可能发生。把这段距离堵死，就得到 $d\ge e+t+1$。

三、三类校验码在这个框架里的位置

编码	最小码距	能力	冗余位数
奇偶校验	2	检出奇数位错，不能纠	1 位
海明码（SEC）	3	纠 1 位 或 检 2 位	$r$ 位，$2^r\ge k+r+1$
海明码（SEC-DED）	4	纠 1 位 且 检 2 位	上式再加 1 位
CRC	取决于生成多项式	检出所有长度 $\le r$ 的突发错误	$r$ 位

三者的差别可以只用码距解释：码距越大能力越强，而码距是靠冗余位数换来的。奇偶校验只加 1 位，能力最弱；海明码加 $\log$ 级的位数换到 $d=3$；SEC-DED 再加 1 位换到 $d=4$。CRC 略有不同——它不是把能力做在"任意 $e$ 位错"上，而是做在突发错误上。

四、奇偶校验：只买了一位冗余

在数据位之外加 1 位校验位，使整个码字里 1 的个数满足奇偶约定：偶校验是全部位异或结果为 0（1 的个数为偶数），奇校验是异或结果为 1。

最小码距 $d=2$：要从一个合法码字变到另一个合法码字，至少得改动 2 位——改 1 位数据位会破坏奇偶性，必须再改校验位补回来。代入 $d\ge e+t+1$：$e=1,t=0$，即只能检 1 位、完全不能纠。

🔴 奇偶校验只能检出奇数位错。 错偶数位时，1 的个数变化量是 $0$ 或 $\pm 2$，奇偶性不变，一律漏检。

五、CRC：把码字看成多项式

把 $k$ 位数据看成一个多项式的系数，用约定的生成多项式 $G(x)$（$r+1$ 位）做模 2 除法，余数（$r$ 位）就是校验位。

$$\mathbf{\text{发送端}}：\text{数据左移 }r\text{ 位（末尾补 }r\text{ 个 0）}÷G(x)\Rightarrow \text{余数即校验位，附在数据后}$$$$\mathbf{\text{接收端}}：\text{整个码字}÷G(x)\Rightarrow \text{余数为 }0\text{ 则认为无错}$$

为什么接收端除出来应该是 0：发送的码字 $=(\text{数据}\times 2^r)+\text{余数}$，而模 2 运算下"减去余数"和"加上余数"是同一件事，所以这个码字恰好能被 $G(x)$ 整除。任何使它不再整除的改动都会暴露。

模 2 除法逐步走一遍：求校验位、验证无错、再制造一位错看余数怎么变（想核对自己的竖式或验证"余数只由错误图样决定"时展开）

数据 110101，生成多项式 $G(x)=x^3+x+1$（即 1011，$r=3$）。

求校验位：数据末尾补 3 个 0 得 110101000，对 1011 做模 2 除法。每一步只看当前最高位：是 1 就把 1011 对齐异或一次，是 0 就直接跳过。

步	当前余式	最高位	动作	结果
0	110101000	1	与 1011 从第 0 位对齐异或	011001000
1	011001000	1（第 1 位）	与 1011 从第 1 位对齐异或	001111000
2	001111000	1（第 2 位）	与 1011 从第 2 位对齐异或	000100000
3	000100000	1（第 3 位）	与 1011 从第 3 位对齐异或	000001100
4	000001100	0（第 4 位）	跳过	000001100
5	000001100	1（第 5 位）	与 1011 从第 5 位对齐异或	000000111

低 3 位即余数 111，故发送码字 = 110101 + 111 = 110101111。（商是 111101，把每一步"做了/跳过"依次记下来就得到它。CRC 只要余数，商可以不算。）

接收端验证：把 110101111 整体除以 1011，余数为 000，判定无错。

出错的情形：设传输中第 3 位由 0 变成 1，接收到 111101111。再除以 1011，余数为 101 $\ne 0$，错误被检出。

这个余数可以不重算：第 3 位（共 9 位）出错对应错误图样 $x^6$，反复用 $x^3\equiv x+1$ 降次得 $x^4\equiv x^2+x$，$x^5\equiv x^2+x+1$，$x^6\equiv x^2+1=$ 101。余数是错误的函数，与数据无关——这也解释了 CRC 为什么只需要余数。

考点速记

1. 检错的前提是让合法码字稀疏：$n$ 位串共 $2^n$ 种，只让 $2^k$ 种合法，其余作为"错误可落入"的缓冲区；能力由最小码距一个数决定。
2. 同时检 $e$ 纠 $t$ 需 $d\ge e+t+1$ 是唯一要记的一式（令 $e=t$ 得 $d\ge 2t+1$，令 $t=0$ 得 $d\ge e+1$）；因此 $d=3$ 是"检 2 或纠 1"不能兼得，纠错能力恒不大于检错能力。
3. 奇偶校验 $d=2$ 只能检奇数位错；CRC 用模 2 除法（异或代替减法），能检出所有长度 $\le r$ 的突发错误但不能定位（要定位得用海明码那种把位置编码进校验组的设计）。三者的差别可归结为：用多少冗余位换多大的码距，以及把能力做在随机错误还是突发错误上。

这一节在真题里的位置：

校验码在 408 真题里出题极少——下方「真题练习」挂的 error-detection-correction 这个 topic 至今只有一道题（问海明码纠一位错所需的校验位数），而且它属于兄弟篇 海明码的构造与纠错。本篇至今不单独成题，这不是漏挂标签。

复习优先级因此很清楚：把 $d\ge e+t+1$ 和"奇偶校验只检奇数位错"两条记住即可，CRC 的模 2 除法会算一遍、知道它检突发错误且不能定位就够了，不必投入更多时间。真要练手，练海明码那篇。

易错：把 $d=3$ 说成"既能检 2 位又能纠 1 位"。兼得要 $d\ge 4$。

易错：认为奇偶校验能检出所有 1 位以上的错。偶数位错一律漏检。

易错：以为 CRC 能定位错误位。它只报"有错"。

教材出处

• 编码最小距离的定义、$L-1=D+C$ 且 $D\ge C$（检错位数不小于纠错位数）、"$L=3$ 时最多能检二位，或检一位纠一位"：唐朔飞《计算机组成原理》第 3 版 第 4 章 存储器·汉明码，印刷页 p100

相关知识

海明码详解｜计算机网络博客的差错控制

真题练习

相关真题（1题）

2013Q152分

上一篇数据对齐与大小端（属指令系统章）下一篇海明码详解（纲外）

相关文章

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