本文從理論上推導出CRC算法實現原理.

1、本文從理論上推導出 CRC 算法實現原理 ,給出三種分別適應不同計算機或微控制器硬件環(huán)境的 序。讀者更能根據本算法原理 ,用不同的語言編寫出獨特風格更加實用的CRC 計算程序。關鍵詞 CRC 算法 C 語言1 引言循環(huán)冗余碼 CRC 檢驗技術廣泛應用于測控及通信領域。 CRC 計算可以靠專用的硬件來實現 , 但是對于低成 本的微控制器系統(tǒng) ,在沒有硬件支持下實現 CRC 檢驗,關鍵的問題就是如何通過軟件來完成 CRC 計算 ,也就 是 CRC 算法的問題。這里將提供三種算法 ,它們稍有不同 , 一種適用于程序空間十分苛刻但CRC 計算速度要求不高的微控制器系統(tǒng), 另一種適用于程序空間較大且 C

2、RC 計算速度要求較高的計算機或微控制器系統(tǒng),最后一種是適用于程序空間不太大 ,且 CRC 計算速度又不可以太慢的微控制器系統(tǒng)。2 CRC 簡介CRC 校驗的基本思想是利用線性編碼理論 , 在發(fā)送端根據要傳送的 k 位二進制碼序列 ,以一定的規(guī)則產生一 個校驗用的監(jiān)督碼(既 CRC 碼)r 位，并附在信息后邊，構成一個新的二進制碼序列數共(k+r)位,最后發(fā)送出 去。在接收端 ,則根據信息碼和 CRC 碼之間所遵循的規(guī)則進行檢驗 ,以確定傳送中是否出錯。16 位的 CRC 碼產生的規(guī)則是先將要發(fā)送的二進制序列數左移 16 位(既乘以)后，再除以一個多項式，最后所得到的余數既是 CRC 碼，如式

3、(2-1)式所示，其中 B(X)表示 n 位的二進制序 列數，G(X)為多項式，Q(X)為整數，R(X)是余數(既 CRC 碼)。( 2-1 )求 CRC 碼所采用模 2 加減運算法則，既是不帶進位和借位的按位加減，這種加減運算實際上就是邏輯上的異 或運算，加法和減法等價，乘法和除法運算與普通代數式的乘除法運算是一樣，符合同樣的規(guī)律。 生成 CRC 碼 的多項式如下，其中 CRC-16 和 CRC-CCITT 產生 16 位的 CRC 碼，而 CRC-32 則產生的是 32 位的 CRC 碼。 本文不討論 32 位的 CRC 算法，有興趣的朋友可以根據本文的思路自己去推導計算方法。CRC-16

4、 ：(美國二進制同步系統(tǒng)中采用)CRC-CCITT ：(由歐洲 CCITT 推薦)CRC-32 ：接收方將接收到的二進制序列數(包括信息碼和 CRC 碼)除以多項式，如果余數為 0，則說明傳輸中無錯誤 發(fā)生，否則說明傳輸有誤，關于其原理這里不再多述。 用軟件計算 CRC 碼時，接收方可以將接收到的信息碼求 CRC 碼，比較結果和接收到的 CRC 碼是否相同。3 按位計算 CRC對于一個二進制序列數可以表示為式 (3-1):(3-1)求此二進制序列數的 CRC 碼時,先乘以后(既左移 16 位)，再除以多項式 G(X)，所得的余數既是所要求的CRC 碼。如式 (3-2) 所示：(3-2)可以設：

5、 (3-3)其中 為整數，為 16 位二進制余數。將式 (3-3) 代入式 (3-2) 得：(3-4)再設： (3-5)C 語言程其中 為整數，為 16 位二進制余數，將式(3-5)代入式 (3-4)，如上類推，最后得到：(3-6)根據 CRC 的定義 ,很顯然 ,十六位二進制數 既是我們要求的 CRC 碼。式(3-5)是編程計算 CRC 的關鍵 ,它說明計算本位后的 CRC 碼等于上一位 CRC 碼乘以 2 后除以多項式 ,所 得的余數再加上本位值除以多項式所得的余數。由此不難理解下面求 CRC 碼的 C 語言程序。 *ptr 指向發(fā) 送緩沖區(qū)的首字節(jié) ,len 是要發(fā)送的總字節(jié)數 ,0 x

6、1021 與多項式有關。unsigned int cal_crc(unsigned char *ptr, unsigned char len) unsigned char i;unsigned int crc=0;while(len-!=0) for(i=0 x80; i!=0; i/=2) if(crc&0 x8000)!=0) crc*=2; cr“=0 x1021;/*余式 CRC 乘以 2 再求 CRC */else crc*=2;if(*ptr&i)!=0) crcA=0 x1021; /*再加上本位的 CRC */ptr+;return(crc);按位計算 CRC

