CRC（循环冗余校验，Cyclic Redundancy Check）的原理

欢迎各位朋友关注“郝旭帅电子设计团队”公众号，本公众号会定时更新相关技术类资料、软件等等，感兴趣的朋友可以浏览一下本公众号的其他“模块”，希望各位朋友都能在本公众号获得一些自己想要的“东西”。

本篇主要是讨论CRC（循环冗余校验，Cyclic Redundancy Check）的原理

核心思想

CRC 的本质是一种根据数据生成简短校验码的方法。它的核心思想是：将一段数据（比如一个文件、一帧网络数据）看作一个很长的二进制数，用一个预先选定好的“除数”（称为生成多项式）去除它，得到的余数就是 CRC 校验码。

发送方计算数据的 CRC 并随数据一起发送。接收方收到数据后，用同样的算法再计算一次 CRC，并与收到的 CRC 进行比较：

如果一致，则认为数据在传输过程中极大概率没有出错。

如果不一致，则肯定有错误发生，接收方可以请求重发。

注：接收方也可以将数据和CRC码一起计算，并且判断是否结果正确。

模 2 运算 (Modulo-2 Arithmetic)

这是 CRC 计算的数学基础。它非常简单，没有进位和借位，等同于异或 (XOR) 操作。

模 2 加法: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 0 (等价于 0 XOR 0, 0 XOR 1, etc.)

模 2 减法: 与加法完全相同！0 - 0 = 0, 1 - 0 = 1, 1 - 1 = 0, 0 - 1 = 1

正是因为减法和加法一样，所以在 CRC 的“除法”过程中，每一步的“减法”实际上就是异或操作。

生成多项式 (Generator Polynomial)

这就是上面提到的“除数”。它是一个预先定义好的二进制数，通常用多项式的形式表示，因为这样能清晰地看出其数学特性。

示例: 常见的 CRC-32 多项式：

x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1

如何转换为二进制：多项式中存在的项，其对应位为 1；不存在的项，其对应位为 0。

最高次项是 x³²，所以总位数是 33 位 (从 x³² 到 x⁰)。

根据上面的多项式，其二进制表示为： 1 00000100 11000001 00011101 10110111 (对应位：x³²,x³¹(无,0),x³⁰(无,0)...x²⁶(有,1), x²⁵(无,0)...)

生成多项式的选择是 CRC 算法的关键，它决定了CRC的检错能力。位数越多（最高次幂越高），检错能力越强。

计算 CRC 的过程非常类似于做除法竖式，但使用的是模 2 运算。

步骤：

附加零 (Appending Zeros): 在原始数据的末尾附加 n 个零。n 是生成多项式的位数减一（即 CRC 校验码的长度）。例如，如果使用 CRC-16（17 位多项式），就附加 16 个零。

模 2 除法: 用附加零后的新数据作为“被除数”，用生成多项式作为“除数”，进行模 2 除法（即每一步用异或操作代替减法）。

取余数: 除法过程结束后，得到的余数就是 CRC 校验码。这个余数的位数一定比除数少一位（即刚好是 n 位）。

组成发送帧: 用这个计算得到的 CRC 余数替换掉第一步中附加的 n 个零，随原始数据一起发送。

一个简单的计算示例（手工计算）：

原始数据 (Data): 11001010101

生成多项式 (Poly): 11011 (CRC-4 的一种)

步骤 1: 附加 4 个零 (因为多项式 11011 是 5 位)，得到新的被除数: 110010101010000

步骤 2 & 3: 进行模 2 除法，求余数。

CRC 校验码: 0011 最终发送的数据: 原始数据 11001010101 + CRC 0011 = 110010101010011

接收方收到 110010101010011 后，用同样的生成多项式 11011 去除它。因为发送的数据已经是“原始数据 + 真余数”了，如果传输没有错误，这个除法得到的余数应该为 0。

强大的检错能力：检测所有奇数个错误位。检测所有长度小于等于 CRC 长度（n位）的突发错误。以非常高的概率检测更长的突发错误。例如，CRC-32 能检测到所有长度在 33 位以下的错误，以及对超过 33 位的错误有 99.99999997% 的检出率。

易于硬件实现： CRC 的计算可以通过一个简单的线性反馈移位寄存器 (LFSR, Linear Feedback Shift Register) 高效实现，硬件成本极低，速度非常快。这对于网络设备、存储控制器等需要高速处理数据流的场景至关重要。

对数据的敏感性：即使只有 1 比特的数据改变，也会导致计算出的 CRC 值发生巨大且不可预测的变化（“雪崩效应”），这使得错误很容易被发现。

本篇内容中有部分资源来源于网络，如有侵权，请联系作者。