crc循环冗余码讲课

循环冗余校验码的原理及应用11crc简介2crc原理3crc的实现4实现框图

Content2循环冗余校验码crc冗余校验码是常用的校验码，在早期的通信中运用广泛，因为早期的通信技术不够可靠（不可靠性的来源是通信技术决定的，比如电磁波通信时受雷电等因素的影响），不可靠的通信就会带来‘确认信息’的困惑，书上提到红军和蓝军通信联合进攻山下的敌军的例子，第一天红军发了条信息要蓝军第二天一起进攻，蓝军收到之后，发一条确认信息，但是蓝军担心的是‘确认信息’如果也不可靠而没有成功到达红军那里，那自己不是很危险？于是红军再发一条‘对确认的确认信息’，但同样的问题还是不能解决，红军仍然不敢贸然行动。对通信的可靠性检查就需要‘校验’，校验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或者进行修复。3明日正午进攻，如何？同意收到“同意”收到：收到“同意”………………这样的协议无法实现！4课件制作人：谢希仁tcrc的特点检错能力极强开销很小易于实现应用范围广zip，arj等压缩软件采用的是crc-32GIF,TIFF等图像存储格式所有链路层或网络接口层协议中crc的特点5差错检测

crc校验码的应用情况

在传输过程中可能会产生比特差错：1可能会变成0而0也可能变成1。在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率

BER(BitErrorRate)。误码率与信噪比有很大的关系。为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。6crc产生背景传播快速性传播可靠性消息在传播过程中，我们往往希望它传播的迅速，又希望它的可靠性强，可是鱼和熊掌不能兼得，这两个条件要同时实现又有点困难，怎么解决呢？于是........pk采用差错控制crc产生啦！crc产生啦！7编码规则相除运用一个生成多项式g(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码.有了加减法就可以用来定义模2除法，于是就可以用生成多项式g(x)生成CRC校验码。移位将原信息码(kbit)左移r位(k+r=n)生成多项式应满足以下原则a、生成多项式的最高位和最低位必须为1。b、当被传送信息（CRC码）任何一位发生错误时，被生成多项式做模2除后应该使余数不为0。c、不同位发生错误时，应该使余数不同。d、对余数继续做模2除，应使余数循环。8循环冗余检验的原理在发送端，先把数据划分为组。假定每组k个比特。在数据链路层传送的信息中，广泛使用了循环冗余检验CRC的检错技术。假设待传送的一组数据M=101001（现在k=6）。我们在M的后面再添加供差错检测用的n

位冗余码一起发送。9

多项式除法循环冗余检验的原理说明举例11010110110000被除数10011

110000101010011100111001110110100111010010011

1110余数商数除数模2加=模2减模2乘模2除=乘的可逆运算10接收端对收到的每条信息进行CRC检验(1)若得出的余数R=0，则判定这个信息没有差错，就接受(accept)。(2)若余数R

0，则判定这个信息有差错，就丢弃。但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。只要经过严格的挑选，并使用位数足够多的除数P，那么出现检测不到的差错的概率就很小很小。11冗余码的计算举例现在

k=6,M=101001。设

n=3,除数

P=1101，被除数是2nM=101001000。模2运算的结果是：商

Q=110101，

余数

R=001。把余数R作为冗余码添加在数据M的后面发送出去。发送的数据是：2nM+R

即：101001001，共(k+n)位。122.“无差错接受”是指：“凡是接受的信息（即不包括丢弃的信息），我们都能以非常接近于1的概率认为这些信息在传输过程中没有产生差错3.也就是说：“凡是接收端接受的信息都没有传输差错”（有差错的信息就丢弃而不接受）。4.要做到“可靠传输”（即发送什么就收到什么）就必须再加上确认和重传机制。1.仅用循环冗余检验CRC差错检测技术只能做到无差错接受(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;}

实现代码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)//生成系统冗余校验码{ 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，所要继续移动

{ 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"<<"余数\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;//存放数值

//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;