1、CRCC語實現(xiàn)CRC校驗的快速算法的C語實現(xiàn)摘要：CRC循環(huán)冗余校驗算法，是種在數(shù)據(jù)存儲和數(shù)據(jù)通訊領(lǐng)域中使分泛的編碼算法，具有強的檢錯和糾錯能，并且開銷較。本從CRC基本原理出發(fā)，介紹了CRC快速算法的原理，以C語為實現(xiàn)段，實現(xiàn)了該算法。1.引在數(shù)據(jù)存儲和數(shù)據(jù)通訊領(lǐng)域，為了保證數(shù)據(jù)的正確，就不得不采檢錯或者糾錯的編碼段。在諸編碼式中，CRC是其中著名的種，其特點是，檢錯能極強，開銷，易于編碼器及檢測電路實現(xiàn)；從其檢錯能來看，它所不能發(fā)現(xiàn)的錯誤的率僅為0.0047%以下。從性能上和開銷上考慮，均遠遠優(yōu)于奇偶校驗及算術(shù)和校驗等式。因，在數(shù)據(jù)存儲和數(shù)據(jù)通訊領(lǐng)域，CRC都被泛運，例如，通訊協(xié)議X.25

2、的FCS(幀檢錯序列)采的是CRC-CCITT，ARJ、LHA等壓縮具軟件采的是CRC32，磁盤驅(qū)動器的讀寫采了CRC16，通的圖像存儲格式GIF、TIFF等也都使CRC作為檢錯段。2.CRC原理CRC校驗是種線性編碼理論，對于要傳輸n位進制碼序列，在發(fā)送端，根據(jù)已定的成多項式，按照定的規(guī)則，產(chǎn)段k位的校驗碼（即CRC碼），附在要發(fā)送的信息后，構(gòu)成個新的長為（n+k）位的進制碼序列，再發(fā)送給接收端。在接收端，則根據(jù)接收的數(shù)據(jù)部分和CRC之間是否預(yù)定的關(guān)系，從判定在傳輸過程中是否出現(xiàn)傳輸錯誤。CRC的計算是種模2的除法，與普通的除法主要的差別是在計算過程中減法，使的不借位/進位的模2加運算，等同

3、于按位異或。進制序列數(shù)據(jù)流，可以模2多項式表，多項式的系數(shù)就是序列的值。如101011可以表為:。假設(shè)要傳輸?shù)膎位長度的進制序列，表為： ，使的CRC成多項式，記為：如果將進制序列和成多項式，進下的計算：（2-1）（2-3）根據(jù)，根據(jù)相同的序列按位異或的結(jié)果為0，因此，式2-3的就可以化為：（2-4）從中就可以看出，接收端計算的結(jié)果是整除的，沒有余數(shù)，這也就是CRC在接收端判斷數(shù)據(jù)是否正確的標準。因此整個CRC計算過程就是將要發(fā)送的信息左移k位，然后將與成多項式進模2除法，等到的k位長的余數(shù)就是CRC校驗信息。CRC的標準時多種多樣的，般是依據(jù)成多項式的長度分為CRC-8，CRC16等，以下就

4、是種典型的成多項式：3.CRC-16快速算法原理在程運中，基于上介紹的按照模2除法，計算CRC校驗算法的作量是很的，特別是對于越長的序列，因為沒1為數(shù)據(jù)就要進個計算。例如個以太數(shù)據(jù)包的包長最為1518byte，計算這樣的個數(shù)據(jù)包需要的時間和計算量的花費很多，找到種快速的CRC計算法（也成并CRC算法），對于程應(yīng)是分有必要的。可以采增加每次CRC的輸?shù)臄?shù)據(jù)長度來簡化運算需要的時間和運算量，般使1byte輸數(shù)據(jù)代替1bit的輸。以CRC-8為例，如果要計算個16bit的數(shù)據(jù)的CRC-8。16bit數(shù)據(jù),記為： ，其中 就是第1byte的數(shù)據(jù)， 是第2byte的數(shù)據(jù)。那么按照前介紹的CRC原理，計算

