原文地址為：CRC校驗(yàn)和CRC各種算法
?

1、簡介

CRC即循環(huán)冗余校驗(yàn)碼（Cyclic Redundancy Check）：是數(shù)據(jù)通信領(lǐng)域中最常用的一種查錯(cuò)校驗(yàn)碼，其特征是信息字段和校驗(yàn)字段的長度可以任意選定。循環(huán)冗余檢查（CRC）是一種數(shù)據(jù)傳輸檢錯(cuò)功能，對數(shù)據(jù)進(jìn)行多項(xiàng)式計(jì)算，并將得到的結(jié)果附在幀的后面，接收設(shè)備也執(zhí)行類似的算法，以保證數(shù)據(jù)傳輸?shù)恼_性和完整性。

2、工作原理

?

循環(huán)冗余校驗(yàn)碼（CRC）的基本原理是：在K位信息碼后再拼接R位的校驗(yàn)碼，整個(gè)編碼長度為N位，因此，這種編碼也叫（N，K）碼。對于一個(gè)給定的（N，K）碼，可以證明存在一個(gè) 最高次冪為N-K=R的多項(xiàng)式G(x)。根據(jù)G(x)可以生成K位信息的校驗(yàn)碼，而G(x)叫做這個(gè)CRC碼的生成多項(xiàng)式。 校驗(yàn)碼的具體生成過程為：假設(shè)要發(fā)送的信息用多項(xiàng)式C(X)表示，將C(x)左移R位（可表示成C(x)*2 R），這樣C(x)的右邊就會(huì)空出R位，這就是校驗(yàn)碼的位置。用 C(x)*2 R?除以生成多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。

任意一個(gè)由二進(jìn)制位串組成的代碼都可以和一個(gè)系數(shù)僅為‘0’和‘1’取值的多項(xiàng)式一一對應(yīng)。例如：代碼1010111對應(yīng)的 多項(xiàng)式為x 6+x 4+x 2+x+1，而多項(xiàng)式為x 5+x 3+x 2+x+1對應(yīng)的代碼101111。

?

3、CRC16 三種算法及c實(shí)現(xiàn)

?

標(biāo)準(zhǔn)CRC生成多項(xiàng)式如下表：

??名稱???????生成多項(xiàng)式?????????????簡記式*??標(biāo)準(zhǔn)引用
?? CRC-4?????? x4+x+1????????????????? 3???????? ITU G.704
?? CRC-8?????? x8+x5+x4+1????????????? 0x31???????????????????
?? CRC-8?????? x8+x2+x1+1????????????? 0x07???????????????????
?? CRC-8?????? x8+x6+x4+x3+x2+x1?????? 0x5E
?? CRC-12????? x12+x11+x3+x+1????????? 80F
?? CRC-16????? x16+x15+x2+1??????????? 8005????? IBM SDLC
?? CRC16-CCITT x16+x12+x5+1??????????? 1021????? ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS
?? CRC-32????? x32+x26+x23+...+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS
?? CRC-32c???? x32+x28+x27+...+x8+x6+1 1EDC6F41 SCTP
?????????????????????????????
?? 生成多項(xiàng)式的最高位固定的1，故在簡記式中忽略最高位1了，如0x1021實(shí)際是0x11021。
I、基本算法（人工筆算）：
?? 以CRC16-CCITT為例進(jìn)行說明，CRC校驗(yàn)碼為16位，生成多項(xiàng)式17位。假如數(shù)據(jù)流為4字節(jié)：BYTE[3]、BYTE[2]、BYTE[1]、BYTE[0]；
數(shù)據(jù)流左移16位，相當(dāng)于擴(kuò)大256×256倍，再除以生成多項(xiàng)式0x11021，做不借位的除法運(yùn)算（相當(dāng)于按位異或），所得的余數(shù)就是CRC校驗(yàn)碼。
發(fā)送時(shí)的數(shù)據(jù)流為6字節(jié)：BYTE[3]、BYTE[2]、BYTE[1]、BYTE[0]、CRC[1]、CRC[0]；

?? 注意：使用長除法進(jìn)行計(jì)算式，需要將除數(shù)多項(xiàng)式與預(yù)置位0x0000或0xFFFF異或以后再進(jìn)行計(jì)算。

II、計(jì)算機(jī)算法1（比特型算法）：
1)將擴(kuò)大后的數(shù)據(jù)流（6字節(jié)）高16位（BYTE[3]、BYTE[2]）放入一個(gè)長度為16的寄存器；
2)如果寄存器的首位為1，將寄存器左移1位(寄存器的最低位從下一個(gè)字節(jié)獲得)，再與生成多項(xiàng)式的簡記式異或；
??? 否則僅將寄存器左移1位(寄存器的最低位從下一個(gè)字節(jié)獲得)；
3)重復(fù)第2步，直到數(shù)據(jù)流（6字節(jié)）全部移入寄存器；
4)寄存器中的值則為CRC校驗(yàn)碼CRC[1]、CRC[0]。

