408

计算机网络

CN-03-03 差错控制（奇偶校验/CRC/海明码）

---

一、定位信息

• 圈层：核心层
• 前置知识：比特运算基础、异或运算（XOR）
• 知识网络位置：本单元是数据链路层差错控制功能的核心实现，CRC是408高频计算题来源
• 考点热度等级：H级（高频重点）——CRC计算和海明码计算是408必考内容，近五年出现≥4次

---

二、知识点讲解

1. 差错类型

• 位错：比特位从0变1或从1变0（单个或多个比特错误）
• 帧错：帧丢失、帧重复、帧失序

数据链路层主要处理位错。

2. 奇偶校验（Parity Check）

在数据后面附加1个校验位，使整个数据（含校验位）中1的个数为奇数（奇校验）或偶数（偶校验）。

• 奇校验：数据+校验位中1的个数为奇数
• 偶校验：数据+校验位中1的个数为偶数

特点：只能检测出奇数个比特错误，无法检测偶数个比特错误，不能纠错。

3. CRC循环冗余校验（Cyclic Redundancy Check）★重点

原理：在数据后面附加若干校验位（FCS），使整个帧能被一个预定义的生成多项式 $G(x)$ 整除（模2除法）。

步骤：

1. 设数据为 $D$，生成多项式 $G(x)$ 对应的二进制为 $G$（$r$ 位）
2. 在 $D$ 后面补 $r-1$ 个0，得到 $D'$
3. 用 $D'$ 除以 $G$（模2除法，即异或运算），得到余数 $R$（$r-1$ 位）
4. 将 $R$ 附加到 $D$ 后面，得到发送的帧 $D + R$

接收方验证：收到的帧除以 $G$，余数为0则无差错。

模2除法：不考虑进位和借位的二进制除法，本质上是异或运算。

4. 海明码（Hamming Code）

原理：在数据位中插入若干校验位，使每个校验位负责校验特定的数据位组合。通过校验位的检查结果（校验子）可以定位错误位置并纠正。

校验位数 $r$ 的确定：$2^r \geq m + r + 1$，其中 $m$ 是数据位数。

校验位位置：第 $1, 2, 4, 8, ...$ 位（$2^i$ 位置）。

校验规则：第 $i$ 个校验位（位置 $2^{i-1}$）负责校验所有位置编号的二进制表示中第 $i$ 位为1的位置。

校验过程：

1. 计算每个校验位的值（使所负责的位置的异或值为0）
2. 接收方重新计算校验位
3. 校验子 $S = S_r S_{r-1} ... S_1$ 的二进制值即为错误位置

海明距离：两个码字之间不同比特位的个数。检测 $d$ 个错误需要海明距离 $d+1$，纠正 $d$ 个错误需要海明距离 $2d+1$。

5. 三种差错控制方法对比

方法	检错能力	纠错能力	开销	复杂度	应用
奇偶校验	检测奇数个错误	无	1 bit	低	简单场景
CRC	可检测≤r个错误	无	r bit	中	以太网、PPP
海明码	可检测2位错误	可纠正1位错误	r bit	高	内存校验

---

三、记忆与理解辅助

1. CRC口诀："补零做除法，余数就是FCS"——数据后补$r-1$个0，除以生成多项式，余数即校验码
2. 海明码口诀："2的幂次放校验，校验子指向错位"——校验位在1,2,4,8位置，校验子的值就是错误位置
3. 海明距离公式："检$d$错要$d+1$，纠$d$错要$2d+1$"

---

四、例题与精解

例题1（基础巩固）

题目：设数据为 1101011011，生成多项式 $G(x) = x^4 + x + 1$（即 10011），求CRC校验码。

命题意图：考查CRC的模2除法计算。

精解：

1. 审题分析：数据 $D = 1101011011$，$G = 10011$（5位，$r=4$），需在数据后补4个0。

2. 解题思路：用模2除法（异或）计算余数。

3. 完整步骤：

   • $D' = 1101011011$0000（补4个0）
   • 模2除法：$11010110110000 \div 10011$
   • 计算过程：

     11010110110000
     10011
     ------
      10011
      10011
      ------
       00001101
       00000000
       ------
        11011000
        10011
        ------
         1000000
         10011
         ------
          0011000
          00000
          ------
           11000
           10011
           ------
            10110
            10011
            ------
             01010
             00000
             ------
              10100
              10011
              ------
               0111

   • 余数 $R = 0111$
   • 发送的帧为 11010110110111

4. 方法反思：模2除法就是逐位异或，注意每步只看最高位是否为1来决定是否做异或。

例题2（中等提升）

题目：在数据为4位的情况下，求海明码的校验位数和编码方案。若数据为 1011，求编码后的海明码。

命题意图：考查海明码的编码过程。

精解：

1. 审题分析：数据位 $m = 4$，需要确定校验位数 $r$。

2. 解题思路：用 $2^r \geq m + r + 1$ 确定 $r$，然后确定校验位和数据位的位置。

3. 完整步骤：

   • 确定校验位数：$2^r \geq 4 + r + 1$
     • $r=2$: $4 \geq 7$，不满足
     • $r=3$: $8 \geq 8$，满足
     • 需要 3个校验位
   • 总位数 = 4 + 3 = 7，位置编号1–7
   • 校验位位置：1($P_1$), 2($P_2$), 4($P_3$)
   • 数据位位置：3($D_1$), 5($D_2$), 6($D_3$), 7($D_4$)
   • 数据 1011 分配：$D_1=1, D_2=0, D_3=1, D_4=1$
   • 各校验位的校验范围：
     • $P_1$（位置1）：校验位置1,3,5,7 → $P_1 \oplus D_1 \oplus D_2 \oplus D_4 = 0$ → $P_1 \oplus 1 \oplus 0 \oplus 1 = 0$ → $P_1 = 0$
     • $P_2$（位置2）：校验位置2,3,6,7 → $P_2 \oplus D_1 \oplus D_3 \oplus D_4 = 0$ → $P_2 \oplus 1 \oplus 1 \oplus 1 = 0$ → $P_2 = 1$
     • $P_3$（位置4）：校验位置4,5,6,7 → $P_3 \oplus D_2 \oplus D_3 \oplus D_4 = 0$ → $P_3 \oplus 0 \oplus 1 \oplus 1 = 0$ → $P_3 = 0$
   • 海明码：位置1–7 = 0 1 1 0 0 1 1

4. 方法反思：海明码的核心是校验位的分配和校验范围的确定。校验子 $S_3S_2S_1$ 的二进制值指向错误位置。

---

五、考情分析

• 考查频次：CRC计算和海明码计算近5年出现≥4次
• 常见题型：计算题
• 分值占比：5–8分
• 命题趋势：CRC模2除法和海明码编码/检错是408必考内容，几乎每年都有。基于大纲与命题规律推测

---

六、易错点提醒

1. 错误表现：CRC模2除法中出现借位 错误原因：习惯性地做普通二进制除法 正确理解：模2除法是异或运算，没有进位和借位

2. 错误表现：海明码中校验位位置放错 错误原因：忘记校验位在 $2^i$ 位置（1,2,4,8...） 正确理解：位置编号从1开始，校验位在1,2,4,8等2的幂次位置

3. 错误表现：认为CRC可以纠错 错误原因：混淆检错和纠错 正确理解：CRC只能检错，不能纠错。海明码才能纠错

---

七、来源标注

• 依据2026考研统考大纲
• 依据《计算机网络》（第8版）谢希仁版
• 依据大学本科经典教材共识