差错检测（CRC校验）

2026 大纲 三（三）1 检错编码（奇偶校验码和 CRC 码）。码距 $d_{min}$ 与检错/纠错位数的能力边界在《海明码》。

一、边界切出来了，可这一帧路上被改过没有

上一节把比特流切成了帧。但切出边界只解决了"这一段是一帧"，没有回答"这一帧还是原来那一帧吗"——线路上的噪声随时可能把某一位从 0 翻成 1。

一段时间内传输错误的比特占所传输比特总数的比率称为误码率 BER。它与信噪比强相关，但实际链路的误码率永远降不到零——所以差错检测是必需的，不是可选的。

先把这一章的两类差错分清，它是理解整章的枢纽：

• 比特差错：某些位被翻转了。本节的检错码管这一类。
• 帧差错：帧丢失、帧重复、帧失序。这三类里一个比特都没错，检错码一概查不出，只能靠编号 + 确认 + 重传来管（本章第四节起）。

所以「无比特差错」≠「无传输差错」≠「可靠传输」。CRC 检验通过只说明"这一帧的比特没被翻转"，它对"本该有一帧却整个不见了"毫无察觉——因为它连"应该有一帧"这件事都不知道。

实际链路上还有一个特点决定了检错码怎么选：错误往往是突发的。噪声脉冲、电磁干扰一次影响连续若干比特，而不是零散打散。CRC 被选中，正因为它对突发错误的检测能力有可证明的下界（见第四节）。

链路层为什么选"检错 + 丢弃"而不是"纠错"

这是一笔代价账，不是技术优劣：有线链路误码率极低，为极少数坏帧让每一帧都背上纠错冗余更亏；纠错码也纠不了突发式的连片错；而重传的成本很低。

重传代价极高时天平就反过来——深空通信、光盘与闪存（根本没有发送方可重传）、无线链路，这些场景就要用纠错码。

PPP 的设计文档把这个取舍写得很直白：TCP/IP 体系里可靠传输由运输层的 TCP 负责，因此链路层的 PPP 不需要纠错、不需要序号、也不需要流量控制——收到帧就做一次 CRC 检验，正确就收下，错了就丢弃，其他什么也不做。

二、奇偶校验码：为什么它必然漏检偶数位错

在数据后附加 1 位，使码字中 1 的个数为奇数（奇校验）或偶数（偶校验）。设数据位为 $a_{n-1}\cdots a_1$，偶校验位

$$a_0=a_{n-1}\oplus a_{n-2}\oplus \cdots \oplus a_1$$

接收端算校正因子 $S=a_{n-1}\oplus \cdots \oplus a_1\oplus a_0$，$S=0$ 判无错、$S=1$ 判有错。

异或的本质是"数 1 的个数的奇偶性"，翻转任意一位就让奇偶性改变一次，所以

$$S=kmod2(k=\text{出错位数})$$

偶数次翻转的净效果为零，这是结构性的漏检，不是运气不好。 它的 $d_{min}=2$，只能检 1 位，既不能定位也不能纠正。

它太弱，实际很少单用，价值在两处：一是理解校正因子的最简模型（海明码就是把它推广成多个监督关系式）；二是 CRC 的一个性质来源——若 $G(x)$ 含因子 $(x+1)$，CRC 就继承了"检出全部奇数位错误"。

三、CRC 循环冗余校验

收发双方事先约定一个生成多项式 $G(x)$（对应二进制串 $P$）。多项式的每一项 $x^i$ 对应二进制串从右往左第 $i$ 位（最低位是 $x^0$）：

$$G(x)=x^3+x+1\Rightarrow 1011G(x)=x^4+x^3+1\Rightarrow 11001$$

转二进制时别漏常数项：$x^3+x+1$ 是 1011 不是 1010。最高位与最低位必须为 1；阶为 $r$ ⇒ 串长 $r+1$ 位、FCS $r$ 位。

