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

时间:2024-04-09 16:16:45

一、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除法”运算法则。

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

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

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

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

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

  • 百度百科中的流程解释:

       实际的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、循环冗余校验码

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

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

4、CRC校验原理及代码

5、CRC校验

6、循环冗余校验(CRC)——C语言版

7、 CRC循环校验C语言版本

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