循环冗余校验CRC

循环冗余校验（Cyclic Redundancy Check, CRC）是一种广泛应用于数字通信和存储系统中的检错码技术。其核心原理是在待发送的数据末尾附加若干位冗余码（FCS，帧检验序列），使得到的新数据能够被一个预先选定的除数整除。接收端用相同的除数除以接收到的数据，若余数为零，则认为数据在传输过程中未发生错误；否则，判定数据出错。CRC以强大的检错能力和高效的硬件实现著称，是计算机网络（如以太网）、存储介质（硬盘、光盘）及众多通信协议中的标准检错方案。

一、CRC的核心原理

1.1 基本原理框图

设待发送的原始数据为二进制序列 M，其长度为 k 位。收发双方预先约定一个长度为 r+1 位的生成多项式（除数）G。

发送端执行如下步骤：

1. 在原始数据 M 末尾添加 r 个 0，得到 M * 2^r（相当于左移 r 位）

2. 用模2除法（即异或运算）计算 M * 2^r 除以 G 的余数 R

3. 将 R 作为冗余码附加到原始数据 M 后，构成最终发送的帧 T = M * 2^r + R。M 的长度为 k 位，R 的长度为 r 位，T 的长度为 k + r 位

接收端收到数据后，用同一个除数 G 除以接收到的数据 T'。若余数为 0，则判定数据无错；若余数不为 0，则判定数据在传输过程中发生了错误。

1.2 模2除法（多项式除法）

模2除法是CRC运算的基础，其特点如下：

• 减法和加法等价，都等同于按位异或（XOR）操作

• 不产生进位或借位

• 每一步比较被除数的最高位和除数的最高位，若被除数当前最高位为1，则商1并执行异或操作；若为0，则商0并直接跳过

模2除法计算示例：计算101101除以1101：

text

1 1 1 0 0 1 (商) _______________ 1101 | 1 0 1 1 0 1 1 1 0 1 -------（异或） 1 1 0 0 1 1 0 1 ------- 0 0 1 0 1 1 1 0 1 ------- 1 0 0 0 1 1 0 1 ------- 1 0 1

运算结果：余数为101。

二、生成多项式的选择

生成多项式