1、課程論文題 目 在通信過程中用C語言實現(xiàn)CRC校驗學(xué)生姓名學(xué)號院系專業(yè)xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx2010年12月4日在通信過程中用C語言實現(xiàn)CRC校驗摘要：通信的目的是要把信息及時可靠地傳送給對方,因此要求一個通信系統(tǒng)傳輸消息必 須可靠與快速，在數(shù)字通信系統(tǒng)中可靠與快速往往是一對矛盾。為了解決可靠性，通信系統(tǒng)都 采用了差錯控制。本文簡述CRC算法原理，給出一種查表計算方法，并給出用C語言編寫的 算法源程序。關(guān)鍵詞:通信;循環(huán)冗余校驗;CRC;多項式;查表法概述在數(shù)字通信系統(tǒng)中可靠與快速往往是一對矛盾。若要求快速，則必然使得每個數(shù)據(jù)碼元 所占地時間縮

2、短、波形變窄、能量減少,從而在受到干擾后產(chǎn)生錯誤的可能性增加，傳送信息 的可靠性下降。若是要求可靠,則使得傳送消息的速率變慢。因此，如何合理地解決可靠性與 速度這一對矛盾,是正確設(shè)計一個通信系統(tǒng)的關(guān)鍵問題之一。為保證傳輸過程的正確性，需要 對通信過程進行差錯控制。差錯控制最常用的方法是自動請求重發(fā)方式(ARQ)、向前糾錯 方式(FEC)和混合糾錯(HEC)。在傳輸過程誤碼率比較低時，用FEC方式比較理想。在傳輸 過程誤碼率較高時，采用FEC容易出現(xiàn)“亂糾”現(xiàn)象。HEC方式則是ARQ和FEC的結(jié)合。 在許多數(shù)字通信中，廣泛采用ARQ方式，此時的差錯控制只需要檢錯功能。實現(xiàn)檢錯功能的 差錯控制方法

3、很多,傳統(tǒng)的有:奇偶校驗、校驗和檢測、重復(fù)碼校驗、恒比碼校驗、行列冗余 碼校驗等,這些方法都是增加數(shù)據(jù)的冗余量,將校驗碼和數(shù)據(jù)一起發(fā)送到接受端，接受端對接 受到的數(shù)據(jù)進行相同校驗,再將得到的校驗碼和接受到的校驗碼比較，如果二者一致則認為傳 輸正確。但這些方法都有各自的缺點,誤判的概率比較高。循環(huán)冗余校驗CRC(Cyclic Redundancy Check)是由分組線性碼的分支而來，其主要應(yīng)用 是二元碼組。編碼簡單且誤判概率很低，在通信系統(tǒng)中得到了廣泛的應(yīng)用。CRC的實現(xiàn)分為 硬件和軟件兩種方法，其中軟件實現(xiàn)的關(guān)鍵在于計算速度。如果單純模擬硬件實現(xiàn)方法，則計 算速度較慢。本文中重點介紹7CRC

4、校驗的原理及查表法計算CRC的實現(xiàn)。循環(huán)冗余校驗碼(CRC)CRC校驗采用多項式編碼方法。被處理的數(shù)據(jù)塊可以看作是一個n階的二進制多項式, 由an - 1xn - 1 + an - 2 xx - 2 + + al x + a0。如一個8 位二進制數(shù) 10110101 可以表示為:1 x7 + 0 x6 + 1 x5 + 1 x4 +0 x3 + 1 x2 + 0 x + 1。多項式乘除法運算過程與普通代數(shù)多項式的乘除 法相同。多項式的加減法運算以2為模，加減時不進，借位，和邏輯異或運算一致。采用CRC校驗時，發(fā)送方和接收方用同一個生成多項式g ( x),并且g ( x)的首位和最后 一位的系數(shù)

5、必須為1CRC的處理方法是:發(fā)送方以g ( x)去除t ( x)，得到余數(shù)作為CRC校驗 碼,校驗時，以計算的校正結(jié)果是否為0為據(jù)，判斷數(shù)據(jù)幀是否出錯。CRC校驗可以100 %地檢測出所有奇數(shù)個隨機錯誤和長度小于等于k ( k g ( x)的階 數(shù))的突發(fā)錯誤。所以CRC的生成多項式的階數(shù)越高，那么誤判的概率就越小。CCITT建議: 2048 kbitPs的PCM基群設(shè)備采用CRC - 4方案,使用的CRC校驗碼生成多項式g ( x) = x4 + x + 1,采用16位CRC校驗，可以保證在1014 bit碼元中只含有一位未被檢測出的錯誤 2 。在IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗

