crc循环冗余码讲课.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,循环冗余校验码的原理及应用,1,1,crc简介,2,crc原理,3,crc的实现,4,实现框图,Content,2,循环冗余校验码,crc冗余校验码是常用的校验码，在早期的通信中运用广泛，因为早期的通信技术不够可靠（不可靠性的来源是通信技术决定的，比如电磁波通信时受雷电等因素的影响），不可靠的通信就会带来,确认信息,的困惑，书上提到红军和蓝军通信联合进攻山下的敌军的例子，第一天红军发了条信息要蓝军第二天一起进攻，蓝军收到之后，发一条确认信息，但是蓝军担心的是,确认信息,如果也不可靠而没有成功到达红军那里，那自己不是很危险？于是红军再发一条,对确认的确认信息,，但同样的问题还是不能解决，红军仍然不敢贸然行动。对通信的可靠性检查就需要,校验,，校验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或者进行修复。,3,明日正午进攻，如何？,同意,收到“同意”,收到,：,收到“同意”,这样的协议无法实现！,4,课件制作人：谢希仁,t,crc的特点,检错能力极强,开销很小,易于实现,应用范围广,zip，arj等压缩软件采用的是crc-32,GIF,TIFF等图像存储格式,所有链路层或网络接口层协议中,crc,的特点,5,差错检测,crc校验码的应用情况,在传输过程中可能会产生,比特差错,：,1,可能会变成,0,而,0,也可能变成,1,。,在一段时间内，传输错误的比特占所传输比特总数的比率称为,误码率,BER(Bit Error Rate),。,误码率与信噪比有很大的关系。,为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种差错检测措施。,6,crc产生背景,传播快速性,传播可靠性,消息在传播过程中，我们往往希望它传播的迅速，又希望它的可靠性强，可是鱼和熊掌不能兼得，这两个条件要同时实现又有点困难，怎么解决呢？于,是.,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,1100001010,10011,10011,10011,10110,10011,10100,10011,1110,余数,商数,除数,模2加=模2减,模2 乘,模2除=乘的可逆运算,10,接收端对收到的每条信息进行,CRC,检验,(1),若得出的余数,R,=0,，则判定这个信息没有差错，就,接受,(accept),。,(2),若余数,R,0,，则判定这个信息有差错，就,丢弃,。,但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。,只要经过严格的挑选，并使用位数足够多的除数,P,，那么出现检测不到的差错的概率就很小很小。,11,冗余码的计算举例,现在,k,=6,M,=101001,。,设,n,=3,除数,P,=1101,，,被除数是,2,nM,=101001000,。,模,2,运算的结果是：,商,Q,=110101,，,余数,R,=001,。,把余数,R,作为,冗余码,添加在数据,M,的后面发送出去。发送的数据是：,2,nMR,即：,101001001,，共,(,k,+,n,),位。,12,2.“无差错接受”是指：“凡是接受的信息（即,不包括丢弃的信息,），我们都能以非常接近于,1,的概率认为这些信息在传输过程中没有产生差错,3.也就是说：“凡是接收端接受的信息都没有传输差错”（,有差错的信息就丢弃而不接受,）。,4.要做到“,可靠传输,”（即发送什么就收到什么）就必须再加上,确认,和,重传,机制。,1.仅用循环冗余检验,CRC,差错检测技术只能做到无差错,接受,(accept),。,attention,13,#include,#include,#include,#include,using namespace std;,#define n 150,#define m 2*n-1,#define MAX_SIZE 1000000,int ss1000;,typedef struct,char ch;,int weight;,int lchild,rchild,parent;,HuffmanTree;,typedef HuffmanTree HTreem;,typedef struct,char ch;,int start;,char bitsn+1;,HuffmanCode;,typedef HuffmanCode HCoden;,int FileRead(int count,char s,char filename),int i=0,N=0,k=0,tempn;,char c;,FILE*rf;,rf=fopen(filename,r);,if(rf=NULL),printf(cannot open filen);,exit(0);,for(i=0;in;i+),sN=i;,countN=tempi;,N+;,return N;,void CreateHuffmanTree(HTree T,int N,int count,char s),int i,j,p1=0,p2=0,l1,l2;,for(i=0;iN;i+),Ti.ch=si;,for(i=0;i2*N-1;i+),Ti.lchild=0;,Ti.rchild=0;,Ti.parent=0;,for(i=0;iN;i+),Ti.weight=counti;,for(i=N;i2*N-1;i+),l1=l2=1000000;,for(j=0;ji;j+),if(Tj.parent=0),if(Tj.weightl1),l1=Tj.weight;,p1=j;,实现代码,14,for(j=0;ji;j+),if(Tj.parent=0),if(Tj.weightl2)&(j!=p1),l2=Tj.weight;,p2=j;,Tp1.parent=i;,Tp2.parent=i;,Ti.lchild=p1;,Ti.rchild=p2;,Ti.weight=Tp1.weight+Tp2.weight;,T2*N-2.parent=0;,void HuffmanCoding(HTree T,HCode H,int N,char s),int c,p,i,start;,char*cd=new charN+1;/cdn+1;,cdN=0;,int temp=0;,for(i=0;iN;i+),Hi.ch=si;,start=N;,c=i;,p=Tc.parent;,while(p),temp+;,if(Tp.lchild=c)cd-start=0;,else cd-start=1;,c=p;,p=Tp.parent;Hi.start=start;,/coutcd-cdstartendl;,for(int j=0;jtemp;j+),Hi.bitsj=cdstart+;,temp=0;,/coutHi.bits+endl;,/strcpy(Hi.bits,delete cd;,void FilePrint(HTree T,HCode H,int N),int i,j=0;,FILE*fp,*rp,*rf;,rf=fopen(HuffmanCode.txt,w);,fp=fopen(Char.txt,w);,rp=fopen(Weight.txt,w);,while(jN),/for(i=Hj.start;iN;i+),/,fprintf(rf,%s,Hj.bits);,/,fprintf(rf,n);,j+;,15,for(i=0;iN;i+)fputc(Hi.ch,fp);,for(i=0;it;/,输入的信息码是,6,位，如果要更长，修改下,l,字,g=g6;,t=t4;,k=t;,g=g3;,int i=0;,for(;i4;),if(t0 x80)/,表示首位为,0,，所要继续移动,t=t4;,k=kt;,return k;,int test(int k,int g)/,测试部分 判断生成码是否正确,int result=0;,g=g0 x80),k=kg;,k=k1;,if(!k),break;,j-;,if(j!=0),/coutsucess,余数,tkendl;,else,/coutfailendl;,result=1;,return result;,void file(int ss,int xx),FILE*rf;,int x;,int g=0 x13;,x=xx;,rf=fopen(crc.txt,wb);,16,for(int i=0;ixx;i+),fputc(ssi,rf);,fclose(rf);,int FileWrite(HCode H,int N,char filename),int i,k,p=0;,int t=0;/,存放数值,/int m=0;char c;,int cc=0;,int sign=0;,FILE*rf,*fp;,rf=fopen(filename,r);,fp=fopen(File.txt,w);,if(rf=NULL),printf(cannot open filenn );,exit(0);,int xx=0;,while(!feof(rf),c=fgetc(rf);,int xxx;,for(i=0;iN;i+),xxx=0;,if(Hi.ch=c),for(k=Hi.start;kN;k+),/fputc(Hi.bitsk,fp);,fprintf(fp,%c,Hi.bitsxxx);,sign=1;,p+if(Hi.bitsxxx=1),t=2*t+1;,else,t=2*t;,if(p=4),fprintf(fp,);,p=0;,/coutt=ttendl;,sscc+=crc(t);,/coutss=tcrc(t)endl;,t=0;,xx+;,sign=0;,xxx+;,if(sign=1),sscc+=crc(t);,xx+;,file(ss,xx);,return xx;,fclose(rf);,fclose(fp);,17,int FileRead(HTree T,HCode H),int i=0,j=0,N=0;,char c,*p;,char strMAX_SIZE;,FILE*rf,*fp,*rp;,rf=fopen(Char.txt,r);,fp=fopen(HuffmanCode.txt,r);,rp=fopen(Weight.txt,r);,if(rf=NULL),printf(cannot open filen);,exit(0);,if(fp=NULL),printf(cannot open filen);,exit(0);,if(rp=NULL),printf(cannot open filen);,exit(0);,while(!feof(rf),HN.ch=fgetc(rf);,TN.ch=HN.ch;,N+;,while(!feof(fp),c=fgetc(fp);,switch(c),casen:,i+;,j=0;break;,default:,Hi.bitsj=c;,j+;,Hi.bitsj=0;,break;,for(i=0;iN;i+),Ti.weight=0;,i=0;,j=0;,while(!feof(rp)/rp=fopen(Weight.txt,r);,c=fgetc(rp);,switch(c),casen:,for(p=str;*p!=0;p+),Ti.weight=*p-48;,i+;,j=0;break;,default:,strj=c;,j+;,strj=0;break;,18,实验截图,19,20,21,22,开始,置移位次数为,8,将一帧数据末尾加两个字节,将这两个字节清 零作为将来,crc,的校验位,指针指向数据区 首地址并将所 指数据给,R0,数据指针加,1,，讲所指数据给,R,数据指针加,1,，讲所指数据给,R0,三字节右移一位,移出位为,R0,最低位,R1R0,与,#A001H,异或,移位次数减,1,长度字节减,1,R1R0,中的数值即,为,CRC,的校验位,为,1?,为,0,？,为,0,？,Y,N,Y,N,Y,N,23,放映结束,謝謝您的觀看,thank you,24,