CRC码的简单计算(课下作业).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,CRC,码的计算,1.,什么是,CRC,码？,循环冗余码校验英文名称为,Cyclical Redundancy,Chec,k,，简称,CR,C,。它是利用多项式除法及余数的原理来作错误侦测（,Error Detecting,）的。实际应用时，发送装置计算出,CRC,值,并随数据一同发送给接收装置，接收装置对收到的数据重新计算,CRC,并与收到的,CRC,相比较，若两个,CRC,值不同，则说明,数据通讯,出现错误。,2.,多项式的生成,CRC,码,把整个数据块当作一串连续的二进制数据。代数结构可看作是一个报文码多项式，是基于将位串看成是系数为,0,或,1,的多项式，一个,k,位帧可以看成是从,x,（,k-1,）到,x,（,0,）的,k,次多项式的系数序列,，这个多项式的,阶数：,k-1,。,码组与多项式系数序列的对应,，高位,(,最左边,),是,x,的,k-1,项系数，下一位是,x,的,k-2,项的系数，以此类推，,生成多项式的最高位和最低位必须是,1,，且,生成多项式必须比该校验和的多项式短。,For example,110101,有,6,位，表示成多项式是,x5+x4+x2+0,，即它的,6,个多项式系数分别是,1,，,1,，,0,，,1,，,0,，和,1,。,when,采用多项式编码的方法，发送方和接收方必须事先商定一个生成多项式,G(x,),。要计算,m,位帧,M(x,),的校验和，生成多项式必须比该校验和的多项式短。,基本思想是：,将校验和加在帧的末尾，使这个带校验和的帧的多项式能被,G(x,),除尽。当接收方收到带有校验和的帧时，用,G(x,),去除它，如果有余数，则传输出错。,CRC,码的计算,由以上分析可知，既然,除数是随机，,或者按标准选定的，所以,CRC,校验的关键是如何求出,余数，也就是,CRC,校验码。,下面以一个例子来具体说明整个过程。现假设选择的,CRC,生成多项式为,G,（,X,）,=X4+X3+1,，要求出二进制序列,10110011,的,CRC,校验码。具体的计算过程如下（不会作图没办法啦）：,（,1,）首先把生成多项式,转换,成,二进制数,，由,G,（,X,）,=X4+X3+1,可以知道（，它一共是,5,位（总位数等于最高位的幂次加,1,，即,4+1=5,），然后根据多项式各项的含义（多项式只列出二进制值为,1,的位，也就是这个二进制的第,4,位、第,3,位、第,0,位的二进制均为,1,，其它位均为,0,）很快就可得到它的,二进制比特串为,11001,。,（,2,）因为生成多项式的位数为,5,，根据前面的介绍，得知,CRC,校验码的位数为,4,（校验码的位数比生成多项式的位数少,1,）。因为,原数据帧,10110011,，在它后面再加,4,个,0,，得到,101100110000,，,然后把这个数以“模,2,除法”方式除以生成多项式,11001,，得到的余数，即得,CRC,校验码为,0100,。具体操作在黑板上演示。,【,说明,】“,模,2,除法”,与“算术除法”类似，但它既不向上位借位，也不比较除数和被除数的相同位数值的大小，只要以相同位数进行相除即可。模,2,加法运算为：,1+1=0,，,0+1=1,，,0+0=0,，无进位，也无借位；模,2,减法运算为：,1-1=0,，,0-1=1,，,1-0=1,，,0-0=0,，也无进位，无借位。,相当于二进制中的逻辑异或运算,。也就是比较后，,两者对应位相同则结果为“,0”,，不同则结果为“,1”,。如,100101,除以,1110,，结果得到商为,11,，余数为,1,，再如,1111=101,。,总结计算,：,只要会把生成多项式按项系数转化为二进制数作为除数，在原帧后补上多项式阶数个,0,得到的新串作为被除数，做多项式除法时按,“,模,2,除法”，相减异或，商到最低位余数即为,CRC,码，将原帧加上,CRC,码发送就,O,啦,！谢谢！,2014-z0,