6、序列FCS中，使用CRC - 16，其生成多 項式g ( x) = x16 + x15 + x2 + 1 ;而在CCITT推薦的高級數(shù)據(jù)鏈路控制規(guī)程HDLC的幀校驗 序列FCS中，使用CCITT - 16，其生成多項式g ( x) = x16 + x15 + x5 + 1。CRC - 32的生成多項式g ( x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 +x10 + x8 + x7 + x5 + x4 + x2 + x + 1CRC - 32出錯的概率比CRC - 16低10- 5倍4 。由于CRC - 32的可靠性，把CRC - 32 用于重要數(shù)據(jù)

7、傳輸十分合適，所以在通信、計算機等領(lǐng)域運用十分廣泛。在一些UART通信 控制芯片(如MC6582、Intel8273和Z80 - SIO)內(nèi),都采用7CRC校驗碼進行差錯控制;以太 網(wǎng)卡芯片、MPEG解碼芯片中,也采用CRC - 32進行差錯控制。3 CRC校驗碼的算法分析CRC校驗碼的編碼方法是用待發(fā)送的二進制數(shù)據(jù)t ( x)除以生成多項式& ( x)，將最后 的余數(shù)作為CRC校驗碼。其實現(xiàn)步驟如下：設(shè)待發(fā)送的數(shù)據(jù)塊是m位的二進制多項式t ( x)，生成多項式為r階的g ( x)。在數(shù)據(jù) 塊的末尾添加r個0,數(shù)據(jù)塊的長度增加到m + r位，對應(yīng)的二進制多項式為xr t ( x)。用生成多項式

8、g ( x)去除xr t ( x)，求得余數(shù)為階數(shù)為r - 1的二進制多項式y(tǒng) ( x)。此 二進制多項式y(tǒng) ( x)就是t ( x)經(jīng)過生成多項式g ( x)編碼的CRC校驗碼。用xr t ( x)以模2的方式減去y ( x)，得到二進制多項式xr t( x)。xr t( x)就是包 含了。日。校驗碼的待發(fā)送字符串。從CRC的編碼規(guī)則可以看出,CRC編碼實際上是將代發(fā)送的m位二進制多項式t ( x) 轉(zhuǎn)換成了可以被g( x)除盡的m + r位二進制多項式xr t( x)，所以解碼時可以用接受到的 數(shù)據(jù)去除8 ( x)，如果余數(shù)為零,則表示傳輸過程沒有錯誤;如果余數(shù)不為零，則在傳輸過程中肯 定

9、存在錯誤。許多CRC的硬件解碼電路就是按這種方式進行檢錯的。同時xr t ( x)可以看 做是由t ( x)和CRC校驗碼的組合，所以解碼時將接收到的二進制數(shù)據(jù)去掉尾部的r位數(shù)據(jù), 得到的就是原始數(shù)據(jù)。為了更清楚的了解。日。校驗碼的編碼過程，下面用一個簡單的例子來說明CRC校驗碼 的編碼過程。由于CRC - 32、CRC - 16、CCITT和CRC - 4的編碼過程基本一致，只有位數(shù) 和生成多項式不一樣。為了敘述簡單,用一個CRC - 4編碼的例子來說明 CRC的編碼過程。表1除法過程除數(shù)次數(shù)被除數(shù)/育(對/結(jié)果余數(shù)0.1 叩100。111000000loonioooooo.1 00110

10、00010011100000011 (Ml 11000000IGOQOOO1 00110 OflOOlOOOOOO2.1 00000011001 00110 001100設(shè)待發(fā)送的數(shù)據(jù)x)為12位的二進制數(shù)據(jù)100100011100 ;CRC - 4的生成多項式為g(x) = x4 + x + 1 ,階數(shù)r為4，即10011。首先在，(x)的末尾添加4個0構(gòu)成詢t ( x),數(shù)據(jù)塊就 成了 1001000111000000。然后用&( x)去除x4t( x)，不用管商是多少,只需要求得余數(shù) (x)。 表1給出了除法過程。從表1中可以看出,CRC編碼實際上是一個循環(huán)移位的模2運算。對CRC -

11、4,我們假設(shè) 有一個5 bits的寄存器，通過反復(fù)的移位和進行CRC的除法，那么最終該寄存器中的值去掉最 高一位就是我們所要求的余數(shù)。所以可以將上述步驟用下面的流程描述：/reg是一個5 bits的寄存器把reg中的值置0.把原始的數(shù)據(jù)后添加r個0.While (數(shù)據(jù)未處理完)BeginIf (reg首位是1)reg = reg XOR 0011.把reg中的值左移一位,讀入一個新的數(shù)據(jù)并置于register的0 bit的位置。Endreg的后四位就是我們所要求的余數(shù)。這種算法簡單，容易實現(xiàn),對任意長度生成多項 式的G( x)都適用。在發(fā)送的數(shù)據(jù)不長的情況下可以使用,但是如果發(fā)送的數(shù)據(jù)塊很長的

12、話， 這種方法就不太適合了，它一次只能處理一位數(shù)據(jù)，效率太低。為了提高處理效率,可以一次處理4位、8位、16位、32位。由于處理器的結(jié)構(gòu)基本 上都支持8位數(shù)據(jù)的處理，所以一次處理8位比較合適。為了對優(yōu)化后的算法有一種直觀的 了解,先將上面的算法換個角度理解一下。在上面例子中，可以將編碼過程看作如下過程：構(gòu)造一個四位的寄存器reg ,初值為0 ,數(shù)據(jù)依次移入reg0 ( reg的0位)，同時reg3的數(shù)據(jù) 移出reg。由上面的算法可以知道,只有當移出的數(shù)據(jù)為1時,reg才和g ( x)進行XOR運算； 移出的數(shù)據(jù)為0時,reg不與g(x)進行XOR運算，相當于和0000進行XOR運算。就是說，

13、reg和什么樣的數(shù)據(jù)進行XOR由移出的數(shù)據(jù)決定。由于只有一個bit ,所以有21種選擇。上述 算法可以描述如下：/reg是一個4 bits的寄存器初始化 t = (0011 ,0000把reg中的值置0.把原始的數(shù)據(jù)后添加r個0.While (數(shù)據(jù)未處理完)Begin把reg中的值左移一位,讀入一個新的數(shù)據(jù)并置于register的0 bit的位置。reg = reg XOR t 移出的位End上面算法是以bit為單位進行處理的，可以將上述算法擴展到8位，即以Byte為單位進行 處理，即CRC - 32。構(gòu)造一個四個Byte的寄存器reg ,初值為0 x00000000,數(shù)據(jù)依次移Areg0 (

14、reg的0字節(jié)，以下類似)，同時reg3的數(shù)據(jù)移出reg。用上面的算法類推可知,移出的數(shù)據(jù)字 節(jié)決定reg和什么樣的數(shù)據(jù)進行XOR。由于有8個bit ,所以有28種選擇。上述 算法可以描述如下：/reg是一個4 Byte的寄存器初始化t = ( 共有28 = 256項把reg中的值置0.把原始的數(shù)據(jù)后添加rP8個0字節(jié).While (數(shù)據(jù)未處理完)Begin把reg中的值左移一個字節(jié)，讀入一個新的字節(jié)并置于reg的第0個byte的位置。reg = reg XOR t 移出的字節(jié)End算法的依據(jù)和多項式除法性質(zhì)有關(guān)。如果一個m位的多項式x)除以一個，階的生成 多項式g ( x) , t ( x)

15、 = am - 1 xm - 1 + am - 2 xm - 2 + + a2 x2 +a1 x1 + a0 ,將每一位ak xk (0 = k m)提出來，在后面不足r個0后，單獨去除g ( x)，得到的余式位狄(x)。再將” - 1 (x) Y ym - 2 ( x) YY y0 ( x)后得到的就是t (x)由生成多項式g ( x)得到的余式。對于CRC - 32 , 可以將每個字節(jié)在后面補上32個0后與生成多項式進行運算，得到余式和此字節(jié)唯一對應(yīng)， 這個余式就是上面算法中t 中的值，由于一個字節(jié)有8位，所以t 共有28 = 256項。多項式 運算性質(zhì)可以參見參考文獻1 。這種算法每次處

16、理一個字節(jié)，通過查表法進行運算,大大提 高了處理速度，故為大多數(shù)應(yīng)用所采用。4 CRC - 32的程序?qū)崿F(xiàn)為了提高編碼效率，在實際運用中大多采用查表法來完成CRC - 32校驗，下面是產(chǎn)生 CRC - 32校驗碼的子程序。首先將CRC生成多項式及CRC值表定義為一個頭文件CRC. H:define CRC CCITT 0 x1021PPCCITT 多項式define REV CCITT 0 x8408PP反轉(zhuǎn)CCITT 多項式define CRC16 0 x8005PPCRC16 多項式define REV CRC16 0 x001PP反轉(zhuǎn)CRC16 多項式unsigned short crc

17、 tble256 ;PPCRC 值表注:16 位CCITT 多項式(X16 + X12 + X5 + 1)和 16位CRC16 多項式(X16 + X15 + X2 + 1)為兩種最常用的CRC多項式。反轉(zhuǎn)多項式是指在數(shù)據(jù)通訊時，信息字節(jié)先傳送或接收低 位字節(jié)，如重新排位影響CRC計算速度，故設(shè)反轉(zhuǎn)多項式。造表和查表法CRC計算函數(shù)。include “crc. h ”void mk crctble (unsigned short genpoly)unsigned short crc tble256 ;unsigned shortccnum = 0 ;unsigned short i ,j ,k

18、 ;for (i = 0 ,k = 0 ;i 256 ;i + + ,k + + )i 0 ;j -)if ( (iAccnum) &0 x8000)ccnum = (ccnum = 1)Agenpoly ;elseccnum = 1 ;i = 1 ;crc tble k =ccnum;void crc updte (unsigned short dt ,unsigned short ccnum)ccnum = (ccnum 8)Adt ;注:genpoly為CRC多項式,ccnum為累加器值(即為新的CRC值),d t為參與CRC計算的 信息。5 結(jié)束語CRC校驗由于實現(xiàn)簡單，檢錯能力強，被廣泛使用在各種數(shù)據(jù)校驗應(yīng)用中。占用系統(tǒng)資源 少，用軟硬件均能實現(xiàn)，是進行數(shù)據(jù)傳輸差錯檢測的一種很