5、過程：（3-1）假定,（3-2）那么,（3-3）由式3-3可以看到，最后的CRC編碼結(jié)果，是由數(shù)據(jù)的第1byte數(shù)據(jù)單獨的CRC編碼的結(jié)果，與第2byte的按位異或得到的結(jié)果，再次進CRC編碼的結(jié)果。以此類推，任何長度的數(shù)據(jù)，從第1byte數(shù)據(jù)起，前1byte的數(shù)據(jù)的CRC-8校驗的結(jié)果與后1byte的數(shù)據(jù)按位異或后得到的數(shù)據(jù)，再次進CRC-8校驗，直整個數(shù)據(jù)結(jié)束。在此過程中，每次CRC-8校驗的結(jié)果都是以被除數(shù)是對應(yīng)的，如果將這些結(jié)果預(yù)先存儲下來，然后通過查表的式進計算，就減少了計算的時間和作量。對于CRC-8來說，將上次計算的結(jié)果，作為查表的依據(jù)，將查表得結(jié)果與輸?shù)?byte數(shù)據(jù)進按位異或

6、減少了計算的時間和作量。對于CRC-8來說，將上次計算的結(jié)果，作為查表的依據(jù)，將查表得結(jié)果與輸?shù)?byte數(shù)據(jù)進按位異或的結(jié)果，就是本次計算的結(jié)果，以此進數(shù)據(jù)結(jié)束。對于CRC-16,CRC-32等也可以按照上類似的法，進改進來完成。對于CRC-16來說，每次計算的過程是，拿上次的結(jié)果的字節(jié)為查表的依據(jù)，查余項表得到的結(jié)果的字節(jié)與上次結(jié)果的低字節(jié)的按位異或的結(jié)果就是本次計算結(jié)果的字節(jié)，查余項表得到的結(jié)果的低字節(jié)與輸字節(jié)的按位異或的結(jié)果就是本次計算結(jié)果的低字節(jié)。在整個過程中，需要計算的數(shù)據(jù)，除信息數(shù)據(jù)外，還有兩byte的全0數(shù)據(jù)。在實際計算的過程中，為了省去最后16位填充0的計算，那么可以將輸?shù)臄?shù)

7、據(jù)左移16位后再進查表就能達到這個的。那么查表過程就變?yōu)椋瑢⑸洗蔚慕Y(jié)果和字節(jié)與輸?shù)慕Y(jié)果進按位異或作為查表的依據(jù)，查表結(jié)果的字節(jié)與上次結(jié)果的低字節(jié)進按位異或得到本次計算結(jié)果的字節(jié)，查表結(jié)果的低字節(jié)就是本次計算結(jié)果的低字節(jié)。4.CRC余項表CRC余項表是快速算法的核，CRC余項表的每個表項的數(shù)據(jù)，是該數(shù)據(jù)的標號，進對應(yīng)的CRC校驗，所得到的結(jié)果。下就是個CRC-16的余項表：unsigned short CRC_table256 =0 x0000, 0 x1189, 0 x2312, 0 x329b, 0 x4624,0 x57ad, 0 x6536, 0 x74bf,0 x8c48, 0 x9d

8、c1, 0 xaf5a, 0 xbed3, 0 xca6c, 0 xdbe5, 0 xe97e, 0 xf8f7,0 x1081, 0 x0108, 0 x3393, 0 x221a, 0 x56a5, 0 x472c, 0 x75b7, 0 x643e,0 x9cc9, 0 x8d40, 0 xbfdb, 0 xae52, 0 xdaed, 0 xcb64, 0 xf9ff, 0 xe876,0 x2102, 0 x308b, 0 x0210, 0 x1399, 0 x6726, 0 x76af, 0 x4434,0 x55bd,0 xad4a, 0 xbcc3, 0 x8e58, 0 x9

