三、常见的CRC算法

虽然CRC可以任意定义二项式、数据长度等,但没有一个统一的标准的话,就会让整个计算变得非常的麻烦。但实际上,不同的厂家经常采用不同的标准算法,这里列出了一些国际常用的模型表:

名称多项式表示法应用举例CRC-8X8+X2+X+10X107
CRC-12X12+X11+X3+X2+X+10X180Ftelecom systemsCRC-16X16+X15+X2+10X18005Bisync, Modbus, USB, ANSI X3．28, SIA DC-07, many others; also known as CRC-16 and CRC-16-ANSICRC-CCITTX16+X12+X5+10X11021ISO HDLC, ITU X．25, V．34/V．41/V．42, PPP-FCSCRC-32X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+10x104C11DB7ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCSCRC-32CX32+X28+X27+X26+X25+X23+X22+X20+X19+X18+X14+X13+X11+X10+X9+X8+X6+10x11EDC6F41iSCSI, SCTP, G．hn payload, SSE4．2, Btrfs, ext4, Ceph

四、CRC校验算法前置知识

在学习CRC校验算法之前,先复习一下CRC会涉及的主要几个主要的算法。

1． 异或

异或,就是不同为1,相同为0,运算符号是^。

0^0 = 0
0^1 = 1
1^1 = 0
1^0 = 1

异或运算存在如下几个规律,需要了解。

0^x = x 即0 异或任何数等于任何数
1^x = ～x 即1异或任何数等于任何数取反
x^x = 0 即任何数与自己异或,结果为0
a ^ b = b ^ a 交换律
a ^ (b ^ c) = (a ^ b) ^c 结合律
2． 模2加法

模2加法相对于普通的算术加法,主要的区别在模2加法,不做进位处理。具体结果如下。0+0 = 00+1 = 11+1 = 01+0 = 1我们发现模2加法的计算结果,同异或运算结果一模一样。进一步推演,我们会发现,异或运算的5个规律,同样适合于模2加法。这里,就不在一一列举了。

3． 模2减法

模2减法相对于普通的算术减法,主要的区别在模2减法,不做借位处理。具体结果如下。0-0 = 00-1 = 11-1 = 01-0 = 1我们发现模2减法的计算结果,同模2加法,以及异或的运算结果一模一样。进一步推演,我们会发现,异或运算的5个规律,同样适合于模2减法。这里,就不在一一列举了。

4． 模2除法

模2除法相对于普通的算术除法,主要的区别在模2除法,它既不向上位借位,也不比较除数和被除数的相同位数值的大小,只要以相同位数进行相除即可。

五、CRC原理

CRC原理:在K位信息码(目标发送数据)后再拼接R位校验码,使整个编码长度为N位,因此这种编码也叫(N,K)码。

通俗的说,就是在需要发送的信息后面附加一个数(即校验码),生成一个新的发送数据发送给接收端。这个数据要求能够使生成的新数据被一个特定的数整除。这里的整除需要引入模 2除法的概念。

那么,CRC校验的具体做法就是

(1)选定一个标准除数(K位二进制数据串)

(2)在要发送的数据(m位)后面加上K-1位0,然后将这个新数(M+K-1位)以模2除法的方式除以上面这个标准除数,所得到的余数也就是该数据的CRC校验码(注:余数必须比除数少且只少一位,不够就补0)

(3)将这个校验码附在原m位数据后面,构成新的M+K-1位数据,发送给接收端。

(4)接收端将接收到的数据除以标准除数,如果余数为0则认为数据正确。

注意:CRC校验中有两个关键点:

一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串(或多项式);

二是把原始帧与上面选定的除进行二进制除法运算,计算出FCS。

前者可以随机选择,也可按国际上通行的标准选择,但最高位和最低位必须均为“1”

六、循环冗余的计算 

实例:

由于CRC-32、CRC-16、CCITT和CRC-4的编码过程基本一致,只有位数和生成多项式不一样,下面就举例,来说明CRC校验码生成过程。

对于数据1110 0101(16#E5),以指定除数11011求它的CRC校验码,其过程如下:

使用上面计算的校验和和消息数据,可以创建要传输的码字。

有时候,我们需要填充checksum到制定的位置,这就涉及到字节序问题,建议用memcpy()进行拷贝。

七、代码实现

实现算法参考网络相关代码,进行整理并验证,可直接使用。crc．c

 
*一口Linux
*2021．6．21
*version: 1．0．0
#include "crc．h"
#include

crc．h

 
*一口Linux
*2021．6．21
*version: 1．0．0
#ifndef __CRC_H__
#define __CRC_H__
#include

main．c

 
*一口Linux
*2021．6．21
*version: 1．0．0
#include

注意

不同的CRC算法,对00H或FFH数据流的计算结果不一样,部分算法存在校验结果也为00H或FFH的情况(也就意味着存储空间处于初始化状态时:全0或全1,CRC校验反而是正确的),在应用中需要注意避免。