CRC16算法分析(資料)

CRC16算法分析概述數(shù)據(jù)校驗：通俗的說，就是為保證數(shù)據(jù)的完整性，用一種指定的算法對原始數(shù)據(jù)計算出的一個校驗值。接收方用同樣的算法計算一次校驗值，如果和隨數(shù)據(jù)提供的校驗值一樣，就說明數(shù)據(jù)是完整的。關(guān)于比較流行的數(shù)據(jù)校驗算法有很多，如奇偶校驗、BCC異或校驗法、CRC循環(huán)冗余校驗、MD5校驗等，各個算法的適用范圍不同，前兩種適用于要求不太高的數(shù)據(jù)通信，CRC則可用于硬盤數(shù)據(jù)和網(wǎng)絡(luò)傳輸，而MD5則適用于數(shù)據(jù)比較大或要求比較高的場合。奇偶校驗（ParityCheck）：在數(shù)據(jù)存儲和傳輸中，字節(jié)中額外增加一個比特位，用來檢驗錯誤，其中校驗位可以通過數(shù)據(jù)位異或計算出來。普通的RS232串口通訊就可另加一位用于放奇偶校驗值。BCC異或校驗法（BlockCheckCharacter）：把所有數(shù)據(jù)都和一個指定的初始值（通常是0）異或一次，最后的結(jié)果就是校驗值，通常把它附在通訊數(shù)據(jù)的最后一起發(fā)送出去。接收方收到數(shù)據(jù)后自己也計算一次異或和校驗值，如果和收到的校驗值一致就說明收到的數(shù)據(jù)是完整的。此法適用于大多數(shù)要求不高的數(shù)據(jù)通訊，在IC卡接口通訊、很多單片機(jī)系統(tǒng)的串口通訊都使用。CRC循環(huán)冗余校驗（CyclicRedundancyCheck）：利用除法及余數(shù)的原理來進(jìn)行錯誤檢測的，將接收到的碼組進(jìn)行除法運(yùn)算，如果除盡，則說明傳輸無誤；如果未除盡，則表明傳輸出現(xiàn)差錯。CRC校驗具還有自動糾錯能力。CRC-12碼通常用來傳送6-bit字符串；CRC-16及CRC-CCITT碼則用是來傳送8-bit字符；CRC-32碼用于硬盤數(shù)據(jù)，網(wǎng)絡(luò)傳輸?shù)?。CRC校驗在WinRAR、以太網(wǎng)卡芯片、MPEG解碼芯片中MD5校驗（MessageDigestAlgorithm5）：對輸入消息按512-bit分組，要填充成為512位的整數(shù)倍，且最后一組的后64位用來填充消息長度，然后算法產(chǎn)生128位散列值就是校驗碼。MD5用于數(shù)據(jù)比較大或要求比較高的場合，如大量數(shù)據(jù)傳輸或文件的校驗等，廣泛應(yīng)用于文件校驗、銀行系統(tǒng)的交易數(shù)據(jù)。CRC原理基本概念（1）多項式與二進(jìn)制數(shù)多項式和二進(jìn)制數(shù)有直接對應(yīng)關(guān)系：x的最高冪次對應(yīng)二進(jìn)制數(shù)的最高位，以下各位對應(yīng)多項式的各冪次，有此冪次項對應(yīng)1，無此冪次項對應(yīng)0。顯然若x的最高冪次為R，轉(zhuǎn)換成對應(yīng)的二進(jìn)制數(shù)有R+1位。若多項式：G(x)=x16+x12+x5+1，則對應(yīng)二進(jìn)制數(shù)為：1,0001,0000,0010,0001。（2）生成多項式是接受方和發(fā)送方的一個約定，也就是一個二進(jìn)制數(shù)，在整個傳輸過程中，這個數(shù)始終保持不變。在發(fā)送方,利用生成多項式對信息多項式做模2除生成校驗碼，而在接受方利用生成多項式對收到的編碼多項式做模2除檢測和確定錯誤位置。生成多項式的選取應(yīng)滿足以下條件：a、生成多項式的最高位和最低位必須為1。b、當(dāng)被傳送信息（CRC碼）任何一位發(fā)生錯誤時，被生成多項式做模2除后應(yīng)該使余數(shù)不為0。c、不同位發(fā)生錯誤時，應(yīng)該使余數(shù)不同。d、對余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán)。將這些要求反映為數(shù)學(xué)關(guān)系是比較復(fù)雜的，國際標(biāo)準(zhǔn)中常用的生成多項式有： CRC-12：G(x)=x12+x11+x3+x2+x+1CRC-16：G(x)=x16+x15+x2+1CRC-CCITT：G(x)=x16+x12+x5+1 CRC-32：G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x+1（3）模2除（按位異或）模2除做法與算術(shù)除法類似，但每一位除（減）的結(jié)果不影響其它位，即不向上一位借位，實際上就是異或，然后再移位做下一位的模2減。步驟如下：a、用除數(shù)對被除數(shù)最高幾位做模2減，沒有借位。b、除數(shù)右移一位，若余數(shù)最高位為1，商為1，并對余數(shù)做模2減。若余數(shù)最高位為0，商為0，除數(shù)繼續(xù)右移一位。c、一直做到余數(shù)的位數(shù)小于除數(shù)時，該余數(shù)就是最終余數(shù)。校驗原理循環(huán)冗余校驗碼（CRC）的基本原理是：發(fā)送端在K位信息碼后再拼接R位的校驗碼，整個編碼長度為N位，故又稱（N，K）碼，如圖1所示。對于一個給定的（N，K）碼，可以證明存在一個最高次冪為N-K=R的多項式G(x)，根據(jù)G(x)可以生成K位信息的校驗碼，而G(x)叫做這個CRC碼的生成多項式。接收端將接收到的N位報文與G(x)進(jìn)行運(yùn)算，如果余數(shù)為0，則表示數(shù)據(jù)有效，再將報文右移R位得到原始報文，如果余數(shù)不為0，則數(shù)據(jù)無效，再做相應(yīng)的處理。圖1（N，K）碼計算CRC校驗碼采用模2加減運(yùn)算法則，既是不帶進(jìn)位和借位的按位加減，這種加減運(yùn)算實際上就是邏輯上的異或運(yùn)算。校驗碼的具體生成過程為：假設(shè)發(fā)送信息用信息多項式C(X)表示，將C(x)左移R位，則可表示成C(x)*2R，這樣C(x)的右邊就會空出R位，這就是校驗碼的位置，通過C(x)*2R模2除以生成多項式G(x)得到的余數(shù)就是校驗碼。CRC碼的生成步驟：a、將x的最高冪次為R的生成多項式G(x)轉(zhuǎn)換成對應(yīng)的R+1位二進(jìn)制數(shù)。b、將信息碼左移R位，相當(dāng)于對應(yīng)的信息多項式C(x)*2R。c、用生成多項式（二進(jìn)制數(shù)）對信息碼做模2除，得到R位的余數(shù)。d、將余數(shù)拼到信息碼左移后空出的位置，得到編碼后的報文。例：假設(shè)使用的生成多項式是G(x)=x16+x12+x5+1，單字節(jié)的原始報文為0x12，求編碼后的報文。解：a、將生成多項式G(x)轉(zhuǎn)換成對應(yīng)的二進(jìn)制數(shù)：1,0001,0000,0010,0001，即0x11021。b、把原始報文左移R=16位變成：0001,0010,0000,0000,0000,0000。c、用生成多項式對應(yīng)的二進(jìn)制數(shù)對移位后的原始報文進(jìn)行模2除：d、編碼后的報文：即編碼后發(fā)送的報文為0x123273，經(jīng)驗證報文0x123273與0x11021異或后余數(shù)為0。誤碼率分析一般情況下，R位生成多項式產(chǎn)生的CRC碼可檢測出所有的雙錯、奇數(shù)位錯和突發(fā)長度小于等于R的突發(fā)錯以及（1-2-(R-1)）的突發(fā)長度為R+1的突發(fā)錯和（1-2-R）的突發(fā)長度大于R+1的突發(fā)錯。例如，對上述R=16的情況，就能檢測出100％的突發(fā)長度小于等于16的突發(fā)錯以及99．997%的突發(fā)長度為17的突發(fā)錯和99．998%的突發(fā)長度大于17的突發(fā)錯。這里，突發(fā)錯誤是指幾乎是連續(xù)發(fā)生的一串錯，突發(fā)長度就是指從出錯的第一位到出錯的最后一位的長度（中間并不一定每一位都錯）。（“16位循環(huán)冗余校驗碼CRC的原理和性能分析”）CRC校驗碼計算不同的應(yīng)用系統(tǒng)，擁有的硬件資源不一樣，要求的數(shù)據(jù)傳輸速度也不一樣。因此可將應(yīng)用系統(tǒng)分為3類：一是程序存儲空間有限，但對CRC計算速度要求不高的微控制系統(tǒng)；二是程序存儲空間較大且對CRC計算速度要求較高的計算機(jī)或微控制系統(tǒng)；三是程序存儲空間不太大，且對CRC計算速度又有一定要求的微控制系統(tǒng)。根據(jù)不同的應(yīng)用系統(tǒng)采取相應(yīng)的CRC算法，CRC校驗碼的生成有按位計算、按字節(jié)計算和按半字節(jié)計算等方法，具體原理如下所述。（“用查表法實現(xiàn)微處理器的快速CRC計算”）按位計算CRC校驗碼對于一個二進(jìn)制序列數(shù)可以表示為式(1-1):

