【科普向】谁都能看懂的CRC（循环冗余校验）原理

循环冗余校验（Cyclic Redundancy Check， CRC）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。

在数据传输过程中，无论传输系统的设计再怎么完美，差错总会存在，这种差错可能会导致在链路上传输的一个或者多个帧被破坏(出现比特差错，0变为1，或者1变为0)，从而接受方接收到错误的数据。为尽量提高接受方收到数据的正确率，在接收方接收数据之前需要对数据进行差错检测，当且仅当检测的结果为正确时接收方才真正收下数据。检测的方式有多种，常见的有奇偶校验、因特网校验和循环冗余校验等。循环冗余校验是一种用于校验通信链路上数字传输准确性的计算方法（通过某种数学运算来建立数据位和校验位的约定关系的）。发送方计算机使用某公式计算出被传送数据所含信息的一个值，并将此值 附在被传送数据后，接收方计算机则对同一数据进行相同的计算，应该得到相同的结果。如果这两个 CRC结果不一致，则说明发送中出现了差错，接收方计算机可要求发送方计算机重新发送该数据。

在计算机网络通信中运用CRC校验时相对于其他校验方法就有一定的优势。CRC可以高比例的纠正信息传输过程中的错误，可以在极短的时间内完成数据校验码的计算，并迅速完成纠错过程，通过数据包自动重发的方式使得计算机的通信速度大幅提高，对通信效率和安全提供了保障。由于 CRC 算法检验的检错能力极强，且检测成本较低，因此在对于编码器和电路的检测中使用较为广泛。从检错的正确率与速度、成本等方面，都比奇偶校验等校验方式具有优势。因而，CRC 成为计算机信息通信领域最为普遍的校验方式。

在对CRC算法进行具体说明前，先来看看什么是模二运算。

移位寄存器的每一级只可能有两种不同的存数(或状态)，分别用0和1来表示。这里， 0和1不再具有一般数量的含义，而只具有逻辑含义。对于这样一种只包含0和1两个元素(符号)的集合(叫做二元集)来说，普通的四则运算不再适用，因而必须重新规定一种新的运算规则。所谓模二运算就是这样一种新的运算规则。

模二运算是一种二进制算法。与四则运算相同，模二运算也包括模二加、模二减、模二乘、模二除四种二进制运算。而且，模二运算也使用与四则运算相同的运算符，即“+”表示模二加，“－”表示模二减，“×”或“·”表示模二乘，“÷”或“/”表示模二除。与四则运算不同的是模二运算不考虑进位和借位，即模二加法是不带进位的二进制加法运算，模二减法是不带借位的二进制减法运算。这样，两个二进制位相运算时，这两个位的值就能确定运算结果，不受前一次运算的影响，也不对下一次造成影响。模二运算是编码理论中多项式运算的基础，也是CRC校验技术中的核心部分。

示例： 很容易看出：

这里重点关注模二除法，因为它与CRC算法密切相关，它有三个性质：

对任意的二进制数都构造与其对应的一个二进制系数多项式。例如：10011B，其对应的二进制系数多项式为 P ( x ) = x 4 + x + 1 P(x)=x^{4}+x+1 P(x)=x4+x+1

CRC算法中，对于二进制数都是以二进制系数多项式去描述的。

基于上述铺垫，我们现在可以对CRC算法进行具体说明：CRC 算法的基本思想是将传输的数据当做一个位数很长的数。将这个数模二除以另一个数。得到的余数作为校验数据附加到原数据后面。 实际应用时，发送方和接收方按以下方式通信：

假设要传输的原始数据为1101011011B，发送方和接收方在通信前约定好的除数为10011B。由于除数10011B是五位数（5bit），那么假设余数（即CRC码）为四位数（4bit）。因为现在余数未知，所以在进行模二除法运算前先将余数设为0000B，即待发送的数据为11010110110000B。下面开始进行模二除法运算来确定余数（即CRC码）： 可见余数（即CRC码）为1110B，因此发送方实际发送的是11010110111110B。接收方在接收后需要将其模二除以10011B来进行CRC校验： 可见余数为0，因此本次通信没有差错。

下面开始运用数学语言来对CRC算法进行描述（就是开始不说人话了hhh）：

