CRC計(jì)算方法與C實(shí)現(xiàn)

CRC的全稱為CyclicRedundancyCheck，中文名稱為循環(huán)冗余校驗(yàn)。它是一類重要的線性分組碼，編碼和解碼方法簡(jiǎn)單，檢錯(cuò)和糾錯(cuò)能力強(qiáng)，在通信領(lǐng)域廣泛地用于實(shí)現(xiàn)差錯(cuò)控制。實(shí)際上，除數(shù)據(jù)通信外，CRC在其它很多領(lǐng)域也是大有用武之地的。例如我們讀軟盤上的文件，以及解壓一個(gè)ZIP文件時(shí)，偶爾會(huì)碰到“BadCRC”錯(cuò)誤，由此它在數(shù)據(jù)存儲(chǔ)方面的應(yīng)用可略見一斑。差錯(cuò)控制理論是在代數(shù)理論基礎(chǔ)上建立起來的。這里我們著眼于介紹CRC的算法與實(shí)現(xiàn)，對(duì)原理只能捎帶說明一下。若需要進(jìn)一步了解線性碼、分組碼、循環(huán)碼、糾錯(cuò)編碼等方面的原理，可以閱讀有關(guān)資料。利用CRC進(jìn)行檢錯(cuò)的過程可簡(jiǎn)單描述為：在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的r位監(jiān)督碼(CRC碼)，附在原始信息后邊，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共k+r位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn)，以確定傳送中是否出錯(cuò)。這個(gè)規(guī)則，在差錯(cuò)控制理論中稱為“生成多項(xiàng)式”。1代數(shù)學(xué)的一般性算法在代數(shù)編碼理論中，將一個(gè)碼組表示為一個(gè)多項(xiàng)式，碼組中各碼元當(dāng)作多項(xiàng)式的系數(shù)。例如1100101表示為1?x6+1?x5+0?x4+0?x3+1?x2+0?x+1,即x6+x5+x2+l。設(shè)編碼前的原始信息多項(xiàng)式為P(x),P(x)的最高幕次加l等于k；生成多項(xiàng)式為G(x),G(x)的最高幕次等于r；CRC多項(xiàng)式為R(x)；編碼后的帶CRC的信息多項(xiàng)式為T(x)。發(fā)送方編碼方法：將P(x)乘以xr(即對(duì)應(yīng)的二進(jìn)制碼序列左移r位)，再除以G(x),所得余式即為R(x)。用公式表示為T(x)=xrP(x)+R(x)接收方解碼方法：將T(x)除以G(x),如果余數(shù)為0,則說明傳輸中無錯(cuò)誤發(fā)生，否則說明傳輸有誤。舉例來說，設(shè)信息碼為1100,生成多項(xiàng)式為1011，即P(x)=x3+x2,G(x)=x3+x+1,計(jì)算CRC的過程為xrP(x)x3(x3+x2) x6+x5 x = = =(x3+x2+x)+ G(x)x3+x+1 x3+x+1 x3+x+1即R(x)=x。注意到G(x)最高幕次r=3，得出CRC為010。如果用豎式除法，計(jì)算過程為11101011/1100000 （1100左移3位）10111010101100100000010因此，T(x)=(x6+x5)+(x)=x6+x5+x,即1100000+010=1100010如果傳輸無誤，T(x)x6+x5+x = =x3+x2+x,G(x)x3+x+1無余式。回頭看一下上面的豎式除法，如果被除數(shù)是1100010，顯然在商第三個(gè)1時(shí)，就能除盡。上述推算過程，有助于我們理解CRC的概念。但直接編程來實(shí)現(xiàn)上面的算法，不僅繁瑣，效率也不高。實(shí)際上在工程中不會(huì)直接這樣去計(jì)算和驗(yàn)證CRC。下表中列出 名稱生成多項(xiàng)式簡(jiǎn)記式*應(yīng)用舉例CRC-4x4+x+1ITUG.704CRC-12x12+x11+x3+x+1CRC-16x16+x12+x2+11005IBMSDLCCRC-ITU**x16+x12+x5+11021ISOHDLC,ITUX.25,V.34/V.41/V.42,PPP-FCSCRC-32x32+x26+x23+...+x2+x+104C11DB7ZIP,RAR,IEEE802LAN/FDDI,IEEE1394,PPP-FCSCRC-32cx32+x28+x27+...+x8+x6+11EDC6F41SCTP*生成多項(xiàng)式的最高冪次項(xiàng)系數(shù)是固定的1，故在簡(jiǎn)記式中，將最高的1統(tǒng)一去掉了，如04C11DB7實(shí)際上是104C11DB7。**前稱CRC-CCITT。ITU的前身是CCITTo2硬件電路的實(shí)現(xiàn)方法多項(xiàng)式除法,可用除法電路來實(shí)現(xiàn)。除法電路的主體由一組移位寄存器和模2加法器(異或單元)組成。以CRC-ITU為例，它由16級(jí)移位寄存器和3個(gè)加法器組成，見下圖(編碼/解碼共用)。編碼、解碼前將各寄存器初始化為"1"，信息位隨著時(shí)鐘移入。當(dāng)信息位全部輸入后，從寄存器組輸出CRC結(jié)果。3比特型算法上面的CRC-ITU除法電路，完全可以用軟件來模擬。定義一個(gè)寄存器組，初始化為全"1"。依照電路圖，每輸入一個(gè)信息位，相當(dāng)于一個(gè)時(shí)鐘脈沖到來，從高到低依次移位。移位前信息位與bitO相加產(chǎn)生臨時(shí)位，其中bitl5移入臨時(shí)位，bitlO、bit3還要加上臨時(shí)位。當(dāng)全部信息位輸入完成后，從寄存器組取出它們的值，這就是CRC碼。typedefunsignedcharbit;typedefunsignedcharbyte;typedefunsignedshortul6;typedefunion{ul6val;struct{ul6bitO:l;ul6bitl:l;ul6bit2:l;ul6bit3:l;ul6bit4:l;ul6bit5:l;ul6bit6:l;ul6bit7:l;ul6bit8:l;ul6bit9:l;ul6bitlO:l;ul6bitll:l;ul6bitl2:l;ul6bitl3:l;ul6bitl4:l;ul6bitl5:l;}bits;}CRCREGS;//寄存器組CRCREGSregs;//初始化CRC寄存器組：移位寄存器置為全"1"voidcrcInitRegisters(){regs.val=0xffff;}//CRC輸入一個(gè)bitvoidcrcInputBit(bitin){bita;a=regs.bits.bitO人in;regs.bits.bit0=regs.bits.bit1;regs.bits.bit1=regs.bits.bit2;regs.bits.bit2=regs.bits.bit3;regs.bits.bit3=regs.bits.bit4人a;regs.bits.bit4=regs.bits.bit5;regs.bits.bit5=regs.bits.bit6;regs.bits.bit6=regs.bits.bit7;regs.bits.bit7=regs.bits.bit8;regs.bits.bit8=regs.bits.bit9;regs.bits.bit9=regs.bits.bit10;regs.bits.bitlO=regs.bits.bitll人a;regs.bits.bit11=regs.bits.bit12;regs.bits.bitl2=regs.bits.bitl3;regs.bits.bitl3=regs.bits.bitl4;regs.bits.bitl4=regs.bits.bitl5;regs.bits.bitl5=a;}//輸出CRC碼(寄存器組的值)ul6crcGetRegisters(){returnregs.val;crcInputBit中一步一步的移位/異或操作，可以進(jìn)行簡(jiǎn)化：voidcrcInputBit(bitin){bita;a=regs.bits.bitO人in;regs.val>>=1;if(a)regs.valA=0x8408;}細(xì)心的話，可以發(fā)現(xiàn)0x8408和0xl021(CRC-ITU的簡(jiǎn)記式)之間的關(guān)系。由于我們是從低到高輸出比特流的，將0x1021左右反轉(zhuǎn)就得到0x8408。將生成多項(xiàng)式寫成G(x)=1+x5+x12+x16,是不是更好看一點(diǎn)？下面是一個(gè)典型的PPP幀。最后兩個(gè)字節(jié)稱為FCS(FrameCheckSequence)，是前面11個(gè)字節(jié)的CRC。FF03C021040300070D0306D03A我們來計(jì)算這個(gè)PPP幀的CRC，并驗(yàn)證它。byteppp[13]={0xFF,0x03,0xC0,0x21,0x04,0x03,0x00,0x07,0x0D,0x03,0x06,0x00,0x00};inti,j;u16result;///////////以下計(jì)算FCS//初始化crcInitRegisters();//逐位輸入，每個(gè)字節(jié)低位在先，不包括兩個(gè)FCS字節(jié)for(i=0;i<11;i++){for(j=0;j<8;j++){crcInputBit((ppp[i]>>j)&1);}}//得到CRC:將寄存器組的值求反result=~crcGetRegisters();//填寫FCS,先低后高ppp[ll]=result&Oxff;ppp[12]=(result>>8)&0xff;///////////以下驗(yàn)證FCS//初始化crcInitRegisters();//逐位輸入,每個(gè)字節(jié)低位在先,包括兩個(gè)FCS字節(jié)for(i=0;i<l3;i++){for(j=0;j<8;j++){crcInputBit((ppp[i]>>j)&l);}}//得到驗(yàn)證結(jié)果result=crcGetRegisters();可以看到，計(jì)算出的CRC等于0x3AD0,與原來的FCS相同。驗(yàn)證結(jié)果等于0。初始化為全”1”，以及將寄存器組的值求反得到CRC，都是CRC-ITU的要求。事實(shí)上，不管初始化為全”1”還是全”0”，計(jì)算CRC取反還是不取反，得到的驗(yàn)證結(jié)果都是0。4字節(jié)型算法比特型算法逐位進(jìn)行運(yùn)算，效率比較低，不適用于高速通信的場(chǎng)合。數(shù)字通信系統(tǒng)(各種通信標(biāo)準(zhǔn))一般是對(duì)一幀數(shù)據(jù)進(jìn)行CRC校驗(yàn)，而字節(jié)是幀的基本單位。最常用的是一種按字節(jié)查表的快速算法。該算法基于這樣一個(gè)事實(shí)：計(jì)算本字節(jié)后的CRC碼，等于上一字節(jié)余式CRC碼的低8位左移8位,加上上一字節(jié)CRC右移8位和本字節(jié)之和后所求得的CRC碼。如果我們把8位二進(jìn)制序列數(shù)的CRC(共256個(gè))全部計(jì)算出來，放在一個(gè)表里，編碼時(shí)只要從表中查找對(duì)應(yīng)的值進(jìn)行處理即可。CRC-ITU的計(jì)算算法如下：寄存器組初始化為全”1”(0xFFFF)。寄存器組向右移動(dòng)一個(gè)字節(jié)。剛移出的那個(gè)字節(jié)與數(shù)據(jù)字節(jié)進(jìn)行異或運(yùn)算，得出一個(gè)指向值表的索引。索引所指的表值與寄存器組做異或運(yùn)算。數(shù)據(jù)指針加1,如果數(shù)據(jù)沒有全部處理完，則重復(fù)步驟b。寄存器組取反，得到CRC，附加在數(shù)據(jù)之后。CRC-ITU的驗(yàn)證算法如下：寄存器組初始化為全T(OxFFFF)。寄存器組向右移動(dòng)一個(gè)字節(jié)。剛移出的那個(gè)字節(jié)與數(shù)據(jù)字節(jié)進(jìn)行異或運(yùn)算，得出一個(gè)指向值表的索引。索引所指的表值與寄存器組做異或運(yùn)算。數(shù)據(jù)指針加1,如果數(shù)據(jù)沒有全部處理完，則重復(fù)步驟b(數(shù)據(jù)包括CRC的兩個(gè)字節(jié))。寄存器組的值是否等于“MagicValue”(0xF0B8若相等則通過，否則失敗。下面是通用的CRC-ITU查找表以及計(jì)算和驗(yàn)證CRC的C語言程序：//CRC-ITU查找表constu16crctab16[]={0x0000,0x1189,0x2312,0x329b,0x4624,0x57ad,0x6536,0x74bf,0x8c48,0x9dc1,0xaf5a,0xbed3,0xca6c,0xdbe5,0xe97e,0xf8f7,0x1081,0x0108,0x3393,0x221a,0x56a5,0x472c,0x75b7,0x643e,0x9cc9,0x8d40,0xbfdb,0xae52,0xdaed,0xcb64,0xf9ff,0xe876,0x2102,0x308b,0x0210,0x1399,0x6726,0x76af,0x4434,0x55bd,0xad4a,0xbcc3,0x8e58,0x9fd1,0xeb6e,0xfae7,0xc87c,0xd9f5,0x3183,0x200a,0x1291,0x0318,0x77a7,0x662e,0x54b5,0x453c,0xbdcb,0xac42,0x9ed9,0x8f50,0xfbef,0xea66,0xd8fd,0xc974,0x4204,0x538d,0x6116,0x709f,0x0420,0x15a9,0x2732,0x36bb,0xce4c,0xdfc5,0xed5e,0xfcd7,0x8868,0x99e1,0xab7a,0xbaf3,0x5285,0x430c,0x7197,0x601e,0x14a1,0x0528,0x37b3,0x263a,0xdecd,0xcf44,0xfddf,0xec56,0x98e9,0x8960,0xbbfb,0xaa72,0x6306,0x728f,0x4014,0x519d,0x2522,0x34ab,0x0630,0x17b9,0xef4e,0xfec7,0xcc5c,0xddd5,0xa96a,0xb8e3,0x8a78,0x9bf1,0x7387,0x620e,0x5095,0x411c,0x35a3,0x242a,0x16b1,0x0738,0xffcf,0xee46,0xdcdd,0xcd54,0xb9eb,0xa862,0x9af9,0x8b70,0x8408,0x9581,0xa71a,0xb693,0xc22c,0xd3a5,0xe13e,0xf0b7,0x0840,0x19c9,0x2b52,0x3adb,0x4e64,0x5fed,0x6d76,0x7cff,0x9489,0x8500,0xb79b,0xa612,0xd2ad,0xc324,0xf1bf,0xe036,0x18c1,0x0948,0x3bd3,0x2a5a,0x5ee5,0x4f6c,0x7df7,0x6c7e,0xa50a,0xb483,0x8618,0x9791,0xe32e,0xf2a7,0xc03c,0xd1b5,0x2942,0x38cb,0x0a50,0x1bd9,0x6f66,0x7eef,0x4c74,0x5dfd,0xb58b,0xa402,0x9699,0x8710,0xf3af,0xe226,0xd0bd,0xc134,0x39c3,0x284a,0x1ad1,0x0b58,0x7fe7,0x6e6e,0x5cf5,0x4d7c,0xc60c,0xd785,0xe51e,0xf497,0x8028,0x91a1,0xa33a,0xb2b3,0x4a44,0x5bcd,0x6956,0x78df,0x0c60,0x1de9,0x2f72,0x3efb,0xd68d,0xc704,0xf59f,0xe416,0x90a9,0x8120,0xb3bb,0xa232,0x5ac5,0x4b4c,0x79d7,0x685e,0x1ce1,0x0d68,0x3ff3,0x2e7a,0xe70e,0xf687,0xc41c,0xd595,0xa12a,0xb0a3,0x8238,0x93b1,0x6b46,0x7acf,0x4854,0x59dd,0x2d62,0x3ceb,0x0e70,0x1ff9,0xf78f,0xe606,0xd49d,0xc514,0xb1ab,0xa022,0x92b9,0x8330,0x7bc7,0x6a4e,0x58d5,0x495c,0x3de3,0x2c6a,0x1ef1,0x0f78,};//計(jì)算給定長(zhǎng)度數(shù)據(jù)的16位CRC。u16GetCrc16(constbyte*pData,intnLength){u16fcs=0xffff;//初始化while(nLength>0){fcs=(fcs>>8)人crctabl6[(fcs人*pData)&Oxff];nLength--;pData++;}return~fcs;//取反}//檢查給定長(zhǎng)度數(shù)據(jù)的16位CRC是否正確。boolIsCrcl6Good(constbyte*pData,intnLength){u16fcs=0xffff;//初始化while(nLength>0){fcs=(fcs>>8)人crctab16[(fcs人*pData)&Oxff];nLength--;pData++;return(fcs==OxfOb8);//OxfOb8是CRC-ITU的"MagicValue"}使用字節(jié)型算法，前面出現(xiàn)的PPP幀F(xiàn)CS計(jì)算和驗(yàn)證過程，可用下面的程序片斷實(shí)現(xiàn)：byteppp[13]={0xFF,0x03,0xC0,0x21,0x04,0x03,0x00,0x07,0x0D,0x03,0x06,0x00,0x00};u16result;//計(jì)算CRCresult=GetCrc16(ppp,11);//填寫FCS，先低后高ppp[11]=result&0xff;ppp[12]=(result>>8)&0xff;//驗(yàn)證FCSif(IsCrc16Good(ppp,13)){}該例中