(1-1)求此二進(jìn)制序列數(shù)的CRC碼時，先乘以216后（既左移16位），再除以多項式G(X)，所得的余數(shù)既是所要求的CRC碼。如式(1-2)所示：

(1-2)可以設(shè)：

(1-3)其中為整數(shù)，為16位二進(jìn)制余數(shù)。將式(1-3)代入式(1-2)得：

(1-4)再設(shè)：

(1-5)其中為整數(shù)，為16位二進(jìn)制余數(shù)，將式(1-5)代入式(1-4)，如上類推，最后得到：

(1-6)根據(jù)CRC的定義，很顯然，十六位二進(jìn)制數(shù)即是我們要求的CRC碼。式(1-5)是編程計算CRC的關(guān)鍵，它說明計算本位后的CRC碼等于上一位CRC碼乘以2后除以多項式，所得的余數(shù)再加上本位值除以多項式所得的余數(shù)。按位計算CRC雖然代碼簡單，所占用的內(nèi)存比較少，但其最大的缺點(diǎn)就是一位一位地計算會占用很多的處理器處理時間，在高速通訊的場合還是得慎重考慮。按字節(jié)計算CRC校驗碼（“循環(huán)冗余校驗碼的查表生成算法及其實現(xiàn)”）不難理解，對于一個二進(jìn)制序列數(shù)可以按字節(jié)表示為式(2-1)，其中為一個字節(jié)(共8位)。

