CRC循环校验介绍&C语言编程实现

叁歲伎倆 2023-07-25 06:15 109阅读 0赞

# 一、CRC循环校验码 #

### 1、理论解释： ###

**(1) 预先确定的多项式G(X)：**

Gx：生成码，这个是可以人为设定的，它就是CRC里面所谓的生成多项式对应的系数。

其中，Gx 的首位和最后一位的系数必须为1

**(2) 信息码，待发送的原始数据序列：Kx**

Kx：信息码，就是指要发送的信息，是一组1、0组合的字符串（当然可以看作是整数，或者浮点数等，在程序里是把它看作字符串的，长度可以自定）。

**(3) CRC码/循环冗余校验码（CRC），简称循环码**

Rx：指冗余码。

**(4) 信息码+冗余码/（最终接收到的数据也就是经过冗余码处理后的信息码）**

Tx：指真正发送出去的码字

*  举例：

以CRC16为例,16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以2^16）后，再除以一个多项式，最后所得到的余数既是CRC码，如下式所示，其中K(X)表示n位的二进制序列数，G(X)为多项式，Q(X)为整数，R(X)是余数（既CRC码）。  
K(X)>>16=G(x)Q(x)+R(x)  
求CRC码所采用模2加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。生成CRC码的多项式如下，其中CRC-16和CRC-CCITT产生16位的CRC码，而CRC-32则产生的是32位的CRC码  
接收方将接收到的二进制序列数（包括信息码和CRC码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误，关于其原理这里不再多述。用软件计算CRC码时，接收方可以将接收到的信息码求CRC码，比较结果和接收到的CRC码是否相同。

*  示例计算：

下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式为G（X） = X^4 + X^3 + 1，要求出二进制序列10110011的CRC校验码。下面是具体的计算过程：

（1）首先把生成多项式转换成二进制数，由G（X） = X^4 + X^3 + 1可以知道（，它一共是5位（总位数等于最高位的幂次加1，即4+1=5），然后根据多项式各项的含义（多项式只列出二进制值为1的位，也就是这个二进制的第4位、第3位、第0位的二进制均为1，其它位均为0）很快就可得到它的二进制比特串为11001。

（2）因为生成多项式的位数为5，根据前面的介绍，得知CRC校验码的位数为4（校验码的位数比生成多项式的位数少1）。因为原数据帧10110011，在它后面再加4个0，得到101100110000，然后把这个数以“模2除法”方式除以生成多项式，得到的余数，即CRC校验码为0100，如下图所示。注意参考前面介绍的“模2除法”运算法则。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1d3VrdTEyMw_size_16_color_FFFFFF_t_70][]

（3）把上步计算得到的CRC校验码0100替换原始帧101100110000后面的四个“0”，得到新帧101100110100。再把这个新帧发送到接收端。

（4）当以上新帧到达接收端后，接收端会把这个新帧再用上面选定的除数11001以“模2除法”方式去除，验证余数是否为0，如果为0，则证明该帧数据在传输过程中没有出现差错，否则出现了差错。

通过以上CRC校验原理的剖析和CRC校验码的计算示例的介绍，大家应该对这种看似很复杂的CRC校验原理和计算方法应该比较清楚了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1d3VrdTEyMw_size_16_color_FFFFFF_t_70 1][]

*  百度百科中的流程解释：

实际的CRC校验码生成是采用二进制的模2算法（即减法不借位、加法不进位）计算出来的，这是一种异或操作。下面通过一些例子来进一步解释CRC的基本工作原理。假设：

(1) 设约定的生成多项式为G(x)=x4+x+1，其二进制表示为10011，共5位，其中k=4。

(2) 假设要发送数据序列的二进制为101011(即f(x))，共6位。

(3) 在要发送的数据后面加4个0(生成f(x)\*xk)/左移4位，二进制表示为1010110000，共10位。

(4) 用生成多项式的二进制表示10011去除乘积1010110000，按模2算法求得余数比特序列为0100（注意余数一定是k位的）。

(5) 将余数添加到要发送的数据后面，得到真正要发送的数据的比特流：1010110100，其中前6位为原始数据，后4位为CRC校验码。

(6) 接收端在接收到带CRC校验码的数据后，如果数据在传输过程中没有出错，将一定能够被相同的生成多项式G(x)除尽，如果数据在传输中出现错误，生成多项式G(x)去除后得到的结果肯定不为0。

### 2、编码实现： ###

如在IBM的SDLC(同步数据链路控制)规程中使用的CRC-16（也就是这个除数一共是17位）生成多项式为g(x)= *x*^16 + *x^*15 + *x^*2 +1（对应二进制比特串为：11000000000000101）

即：crc16 = 0x00018005; //生成码CRC-16:

对应的二进制位：11000000000000101 生成码为17位，冗余码16位

其中，生成码和信息码之间位异或(^)运算；

参考：

1、[循环冗余校验码][Link 1]

2、[CRC码计算及校验原理的最通俗诠释][CRC]

3、[CRC校验算法学习(这个算法看了很多遍了,都是囫囵吞枣,这次将资料拷贝到这里,好好学习一下)][CRC 1]

4、[CRC校验原理及代码][CRC 2]

5、[CRC校验][CRC 3]

6、[循环冗余校验（CRC）——C语言版][CRC_C]

7、[ CRC循环校验C语言版本][CRC_C 1]

8、[CRC校验码原理、实例、手动计算][CRC 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1d3VrdTEyMw_size_16_color_FFFFFF_t_70]: /images/20230528/4791514aad794289958d623cd77d9246.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1d3VrdTEyMw_size_16_color_FFFFFF_t_70 1]: /images/20230528/5763a7e3b4df4fc6a36c504931b37ab6.png
[Link 1]: https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E5%86%97%E4%BD%99%E6%A0%A1%E9%AA%8C%E7%A0%81/10168758?fromtitle=CRC%E6%A0%A1%E9%AA%8C&fromid=3439037&fr=aladdin
[CRC]: https://blog.csdn.net/lycb_gz/article/details/8201987?depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-2&utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-2
[CRC 1]: http://www.52rd.com/Blog/Detail_RD.Blog_zx_zx_13124.html
[CRC 2]: https://blog.csdn.net/qiaobt/article/details/81661345?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1
[CRC 3]: https://blog.csdn.net/k331922164/article/details/51648707
[CRC_C]: https://blog.csdn.net/qq_42144047/article/details/88696171
[CRC_C 1]: https://blog.csdn.net/qq_42144047/article/details/90241248
[CRC 4]: https://www.cnblogs.com/bugutian/p/6221783.html