crc循環(huán)冗余碼講課

循環(huán)冗余校驗碼的原理及應(yīng)用11crc簡介2crc原理3crc的實現(xiàn)4實現(xiàn)框圖

Content2循環(huán)冗余校驗碼crc冗余校驗碼是常用的校驗碼，在早期的通信中運用廣泛，因為早期的通信技術(shù)不夠可靠（不可靠性的來源是通信技術(shù)決定的，比如電磁波通信時受雷電等因素的影響），不可靠的通信就會帶來‘確認信息’的困惑，書上提到紅軍和藍軍通信聯(lián)合進攻山下的敵軍的例子，第一天紅軍發(fā)了條信息要藍軍第二天一起進攻，藍軍收到之后，發(fā)一條確認信息，但是藍軍擔(dān)心的是‘確認信息’如果也不可靠而沒有成功到達紅軍那里，那自己不是很危險？于是紅軍再發(fā)一條‘對確認的確認信息’，但同樣的問題還是不能解決，紅軍仍然不敢貿(mào)然行動。對通信的可靠性檢查就需要‘校驗’，校驗是從數(shù)據(jù)本身進行檢查，它依靠某種數(shù)學(xué)上約定的形式進行檢查，校驗的結(jié)果是可靠或不可靠，如果可靠就對數(shù)據(jù)進行處理，如果不可靠，就丟棄重發(fā)或者進行修復(fù)。3明日正午進攻，如何？同意收到“同意”收到：收到“同意”………………這樣的協(xié)議無法實現(xiàn)！4課件制作人：謝希仁tcrc的特點檢錯能力極強開銷很小易于實現(xiàn)應(yīng)用范圍廣zip，arj等壓縮軟件采用的是crc-32GIF,TIFF等圖像存儲格式所有鏈路層或網(wǎng)絡(luò)接口層協(xié)議中crc的特點5差錯檢測

crc校驗碼的應(yīng)用情況

在傳輸過程中可能會產(chǎn)生比特差錯：1可能會變成0而0也可能變成1。在一段時間內(nèi)，傳輸錯誤的比特占所傳輸比特總數(shù)的比率稱為誤碼率

BER(BitErrorRate)。誤碼率與信噪比有很大的關(guān)系。為了保證數(shù)據(jù)傳輸?shù)目煽啃?，在計算機網(wǎng)絡(luò)傳輸數(shù)據(jù)時，必須采用各種差錯檢測措施。6crc產(chǎn)生背景傳播快速性傳播可靠性消息在傳播過程中，我們往往希望它傳播的迅速，又希望它的可靠性強，可是魚和熊掌不能兼得，這兩個條件要同時實現(xiàn)又有點困難，怎么解決呢？于是........pk采用差錯控制crc產(chǎn)生啦！crc產(chǎn)生啦！7編碼規(guī)則相除運用一個生成多項式g(x)（也可看成二進制數(shù)）用模2除上面的式子，得到的余數(shù)就是校驗碼.有了加減法就可以用來定義模2除法，于是就可以用生成多項式g(x)生成CRC校驗碼。移位將原信息碼(kbit)左移r位(k+r=n)生成多項式應(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)。8循環(huán)冗余檢驗的原理在發(fā)送端，先把數(shù)據(jù)劃分為組。假定每組k個比特。在數(shù)據(jù)鏈路層傳送的信息中，廣泛使用了循環(huán)冗余檢驗CRC的檢錯技術(shù)。假設(shè)待傳送的一組數(shù)據(jù)M=101001（現(xiàn)在k=6）。我們在M的后面再添加供差錯檢測用的n

位冗余碼一起發(fā)送。9

多項式除法循環(huán)冗余檢驗的原理說明舉例11010110110000被除數(shù)10011

110000101010011100111001110110100111010010011

