1.2.3 CRC循环冗余校验码
📝 学习目标
- 理解CRC校验码的基本原理
- 掌握多项式表示和运算方法
- 熟练进行CRC编码和校验计算
- 了解常用CRC标准及其应用
🎯 CRC基本概念
什么是CRC
CRC（Cyclic Redundancy Check）：循环冗余校验码
- 一种基于多项式运算的错误检测码
- 能检测突发错误和随机错误
- 广泛应用于数据通信和存储系统
CRC的优势
| 特点 | 说明 |
|---|---|
| 检错能力强 | 能检测所有单比特错误和双比特错误 |
| 突发错误检测 | 能检测长度≤r的所有突发错误 |
| 实现简单 | 硬件实现容易，计算速度快 |
| 标准化 | 有多种国际标准可选择 |
🔢 多项式表示
二进制多项式
原理：将二进制数表示为多项式形式
示例：
二进制：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
多项式除法：
1111
________
10011 ) 11010000
10011
------
10110
10011
------
01010
0
------
10100
10011
------
01110
0
------
1110余数：1110
CRC码字：1101 + 1110 = 11011110
示例2：错误检测
接收码字：11001110（假设第2位出错）
校验计算：
1101
________
10011 ) 11001110
10011
------
10111
10011
------
01001
0
------
10011
10011
------
00001余数：0001 ≠ 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压缩文件
- 嵌入式系统：串口通信校验
🧪 例题（按难度）
简单（3题）
下面练习按“真实考试”方式做：先提交答案，再查看解析。
0) 生成多项式转换（填空）
将生成多项式 `G(x)=x^3 + x + 1` 转换为二进制表示（从 x^3 到 x^0）。
1) 编码计算（填空）
信息位：1011；生成多项式：x^3 + x + 1。求 CRC 码字。
2) 校验计算（单选）
接收码字：1011101；生成多项式：x^3 + x + 1。判断是否有错误。
中级（3题）
3) 多项式转换（填空）
将二进制 10110 转换为多项式表示（用 X^k 形式）。
将多项式 x^5 + x^2 + 1 转换为二进制表示。
若生成多项式最高次数为 r（例如 `G(x)` 最高项为 `x^r`），则 CRC 校验位的位数通常为：
困难（1题）
4) 错误分析（单选）
下列关于 CRC 的说法正确的是：
💡 解题技巧
考试要点
- 多项式转换：熟练进行二进制与多项式互转
- 模2除法：掌握异或运算规则
- 标准应用：了解常用CRC标准
- 错误检测：理解CRC的检错能力
常见错误
- 借位错误：模2除法不需要借位
- 位数错误：生成多项式位数与校验位数的关系
- 余数处理：余数位数不足时要补0
- 应用混淆：不同CRC标准的应用场景
🔬 深入理解
CRC的数学原理
- 多项式环：CRC基于GF(2)上的多项式运算
- 生成多项式：必须是不可约多项式
- 检错能力：与生成多项式的选择有关
硬件实现
线性反馈移位寄存器(LFSR)实现：
输入数据 → [移位寄存器] → [异或门] → CRC输出📚 本课小结
- CRC原理：基于多项式除法的循环冗余校验
- 计算方法：模2除法，余数作为校验码
- 检错能力：能检测单比特、双比特和突发错误
- 实际应用：广泛用于通信和存储系统
💪 课后作业
- 完成所有练习题的计算
- 查阅CRC-32的完整多项式
- 了解硬件CRC实现原理
- 练习不同生成多项式的CRC计算