7、雖然代碼簡單 ,所占用的內存比較少 ,但其最大的缺點就是一位一位地計算會占用很多的處理 器處理時間 ,尤其在高速通訊的場合 ,這個缺點更是不可容忍。因此下面再介紹一種按字節(jié)查表快速計算CRC 的方法。4 按字節(jié)計算 CRC不難理解 ,對于一個二進制序列數可以按字節(jié)表示為式(4-1),其中 為一個字節(jié) (共 8 位)。(4-1)求此二進制序列數的 CRC 碼時,先乘以后(既左移 16 位)，再除以多項式 G(X),所得的余數既是所要求的CRC 碼。如式 (4-2) 所示：( 4-2 )可以設： (4-3)其中 為整數 , 為 16 位二進制余數。將式 (4-3) 代入式 (4-2) 得：( 4-

8、4 )因為：( 4-5 )其中 是 的高八位 , 是 的低八位。將式( 4-5 )代入式( 4-4) ,經整理后得：( 4-6 )再設： (4-7)其中 為整數 , 為 16 位二進制余數。將式 (4-7)代入式(4-6),如上類推 ,最后得：(4-8)很顯然 , 十六位二進制數 既是我們要求的 CRC 碼。式(4-7) 是編寫按字節(jié)計算 CRC 程序的關鍵 ,它說明計算本字節(jié)后的 CRC 碼等于上一字節(jié)余式 CRC 碼的低 8 位左移 8 位后,再加上上一字節(jié) CRC 右移 8 位(也既取高 8 位)和本字節(jié)之和后所求得的 CRC 碼,如果 我們把 8 位二進制序列數的 CRC 全部計算出來

9、 ,放如一個表里 ,采用查表法 ,可以大大提高計算速度。由此不 難理解下面按字節(jié)求 CRC碼的 C 語言程序。 *ptr 指向發(fā)送緩沖區(qū)的首字節(jié) ,len 是要發(fā)送的總字節(jié)數 ,CRC 余式表是按 0 x11021 多項式求出的。unsigned int cal_crc(unsigned char *ptr, unsigned char len) unsigned int crc;unsigned char da; unsigned int crc_ta256= /* CRC 余式表 */ 0 x0000, 0 x1021, 0 x2042, 0 x3063, 0 x4084, 0 x50a5

10、,0 x60c6, 0 x70e7, 0 x8108, 0 x9129, 0 xa14a, 0 xb16b, 0 xc18c, 0 xd1ad, 0 xe1ce, 0 xf1ef, 0 x 1231, 0 x0210, 0 x3273,0 x2252, 0 x52b5, 0 x4294, 0 x72f7, 0 x62d6, 0 x9339, 0 x8318, 0 xb37b, 0 xa35a, 0 xd3bd, 0 xc39c, 0 xf3ff, 0 xe3de, 0 x2462,0 x3443, 0 x0420, 0 x1401, 0 x64e6, 0 x74c7, 0 x44a4, 0 x

11、5485, 0 xa56a, 0 xb54b, 0 x8528, 0 x9509, 0 xe5ee, 0 xf5cf, 0 xc5ac,0 xd58d, 0 x3653, 0 x2672, 0 x1611, 0 x0630, 0 x76d7, 0 x66f6, 0 x5695, 0 x46b4, 0 xb75b, 0 xa77a, 0 x9719, 0 x8738, 0 xf7df,0 xe7fe, 0 xd79d, 0 xc7bc, 0 x48c4, 0 x58e5, 0 x6886, 0 x78a7, 0 x0840, 0 x1861, 0 x2802, 0 x3823, 0 xc9cc,

12、 0 xd9ed,0 xe98e, 0 xf9af, 0 x8948, 0 x9969, 0 xa90a, 0 xb92b, 0 x5af5, 0 x4ad4, 0 x7ab7, 0 x6a96, 0 x1a71, 0 x0a50, 0 x3a33, 0 x2a12,0 xdbfd, 0 xcbdc, 0 xfbbf, 0 xeb9e, 0 x9b79, 0 x8b58, 0 xbb3b, 0 xab1a, 0 x6ca6, 0 x7c87, 0 x4ce4, 0 x5cc5, 0 x2c22, 0 x3c03,0 x0c60, 0 x1c41, 0 xedae, 0 xfd8f, 0 xcd

13、ec, 0 xddcd, 0 xad2a, 0 xbd0b, 0 x8d68, 0 x9d49, 0 x7e97, 0 x6eb6, 0 x5ed5, 0 x4ef4,0 x3e13, 0 x2e32, 0 x1e51, 0 x0e70, 0 xff9f, 0 xefbe, 0 xdfdd, 0 xcffc, 0 xbf1b, 0 xaf3a, 0 x9f59, 0 x8f78, 0 x9188, 0 x81a9,0 xb1ca, 0 xa1eb, 0 xd10c, 0 xc12d, 0 xf14e, 0 xe16f, 0 x1080, 0 x00a1, 0 x30c2, 0 x20e3, 0

