1.2.3 CRC循环冗余校验码
本节导学
CRC 循环冗余校验码是奇偶校验之后更强的一类检错码。字幕里特别强调：软件设计师中级考试通常不要求完整手算 CRC 编码，真正要掌握的是它的特点：校验位拼接在信息位后，位数由生成多项式决定，计算使用模 2 除法，余数作为校验位，接收端余数为 0 表示通过；CRC 可检错，但通常不可纠错。
把它放在技术演进里看会更清楚：奇偶校验只用 1 位约束 1 的个数，偶数位错可能漏检；CRC 用一个事先约定的生成多项式形成多位余数，检错规则更细，因此能覆盖更多多位错误和突发错误。但 CRC 的余数通常只告诉你“校验失败”，不能唯一指出哪一位错，所以它没有替代海明码的纠错角色。
CRC 解决了奇偶校验的什么问题
CRC 是一种基于多项式除法思想的错误检测码。发送方把信息位看成一个二进制多项式，按约定的生成多项式做模 2 除法，把得到的余数作为校验位拼接到信息位后面。接收方收到完整码字后，再用同一个生成多项式检查余数。
| 要点 | 结论 |
|---|---|
| 校验位位置 | 拼接在信息位后面 |
| 校验位长度 | 由生成多项式决定 |
| 计算方法 | 用生成多项式做模 2 除法，余数作为校验位 |
| 接收端校验 | 完整码字再除以生成多项式，余数为 0 表示通过 |
| 能力 | 可检错，通常不可纠错 |
遇到 CRC 题，先抓三个关键词：
- “生成多项式”：发送方和接收方事先约定。
- “模 2 除法”：CRC 构造校验位的核心运算。
- “余数”：编码时余数作为校验位；接收端余数为 0 则认为通过。
如果选项里问“哪种校验采用模 2 运算构造校验位”，优先选 CRC 循环冗余校验。若问能力对比，CRC 是检错能力较强但通常不能纠错；海明码才是既可检错又可纠错。
生成多项式决定校验位长度
生成多项式是 CRC 的除数规则。二进制串可以表示成多项式系数，例如 1101 表示：
发送方和接收方必须使用同一个生成多项式，才能得到一致的校验判断。生成多项式不同，校验位长度和检错特性都会不同。
若生成多项式最高次数为 r，则 CRC 校验位通常是 r 位。计算时在信息位后补 r 个 0，再用生成多项式对应的二进制串做模 2 除法。
模 2 除法：减法就是异或
模 2 除法是一种不进位、不借位的二进制除法。减法在模 2 中等价于异或 XOR。
CRC 需要一种硬件容易实现、规则稳定的校验计算方式。异或运算非常适合电路实现，因此 CRC 在通信和存储中广泛使用。
做长除时，当前最高位为 1 才与除数异或；最高位为 0 时直接下移。最后留下的 r 位余数就是校验位。
CRC 的能力边界
CRC 能发现很多随机错误和突发错误，但通常不能直接指出是哪一位错，因此一般归为检错码，不归为纠错码。
CRC 的余数告诉我们“校验关系是否成立”，但不同错误模式可能产生同类非零余数；仅凭余数通常无法唯一定位错误位。
能力对比题记住：奇偶校验简单但弱；CRC 检错强但通常不纠错；海明码可以定位并纠正典型单比特错误。
CRC 的优势与代价
| 特点 | 说明 |
|---|---|
| 检错能力强 | 合适的生成多项式可稳定检出单比特错误，并覆盖大量多位错误 |
| 突发错误检测 | 最高次数为 r 的生成多项式可检测长度不超过 r 的突发错误 |
| 实现简单 | 硬件实现容易，计算速度快 |
| 标准化 | 有多种国际标准可选择 |
这些优势的代价是需要额外的多位校验序列，并且发送方、接收方必须预先一致使用同一个生成多项式。与海明码相比，CRC 更适合“发现错误后重传”的通信场景；如果系统要求本地自动修复错误，则需要海明码或更强的纠错码。
🔢 多项式表示
二进制多项式
原理：将二进制数表示为多项式形式
示例：
二进制：1101
多项式：1×x³ + 1×x² + 0×x¹ + 1×x⁰ = x³ + x² + 1常用生成多项式
| 名称 | 多项式 | 二进制 | 位数 |
|---|---|---|---|
| CRC-4 | x⁴ + x + 1 | 10011 | 4 |
| CRC-8 | x⁸ + x² + x + 1 | 100000111 | 8 |
| CRC-12 | x¹² + x¹¹ + x³ + x² + x + 1 | 1100000001111 | 12 |
| CRC-16 | x¹⁶ + x¹⁵ + x² + 1 | 11000000000000101 | 16 |
| CRC-32 | x³² + x²⁶ + x²³ + ... | 复杂 | 32 |
🧮 CRC计算过程
编码过程
步骤：
- 确定生成多项式G(x)，位数为r+1
- 在信息位后添加r个0
- 用扩展后的信息多项式除以G(x)
- 将余数作为校验位添加到信息位后
校验过程
步骤：
- 接收到的码字除以生成多项式G(x)
- 如果余数为0，则无错误
- 如果余数不为0，则有错误
📊 计算示例
示例1：CRC-4编码
已知：
- 信息位：1101
- 生成多项式：G(x) = x⁴ + x + 1 = 10011
计算过程：
扩展信息位：1101 + 0000 = 11010000
多项式除法：
1101
________
10011 ) 11010000
10011
------
10110
10011
------
01010
00000
------
10100
10011
------
00100余数：0100
CRC码字：1101 + 0100 = 11010100
示例2：错误检测
接收码字：10010100（假设正确码字 11010100 的第2位出错）
用同一个生成多项式 10011 对接收码字做模 2 除法，余数为 1100。因为余数不为 0，所以检测到错误。
⚡ 快速计算方法
模2除法规则
- 不借位减法：实际上是异或运算
- 商的确定：被除数最高位为1时商1，为0时商0
- 余数计算：逐位进行异或运算
计算技巧
模2除法示例：
1011 ÷ 101
10
___
101)1011
101
---
001 (1⊕1=0, 0⊕0=0, 1⊕1=0)🔍 CRC标准应用
常用CRC标准
| 标准 | 多项式 | 应用领域 |
|---|---|---|
| CRC-8 | x⁸+x²+x+1 | 1-Wire总线 |
| CRC-16-IBM | x¹⁶+x¹⁵+x²+1 | Modbus协议 |
| CRC-16-CCITT | x¹⁶+x¹²+x⁵+1 | X.25协议 |
| CRC-32 | IEEE 802.3标准 | 以太网、ZIP |
| CRC-32C | x³²+x²⁸+x²⁷+... | SCTP、iSCSI |
实际应用场景
- 网络通信：以太网帧校验
- 存储系统：硬盘数据校验
- 文件系统：ZIP、RAR压缩文件
- 嵌入式系统：串口通信校验
📊 关键对比表
| 对比项 | 奇偶校验 | CRC | 海明码 |
|---|---|---|---|
| 冗余复杂度 | 低（1 位） | 中（r 位余数） | 中（按位插入校验位） |
| 检错能力 | 弱 | 强，尤其突发错误 | 可检错且可单错纠正 |
| 是否常用于纠错 | 否 | 通常否 | 是（经典单错纠正） |
| 软考考法 | 概念判断 | 模2除法/多项式互转 | r 求解+定位纠错 |
🧠 难点与易错点
- 多项式与二进制串互转时要严格按幂次对齐，不可跳位。
- 模2除法本质是异或，不存在十进制长除中的借位。
- 生成多项式次数为 r 时，补 0 位数和余数位数都应是 r。
🔑 关键词解释
- 生成多项式 G(x)：发送端和接收端共同约定的除数。
- 模2除法：按位异或的多项式除法，不进位不借位。
- CRC 余数：编码阶段得到的 r 位校验位。
- 突发错误：连续若干位发生翻转的错误模式。
🧪 例题（按难度）
简单（3题）
下面练习按“真实考试”方式做：先提交答案，再查看解析。
0) 生成多项式转换（填空）
1) 编码计算（填空）
2) 校验计算（单选）
中级（3题）
3) 多项式转换（填空）
困难（1题）
4) 错误分析（单选）
💡 解题技巧
考试要点
- 多项式转换：熟练进行二进制与多项式互转
- 模2除法：掌握异或运算规则
- 标准应用：了解常用CRC标准
- 错误检测：理解CRC的检错能力
常见错误
- 借位错误：模2除法不需要借位
- 位数错误：生成多项式位数与校验位数的关系
- 余数处理：余数位数不足时要补0
- 应用混淆：不同CRC标准的应用场景
🔍 知识扩展
CRC的数学原理
- 多项式环：CRC基于GF(2)上的多项式运算
- 生成多项式：必须是不可约多项式
- 检错能力：与生成多项式的选择有关
硬件实现
线性反馈移位寄存器(LFSR)实现：
输入数据 → [移位寄存器] → [异或门] → CRC输出📚 本课小结
- CRC原理：基于多项式除法的循环冗余校验
- 计算方法：模2除法，余数作为校验码
- 检错能力：依赖生成多项式选择，通常对单比特、常见多位错误和突发错误检出能力强
- 实际应用：广泛用于通信和存储系统
💪 课后作业
- 完成所有练习题的计算
- 查阅CRC-32的完整多项式
- 了解硬件CRC实现原理
- 练习不同生成多项式的CRC计算