分享
分销 收藏 举报 申诉 / 23

类型第3章-(3.7-数据校验码).ppt

  • 上传人:仙人****88
  • 文档编号:14748240
  • 上传时间:2026-11-13
  • 格式:PPT
  • 页数:23
  • 大小:611.50KB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    3.7 数据 校验码
    资源描述:
    单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,/23,*,校验码,将有效代码和增加的校验位一起,按约定的 校验规律进行编码而获得。,3.7,数据校验码,是一种常用的带有发现错误或带有自动改错 能力的数据编码方法。,实现原理:,加进一些冗余码,使合法编码出现某些错误时,就,成为非法编码。这样,就可通过检测编码的合法性,来达到发现错误的目的。,1,1,/23,码距:,指任意两个合法码之间至少有几个 二进制位不相同。,若码距为,1,,则发生错误时仍是合法码,无查错能力。,一般来说,合理增大码距,就能提高发现错误的能力,但码使用的二进制位数变多,增加了数据存储的容量 或数据传送的数量。,在确定与使用数据校验码时,通常要考虑在不过多增 加硬件开销的情况下,尽可能发现或改正更多的错误。,2,2,/23,开销最小,能发现数据中一位出错的情况。,一、奇偶校验码,实现原理:,使码距由,1,增加到,2,。,若编码中有一个二进制位出错(由,1,变成,0,,或由,0,变成,1,),这个码都将成为非法编码。,实现方法,为一个字节补充一个二进制位(校验位),设置该校验位的值为,0,或,1,,使字节的,8,位和该校验位中含有“,1”,值的总个数为奇数(奇校验)或偶数(偶校验)。,3,3,/23,例如,设某数据为:,10110001,奇校验码为:,偶校验码为:,缺点,只能发现奇数位错,但不能确定是哪一位。,因一位出错的几率大,故有实用价值。,1,10110001,0,10110001,4,4,/23,逻辑实现:,多采用并行奇偶统计方法。,编,码,译,码,5,5,/23,实质:,是一种多重奇偶校验。,二、海明校验码(广泛采用),实现原理:,将代码按一定的规律组织为若干组,分组 进行奇偶校验。,各组的检错信息构成一个指误字,不但可以 发现出错,还能指出是哪一位出错,为自动 纠错提供依据。,6,6,/23,(1),分成几组?增加多少校验位?,设待编信息,k,位,分为,r,组,每组增加一个,校验位,则,r,位校验位构成一个,r,位的指误字。,r,位校验位能表示,2,r,种状态:,用全,0,表示“没有错误”;,用其余,2,r,-1,种状态指出错误发生在哪一位。,具体实现,7,7,/23,因为错误也可能发生在校验位,所以只有,k=2,r,-1-r,个信息能用于纠正被传送数据的位数。,即需要满足:,2,r,k+r+1,若设,k=4,,则,r3,,组成,7,位海明码。,8,8,/23,(2),分组方法?,设待编信息,4,位,A,4,A,3,A,2,A,1,,增加,3,位校验位,P,3,P,2,P,1,,构成一个,3,位的指误字,G,3,G,2,G,1,。,7,6,5,4,3,2,1,A,4,A,3,A,2,P,3,A,1,P,2,P,1,P,i,在海明码中位号为,2,i-1,的位置上。,9,9,/23,7,6,5,4,3,2,1,指误字,A,4,A,3,A,2,P,3,A,1,P,2,P,1,第,3,组,G,3,第,2,组,G,2,第,1,组,G,1,“”表示某位海明码参加某组。,有效信息位,A,i,分别参加,2,组以上。,每个校验位,P,i,只参加,1,组。,10,10,/23,(3),编码(以偶校验为例)?,第,1,组:,P,1,=A,1,A,2,A,4,G,1,=P,1,A,1,A,2,A,4,第,2,组:,P,2,=A,1,A,3,A,4,G,2,=P,2,A,1,A,3,A,4,第,3,组:,P,3,=A,2,A,3,A,4,G,3,=P,3,A,2,A,3,A,4,(4),查错与纠错,若,G,3,G,2,G,1,000,,,若,G,3,G,2,G,1,000,,,则无错;,则,G,3,G,2,G,1,的值即指明出错位,,将该位取反即可纠正。,11,11,/23,7,6,5,4,3,2,1,指误字,G,3,G,2,G,1,A,4,A,3,A,2,P,3,A,1,P,2,P,1,正确码,0,1,0,1,1,0,1,000,出错码,0,1,1,1,1,0,1,101,G,1,=P,1,A,1,A,2,A,4,=1 1 1 0=1,G,2,=P,2,A,1,A,3,A,4,=0 1 1 0=0,G,3,=P,3,A,2,A,3,A,4,=1 1 1 0=1,12,12,/23,(5),逻辑实现,(,译码电路,),13,13,/23,在,k,4,,,r,3,的海明码中,两个合法码之间,至少有,1,个有效信息位不同。因一个有效信息,位至少参加,2,组校验,相应的两个校验位也会,不同,故其码距,d,3,。,(6),分析,d,3,的码能够检测,2,位错,或用来检测并纠正,1,位错,但两者只能择一。,如要能检测并纠正,1,位错,同时能发现,2,位错,,此时应增加一个校验位,即应满足:,2,r-1,k+r,14,14,/23,校验规则:,让校验码能被某一约定代码除尽。,若能除尽,表明代码无错;,若除不尽,余数将指明出错位置。,三、循环冗余校验码(,CRC,码),实现原理:,在,k,位信息位之后拼接,r,位校验位。,问题,1,:如何从,k,位信息位简便地得到,r,位校验位?,问题,2,:如何从,k+r,位信息码判断是否有错?,15,15,/23,模,2,运算:,以按位模,2,相加为基础,运算时不考虑进位和借位。,模,2,加减(异或),0,0,0,0,1,1,1,0,1,1,1,0,模,2,乘(用模,2,加求和),例如:,1 0 1 0 1 0 1 1 0 1 0 0 0 0 0,1 0 1 0 1 0 0 0 1 0,16,16,/23,模,2,除(用模,2,减求余数)每求,1,位商使部分余数减少,1,位。,上商原则:部分余数的首位为,1,,商取,1,;部分余数的首位为,0,,商取,0,。,当部分余数位数小于除数位数时,该余数为最后余数。,例如:,1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1,17,17,/23,设:被除数,M(x,),:,k,位待编信息 除数,G(x,),:,r+1,位,?,余数,R(x,),:,r,位校验位 商,Q(x,),(1)CRC,码的编码方法,具体实现,a.,将待编码的,k,位有效信息位组写成表达式:,M(x,)=C,k-1,X,k-1,+C,k-2,X,k-2,+C,1,X+C,0,(,C,i,=0,或,1),b.,将信息位组左移,r,位,变成多项式,M(x,),X,r,;,c.,用,M(x,),X,r,除以,G(x,),,所得余数作为校验位。,d.,有效的,CRC,码为:,M(x,),X,r,+R(x,)=,Q(x,),G(x)+R(x)+R(x,)=,Q(x,),G(x,),。,所以:,CRC,码能够被,G(x,),除尽。,18,18,/23,例如:,对,M(x,)=1100,,用,G(x,)=1011,,求,CRC,码。,a.,将待编码的,k=4,位有效信息位组写成表达式:,M(x,)=C,k-1,X,k-1,+C,k-2,X,k-2,+C,1,X+C,0,=X,3,+X,2,=1100,b.,将信息位组左移,r=3,位,M(x,),X,r,=M(X),X,3,=1100000,c.,用,M(x,),X,r,除以,G(x,),,所得余数作为校验位。,d.,有效的,CRC,码,此处为,(7,4),码,为:,M(x,),X,r,+R(x,),=1100000+010=1100010,。,19,19,/23,(2)CRC,码的译码与纠错,译码:,用收到的,CRC,码除以,G(x,),。,若码字无误,则余数为,0,;,若有某,1,位错,则余数不为,0,且不同位出错时的余数不同。,注意:,余数与出错位的对应关系不变,它只与码制和生成多项式,G(x,),有关,而与待测码字无关。,20,20,/23,(7,,,4),循环码的出错模式,(,生成多项式,G(x,)=1011),A,1,A,2,A,3,A,4,A,5,A,6,A,7,余数,出错位,正确,1,1,0,0,0,1,0,0 0 0,无,错误,1,1,0,0,0,1,1,0 0 1,7,1,1,0,0,0,0,0,0 1 0,6,1,1,0,0,1,1,0,1 0 0,5,1,1,0,1,0,1,0,0 1 1,4,1,1,1,0,0,1,0,1 1 0,3,1,0,0,0,0,1,0,1 1 1,2,0,1,0,0,0,1,0,1 0 1,1,21,21,/23,纠错:,对于用,G(x,),作模,2,除得到的余数,R(x,),,若补,0,继续除下去,发现各次的余数按上表的顺序循环。,所以,可以采用一种节省硬件的纠错办法:,如只设置余数,101,的译码输出,对应于第,1,位,A1,出错。,在求出余数不为,0,后,对余数一边补,0,一边作模,2,除,,同时将被测码字循环左移,当余数为,101,时,出错位,移到,A1,位置,将它纠正后继续移位,使移位次数满,k+r,次即可。,22,22,/23,(3),生成多项式,G(x,),不是任一个,(r+1),位多项式都可作生成多项式。,生成多项式应能满足下列要求:,任何一位发生错误都应使余数不为,0,。,不同位发生错误应当使余数不同。,对余数继续作模,2,除,应使余数循环。,生成多项式可以查表得到。,23,23,/23,
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:第3章-(3.7-数据校验码).ppt
    链接地址:https://www.zixin.com.cn/doc/14748240.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork