云知道-循环冗余校验码_第1页
云知道-循环冗余校验码_第2页
云知道-循环冗余校验码_第3页
云知道-循环冗余校验码_第4页
云知道-循环冗余校验码_第5页
已阅读5页,还剩1页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

循环冗余校验码在串行通信中,如外存储器与内存之间、计算机网络通信一般采用循环冗余校验码CRC(CyclicRedundancyCheck)。循环冗余校验码是在n位有效信息位后拼接k位校验位构成的,它通过除法运算来建立有效信息和校验位之间的约定关系,是一种具有很强检错纠错能力的校验码。1.循环冗余校验码的原理循环冗余校验码的基本思想是把n位有效信息的二进制数位看成是一个n阶多项式M(x)的系数。如n=8的一个信息11010011对应的n阶多项式为:M(x)=1x7+1x6+0x5+1x4+0x3+0x2+1x1+1x0=x7+x6+x4+x1+x0多项式M(x)承载着要传输的有效信息,对于多项式M(x)用事先约定的多项G(x)去除,然后得到商Q(x)和余数R(x),商和余数也是一个多项式,它们的关系是:M(x)根据余数定义可得:M(x)-R(x)=Q(x)×G(x)在数据通信中,把M(x)-R(x)作为信息的校验码发送,接收方收到编码后,使用原约定的多项式G(x)去除,如果能够整除,即余数为0,则表示该校验码传输过程中没有出错;如果不能够整除,即余数不为0,则表示数据传输过程中发生了错误。在生成CRC编码时,需要执行二进制数的算术运算,必然涉及进位和借位问题,为提高CRC码的生成效率,简化逻辑运算电路的设计与实现,CRC编码运算中采用了模2运算(就是按位异或运算,请参见“任务二认识数的进制与转换”中的相关内容),这种运算不考虑运算过程的进位和借位,极大地简化了操作。2.循环冗余校验码编码方法(1)把n位有效信息表示为多项式M(x)=Cn-1xn-1+Cn-2xn-2+…+c1x1+c0,系数Ci的值为0或1(i=0~n-1)表示有效信息位中第i位的数码。(2)选择一个作除数的k+1位生成多项式G(x)=Gkxk+Gk-1xk-1+…+G1x1+G0,其中系数Gi=0或1(i=0~k),对应k+1位的生成多项式中第i位的信息。(3)将M(x)左移k位,得到n+k位的M(x)·xk,然后按模2除法除以G(x)得到k位余数R(x):Mx·xkG(x)=(4)把M(x)·xk与余数R(x)做模2加运算,得:M(x)·xk+R(x)=Q(x)·G(x)+R(x)+R(x)=Q(x)·G(x),由于执行的是模2加运算,所以R(x)+R(x)=0,于是有M(x)·xk+R(x)=Q(x)·G(x),可知M(x)·xk+R(x)能被多项式G(x)整除,所以M(x)·xk+R(x)能作为CRC码。根据该表达式,生成CRC的过程为把M(x)左移k位,M(x)·xk的后k位全为0,然后与R(x)模2加就得到了n+k位循环冗余校验码。此法把原来的M(x)-R(x)运算简化为移位操作和与0相加的拼接运算。对生成多项式G(x)=x3+x1+1,生成4位有效信息1101的CRC码。有效信息多项式M(x)=1101=1·x3+1·x2+0·x1+1·x0=x3+x2+1生成多项式G(x)=x3+x1+1=G3x3+G2x2+G1x1+G0=1011则有:M(x)·x3=1101000M(x)·x3÷G(x)=1101000÷1011=1111…001R(x)=001得到有效信息1101的循环冗余校验码:M(x)·x3+R(x)=1101000+001=1101001循环冗余校验码由n位有效信息和k位校验信息构成的n+k位编码,称为(n+k,n)码。例中的n=4,k=3,n+k=7,得到的CRC码简称为(7,4)码。3.校验CRC码接收端对收到的CRC码用原约定的生成多项式G(x)做模2除,若得到的余数为0,表示接收到的信息中没有错误;若除得的余数不为0,则表示接收到的信息中某一位出错。由于不同位出错对应的余数不同,所以根据余数值就可确定出错的位置并实现自动纠错。以生成多项式G(x)=x3+x1+1和4位有效信息1101的CRC码为例,当不同的位出错与余数结果如下表所示。A7A6A5A4A3A2A1余数出错位无错码1101001000出错码11010000011110101101021101101100311000010114111100111051001001111601010011017表中任意一个出错码除以生成多项式G(x)=1011得到的余数不为0,如果补0后继续除以多项式G(x),你会发现余数会循环出现,所以称这样生成的校验码为循环冗余校验码。如图2-29所示,以上表中最后一行的出错码为例,图中有加粗标注的3位数字是当次的余数,在余数后补0再除得下一个余数,这些余数以为7周期重复出现。采用循环冗余校验码的关键是找到恰当的生成多项式G(x),生成多项式不同,得到的CRC码的码距就不同,CRC码的出错模式也不同,而且检错和纠错能力不同。不是任意的k+1位多项式都能作为生成多项式使用。生成多项式应满足下列要求:任何一位发生错误都应使余数不为0;不同位发生错误应当使余数不同;对余数做模2除法,应能使余数循环。常用的生成多项式G(x)如下表所示。信息位G(x)多项式G(x)二进制形式CRC码长码距3x4+x3+x2+111101743x4+x2+x1+110111744x3+x1+11011734x3+x2+11101735x10+x8+x5+x4+x2+x1+1101001101111577x8+x7+x6+x4+x1+111101001115511x4+x1+11001115321x10+x9+x8+x6+x5+x3+11110110100131526x5+x2+110010131351x12+x10+x5+x4+x2+1101000011010163557x6+x1+11000011633在实际数据通信网络中,n一般较大,由一千甚至数千个二进制数据位构成,为检测信息传输的正确与否,需要所使用的生成多项式的幂次也比较高,常用k=16和k=32的生成多项式,如下所示。CRC-16=x1

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论