(2-1)求此二進(jìn)制序列數(shù)的CRC碼時，先乘以216后（既左移16位），再除以多項式G(X)，所得的余數(shù)既是所要求的CRC碼。如式(2-2)所示：

(2-2)可以設(shè)：

(2-3)其中為整數(shù)，為16位二進(jìn)制余數(shù)。將式(2-3)代入式(2-2)得： (2-4)因為：

(2-5)其中是的高八位，是的低八位。將式(2-5)代入式(2-4)，經(jīng)整理后得：(2-6)再設(shè)：

(2-7)其中為整數(shù)，為16位二進(jìn)制余數(shù)。將式(2-7)代入式(2-6)，如上類推，最后得：

(2-8)很顯然，十六位二進(jìn)制數(shù)即是我們要求的CRC碼。式(2-7)是編寫按字節(jié)計算CRC程序的關(guān)鍵，它說明計算本字節(jié)后的CRC碼等于上一字節(jié)余式CRC碼的低8位左移8位后，再加上上一字節(jié)CRC右移8位（也既取高8位）和本字節(jié)之和后所求得的CRC碼，如果將8位二進(jìn)制序列數(shù)的CRC全部計算出來，放在一個表里，采用查表法，可以大大提高計算速度。但對于廣泛運(yùn)用的8位微處理器，代碼空間有限，對于要求256個CRC-16余式表（共512字節(jié)的內(nèi)存）已占用相當(dāng)大的內(nèi)存空間，但CRC的計算速度又不可以太慢，因此考慮下面一種按半字節(jié)求CRC的算法。按半字節(jié)計算CRC校驗碼同樣道理，對于一個二進(jìn)制序列數(shù)可以按字節(jié)表示為式(3-1)，其中為半個字節(jié)(共4位)。

