奇偶校验与 CRC

考情分析

校验码是 408 数据表示章节的固定考点。奇偶校验以概念选择题为主，CRC 则经常出大题，要求手工做模 2 除法求出校验码。海明码由于内容较多，单独成篇讨论。

检错与纠错的基础：码距

码距（Hamming Distance）：两个合法编码之间不同位的个数。编码方案的最小码距 $d$ 决定了检错纠错能力。

最小码距 $d$	能力
$d\ge 2$	检测 1 位错误
$d\ge 3$	检测 2 位，或纠正 1 位
$d\ge 2t+1$	纠正 $t$ 位错误
$d\ge t_d+t_c+1$（$t_d>t_c$）	同时检测 $t_d$ 位、纠正 $t_c$ 位

检错和纠错不能同时达到理论上限。如 $d=3$，可选"检 2 纠 0"或"检 0 纠 1"，不能同时"检 2 纠 1"。

奇偶校验

在数据后附加 1 位校验位，使整个编码中 1 的个数满足奇偶性要求。

偶校验

所有位（含校验位）中 1 的个数为偶数：

$$P=b_{n-1}\oplus b_{n-2}\oplus \cdots \oplus b_0$$

奇校验

所有位中 1 的个数为奇数：

$$P=\overline{b_{n-1}\oplus b_{n-2}\oplus \cdots \oplus b_0}$$

检错能力与局限

奇偶校验的最小码距 $d=2$：

错误类型	能否检测	原因
1 位出错	能	1 的奇偶性改变
2 位出错	不能	奇偶性不变
3 位出错	能	奇偶性改变
偶数位出错	不能	奇偶性始终不变

总结：只能检测奇数位错误，不能纠错（不知道哪一位出错），也不能检测偶数位错误。

硬件实现极其简单——只需一个多输入 XOR 门。

三种校验方式

方式	校验范围	检错能力
水平校验	每个字按行加 1 位	检单字内奇数位错
垂直校验	同一位列加 1 位	检同列奇数位错
水平 + 垂直	行列都加校验位	可定位出错位，能纠 1 位错

CRC 循环冗余校验

CRC 是一种基于多项式除法的校验方法，检错能力远强于奇偶校验，广泛用于网络通信和存储系统。

基本原理

1. 将数据位串看作一个二进制多项式 $M(x)$
2. 选定一个 $r$ 阶的生成多项式 $G(x)$（最高次幂为 $r$，共 $r+1$ 位）
3. 将 $M(x)$ 左移 $r$ 位（数据后补 $r$ 个 0），得到 $M(x)\cdot x^r$
4. 对 $G(x)$ 做模 2 除法，余数即为 $r$ 位 CRC 校验码
5. 用余数替换补的 0，拼接在数据后面发送

模 2 运算规则

模 2 运算中加法和减法都是 XOR（异或），不进位不借位：

$$1+1=0,0+1=1,1-1=0,0-1=1$$

模 2 除法的过程类似普通长除法，但每步"减法"用 XOR 替代，且对齐被除数最高位为 1 时商 1、为 0 时商 0。

CRC 计算步骤

1. 数据 $k$ 位，生成多项式 $r+1$ 位（$r$ 阶）
2. 数据后补 $r$ 个 0，得到 $k+r$ 位被除数
3. 模 2 除法除以生成多项式
4. 余数不足 $r$ 位时高位补 0
5. 余数替换第 2 步中补的 0 → 发送的完整编码为 $k+r$ 位

接收端校验

接收到 $k+r$ 位数据后，用同一个生成多项式做模 2 除法：

• 余数 = 0：传输正确（或未检测到的错误）
• 余数 $\ne$ 0：传输出错

CRC 的检错能力

能力	条件
检测所有 1 位错误	$G(x)$ 至少有两项
检测所有奇数位错误	$G(x)$ 含因子 $(x+1)$
检测所有双位错误	$G(x)$ 为本原多项式
检测所有长度 $\le r$ 的突发错误	总是成立

常见生成多项式

名称	多项式	二进制	校验位数
CRC-4（ITU）	$x^4+x+1$	10011	4
CRC-8	$x^8+x^2+x+1$	100000111	8
CRC-16（IBM）	$x^{16}+x^{15}+x^2+1$	17 位	16
CRC-32（IEEE）	$x^{32}+x^{26}+\cdots +1$	33 位	32

例题

例 1：数据 $M=1011001$（7 位），生成多项式 $G(x)=x^4+x+1$（即 10011，4 阶），求 CRC 校验码。

数据后补 4 个 0：10110010000

模 2 除法过程：

10110010000 | 10011
10011       |
─────       |
 01010      |
 00000      |
 ─────      |
  10100     |
  10011     |
  ─────     |
   01110    |
   00000    |
   ─────    |
    11100   |
    10011   |
    ─────   |
     11110  |
     10011  |
     ─────  |
      11010 |
      10011 |
      ───── |
       1001 ← 余数

CRC 校验码 = 1001

发送数据 = 10110011001（原数据 + 校验码）

例 2：接收到数据 10110011001，用生成多项式 10011 校验。

将 10110011001 对 10011 做模 2 除法，余数为 0000，传输正确。

若接收到 10110011011（最后一位翻转），模 2 除法余数不为 0，检测到错误。

例 3：对 8 位数据 11001010 做偶校验编码。

数据中 1 的个数 = 4（偶数），偶校验位 $P=0$。

编码结果：110010100。

考点清单

• [ ] 码距与检错纠错能力：$d\ge 2$ 检 1 位，$d\ge 3$ 检 2 或纠 1
• [ ] 偶校验：所有位异或为 0；奇校验：异或为 1
• [ ] 奇偶校验只能检测奇数位错误，不能纠错
• [ ] CRC 计算步骤：数据补 $r$ 个 0 → 模 2 除法 → 取余数
• [ ] 模 2 运算规则：加减都是 XOR，不进位不借位
• [ ] 接收端校验：整体除以生成多项式，余数为 0 则无错
• [ ] CRC 能检测所有长度 $\le r$ 的突发错误

相关文章

• 进制与进制转换
• 真值与机器数
• 定点数的编码表示
• C 语言数据类型与转换
• 定点数的移位运算
• 补码加减法与溢出判断
• Booth 乘法
• 恢复余数除法
• 不恢复余数除法
• 浮点数表示（IEEE 754）
• 浮点数运算
• 算术逻辑单元（ALU）
• 数据对齐与大小端
• 奇偶校验与 CRC
• 海明码详解

真题练习

相关真题（1题）

2013Q15选择题2分

可视化详解

海明码校验位数的计算

海明码校验码