14、 x5004, 0 x4025, 0 x7046, 0 x6067,0 x83b9, 0 x9398, 0 xa3fb, 0 xb3da, 0 xc33d, 0 xd31c, 0 xe37f, 0 xf35e, 0 x02b1, 0 x1290, 0 x22f3, 0 x32d2, 0 x4235, 0 x5214,0 x6277, 0 x7256, 0 xb5ea, 0 xa5cb, 0 x95a8, 0 x8589, 0 xf56e, 0 xe54f, 0 xd52c, 0 xc50d, 0 x34e2, 0 x24c3, 0 x14a0, 0 x0481,0 x7466, 0 x6447

15、, 0 x5424, 0 x4405, 0 xa7db, 0 xb7fa, 0 x8799, 0 x97b8, 0 xe75f, 0 xf77e, 0 xc71d, 0 xd73c, 0 x26d3, 0 x36f2,0 x0691, 0 x16b0, 0 x6657, 0 x7676, 0 x4615, 0 x5634, 0 xd94c, 0 xc96d, 0 xf90e, 0 xe92f, 0 x99c8, 0 x89e9, 0 xb98a, 0 xa9ab,0 x5844, 0 x4865, 0 x7806, 0 x6827, 0 x18c0, 0 x08e1, 0 x3882, 0 x

16、28a3, 0 xcb7d, 0 xdb5c, 0 xeb3f, 0 xfb1e, 0 x8bf9, 0 x9bd8,0 xabbb, 0 xbb9a, 0 x4a75, 0 x5a54, 0 x6a37, 0 x7a16, 0 x0af1, 0 x1ad0, 0 x2ab3, 0 x3a92, 0 xfd2e, 0 xed0f, 0 xdd6c, 0 xcd4d,0 xbdaa, 0 xad8b, 0 x9de8, 0 x8dc9, 0 x7c26, 0 x6c07, 0 x5c64, 0 x4c45, 0 x3ca2, 0 x2c83, 0 x1ce0, 0 x0cc1, 0 xef1f,

17、 0 xff3e,0 xcf5d, 0 xdf7c, 0 xaf9b, 0 xbfba, 0 x8fd9, 0 x9ff8, 0 x6e17, 0 x7e36, 0 x4e55, 0 x5e74, 0 x2e93, 0 x3eb2, 0 x0ed1, 0 x1ef0 ;crc=0; while(len-!=0) da=(uchar) (crc/256); /* 以 8 位二進制數的形式暫存 CRC 的高 8 位 */ crc=8; /* 左移 8 位,相當于 CRC 的低 8 位乘以 */crcA=crc_tadaA*ptr;/* 高 8 位和當前字節(jié)相加后再查表求CRC ,再加上以前的 CR

18、C */ ptr+;return(crc);很顯然,按字節(jié)求 CRC 時,由于采用了查表法 ,大大提高了計算速度。但對于廣泛運用的 8 位微處理器 ,代碼 空間有限，對于要求 256 個 CRC 余式表(共 512 字節(jié)的內存)已經顯得捉襟見肘了，但 CRC 的計算速度又 不可以太慢 ,因此再介紹下面一種按半字節(jié)求 CRC 的算法。5 按半字節(jié)計算 CRC同樣道理，對于一個二進制序列數可以按字節(jié)表示為式(5-1)，其中 為半個字節(jié) (共 4 位)。(5-1)求此二進制序列數的 CRC 碼時,先乘以后(既左移 16 位)，再除以多項式 G(X),所得的余數既是所要求的 CRC 碼。如式 (4-2

19、) 所示：( 5-2 )可以設： (5-3)其中 為整數，為 16 位二進制余數。將式 (5-3) 代入式 (5-2) 得：(5-4 )因為：( 5-5 )其中 是 的高 4 位，是 的低 12 位。將式( 5-5)代入式( 5-4)，經整理后得：( 5-6 )再設： (5-7)其中 為整數，為 16 位二進制余數。將式 (5-7)代入式(5-6)，如上類推，最后得：(5-8)很顯然，十六位二進制數 既是我們要求的 CRC 碼。式(5-7) 是編寫按字節(jié)計算 CRC 程序的關鍵，它說明計算本字節(jié)后的 CRC 碼等于上一字節(jié) CRC 碼的低 12 位左移4 位后，再加上上一字節(jié)余式 CRC 右移

20、 4 位(也既取高 4 位)和本字節(jié)之和后所求得的 CRC 碼，如果我們把 4 位二進制序列數的 CRC 全部計算出來，放在一個表里，采用查表法，每個字節(jié)算兩次 (半字節(jié)算 一次)，可以在速度和內存空間取得均衡。由此不難理解下面按半字節(jié)求CRC 碼的 C 語言程序。 *ptr 指向發(fā)送緩沖區(qū)的首字節(jié)，len 是要發(fā)送的總字節(jié)數，CRC 余式表是按 0 x11021 多項式求出的。unsigned cal_crc(unsigned char *ptr，unsigned char len) unsigned int crc;unsigned char da;unsigned int crc_ta16= /* CRC 余式表 */ 0 x0000，0 x1021，0 x204