欢迎来到天天文库
浏览记录
ID:40148466
大小:28.95 KB
页数:3页
时间:2019-07-23
《CRC32校验理解与实现》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、一、CRC的作用CRC的英文全称为CyclicRedundancyCheck(Code),中文名称为循环冗余校验(码)。它是一类重要的线性分组码,编码和解码方法简单,检错和纠错能力强,在通信领域广泛地用于实现差错控制。二、CRC的原理(一)CRC的校验过程描述1、被校验的原数据转换成二进制序列,假设共K位2、以一定规则产生一个新的二进制序列,假设共R位的。3、把新的二进制序列附加在原数据二进制序列后面,共K+R位,发送出去。4、接收端接收数据后,把原数据的K位二进制序列按相同规则产生一个R位二进制序列与附加的R位二进制序列进行比较,相同表示传递的数据没有问题,不相
2、同表示传递的数据出现错误与误差。(二)CRC的校验码生成过程描述其中对二进制序列的转换规则是CRC中的关键。校验规则规则描述如下:1、首先把原数据二进制序列可以看成一个多项式,比如10011看成多项式x4+x1+1,其中多项式系数只能是0,1。2、然后定义一个规则,也是使用多项式,这个多项式专业名称叫生成多项式。其系数也只能是0,1。3、使用原数据对应的多项式除以生成多项式,得到一个余数多项式。其系数也只能是0,1。4、余数多项式的系数转换成一个二进制,这就是CRC校验码。(三)CRC生成多项式说明根据不同的需求,生成多项式有多种类型,说明如下表:名称生成多项式C
3、RC-4x4+x1+1CRC-8x8+x2+x1+1CRC-12x12+x11+x3+x2+x1+1CRC-16x16+x15+x2+1CRC-ITUx16+x15+x5+1CRC-32x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x1+1CRC-32使用的就是上面最高指数为32的多项式,对应的二进制序列是100000100110000010001110110110111。(四)CRC多项式除法规则在一般的除法中,都使用的是减运算,但在CRC多项式除法运算中使用的是异或运算。(五)CRC原理实例说明下面使用一个实例说
4、明校验码生成及其除法规则。已知原始数据的二进制序列是1010,采用的生成多项式是CRC-8类型100000111。原始数据对应的多项式是t(x)=x3+x1,生成多项式是Gx=x8+x2+x1+1。大家可以看到上面的一个现象,就是不用除了,原数据对应的二进制序列对应的多项式就已经是余数多项式了,这样CRC运算就没有意义了。所以要保证每一位都能进行运算,需要对在原始数据的二进制序列后加若干0,0的个数由生成多项式的最高指数(阶数)决定,这里就是补充8个0,原数据二进制序列变成101000000000,对应对多项式就是x8tx=x11+x9。这样可以保证CRC除法至少
5、进行一次。除法过程如下图示:结果是110110,对应多项式是x5+x4+x2+x1校验码是110110。(六)CRC的算法上面的原理转换成程序还是比较难的,所以需要把上面过程转换成算法,同时在该算法基础上提出了很多优化算法,比如查表算法。计算机硬件已经实现了CRC的算法,对CRC-8其中使用寄存器8个,异或运算三个。因为CRC-8的生成多项式是x8+x2+x1+1,其中R0表示常数项1,R1表示x1,R2表示x2。多项式中的连续两项之间对应一个异或运算。记住R7到R0是连续的两项。R0,R1,R2,R3,R4,R5,R6,R7是8个寄存器,如果采用32,需要32个
6、寄存器。其中的异或运算的位置根据生成多项式来确定。下面八上面的图示的过程转换成算法描述:1、寄存器全部初始化为0。2、每次位移全部进行。3、其中的异或操作的输入需要两个位,其中一位是R7的移出位,另外一个就是右边的异或运算输出。4、结束条件是原数据位都进行了输入。运算步骤过程图示:输入原数据二进制序列101000000000,每个位输入完毕,则算法完毕。移出寄存器R7-R2xorR1xorR0xor输入ß000000000000000ß0+00ß0+01ß0+110000000ß0+01ß0+10ß0+000000001ß0+10ß0+01ß0+110000010
7、ß0+01ß0+10ß0+000000101ß0+10ß0+00ß0+000001010ß0+00ß0+00ß0+000010100ß0+00ß0+00ß0+000101000ß0+00ß0+00ß0+001010001ß1+01ß1+01ß1+000100011ß0+11ß0+10ß0+001000110ß1+11ß1+01ß1+000001101ß0+11ß0+10ß0+00结果00110110注意其中+是异或运算,异或运算就是不进位的加法。结果与前面多项式余数一样都是110110一、CRC的实现下面采用伪代码的方式说明算法:定义8位积存器register8=
8、0;定义原
此文档下载收益归作者所有