1、精選優(yōu)質(zhì)文檔-傾情為你奉上 CRC檢驗原理及程序?qū)崿F(xiàn)引言： 循環(huán)冗余檢驗CRC(Cyclic Redundancy Check)的檢錯技術(shù)應(yīng)用較為廣泛，由于實際的通信線路并非是理想的，它不可能將誤碼率（在一段時間內(nèi)，傳輸錯誤的比特占所傳輸比特總數(shù)的比率稱為誤碼率BER）下降到零。因此，為了保證數(shù)據(jù)傳輸?shù)目煽啃?，在計算機(jī)網(wǎng)絡(luò)傳輸數(shù)據(jù)時，必須采用檢錯措施。目前在數(shù)據(jù)鏈路中廣泛采用循環(huán)冗余檢驗CRC檢測技術(shù)。 1、循環(huán)冗余檢驗CRC的原理 利用CRC進(jìn)行檢錯的過程可簡單描述為：在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個校驗用的n位監(jiān)督碼(CRC碼)，附在原始信息后邊，構(gòu)成一個新的二進(jìn)

2、制碼序列數(shù)共k+n位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行檢驗，以確定傳送中是否出錯。這個規(guī)則，在差錯控制理論中稱為“生成多項式”。 代數(shù)學(xué)的一般性算法： 在代數(shù)編碼理論中，將一個碼組表示為一個多項式，碼組中各碼元當(dāng)作多項式的系數(shù)。例如 表示為 1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即 x6+x5+x2+1。 設(shè)編碼前的原始信息多項式為G(x)，G(x)的最高冪次加1等于k；生成多項式為P(x)，P(x)的最高冪次等于r；CRC多項式為R(x)；編碼后的帶CRC的信息多項式為T(x)

3、。 發(fā)送方編碼方法：將(x)乘以xr(即對應(yīng)的二進(jìn)制碼序列左移r位)，再除以(x)，所得余式即為R(x)。用公式表示為 T(x)=xr(x)+R(x) 接收方解碼方法：將T(x)除以G(x)，如果余數(shù)為0，則說明傳輸中無錯誤發(fā)生，否則說明傳輸有誤。2、循環(huán)冗余碼的產(chǎn)生及正確性檢驗的例子 舉例來說，設(shè)信息碼為，生成多項式為1101，即P(x)=x3+x2+1，G(x)=x5+x3+1，計算CRC的過程為 xrP(x) 即左移三位 (x) =x3+x2+1 即 R(x)=。 注意到G(x)最高冪次r=3，得出CRC為001。 如果用豎式除法，計算過程為（用異或計算）以(x)為準(zhǔn)，（x）左移P(x)

4、的最高次位（r）再除以P(x)本身求余可得一個的位的CRC碼: 1 1 0 1 0 1 （商） P（除數(shù)） 1 1 0 1 ) 1 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 1 R（余數(shù)）即檢驗碼因此，T(x)=XrG(x)+R(x), 即 +010= 如果傳輸無誤，T(x)除以P(x) 無余式?；仡^看一下上面的豎式除法，如果被除數(shù)是，除數(shù)是P=1101，顯然就能除盡?？傊?，在接收端對收到的每一幀經(jīng)過CRC檢驗后，（1）若得出的余數(shù)R=0，則判斷這個幀沒有差

5、錯，就接受。（2）若余數(shù)R不等于0，則判斷這個幀有差錯（但無法確定究竟是哪一位或那幾位出現(xiàn)了差錯），就丟棄。 3、用C語言程序?qū)崿F(xiàn) 下面以最常見的CRC-16為例說明生成過程，假設(shè)發(fā)送信息用信息多項式K(x)表示，將K(x)左移R位，則可以表示成K(x)*2R，這樣K(x)的右邊就會生成R位，這就是檢驗碼的位置，通過K(x)*2R除以生成多項式G(x)得到的余數(shù)就是檢驗碼。實現(xiàn)方法：1） 最高冪次為R的生成多項式G(x)轉(zhuǎn)換成對應(yīng)的R+1位二進(jìn)制數(shù)；2） 碼左移R位，相當(dāng)于對應(yīng)的信息多項式K(x)*2R；3） 多項式（二進(jìn)制）對信息碼做模2除，得到R位的余數(shù)；4） 拼到信息碼左移后空出的位置，

6、得到完整的CRC碼。C語言源程序代碼：#include<stdio.h> void main() unsigned int g,k,r,l,n,b,c,d,e,p,i,s,j,cont; register s1; printf("以下數(shù)據(jù)一十六進(jìn)制計數(shù)方式輸入n"); printf("請輸入生成碼的值：n"); scanf("%d",&g); printf("請輸入信息碼的值：n"); scanf("%d",&k); unsigned int m,w=0; /* 測量

7、生成碼的長度r*/ m=g; do m>>=1;w+; while (m!=0); r=w; unsigned int m,w=0; /* 測量信息碼的長度n*/m=k; do m>>=1;w+; while (m!=0); n=w; k<<=r-1; /* 信息碼左移r-1 位，相當(dāng)于K(x)*Xr*/ l=n+r-1; /* 信息總長度*/ cont=r; /*cont 作為已被除信息位數(shù)的計數(shù)器*/ i=k; i>>=(n-1); /* 取被除數(shù)信息碼的高r+1 位，即和生成碼的位數(shù)相同*/ do s=ig; /* 被除數(shù)信息碼與生成碼異或

8、運算*/ p=r;c=0; /* 統(tǒng)計余數(shù)s 高位零的個數(shù)，保存到c */ for(j=0;j<r;j+) s1=s; s1>>=(p-1); if(s1&01)=0) p-;c+; else break; if (c>l-cont)break; /* 余數(shù)s 高位零的個數(shù)高于信息碼沒有被除的位數(shù)，跳出循環(huán)，不再做異或運算*/ s<<=c; i=k; b=i>>(n-1-c); /* 取信息碼K 的從右端開始的(n+r-1)-r-c=n-1-c的C 位*/ d=(0<<c); e=b&d; s=s|e; /* 取s 的高位與信息碼沒被除的高位合成被除數(shù)*/ i=s; cont+=c; while (cont=l); s=s|k; /* 將最后余數(shù)和信息碼合在一起，形成CRC 的值*/ printf("運行結(jié)果為：n&qu