III、計(jì)算機(jī)算法2（字節(jié)型算法）：256^n表示256的n次方
??? 把按字節(jié)排列的數(shù)據(jù)流表示成數(shù)學(xué)多項(xiàng)式，設(shè)數(shù)據(jù)流為BYTE[n]BYTE[n－1]BYTE[n－2]、、、BYTE[1]BYTE[0]，表示成數(shù)學(xué)表達(dá)式為BYTE[n]×256^n+BYTE[n-1]×256^(n-1)

+...+BYTE[1]*256+BYTE[0]，在這里+表示為異或運(yùn)算。設(shè)生成多項(xiàng)式為G17（17bit），CRC碼為CRC16。
??? 則，CRC16＝(BYTE[n]×256^n+BYTE[n-1]×256^(n-1)+...+BYTE[1]×256+BYTE[0])×256^2/G17，即數(shù)據(jù)流左移16位，再除以生成多項(xiàng)式G17。
??? 先變換BYTE[n-1]、BYTE[n-1]擴(kuò)大后的形式，
??? CRC16＝BYTE[n]×256^n×256^2/G17+BYTE[n-1]×256^(n-1)×256^2/G17+...+BYTE[1]×256×256^2/G17+BYTE[0]×256^2/G17
???????? ＝(Z[n]+Y[n]/G17)×256^n+BYTE[n-1]×256^(n-1)×256^2/G17+...+BYTE[1]×256×256^2/G17+BYTE[0]×256^2/G17
???????? ＝Z[n]×256^n+{Y[n]×256/G17+BYTE[n-1]×256^2/G17}×256^(n-1)+...+BYTE[1]×256×256^2/G17+BYTE[0]×256^2/G17
???????? ＝Z[n]×256^n+{(YH8[n]×256+YHL[n])×256/G17+BYTE[n-1]×256^2/G17}×256^(n-1)+...+BYTE[1]×256×256^2/G17+BYTE[0]×256^2/G17
???????? ＝Z[n]×256^n+{YHL[n]×256/G17+(YH8[n]+BYTE[n-1])×256^2/G17}×256^(n-1)+...+BYTE[1]×256×256^2/G17+BYTE[0]×256^2/G17
??? 這樣就推導(dǎo)出，BYTE[n-1]字節(jié)的CRC校驗(yàn)碼為{YHL[n]×256/G17+(YH8[n]+BYTE[n-1])×256^2/G17}，即上一字節(jié)CRC校驗(yàn)碼Y[n]的高8位（YH8[n]）與本字節(jié)BYTE[n-1]異或，

該結(jié)果單獨(dú)計(jì)算CRC校驗(yàn)碼（即單字節(jié)的16位CRC校驗(yàn)碼，對單字節(jié)可建立表格，預(yù)先生成對應(yīng)的16位CRC校驗(yàn)碼），所得的CRC校驗(yàn)碼與上一字節(jié)CRC校驗(yàn)碼Y[n]的低8位（YL8[n]）

乘以256（即左移8位）異或。然后依次逐個(gè)字節(jié)求出CRC，直到BYTE[0]。
??? 字節(jié)型算法的一般描述為：本字節(jié)的CRC碼，等于上一字節(jié)CRC碼的低8位左移8位，與上一字節(jié)CRC右移8位同本字節(jié)異或后所得的CRC碼異或。???
??? 字節(jié)型算法如下：
??? 1)CRC寄存器組初始化為全"0"(0x0000)。（注意：CRC寄存器組初始化全為1時(shí)，最后CRC應(yīng)取反。）
??? 2)CRC寄存器組向左移8位,并保存到CRC寄存器組。
??? 3)原CRC寄存器組高8位（右移8位）與數(shù)據(jù)字節(jié)進(jìn)行異或運(yùn)算，得出一個(gè)指向值表的索引。
??? 4)索引所指的表值與CRC寄存器組做異或運(yùn)算。
??? 5)數(shù)據(jù)指針加1，如果數(shù)據(jù)沒有全部處理完，則重復(fù)步驟2)。
??? 6)得出CRC。

?

CRC?CCITT—1，“-1”的意思是CRC的初值為0Xffff。

方法1：將存有數(shù)據(jù)的字節(jié)數(shù)組進(jìn)行逐位計(jì)算，求得字節(jié)形式的CRC

typedef unsigned __int16??? INT16U;
#define CRC_SEED?? 0xFFFF?? // 該位稱為預(yù)置值，使用人工算法（長除法）時(shí) 需要將除數(shù)多項(xiàng)式先與該與職位 異或 ，才能得到最后的除數(shù)多項(xiàng)式
#define POLY16 0x1021? // 該位為簡式書寫 實(shí)際為0x11021
INT16U crc16(unsigned char *buf,unsigned short length)
{
? INT16U shift,data,val;
? int i;

? shift = CRC_SEED;

? for(i=0;i<length;i++) {
??? if((i % 8) == 0)
????? data = (*buf++)<<8;
??? val = shift ^ data;
??? shift = shift<<1;
??? data = data <<1;
??? if(val&0x8000)
????? shift = shift ^ POLY16;
? }
? return shift;
}?

