奇偶校验与 CRC

大纲定位

本条已移出计算机组成原理大纲

不在现行 408 计组大纲内。CO「二、数据的表示和运算」现为数制与编码 / 运算方法和运算电路 / 整数的表示和运算 / 浮点数的表示和运算四条，「三、存储器层次结构」七条中亦无校验码。

但它没有消失，只是换了科目：408 计算机网络「三、数据链路层（三）差错控制」的检错编码（奇偶校验、CRC）与纠错编码（海明码）仍在纲。本篇的模 2 除法、码距分析就是那边的解题手段。

谁该读：① 备考 CN 差错控制的考生，原理完全通用；② 目标院校自命题的考生，不少院校仍按传统计组大纲命题；③ 想搞懂内存 ECC / SSD 纠错的读者。 谁可以跳过：只考统考 408、且 CN 部分已按网络教材单独复习的考生，本篇可作选读。

考情分析

CO 侧现存真题仅 2013 年一道 2 分选择题（已加编者注说明大纲变动），不必按高强度考点投入时间。奇偶校验与 CRC 的能力目标是：会判断码距与检错/纠错能力、会做模 2 除法求校验位并在接收端验证。海明码内容较多，单独成篇讨论。

检错与纠错的基础：码距

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

最小码距 $d$	能力
$d \geq 2$	检测 1 位错误
$d \geq 3$	检测 2 位，或纠正 1 位
$d \geq 2 t + 1$	纠正 $t$ 位错误
$d \geq t_{d} + t_{c} + 1$ （ $t_{d} > t_{c}$ ）	同时检测 $t_{d}$ 位、纠正 $t_{c}$ 位

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

奇偶校验：最小知识

在数据位后加 1 位校验位，使整个码字里 1 的个数 满足奇偶约定：

偶校验：全部位异或结果为 0（1 的个数为偶数）
奇校验：全部位异或结果为 1

最小码距 $d = 2$ ，所以只能检测奇数位错误，不能纠错——错 2 位时奇偶性不变，检不出来。

CRC：最小知识

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

模 2 运算就是异或：不进位、不借位，加和减都是 XOR。

发送 ： 数据左移 r 位 \div 生成多项式 \Rightarrow 余数即校验位

接收 ： 整个码字 \div 生成多项式 \Rightarrow 余数为 0 则无错

CRC 能检测所有长度 $\leq r$ 的突发错误。

完整推导和例题在网络那边：模 2 除法的竖式走查、生成多项式的选取、检错能力证明，见计算机网络博客的差错控制一篇——那里是纲内内容，写得比这里详细。本篇只保留 CO 侧遗留真题用得上的最小集合。

考点清单

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

真题练习

2013Q152分

奇偶校验与 CRC

大纲定位

考情分析

检错与纠错的基础：码距

奇偶校验：最小知识

CRC：最小知识

考点清单

真题练习

相关真题（1题）

相关文章

奇偶校验与 CRC ​

大纲定位 ​

考情分析 ​

检错与纠错的基础：码距 ​

奇偶校验：最小知识 ​

CRC：最小知识 ​

考点清单 ​

真题练习 ​

相关真题（1题）

相关文章

奇偶校验与 CRC

大纲定位

考情分析

检错与纠错的基础：码距

奇偶校验：最小知识

CRC：最小知识

考点清单

真题练习