1110余數(shù)商數(shù)除數(shù)模2加=模2減模2乘模2除=乘的可逆運算10接收端對收到的每條信息進行CRC檢驗(1)若得出的余數(shù)R=0，則判定這個信息沒有差錯，就接受(accept)。(2)若余數(shù)R

0，則判定這個信息有差錯，就丟棄。但這種檢測方法并不能確定究竟是哪一個或哪幾個比特出現(xiàn)了差錯。只要經(jīng)過嚴(yán)格的挑選，并使用位數(shù)足夠多的除數(shù)P，那么出現(xiàn)檢測不到的差錯的概率就很小很小。11冗余碼的計算舉例現(xiàn)在

k=6,M=101001。設(shè)

n=3,除數(shù)

P=1101，被除數(shù)是2nM=101001000。模2運算的結(jié)果是：商

Q=110101，

余數(shù)

R=001。把余數(shù)R作為冗余碼添加在數(shù)據(jù)M的后面發(fā)送出去。發(fā)送的數(shù)據(jù)是：2nM+R

即：101001001，共(k+n)位。122.“無差錯接受”是指：“凡是接受的信息（即不包括丟棄的信息），我們都能以非常接近于1的概率認為這些信息在傳輸過程中沒有產(chǎn)生差錯3.也就是說：“凡是接收端接受的信息都沒有傳輸差錯”（有差錯的信息就丟棄而不接受）。4.要做到“可靠傳輸”（即發(fā)送什么就收到什么）就必須再加上確認和重傳機制。1.僅用循環(huán)冗余檢驗CRC差錯檢測技術(shù)只能做到無差錯接受(accept)。attention

13#include<stdio.h>#include<string.h>#include<stdlib.h>#include<iostream>usingnamespacestd;#definen150#definem2*n-1#defineMAX_SIZE1000000intss[1000];typedefstruct{ charch; intweight; intlchild,rchild,parent;}HuffmanTree;typedefHuffmanTreeHTree[m];typedefstruct{ charch; intstart; charbits[n+1];}HuffmanCode;typedefHuffmanCodeHCode[n];intFileRead(intcount[],chars[],charfilename[]){inti=0,N=0,k=0,temp[n];charc;FILE*rf;rf=fopen(filename,"r");if(rf==NULL){printf("cannotopenfile\n");

exit(0);}for(i=0;i<n;i++)

s[N]=i;count[N]=temp[i];N++;}}returnN;}voidCreateHuffmanTree(HTreeT,intN,intcount[],chars[]){inti,j,p1=0,p2=0,l1,l2; for(i=0;i<N;i++) { T[i].ch=s[i]; }for(i=0;i<2*N-1;i++){T[i].lchild=0;T[i].rchild=0;T[i].parent=0;}for(i=0;i<N;i++)T[i].weight=count[i];for(i=N;i<2*N-1;i++){l1=l2=1000000;for(j=0;j<i;j++){if(T[j].parent==0){if(T[j].weight<l1){l1=T[j].weight;p1=j;}

實現(xiàn)代碼14

}}for(j=0;j<i;j++){if(T[j].parent==0){if((T[j].weight<l2)&&(j!=p1)){l2=T[j].weight;p2=j;}}}T[p1].parent=i;T[p2].parent=i;T[i].lchild=p1;T[i].rchild=p2;T[i].weight=T[p1].weight+T[p2].weight;}T[2*N-2].parent=0;}voidHuffmanCoding(HTreeT,HCodeH,intN,chars[]){ intc,p,i,start; char*cd=newchar[N+1];//cd[n+1]; cd[N]='\0'; inttemp=0; for(i=0;i<N;i++) {H[i].ch=s[i]; start=N; c=i;p=T[c].parent;while(p){

temp++;if(T[p].lchild==c)cd[--start]='0';elsecd[--start]='1';c=p;p=T[p].parent;H[i].start=start; //cout<<"cd---"<<cd[start]<<endl;} for(intj=0;j<temp;j++) { H[i].bits[j]=cd[start++]; } temp=0;

//cout<<H[i].bits<<"++++++"<<endl;//strcpy(H[i].bits,&cd[start]);} deletecd;}voidFilePrint(HTreeT,HCodeH,intN){ inti,j=0; FILE*fp,*rp,*rf; rf=fopen("HuffmanCode.txt","w"); fp=fopen("Char.txt","w"); rp=fopen("Weight.txt","w"); while(j<N) {//for(i=H[j].start;i<N;i++) //{ fprintf(rf,"%s",H[j].bits); //}fprintf(rf,"\n");j++;}15for(i=0;i<N;i++)fputc(H[i].ch,fp); for(i=0;i<N;i++)fprintf(rp,"%d\n",T[i].weight); fclose(rf); fclose(fp); fclose(rp);}intcrc(intt)//生成系統(tǒng)冗余校驗碼{ intk; intg=0x13;//這里生成多項式使是4次10011 //cin>>t;//輸入的信息碼是6位，如果要更長，修改下l字g=g<<5;for(;i<6;)if(t<0x200)t=t>>6; t=t<<4; k=t; g=g<<3; inti=0; for(;i<4;) { if(t<0x80)//表示首位為0，所要繼續(xù)移動

{ t=t<<1; i++; } else t=t^g;//做模二運算

} t=t>>4; k=k^t; returnk;}inttest(intk,intg)//測試部分判斷生成碼是否正確{ intresult=0; g=g<<3;