最低位必须是 1 不只是习惯：若 $G(x)$ 能被 $x$ 整除，它就检测不出"只有最低若干位出错"的情况——错误多项式恰好含因子 $x$ 时会被整除掉。常用标准：CRC-16 是 $x^{16}+x^{15}+x^2+1$，CRC-CCITT 是 $x^{16}+x^{12}+x^5+1$，以太网用 32 阶的 CRC-32——所以以太网帧尾的 FCS 是 4 字节。

四步与模 2 除法

模 2 除法怎么做：每步只看当前最高位——是 1 就商 1 并做一次异或，是 0 就商 0 直接右移。不进位、不借位、不比大小。

为什么不能用普通除法。 普通减法要借位，借位会让一个比特的错误"传染"到相邻比特，而且商的每一位要靠比较大小才能定，硬件上既慢又复杂。模 2 除法每一步只判断一个比特、只做一次异或——移位寄存器加几个异或门就能线速实现，这是 CRC 成为工业标准的决定性因素。

走一遍：$M=101001$，$P=1011$，$r=3$

补 3 个 0 得 $2^{3}M=101001\underset{―}{000}$，模 2 除以 1011：

轮次	当前被除数	首位	商	运算	结果
1	101001000	1	1	1010 $\oplus$ 1011 = 0001	000101000
2	000101000	0	0	首位为 0，直接右移	000101000
3	000101000	0	0	首位为 0，直接右移	000101000
4	000101000	1	1	1010 $\oplus$ 1011 = 0001	000000100
5	000000100	0	0	首位为 0，直接右移	000000100
6	000000100	0	0	首位为 0，直接右移	000000100

一共走 $9-4+1=6$ 轮（被除数 9 位、除数 4 位）——轮数不能少走，少走一轮余数就多带一位。余数取末 3 位 $R=100$，即 FCS；发送帧 $T=101001100$。

接收方用 101001100 除以 1011：第 1 轮异或后得 000101100，第 4 轮 1011 $\oplus$ 1011 = 0000，其余各轮首位为 0 直接右移，最终余数 000，判无差错。

余数不足 $r$ 位时必须补零

$M=10110011$，$P=11001$，$r=4$。补 4 个 0 得 101100110000（12 位），共走 $12-5+1=8$ 轮：

轮次	当前被除数	首位	商	运算	结果
1	101100110000	1	1	10110 $\oplus$ 11001 = 01111	011110110000
2	011110110000	1	1	11110 $\oplus$ 11001 = 00111	000111110000
3	000111110000	0	0	右移	000111110000
4	000111110000	1	1	11111 $\oplus$ 11001 = 00110	000001100000
5	000001100000	0	0	右移	000001100000
6	000001100000	1	1	11000 $\oplus$ 11001 = 00001	000000000100
7	000000000100	0	0	右移	000000000100
8	000000000100	0	0	右移	000000000100

末 4 位余数 $R=\mathbf{0}100$——有效数字只有 100 三位，必须在高位补一个 0 凑够 4 位，否则接收方按"末 4 位是 FCS"切分时会整体错一位、检验必败。发送帧 $T=101100110100$。

接收方为什么只看余数

设 $2^{r}M=QP+R$，则发送的帧

$$T=2^{r}M+R=QP+R+R=QP$$

模 2 加法即异或，$R\oplus R=0$，所以 $T$ 恰好是 $P$ 的倍数。接收方只需验证 $TmodP=0$，一次除法搞定，不必先切数据段、再算一遍 FCS、再比较——发送和接收因此可以共用同一个电路。

余数非 0 时整帧丢弃，因为 CRC 只回答"是/否有错"，不知道错在哪一位。

⚠️ CRC 与 FCS 不是同一个概念。 CRC 是检错方法，FCS 是帧尾那段冗余码，术语不可互换——检错方法可以选 CRC 也可以不选。另外严格讲"余数为 0"只能说"以非常接近 1 的概率认为没有差错"，不是"一定没有差错"。

交互可视化

加载可视化中...

加载可视化中...

