CRC(Cyclic Redundancy Check)校驗(yàn)應(yīng)用較為廣泛，以前為了處理簡(jiǎn)單，在程序中大多數(shù)采用LRC(Longitudinal Redundancy Check)校驗(yàn)，LRC校驗(yàn)很好理解，編程實(shí)現(xiàn)簡(jiǎn)單。用了一天時(shí)間研究了CRC的C語(yǔ)言實(shí)現(xiàn)，理解和掌握了基本原理和C語(yǔ)言編程。結(jié)合自己的理解簡(jiǎn)單寫下來(lái)。
1、CRC簡(jiǎn)介
CRC檢驗(yàn)的基本思想是利用線性編碼理論，在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)檢驗(yàn)碼r位(就是CRC碼)，附在信息后面，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共(k+r)位，最后發(fā)送出去。接收端根據(jù)同樣的規(guī)則校驗(yàn)，以確定傳送中是否出錯(cuò)。接收端有兩種處理方式：1、計(jì)算k位序列的CRC碼，與接收到的CRC比較，一致則接收正確。2、計(jì)算整個(gè)k+r位的CRC碼，若為0，則接收正確。
CRC碼有多種檢驗(yàn)位數(shù)，8位、16位、32位等，原理相同。16位的CRC碼產(chǎn)生的規(guī)則是先將要發(fā)送的二進(jìn)制序列數(shù)左移16位（即乘以2的16次方后），除以一個(gè)多項(xiàng)式，最后所得到的余數(shù)就是CRC碼。
求CRC碼所采用的是模2運(yùn)算法則，即多項(xiàng)式除法中采用不帶借位的減法運(yùn)算，運(yùn)算等同于異或運(yùn)算。這一點(diǎn)要仔細(xì)理解，是編程的基礎(chǔ)。
CRC-16: (美國(guó)二進(jìn)制同步系統(tǒng)中采用) G(X) = X16 + X15 + X2 + 1
CRC-CCITT: (由歐洲CCITT推薦) G(X) = X16 + X12 + X5 + 1
CRC-32: G(X) = X32 + X26 + X23 + X22 + X16 +X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1
2、按位計(jì)算CRC
采用CRC-CCITT多項(xiàng)式，多項(xiàng)式為0x11021，C語(yǔ)言編程時(shí)，參與計(jì)算為0x1021，這個(gè)地方得深入思考才能體會(huì)其中的奧妙，分享一下我的思路：當(dāng)按位計(jì)算CRC時(shí)，例如計(jì)算二進(jìn)制序列為1001 1010 1010 1111時(shí)，將二進(jìn)制序列數(shù)左移16位，即為1001 1010 1010 1111 (0000 0000 0000 0000)，實(shí)際上該二進(jìn)制序列可拆分為1000 0000 0000 0000 (0000 0000 0000 0000) + 000 0000 0000 0000 (0000 0000 0000 0000) + 00 0000 0000 0000 (0000 0000 0000 0000) + 1 0000 0000 0000 (0000 0000 0000 0000) + ……
現(xiàn)在開始分析運(yùn)算：
<1>對(duì)第一個(gè)二進(jìn)制分序列求余數(shù)，豎式除法即為0x10000 ^ 0x11021運(yùn)算，后面的0位保留；
<2>接著對(duì)第二個(gè)二進(jìn)制分序列求余數(shù)，將第一步運(yùn)算的余數(shù)*2后再和第二個(gè)二進(jìn)制分序列一起對(duì)0x11021求余，這一步理解應(yīng)該沒(méi)什么問(wèn)題。如果該分序列為0，無(wú)需計(jì)算。
<3>對(duì)其余的二進(jìn)制序列求余與上面兩步相同。
<4>計(jì)算到最后一位時(shí)即為整個(gè)二進(jìn)制序列的余數(shù)，即為CRC校驗(yàn)碼。
該計(jì)算方法相當(dāng)于對(duì)每一位計(jì)算，運(yùn)算過(guò)程很容易理解，所占內(nèi)存少，缺點(diǎn)是一位一位計(jì)算比較耗時(shí)。
下面給出C語(yǔ)言實(shí)現(xiàn)方法：
while( len-- ) {
for(i = 0x80; i != 0; i = i >> 1) {
temp = temp * 2;
if((temp & 0x10000) != 0)
temp = temp ^ 0x11021;
if((*ptr & i) != 0)
temp = temp ^ (0x10000 ^ 0x11021);
}
ptr++;
}
crc = temp;
printf("0x%x ",crc);
}
while( len-- ) {
for(i = 0x80; i != 0; i = i >> 1) {
if((crc & 0x8000) != 0) {
crc = crc << 1;
crc = crc ^ 0x1021;
}
else {
crc = crc << 1;
}
if((*ptr & i) != 0) {
crc = crc ^ 0x1021;
}
}
ptr++;
}
printf("0x%x ",crc);
}