9、fd1, 0 xeb6e, 0 xfae7, 0 xc87c, 0 xd9f5,0 x3183, 0 x200a, 0 x1291, 0 x0318, 0 x77a7, 0 x662e, 0 x54b5, 0 x453c,0 xbdcb, 0 xac42, 0 x9ed9, 0 x8f50, 0 xfbef, 0 xea66, 0 xd8fd, 0 xc974,0 x4204,0 x538d, 0 x6116, 0 x709f, 0 x0420,0 x15a9, 0 x2732, 0 x36bb,0 xce4c, 0 xdfc5, 0 xed5e, 0 xfcd7, 0 x8868, 0 x9

10、9e1, 0 xab7a, 0 xbaf3,0 x5285, 0 x430c, 0 x7197, 0 x601e, 0 x14a1, 0 x0528, 0 x37b3, 0 x263a,0 xdecd, 0 xcf44, 0 xfddf, 0 xec56, 0 x98e9, 0 x8960, 0 xbbfb, 0 xaa72,0 x6306, 0 x728f, 0 x4014,0 x519d, 0 x2522, 0 x34ab, 0 x0630, 0 x17b9,0 xef4e, 0 xfec7, 0 xcc5c, 0 xddd5, 0 xa96a, 0 xb8e3, 0 x8a78, 0 x

11、9bf1,0 x7387, 0 x620e, 0 x5095, 0 x411c, 0 x35a3, 0 x242a, 0 x16b1, 0 x0738,0 xffcf, 0 xee46, 0 xdcdd, 0 xcd54, 0 xb9eb, 0 xa862, 0 x9af9, 0 x8b70,0 x8408,0 x9581, 0 xa71a, 0 xb693, 0 xc22c, 0 xd3a5, 0 xe13e, 0 xf0b7,0 x0840,0 x19c9, 0 x2b52, 0 x3adb, 0 x4e64, 0 x5fed, 0 x6d76, 0 x7cff,0 x9489,0 x85

12、00, 0 xb79b, 0 xa612, 0 xd2ad, 0 xc324, 0 xf1bf, 0 xe036,0 x18c1, 0 x0948,0 x3bd3, 0 x2a5a, 0 x5ee5, 0 x4f6c, 0 x7df7, 0 x6c7e,0 xa50a, 0 xb483, 0 x8618, 0 x9791, 0 xe32e, 0 xf2a7, 0 xc03c, 0 xd1b5,0 x2942,0 x38cb, 0 x0a50, 0 x1bd9, 0 x6f66, 0 x7eef, 0 x4c74, 0 x5dfd,0 xb58b, 0 xa402, 0 x9699, 0 x87

13、10, 0 xf3af, 0 xe226, 0 xd0bd, 0 xc134,0 x39c3, 0 x284a, 0 x1ad1, 0 x0b58, 0 x7fe7, 0 x6e6e, 0 x5cf5, 0 x4d7c,0 xc60c, 0 xd785, 0 xe51e, 0 xf497, 0 x8028, 0 x91a1, 0 xa33a, 0 xb2b3,0 x4a44, 0 x5bcd, 0 x6956, 0 x78df, 0 x0c60, 0 x1de9, 0 x2f72, 0 x3efb,0 xd68d, 0 xc704, 0 xf59f, 0 xe416, 0 x90a9, 0 x

14、8120, 0 xb3bb, 0 xa232,0 x5ac5, 0 x4b4c, 0 x79d7, 0 x685e, 0 x1ce1, 0 x0d68, 0 x3ff3, 0 x2e7a,0 xe70e, 0 xf687, 0 xc41c, 0 xd595, 0 xa12a, 0 xb0a3, 0 x8238, 0 x93b1,0 x6b46, 0 x7acf, 0 x4854,0 x59dd, 0 x2d62, 0 x3ceb, 0 x0e70, 0 x1ff9,0 xf78f, 0 xe606, 0 xd49d, 0 xc514, 0 xb1ab, 0 xa022, 0 x92b9, 0 x8330,0 x7bc7, 0 x6a4e, 0 x58d5, 0 x495c, 0 x3de3, 0 x2c6a, 0 x1ef1, 0 x0f78,;5.CRC快速算法使C語實現(xiàn)CRC-16快速算法。