(3-1)求此二進(jìn)制序列數(shù)的CRC碼時，先乘以216后（既左移16位），再除以多項式G(X)，所得的余數(shù)既是所要求的CRC碼。如式(3-2)所示： (3-2)可以設(shè)：

(3-3)其中為整數(shù)，為16位二進(jìn)制余數(shù)。將式(3-3)代入式(3-2)得： (3-4)因為：

(3-5)其中是的高4位，是的低12位。將式(3-5)代入式(3-4)，經(jīng)整理后得：

(3-6)再設(shè)：

(3-7)其中為整數(shù)，為16位二進(jìn)制余數(shù)。將式(3-7)代入式(3-6)，如上類推，最后得：

(3-8)很顯然，十六位二進(jìn)制數(shù)即是我們要求的CRC碼。式(3-7)是編寫按字節(jié)計算CRC程序的關(guān)鍵，它說明計算本字節(jié)后的CRC碼等于上一字節(jié)CRC碼的低12位左移4位后，再加上上一字節(jié)余式CRC右移4位（也既取高4位）和本字節(jié)之和后所求得的CRC碼，如果把4位二進(jìn)制序列數(shù)的CRC全部計算出來，放在一個表里，采用查表法，每個字節(jié)算兩次（半字節(jié)算一次），可以在速度和內(nèi)存空間取得均衡。運(yùn)算代碼及運(yùn)算速度分析前提條件8位單片機(jī)編譯環(huán)境KeiluVision2，在主程序中給發(fā)送緩沖區(qū)賦初值，然后調(diào)用CRC校驗碼生成子程序即可。程序代碼buffer[]指向發(fā)送緩沖區(qū)的字節(jié)，len為發(fā)送的字節(jié)總數(shù)，0x1021為生成多項式對應(yīng)的二進(jìn)制數(shù)（最高位肯定為1，故略去），crc_table[16]是32個字節(jié)的CRC余式表。按位計算CRC碼的C語言程序代碼：unsignedintcal_crc16(unsignedcharbuffer[],unsignedcharlen){unsignedchari,j=0;unsignedintcrc_register=0;while(len--!=0)//總字節(jié)數(shù){for(i=0x80;i!=0;i=i>>1)//一個字節(jié)8位，故循環(huán)8次{if((crc_register&0x8000)!=0)//高位為1則進(jìn)行位或運(yùn)算{crc_register<<=1;//高位肯定為1，無需運(yùn)算crc_register^=0x1021;//與生成多項式異或}elsecrc_register<<=1; //高位不為1，則乘2if((buffer[j]&i)!=0)crc_register^=0x1021;//加上本位的CRC碼}j++; //指向下一字節(jié)}return(crc_register); //返回CRC-16校驗碼}按半字節(jié)計算CRC碼的C語言程序代碼：unsignedintcrc_table[16]={0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef};unsignedintcal_crc16(unsignedcharbuffer[],unsignedcharlen){unsignedcharcrc_upper,i=0;unsignedintcrc_register=0;while(len--!=0){crc_upper=((unsignedchar)(crc_register/256))/16; //暫存高4位crc_register<<=4;//CRC右移4位，取CRC的低12位crc_register^=crc_table[crc_upper^(buffer[i]/16)]; //CRC的高4位和本字節(jié)的前半字節(jié)相加后查表得CRC，再加上上一次CRC的余數(shù)crc_upper=((unsignedchar)(crc_register/256))/16;//暫存高4位crc_register<<=4; crc_register^=crc_table[crc_upper^(buffer[i]&0x0F //CRC的高4位和本字節(jié)的后半字節(jié)相加后查表得CRC，再加上上一次CRC的余數(shù)i++; //指向下一字節(jié)}return(crc_register); //返回校驗碼}比較分析在KeiluVision2的調(diào)試模式下將C語言程序轉(zhuǎn)換成匯編語言，通過調(diào)試命令，逐步地觀測程序的執(zhí)行步驟，算出每條執(zhí)行過的匯編語句的指令周期，進(jìn)而總結(jié)出計算CRC校驗碼所需要的時間。（“適用于單片機(jī)的循環(huán)冗余校驗碼的快速算法”）對按位和按字節(jié)計算CRC校驗碼的子程序unsignedintcal_crc16(unsignedcharbuffer[],unsignedcharlen)進(jìn)行分析，總結(jié)如表1所示。表1按位和按半字節(jié)計算CRC校驗碼的比較按位計算按半字節(jié)計算備注占用內(nèi)存情況幾乎不占32字節(jié)半字節(jié)共16個CRC-16余氏碼，故32個字節(jié)發(fā)送單個字節(jié)平均指令執(zhí)行條數(shù)5＋32×8＋8＝26984按位計算一個字節(jié)要循環(huán)8次平均指令執(zhí)行周期數(shù)7＋47×8＋12＝395（指令周期）98（指令周期）不包括初始化的12個指令周期和CRC校驗碼返回的6個指令周期發(fā)送13個字節(jié)平均指令執(zhí)行周期數(shù)395×13＝5135（指令周期）98×13＝1274（指令周期）循環(huán)13次的總指令周期數(shù)對于半字節(jié)計算CRC校驗碼，在12MHz系統(tǒng)晶振下，完成13個字節(jié)數(shù)據(jù)校驗的時間為108us，而對于8位單片機(jī)在以38400bps進(jìn)行串口通信時，傳送13個字節(jié)數(shù)據(jù)的時間約為3ms，因此可以邊傳送邊校驗，利用串行發(fā)送的時間完成校驗的工作，可以提高單片機(jī)通信系統(tǒng)的工作效率。（“基于MCS_51單片機(jī)的CRC_16的實現(xiàn)方法”）考慮到計算CRC校驗碼的處理速度和內(nèi)存空間：按位計算，速度較慢，但占用最小的內(nèi)存空間；按字節(jié)查表計算，速度較快，但占用較大的內(nèi)存，一個字節(jié)占256個內(nèi)存空間，對CRC-16來說就是512個字節(jié)；按半字節(jié)查表計算，是前兩者的均衡，即不會占用太多的內(nèi)存，對CRC-16來說就是32個字節(jié)，同時速度又不至于太慢，比較適合8位小內(nèi)存的單片機(jī)的應(yīng)用場合。附錄：匯編語言指令周期分析記錄按位計算CRC校驗碼（發(fā)送單字節(jié)0xFF）crc_bit_len_FF:C:0x0003 MOV 0x0D,R3 //2C:0x0005 MOV 0x0E,R2 //2C:0x0007 MOV 0x0F,R1 //2C:0x0009 MOV 0x10,R5 //2C:0x000B CLR A //1C:0x000C MOV R5,A //1C:0x000D MOV 0x11,A //1C:0x000F MOV 0x12,A //1C:0x0011 MOV R7,0x10 //2C:0x0013 DEC 0x10 //1C:0x0015 MOV A,R7 //1C:0x0016 JZ C:0060 //2C:0x0018 MOV R4,#P0 //1.....8......C:0x001A MOV A,R4 //1C:0x001B JZ C:005D //2C:0x001D MOV A,0x11 //1C:0x001F JNB 0xE0.7,C:0035 //2C:0x0035 MOV A,0x12 //1C:0x0037 ADD A,ACC //1C:0x0039 MOV 0x12,A //1C:0x003B MOV A,0x11 //1C:0x003D RLC A //1C:0x003E MOV 0x11,A //1C:0x0040 MOV R3,0x0D //2C:0x0042 MOV R2,0x0E //2C:0x0044 MOV R1,0x0F //2C:0x0046 MOV DPL,R5 //2C:0x0048 MOV DPH,#0x00 //2C:0x004B LCALLC?CLDOPTR(C:0x0065)//2C:0x0065 CJNER3,#0x01,C:0x0074 //2C:0x0074 JNC C:0x007C //2C:0x0076 MOV A,R1 //1C:0x0077 ADD A,DPL //1C:0x0079 MOV R0,A //1C:0x007A MOV A,@R0 //1C:0x007B RET //2C:0x004E ANL A,R4 //1C:0x004F JZ C:0x0057 //2C:0x0051 XRL 0x12,#0x21 //2C:0x0054 XRL 0x11,#0x10 //2C:0x0057 MOV A,R4 //1C:0x0058 CLR C //1C:0x0059 RRC A //1C:0x005A MOV R4,A //1C:0x005B SJMP C:0x001A //2.....8......C:0x001A MOV A,R4 //1C:0x001B JZ C:005D //2C:0x005D INC 0x10 //1C:0x005E SJMP C:0x0015 //2C:0x0011 MOV R7,0x10 //2C:0x0013 DEC 0x10 //1C:0x0015 MOV A,R7 //1C:0x0016 JZ C:0060 //2C:0x0060 MOV R6,0x11 //2C:0x0062 MOV R7,0x12 //2C:0x0064 RET //2指令周期數(shù)：12＋（7＋47×8＋12）＋6＝413按半字節(jié)計算CRC校驗碼（發(fā)送單字節(jié)0xFF）crc_half_byte_len_FF:C:0x008F MOV 0x2E,R3 //2C:0x0091 MOV 0x2F,R2 //2C:0x0093 MOV 0x30,R1 //2C:0x0095 MOV 0x31,R5 //2C:0x0097 CLR A //1C:0x0098 MOV R5,A //1C:0x0099 MOV 0x32,A //1C:0x009B MOV 0x33,A //1…C:0x009D MOV R7,0x31 //2C:0x009F DEC 0x31 //1C:0x00A1 MOV A,R7 //1C:0x00A2 JZ C:010C //2C:0x00A4 MOV A,0x32 //1C:0x00A6 MOV R7,A //1C:0x00A7 SWAP A //1C:0x00A8 ANL A,#0x0F //1C:0x00AA MOV R4,A //1C:0x00AB MOV A,0x33 //1C:0x00AD SWAP A //1C:0x00AE MOV R0,A //1C:0x00AF ANL A,#0x0F //1C:0x00B1 XCH A,R0 //1C:0x00B2 XRL A,R0 //1C:0x00B3 MOV 0x33,A //1C:0x00B5 MOV A,0x32 //1C:0x00B7 SWAP A //1C:0x00B8 ANL A,#B //1C:0x00BA ORL A,R0 //1C:0x00BB MOV 0x32,A //1C:0x00BD MOV R3,0x2E //2C:0x00BF MOV R2,0x2F //2C:0x00C1 MOV R1,0x30 //2C:0x00C3 MOV DPL,R5 //2C:0x00C5 MOV DPH,#0x00 //2C:0x00C8 LCALLC?CLDOPTR(C:0111)//2C:0x0111 CJNER3,#0x01,C:0120 //2C:0x0120 JNC C:0128 //2C:0x0122 MOV A,R1 //1C:0x0123 ADD A,DPL //1C:0x0125 MOV R0,A //1C:0x0126 MOV A,@R0 //1C:0x0127 RET //2C:0x00CB MOV R3,A //1C:0x00CC SWAP A //1C:0x00CD ANL A,#0x0F //1C:0x00CF XRL A,R4 //1C:0x00D0 ADD A,ACC //1C:0x00D2 ADD A,#crc_table(0x08) //1C:0x00D4 MOV R0,A //1C:0x00D5 MOV A,@R0 //1C:0x00D6 MOV R6,A //1C:0x00D7 INC R0 //1C:0x00D8 MOV A,@R0 //1C