CRC校验算法与实现程序

CRC校验算法与实现程序作者：WaterShining日期：2012-10-28邮箱：[e-mail]基本原理：CRC的全称为CyclicRedundancyCheck，中文名称为循环冗余校验。利用CRC进行检错的过程可简单描述为：在发送端根据要传送的k位二进制数序列(信息码)，以一定的规则产生一个校验用的r位监督码(CRC码)，附在原始信息后边，构成一个新的二进制数序列共k+r位，然后发送出去。在接收端，根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。这个规则，在差错控制理论中称为“生成多项式”。在代数编码理论中，将一个码组表示为一个多项式，码组中各码元当作多项式的系数。例如：1100101表示为：1・x6+1・x5+0・x4+0・x3+1・x2+0・x1+1・x0，即x6+x5+x2+1。设编码前原始信息多项式为P(x)，P(x)的最高次幂加1等于k；生成多项式为G(x)，G(x)的最高次幂等于r；CRC多项式为R(x)；编码后的带CRC的信息多项式为T(x)。发送方编码方法：将P(x)乘以xr(即对应的二进制数序列左移r位)，再除以G(x)，所得余式即为R(x)，用公式表示为T(x)=xr・P(x)+R(x)；接收方解码方法：将T(x)除以G(x)，如果余数为0，则说明传输中无错误发生，否则说明传输有误。常见的生成多项式如表格1所示。名称生成多项式简记式应用举例CRC-4x4+x+10x3ITUG.704CRC-12x12+x11+x3+x+1CRC-16x16+x12+x2+10x1005IBMSDLCCRC-ITUx16+x12+x5+10x1021ISOHDLC，PPP-FCSCRC-32x32+x26+x23+…+x2+x+10x04C11DB7ZIP，RAR，PPP-FCSCRC-32cx32+x28+x27+…+x8+x6+10x1EDC6F41SCTP表1常见生成多项式及其应用说明：生成多项式的最高幂次项系数是固定的1，故在简记式中，将最高的1统一去掉了，如04C11DB7，实际上是104C11DB7。举例说明：设需要编码的二进制数序列(信息码)为1100101，共k=7个bit，生成多项式为10011，即r=4，也就是P(x)=x6+x5+x2+1，G(x)=x4+x+1，xr・P(x)=x10+x9+x6+x4，下面计算xr・P(x)除以G(x)，如图1所示，图中是按照模2和进行的，即0+0=0，1+0=1，1+1=0，0-1=1，仔细观察图1的计算规律，可以用图2所示的除法电路来实现，除法电路的主体由一组移位寄存器和模2加法器(异或单元)组成，图1中加底纹的数字代表移位寄存器中暂时存放的值。当所有的码全部输入(包括左移r位后补上的r个零)，最后存放在移位寄存器中的值就是校验码(0010)了，即b3=0，b2=1，b1=0，b0=0。0000110111010011/00001100101000000000000010000000011000000011000000011000000011001100111010010011011110000011110100111101010011100101001100010000000010图1竖式除法图2硬件除法b0b1b2b3input1100C语言程序：#defineCRC_Parity_Bits_Number4#defineCRC_Generator_Polynomial0x3//CRC-4,g(x)=x4+x+1voidCRC_ParityBits_Generator(unsignedint*BinaryDataIn,unsignedintBinaryDataIn_Length,unsignedint*CRC_ParityBits){unsignedinti;unsignedlongShift_Register=0;unsignedlongCRC_Polynomial_Register=0,temp_long;//CRC_Generator_Polynomialbitreversefor(i=0;iCRC_Parity_Bits_Number;i++){CRC_Polynomial_Register=1;CRC_Polynomial_Register+=(((unsignedlong)CRC_Generator_Polynomiali)&0x01);}//CRCloopfor(i=0;iBinaryDataIn_Length;i++){temp_long=Shift_Register&0x1;Shift_Register=(((unsignedlong)(BinaryDataIn[i]&0x1))(CRC_Parity_Bits_Number-1))+(Shift_Register1);Shift_Register^=(CRC_Polynomial_Register*temp_long);}//parityfor(i=0;iCRC_Parity_Bits_Number;i++){temp_long=Shift_Register&0x1;Shift_Register=1;Shift_Register^=(CRC_Polynomial_Register*temp_long);}//convertparityvariabletobinarydatafor(i=0;iCRC_Parity_Bits_Number;i++)CRC_ParityBits[i]=((Shift_Registeri)&0x1);}////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////unsignedintBinaryDataIn[11]={1,1,0,0,1,0,1};unsignedintCRC_ParityBits[CRC_Parity_Bits_Number];voidmain(void){//generatCRCparityCRC_ParityBits_Generator(BinaryDataIn,7,CRC_ParityBits);//abreakpointputhere}//运行程序后CRC_ParityBits[4]={0,0,1,0}，证明了程序的正确性，对于其他的生成多项式，只需要改变宏定义就可以了。