设原始数据为 D ( x ) D(x) D(x)，约定好的除数为 P ( x ) P(x) P(x)， P ( x ) P(x) P(x)最高次数为r，模二除法运算的余数为 R ( x ) R(x) R(x)，即 R ( x ) = [ 2 r D ( x ) ]   m o d   P ( x ) R(x)=[2^{r}D(x)]\,mod\,P(x) R(x)=[2rD(x)]modP(x)，CRC码为 F ( x ) F(x) F(x)，实际发送的数据为 T ( x ) T(x) T(x)。显然， T ( x ) = 2 r D ( x ) + F ( x ) T(x)=2^{r}D(x)+F(x) T(x)=2rD(x)+F(x)。 所以CRC算法问题变为：求解 F ( x ) F(x) F(x)使 T ( x )   m o d   P ( x ) = 0 T(x)\,mod\,P(x)=0 T(x)modP(x)=0。（这里不考虑正负，所以取模和取余等效）

而 T ( x )   m o d   P ( x ) = [ 2 r D ( x ) + F ( x ) ]   m o d   P ( x ) = { [ 2 r D ( x ) ]   m o d   P ( x ) + F ( x )   m o d   P ( x ) }   m o d   P ( x ) = { R ( x ) + F ( x )   m o d   P ( x ) }   m o d   P ( x ) T(x)\,mod\,P(x)\\=[2^{r}D(x)+F(x)]\,mod\,P(x)\\=\{[2^{r}D(x)]\,mod\,P(x)+F(x)\,mod\,P(x)\}\,mod\,P(x)\\=\{R(x)+F(x)\,mod\,P(x)\}\,mod\,P(x) T(x)modP(x)=[2rD(x)+F(x)]modP(x)={[2rD(x)]modP(x)+F(x)modP(x)}modP(x)={R(x)+F(x)modP(x)}modP(x)

注意，这里是模二加法。因此，取 F ( x ) = R ( x ) F(x)=R(x) F(x)=R(x)可以使 { R ( x ) + F ( x )   m o d   P ( x ) }   m o d   P ( x ) = [ R ( x ) + R ( x ) ]   m o d   P ( x ) = 0   m o d   P ( x ) = 0 \{R(x)+F(x)\,mod\,P(x)\}\,mod\,P(x)=[R(x)+R(x)]\,mod\,P(x)=0\,mod\,P(x)=0 {R(x)+F(x)modP(x)}modP(x)=[R(x)+R(x)]modP(x)=0modP(x)=0。

故 F ( x ) = R ( x ) = [ 2 r D ( x ) ]   m o d   P ( x ) F(x)=R(x)=[2^{r}D(x)]\,mod\,P(x) F(x)=R(x)=[2rD(x)]modP(x)。

上面介绍了CRC基本原理以及 F ( x ) F(x) F(x)的求解，但一直没有探讨如何来“约定”一个好的 P ( x ) P(x) P(x)。实际上， P ( x ) P(x) P(x)是由一种称为本原元的特殊多项式计算而来的， P ( x ) P(x) P(x)应该满足：

基于这些限定条件，在有限域内求解本原元以及对 P ( x ) P(x) P(x)的取值是通信领域的一个研究课题（没有再深究下去了）。

下面列出常用的研究成果：

表中的多项式均省略了最高位（1）。 从这里可以很容易看出奇偶校验实际上是CRC校验的其中之一（CRC-1）。

CRC算法的编程实现方法较多，例如直接计算、正向查表、逆向查表等。这里以直接计算CRC32为例说明其编程实现：

CRC-32/ISO-HDLC算法模型 width=32 poly=0x04c11db7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xcbf43926 residue=0xdebb20e3 name=“CRC-32/ISO-HDLC” （数据来源：http://reveng.sourceforge.net/crc-catalogue/）

其中：

下面开始根据此模型编制实现代码（C/C++）：

运行结果与模型中的一致： 注意，该算法对数据流逐位进行计算，效率很低。实际应用中较常用的算法之一是按字节查表的快速算法，即先把八位二进制数的CRC码提前计算好并放入表中，实际对数据流处理时可以按字节查表来快速处理。其具体实现这里就不展开了。有兴趣可以继续浏览博主的另一篇博文：https://blog.csdn.net/weixin_44256803/article/details/111794445