《crc32校验理解与实现》由会员分享，可在线阅读，更多相关《crc32校验理解与实现（3页珍藏版）》请在金锄头文库上搜索。
1、一、 CRC的作用CRC的英文全称为Cyclic Redundancy Check（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生成多项式说明根据不同的需求，生成多项式有多种类型，说明如下表：名称生成多项式CRC-4x4+x1+1CRC-8x8+x2+
3、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原理实例说明下面使用一个实例说明校验码生成及其除法规则。已知原始数据的二进制序列是1010，采用的生成多
4、项式是CRC-8类型100000111。原始数据对应的多项式是t(x)=x3+x1，生成多项式是Gx=x8+x2+x1+1。大家可以看到上面的一个现象，就是不用除了，原数据对应的二进制序列对应的多项式就已经是余数多项式了，这样CRC运算就没有意义了。所以要保证每一位都能进行运算，需要对在原始数据的二进制序列后加若干0，0的个数由生成多项式的最高指数（阶数）决定，这里就是补充8个0，原数据二进制序列变成101000000000，对应对多项式就是x8tx=x11+x9。这样可以保证CRC除法至少进行一次。除法过程如下图示：结果是110110，对应多项式是x5+x4+x2+x1校验码是110110。
5、（六）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个寄存器。其中的异或运算的位置根据生成多项式来确定。下面八上面的图示的过程转换成算法描述：1、 寄存器全部初始化为0。2、 每次位移全
6、部进行。3、 其中的异或操作的输入需要两个位，其中一位是R7的移出位，另外一个就是右边的异或运算输出。4、 结束条件是原数据位都进行了输入。运算步骤过程图示：输入原数据二进制序列101000000000，每个位输入完毕，则算法完毕。移出寄存器R7-R2xorR1xorR0xor输入0000000000000000+000+010+1100000000+010+100+0000000010+100+010+1100000100+010+100+0000001010+100+000+0000010100+000+000+0000101000+000+000+0001010000+000+000+0
7、010100011+011+011+0001000110+110+100+0010001101+111+011+0000011010+110+100+00结果00110110注意其中+是异或运算，异或运算就是不进位的加法。结果与前面多项式余数一样都是110110三、 CRC的实现下面采用伪代码的方式说明算法：定义8位积存器register8=0;定义原始数据input;把原始数据左移8位input=8;While(input数据没有处理完毕) If(register8首位=1) register8=1; if(input读入的数据=1) 将register8的低位设置=1；register8=register8 XOR 00000111else register8=1; if(input读入的数据=1) 将register8的低位设置=1；上面的00000111是对应多项式的二进制表示，对其中8的位省略。四、 CRC的代码