2、查表法

static?unsigned?short?ccitt_table[256]?=?{
0x0000,?0x1021,?0x2042,?0x3063,?0x4084,?0x50A5,?0x60C6,?0x70E7,
0x8108,?0x9129,?0xA14A,?0xB16B,?0xC18C,?0xD1AD,?0xE1CE,?0xF1EF,
0x1231,?0x0210,?0x3273,?0x2252,?0x52B5,?0x4294,?0x72F7,?0x62D6,
0x9339,?0x8318,?0xB37B,?0xA35A,?0xD3BD,?0xC39C,?0xF3FF,?0xE3DE,
0x2462,?0x3443,?0x0420,?0x1401,?0x64E6,?0x74C7,?0x44A4,?0x5485,
0xA56A,?0xB54B,?0x8528,?0x9509,?0xE5EE,?0xF5CF,?0xC5AC,?0xD58D,
0x3653,?0x2672,?0x1611,?0x0630,?0x76D7,?0x66F6,?0x5695,?0x46B4,
0xB75B,?0xA77A,?0x9719,?0x8738,?0xF7DF,?0xE7FE,?0xD79D,?0xC7BC,
0x48C4,?0x58E5,?0x6886,?0x78A7,?0x0840,?0x1861,?0x2802,?0x3823,
0xC9CC,?0xD9ED,?0xE98E,?0xF9AF,?0x8948,?0x9969,?0xA90A,?0xB92B,
0x5AF5,?0x4AD4,?0x7AB7,?0x6A96,?0x1A71,?0x0A50,?0x3A33,?0x2A12,
0xDBFD,?0xCBDC,?0xFBBF,?0xEB9E,?0x9B79,?0x8B58,?0xBB3B,?0xAB1A,
0x6CA6,?0x7C87,?0x4CE4,?0x5CC5,?0x2C22,?0x3C03,?0x0C60,?0x1C41,
0xEDAE,?0xFD8F,?0xCDEC,?0xDDCD,?0xAD2A,?0xBD0B,?0x8D68,?0x9D49,
0x7E97,?0x6EB6,?0x5ED5,?0x4EF4,?0x3E13,?0x2E32,?0x1E51,?0x0E70,
0xFF9F,?0xEFBE,?0xDFDD,?0xCFFC,?0xBF1B,?0xAF3A,?0x9F59,?0x8F78,
0x9188,?0x81A9,?0xB1CA,?0xA1EB,?0xD10C,?0xC12D,?0xF14E,?0xE16F,
0x1080,?0x00A1,?0x30C2,?0x20E3,?0x5004,?0x4025,?0x7046,?0x6067,
0x83B9,?0x9398,?0xA3FB,?0xB3DA,?0xC33D,?0xD31C,?0xE37F,?0xF35E,
0x02B1,?0x1290,?0x22F3,?0x32D2,?0x4235,?0x5214,?0x6277,?0x7256,
0xB5EA,?0xA5CB,?0x95A8,?0x8589,?0xF56E,?0xE54F,?0xD52C,?0xC50D,
0x34E2,?0x24C3,?0x14A0,?0x0481,?0x7466,?0x6447,?0x5424,?0x4405,
0xA7DB,?0xB7FA,?0x8799,?0x97B8,?0xE75F,?0xF77E,?0xC71D,?0xD73C,
0x26D3,?0x36F2,?0x0691,?0x16B0,?0x6657,?0x7676,?0x4615,?0x5634,
0xD94C,?0xC96D,?0xF90E,?0xE92F,?0x99C8,?0x89E9,?0xB98A,?0xA9AB,
0x5844,?0x4865,?0x7806,?0x6827,?0x18C0,?0x08E1,?0x3882,?0x28A3,
0xCB7D,?0xDB5C,?0xEB3F,?0xFB1E,?0x8BF9,?0x9BD8,?0xABBB,?0xBB9A,
0x4A75,?0x5A54,?0x6A37,?0x7A16,?0x0AF1,?0x1AD0,?0x2AB3,?0x3A92,
0xFD2E,?0xED0F,?0xDD6C,?0xCD4D,?0xBDAA,?0xAD8B,?0x9DE8,?0x8DC9,
0x7C26,?0x6C07,?0x5C64,?0x4C45,?0x3CA2,?0x2C83,?0x1CE0,?0x0CC1,
0xEF1F,?0xFF3E,?0xCF5D,?0xDF7C,?0xAF9B,?0xBFBA,?0x8FD9,?0x9FF8,
0x6E17,?0x7E36,?0x4E55,?0x5E74,?0x2E93,?0x3EB2,?0x0ED1,?0x1EF0
};

unsigned?short?crc_ccitt(unsigned?char?*q,?int?len)
{
unsigned?short?crc?=?0;

while?(len--?>?0)
crc?=?ccitt_table[(crc?>>?8?^?*q++)?&?0xff]?^?(crc?<<?8);
return?~crc

}

總結(jié)

以上是生活随笔為你收集整理的CRC校验和CRC各种算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。