四、检错能力从哪来：只有一条判据

设收到 $T^{\prime }=T\oplus E$，$E$ 是错误图样（出错位置为 1，其余为 0）。因 $T$ 本身能被 $P$ 整除，

$$T^{\prime }modP=(T\oplus E)modP=EmodP$$

能否发现错误完全取决于 $E$ 能不能被 $P$ 整除，与数据 $M$ 是什么毫无关系。 换句话说：漏检当且仅当错误图样恰是 $P$ 的倍数。 下面四条能力结论全部由这一句推出。

结论	条件	依据
检出所有单比特错误	$G(x)$ 至少有两项	$E=x^i$，多项式无法整除单项式
检出所有奇数个比特错误	$G(x)$ 含因子 $(x+1)$	含 $(x+1)$ 者项数必为偶数，整除不了项数为奇数的 $E$
检出所有双比特错误	$G(x)$ 不能整除 $x^k+1$（$k$ 小于帧长）	$E=x^i(x^j+1)$
检出所有长度 $\le r$ 的突发错误	$G(x)$ 的阶为 $r$	见下
长度 $r+1$ 的突发错误漏检概率 $2^{-(r-1)}$	—	计数论证

突发长度的门槛为什么恰好是 $r$

长度为 $L$ 的突发错误可写成

$$E(x)=x^i\cdot (x^{L-1}+\cdots +1)$$

其中 $x^i$ 表示突发起始位置。$G(x)$ 的常数项为 1，故 $G(x)$ 与 $x^i$ 互质，要整除 $E(x)$ 就必须整除括号里那个 $L-1$ 次多项式。而 $G(x)$ 是 $r$ 次的——$r$ 次多项式整除不了次数低于 $r$ 的非零多项式。所以只要 $L-1<r$，即 $L\le r$，就绝不可能整除，错误必被检出。

以太网用 32 阶的 CRC-32，意味着任何连续 32 位以内的突发错误都能 100% 检出；而链路上的干扰恰恰以突发形式为主。

一旦 $L=r+1$，括号里就是 $r$ 次多项式，与 $G(x)$ 同次，有可能正好相等——此时漏检。$r$ 次多项式最高位与最低位固定为 1、中间 $r-1$ 位自由，共 $2^{r-1}$ 种，只有 1 种撞上 $G(x)$，故漏检概率 $2^{-(r-1)}$。

一个可以自己验证的推论

沿用 $T=101100110100$，设第 3 位由 1 翻成 0，收到 $T^{\prime }=100100110100$，除以 11001 得余数 0101 $\ne 0$，丢弃。而把错误图样 $E=001000000000$ 单独除以 $P$，余数同样是 0101——这不是巧合，正是 $T^{\prime }modP=EmodP$ 的直接体现。

本节小结

1. 差错分比特差错（本篇的检错码管）与帧差错（每一位都没错，只能靠编号+确认+重传管）；链路层选"检错 + 丢弃 + 上层重传"是一笔代价账，重传代价极高的场景才倒向纠错码。
2. CRC 的机制链条是：$G(x)$ 的阶 $r$ 决定 FCS 位数 → 补 $r$ 个 0 → 模 2 除取余得 FCS → $T=2^{r}M+R=QP$，所以接收方只需验"余数为 0"，收发共用一套硬件。
3. 检错能力的唯一判据是 $T^{\prime }modP=EmodP$——漏检当且仅当错误图样是 $P$ 的倍数，与数据内容无关；由它推出"长度 $\le r$ 的突发错误 100% 检出"。CRC 只检错不纠错，余数非 0 时整帧丢弃。

考点速记

本节在真题里被考过的形式是一道反向题——给生成多项式与四个候选比特串，问哪一个在传输中未发生错误（cn-2023-37，$G(x)=x^4+x+1$ 即 $G=10011$）。

有两条路可走，第二条快得多：

路线一（老实做）：拿每个选项整个去模 2 除以 10011，余数为 0 的那个就是答案。四个选项就是四次除法。