intj=5; while(j) { if(k>0x80) { k=k^g; } k=k<<1; if(!k) { break; } j--; }if(j!=0) { //cout<<"sucess"<<"余數(shù)\t"<<k<<endl; } else { //cout<<"fail"<<endl; result=1; } returnresult;}voidfile(intss[],intxx){ FILE*rf; intx; intg=0x13; x=xx; rf=fopen("crc.txt","wb");

16for(inti=0;i<xx;i++) { fputc(ss[i],rf); } fclose(rf); }intFileWrite(HCodeH,intN,charfilename[]){ inti,k,p=0; intt=0;//存放數(shù)值

//intm=0; charc; intcc=0; intsign=0; FILE*rf,*fp; rf=fopen(filename,"r"); fp=fopen("File.txt","w"); if(rf==NULL) {printf("cannotopenfile\n\n");exit(0);

} intxx=0; while(!feof(rf)) {c=fgetc(rf); intxxx;for(i=0;i<N;i++) { xxx=0;if(H[i].ch==c) {for(k=H[i].start;k<N;k++)

{ //fputc(H[i].bits[k],fp); fprintf(fp,"%c",H[i].bits[xxx]); sign=1;p++; if(H[i].bits[xxx]=='1') t=2*t+1; else t=2*t;if(p==4) {fprintf(fp,"");p=0; //cout<<"t="<<t<<"\t"<<endl; ss[cc++]=crc(t); //cout<<"ss==\t"<<crc(t)<<endl; t=0; xx++; sign=0; }xxx++; } }}} if(sign==1) { ss[cc++]=crc(t); xx++; } file(ss,xx); returnxx; fclose(rf); fclose(fp);17}intFileRead(HTreeT,HCodeH){inti=0,j=0,N=0;charc,*p;charstr[MAX_SIZE];FILE*rf,*fp,*rp;rf=fopen("Char.txt","r"); fp=fopen("HuffmanCode.txt","r");rp=fopen("Weight.txt","r");if(rf==NULL){printf("cannotopenfile\n");exit(0);}if(fp==NULL){printf("cannotopenfile\n");exit(0);}if(rp==NULL){printf("cannotopenfile\n");exit(0);}while(!feof(rf)){H[N].ch=fgetc(rf);T[N].ch=H[N].ch;N++;}while(!feof(fp)){c=fgetc(fp);switch(c)

{case'\n':i++;j=0;break;default:H[i].bits[j]=c;