408 计算机网络

Appearance

差错检测（CRC校验） ​

考情分析 ​

CRC 校验是 408 数据链路层的高频考点，几乎每隔一两年就会出现，常见形式是给定数据位和生成多项式，要求手算 FCS（帧检验序列）或判断接收到的帧是否出错。模 2 除法的计算过程必须熟练掌握。

考频：★★★★

差错的来源与分类 ​

比特在传输过程中可能发生错误，0 变成 1 或者 1 变成 0。根据错误的分布模式，分为两类：

  • 位错（比特错）： 某一个或几个比特发生翻转
    • 单比特错：只有 1 位出错
    • 多比特错：多个不相邻的位出错
    • 突发错误：连续多个位出错（实际链路中最常见）
  • 帧错： 帧丢失、帧重复、帧失序（这些由协议层面处理，不在差错检测的范围内）

检错 vs 纠错 ​

类型能力代表方法开销
检错码只能检测出错误，不能定位和纠正CRC、奇偶校验冗余位少，开销小
纠错码能检测并纠正错误海明码冗余位多，开销大

数据链路层通常使用检错码 + 重传的策略（ARQ），而不是纠错码。因为有线链路的误码率很低，大部分帧是正确的，用纠错码会浪费带宽。

奇偶校验码 ​

最简单的检错方法，在数据后面附加 1 个校验位，使整个码字中 1 的个数为奇数（奇校验）或偶数（偶校验）。

  • 奇校验：包括校验位在内，1 的总数为奇数
  • 偶校验：包括校验位在内，1 的总数为偶数
特性说明
检错能力只能检测奇数位错误，偶数位同时出错时检测不出
纠错能力无法纠错，也无法定位出错位置
编码效率高（只增加 1 位冗余）
应用场景早期通信、存储系统（如内存 ECC 的基础）

奇偶校验的码距 dmin=2，所以只能检测 1 位错误。408 选择题偶尔考"奇偶校验能否检测 2 位错误"这类辨析题，答案是不能。

CRC 循环冗余校验 ​

基本思路 ​

发送方和接收方事先约定一个生成多项式 G(x)。发送方根据数据和 G(x) 计算出一个校验序列 FCS（Frame Check Sequence），附加在数据后面一起发送。接收方用同样的 G(x) 对收到的整个帧做除法，如果余数为 0 则认为没有错误。

生成多项式 G(x) ​

生成多项式用二进制表示。例如：

G(x)=x3+x+1⇒1011G(x)=x4+x3+1⇒11001

规则：G(x) 的最高位和最低位必须是 1。G(x) 的阶（最高次幂）记为 r，FCS 就是 r 位。

模 2 运算 ​

CRC 中的"除法"不是普通的算术除法，而是模 2 除法：

  • 模 2 加法 = 模 2 减法 = 异或（XOR）
  • 0 XOR 0 = 0, 0 XOR 1 = 1, 1 XOR 0 = 1, 1 XOR 1 = 0
  • 不进位、不借位

CRC 计算步骤 ​

设数据为 D，生成多项式为 G(x)，其阶为 r。

第 1 步： 在数据 D 后面补 r 个 0，得到 D×2r

第 2 步： 用 D×2r 对 G(x) 做模 2 除法，得到余数 R

第 3 步： 余数 R 就是 FCS（不足 r 位则高位补 0）

第 4 步： 发送的帧 = 数据 D + FCS R

计算例题 ​

已知： 数据 D=101001，生成多项式 G(x)=x3+x+1（即 1011），r=3。

第 1 步： 数据后补 3 个 0 → 101001000―

第 2 步： 模 2 除法（101001000÷1011）：

  101001000
⊕ 1011          (首位为1，可以除)
  ---------
  0001 01000
      ↓
  00101000       (去掉前导0，取够4位)
⊕ 0000          (首位为0，商0，不除)
  ---------
  0101000
⊕ 0000          (首位为0，商0)
  ---------
  101000
⊕ 1011          (首位为1，可以除)
  ---------
  001100
⊕  0000         (首位为0)
  ---------
  01100
⊕ 0000          (首位为0)
  ---------
  1100
⊕ 1011          (首位为1)
  ---------
  0110
⊕ 0000
  ----
   110           ← 余数 R = 110

第 3 步： FCS = 110

第 4 步： 发送帧 = 101001110

接收方校验 ​

接收方收到 101001110，用 1011 做模 2 除法。如果余数为 000，则认为传输无误；否则说明帧出错，丢弃该帧。

交互可视化 ​

下面的可视化工具可以动态演示 CRC 的模 2 除法计算过程，输入数据和生成多项式后逐步展示每一轮异或运算。

加载可视化中...

也可以使用计算器快速验算 CRC 结果：

加载可视化中...

CRC 的检错能力 ​

CRC 不是万能的，它的检错能力取决于生成多项式的选择：

  • 能检测出所有奇数个比特错误（前提是 G(x) 含因子 x+1）
  • 能检测出所有双比特错误（前提是 G(x) 的阶 ≥ 突发长度）
  • 能检测出所有长度 ≤r 的突发错误
  • 长度为 r+1 的突发错误，检测不出的概率为 2−(r−1)

CRC 只能检错，不能纠错。检测到错误后，数据链路层的做法是直接丢弃该帧，由上层协议负责重传。

易错点 ​

1. 余数位数必须等于 r

如果计算出的余数不足 r 位，高位要补 0。比如 r=3 但余数算出来是 01，那 FCS 应该是 001，不能写成 01 或 1。

2. 模 2 除法不是普通除法

最容易犯的错误是在做除法时借位。模 2 除法全程用异或运算，不存在借位。每一步就是简单的 XOR。

3. 生成多项式的二进制表示

G(x)=x3+x+1 对应 1011，不是 1010。常数项 1 对应最低位的 1，不能漏掉。

4. CRC 检错 ≠ 纠错

CRC 余数不为 0 只能说明"出错了"，但不知道哪一位错了。海明码才具备定位和纠正错误的能力。

高频考点清单 ​

  • 奇偶校验只能检测奇数位错误（码距 dmin=2）
  • 给定数据和生成多项式，手算 FCS
  • 模 2 除法的完整计算过程
  • 接收方校验：用收到的完整帧除以 G(x)，余数为 0 则正确
  • 生成多项式与二进制串的互相转换
  • CRC 的检错能力范围
  • FCS 位数 = 生成多项式的阶 r

相关文章

交互体验

前往完整可视化页面 →

真题练习 ​

相关真题（2题）

2025Q34选择题2分
详解

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

CRC校验海明码
2023Q37选择题2分
可视化详解

CRC 校验：接收方用生成多项式除接收数据判断是否出错

CRC校验