路线二（推荐）：四个选项通常只在末 $r$ 位上不同——本题都是 10111 开头、末 4 位分别是 0000/0100/1000/1100。那么直接把公共前缀当作数据 $M=10111$，算一次 FCS 就够了：补 4 个 0 得 101110000，模 2 除以 10011 得余数 1100，所以正确的帧是 10111 + 1100 = 101111100，对上第四个选项。一次除法代替四次。

用哪条路，看四个选项的前缀是不是一样长、一样内容。前缀相同就走路线二。

易错：$G(x)$ 转二进制别漏常数项。 $x^4+x+1$ 是 10011（5 位），不是 10010；阶为 4 ⇒ FCS 4 位、除数 5 位。

易错：FCS 必须补足 $r$ 位。 余数算出 100 而 $r=4$ 时要写成 0100，少一位则数据与 FCS 整体错位。

易错：模 2 除法的轮数是"被除数位数 − 除数位数 + 1"，不能少走。 少走一轮，余数就多带一位。

易错：接收端是拿整个收到的帧（数据 + FCS）去除，不是只除数据部分再和 FCS 比对。这两种做法结果等价，但前者只需一次除法，也是硬件实际的做法。

易错：CRC 只检错不纠错。 余数非 0 时不知道错在哪一位，只能整帧丢弃。"CRC 能纠正 1 位错"是错的。

易错："CRC 校验通过"只等于无比特差错。 帧丢失、帧重复、帧失序它一概查不出——那是可靠传输要管的事。

教材出处

• 谢希仁《计算机网络》（第 8 版）p76（3. 差错检测）：比特差错与误码率 BER 的定义——"在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率 BER"，"实际的通信链路并非是理想的，它不可能使误码率下降到零"；并给出 CRC 的引入与 $M=101001$、$P=1101$ 的完整算例（商 $Q=110101$，余数 $R=001$，发送帧 101001001）。同页脚注给出模 2 运算口径："用模 2 运算进行加法时不进位……减法和加法一样，按加法规则计算"。
• 同书 p76 末段明确"循环冗余检验 CRC 和帧检验序列 FCS 并不是同一个概念。CRC 是一种检错方法，而 FCS 是添加在数据后面的冗余码，在检错方法上可以选用 CRC，但也可不选用 CRC"。
• 同书 p77：接收端的判定规则——"若得出的余数 $R=0$，则判定这个帧没有差错，就接受"，"若余数 $R\ne 0$，则判定这个帧有差错（但无法确定究竟是哪一位或哪几位出现了差错），就丢弃"；同页列出 CRC-16 / CRC-CCITT / CRC-32 三个标准生成多项式，并指出 FCS 的生成与检验"都是用硬件完成的，处理很迅速，因此并不会延误数据的传输"；末段给出"凡是接收端数据链路层接受的帧，我们都能以非常接近于 1 的概率认为这些帧在传输过程中没有产生差错"这一口径。
• 同书 p78：区分"无比特差错"与"无传输差错"——列出帧丢失、帧重复、帧失序三种"没有比特差错却仍属传输差错"的情形，并强调"在数据链路层使用 CRC 检验，能够实现无比特差错的传输，但这还不是可靠传输"。
• 同书 p79–p80（PPP 协议应满足的需求）：解释为什么链路层选择不纠错——"数据链路层没有必要提供比 IP 协议更多的功能。因此，对数据链路层的帧，不需要纠错，不需要序号，也不需要流量控制"，"接收方每收到一个帧，就进行 CRC 检验。如 CRC 检验正确，就收下这个帧；反之，就丢弃这个帧，其他什么也不做"。

相关知识

封装成帧与透明传输｜海明码校验与纠错｜三种 ARQ 协议对比｜PPP 协议

上一篇封装成帧与透明传输下一篇海明码

相关文章

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

交互体验

前往完整可视化页面 →

真题练习

相关真题（2题）

2025Q342分2023Q372分