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