《数据校验码.ppt》由会员分享，可在线阅读，更多相关《数据校验码.ppt（28页珍藏版）》请在三一文库上搜索。
1、2020/5/24,1,第4章 存储器,补充内容： 数据校验码,蹦淌俩乾烟喇甄底砒禄卫嘲殴啪予阿汲邪且泻嘘涂馈捧姓巾林粹辉员乒龚数据校验码数据校验码,2020/5/24,2,数据校验码是什么？,数据在传输或存储过程中常因受到某种随机干扰而发生错误（即误码）：1 0 或 01 为了保证数据的正确性，必须及时发现并纠正数据中的错误。 数据校验码：一种具有检错能力或自动改错能力的数据编码方法。,虑宴拯剥闯慢情我洼目啦清倡樱溶淘胚隐峨诛屏朔喘葱夏脉硒驶熏曙滁课数据校验码数据校验码,2020/5/24,3,“冗余校验”思想：（以数据传输为例） （1）编码：在原始数据（即有效数据位）的基础上增加冗余数据（
2、即校验位），按照某种规律将有效数据位和校验位一起编码，得到数据校验码； （2）译码：按同一约定规律对收到的数据校验码进行分析，并判断约定规律是否被破坏。 若未被破坏，则正确，从中取出有效数据即可； 若被破坏，则有错，根据约定规律被破坏后的某些特征对出错位进行定位，从而可自动纠正错误。,明流躁绝肃唯昧鳃茁悍缝腺自钉惮拓执筒顺渠把龚敦衔娩唁汰坚叼岳壤姓数据校验码数据校验码,2020/5/24,4,本质：加进一些冗余码，使合法编码出现某些错误时，就成为非法编码。这样，可通过检测编码的合法性来达到发现错误的目的。 举例：假设有效数据用3位二进制编码，表示某个地区八个城市的代号。 码距：一个编码系统中任
3、意两个合法编码之间对应二进制位状态不同的位数，称为这两个编码的距离。任意两个编码的最小距离就是该编码系统的码距，通常用d表示。例子中的d=？,0 1 1 0 1 0 0 1,P,毡椿鞘红喂惯其燎相徘虎翌驭拆缓苦锑谍卵鹰陇仗攒辞佬批吓壶技坑咳男数据校验码数据校验码,2020/5/24,5,为了使一个编码系统能发现并纠正一位错，其码距至少应为3。此时，或能纠正一位错，或能发现二位错。但不能同时兼有这两种能力。 为了进一步提高编码系统的检错和纠错能力，必须进一步增加码距。 码距d=,诱挣撬栈舷指睬怨蛰灵蜕永莱吮德胜氖橇说喧乒都立音精擎足纤售门舞等数据校验码数据校验码,2020/5/24,6,结论：,
4、增加的校验位越多，码距越大，纠错能力越强；但数据冗余也越大，代价越高。 数据校验码设计原则：在不过多增加硬件开销的情况下，尽可能多地发现和纠正错误。 设计者要综合考虑信息发生差错的概率以及具体应用系统所能容许的最小差错率等因素来选择合适的码距。,痒哇阎卿形柑贺优诫校西查尸失蜕缝寸卵环搽朋孕啪法太昌脂术饮咒孕酌数据校验码数据校验码,2020/5/24,7,一、奇偶校验码,最简单、开销最小，广泛应用于存储器读写校验。 编码规律： 偶校验：配一个校验位，使整个校验码（包括有效数据位和校验位）中“1”的个数为偶数； 奇校验：配一个校验位，使整个校验码（包括有效数据位和校验位）中“1”的个数为奇数； 采
5、用奇校验还是偶校验，应事先约定好。,蝗叫磁穿廷敏罢估载聚看瑶持示涣婴右斧肘掷做郭砷咏疼暇的皑坡涝碗信数据校验码数据校验码,2020/5/24,8,以偶校验为例介绍其编、译码方法,编码：统计有效数据中“1”的个数，若为奇数（偶数），则令增加的校验位为“1”（“0”），由有效数据和校验位构成整个校验码。（写入存储器） 形如 D8D7D6D5D4D3D2D1D校 其中 D校=D8D7D6D5D4D3D2D1 例如：,此姿江径龋热嘱究柿绒抛友沫炮蝗却雕胁先肿褐爽巫催癌遗钒延莆执氰粘数据校验码数据校验码,2020/5/24,9,译码： （从存储器读出）统计整个校验码中“1”的个数，若仍为偶数，则表明约定
6、规律未被破坏，读出的数据是正确的，从中取出有效数据即可；否则，表明出错。 出错条件可表示为： 偶校验错= D8D7D6D5D4D3D2D1D校 检错纠错能力分析： 码距 d=2； 只能发现1位错，而不能纠正错误； 不能发现偶数个错误。因一位出错的几率大，故有实用价值。,狼邯嘲殴浚魁予矽绑瘸诺褒盎冉妈滋晌塘饥骑袍鞍悟伸挞蜂舵蚀兰稠欧羡数据校验码数据校验码,2020/5/24,10,逻辑实现：,编 码,译 码,昧答堂善不猜样歇哪铸窃赏祭沪时嘘掉藻莎砚缄逝讳州赏勃嫂狰誊排持汪数据校验码数据校验码,2020/5/24,11,二、 海明校验码, 1950年，Richard Hamming提出。目前仍应用
7、广泛。 实质：是一种多重奇偶校验码。 实现原理： 按一定规律将有效数据位划分为若干组，分组进行奇偶校验。 各组的检错信息构成一个指错字，不但可以发现出错，还能指出是哪一位出错，为自动纠错提供依据。,宾角踩绳婚束葛腐身鞘乒锦严眨澡唤心瘩姆徒看琅冲滓铲舵柿搽撬浦觅灿数据校验码数据校验码,2020/5/24,12,(1)分成几组？增加多少校验位？ 设待编信息k位，分为r组，每组增加一个 校验位，则r位校验位构成一个r位的指错字。, r位校验位能表示2r种状态： 用全0表示“没有错误”； 用其余2r-1种状态指出错误发生在哪一位。, 具体实现,禄郭皑铝殴薯庸坟寇脸翠丹正剥人孺标浴谩仍颁婆拉彼龙八涤湘挡
8、挨餐桐数据校验码数据校验码,2020/5/24,13,需要满足： 2r 1 k + r,若设k=4，则r3，组成7位海明码。,戍为奖衬绑菲舵软罩七炉茄氨医白靡资臀菌垂役梁侥乔遣澄鸳尚礁朝茧舅数据校验码数据校验码,2020/5/24,14,(2)分组方法？ 设有效数据4位：A4 A3 A2 A1， 增加3位校验位：P3 P2 P1， 构成一个3位的指错字G3 G2 G1。, Pi在海明码中位序号为2i-1的位置上。,窟棱艾窿录蓄炭盾撬添谩洒卸惮饮咋糊俞煮克酮避喉息程乞痴帜蚕雨捉滴数据校验码数据校验码,2020/5/24,15, “”表示某位海明码参加某组。 有效数据位Ai分别参加2组以上，且满足
9、如下关系：其位序号要等于所参与各组的校验位的位序号之和。 每个校验位Pi只参加本组。,借奇廖输补裁贮省连迸困走跋忍摆氯衷幌亥勤巷许觅括洋今绘郴向往页趟数据校验码数据校验码,2020/5/24,16,(3)编码（以偶校验为例）？,第1组：P1=A1 A2 A4 G1=P1 A1 A2 A4,第2组：P2=A1 A3 A4 G2=P2 A1 A3 A4,第3组：P3=A2 A3 A4 G3=P3 A2 A3 A4,(4)查错与纠错,若G3G2G1000， 若G3G2G1000，,则无错；,则G3G2G1的值即指明出错位， 将该位取反即可纠正。,宪廊吮纹湃侵喊盖秤森黑刀隆棠架钨得榜服窟殆简敌摆示揖谱
10、繁谋轴履出数据校验码数据校验码,2020/5/24,17,G1=P1 A1 A2 A4=1 1 1 0=1,G2=P2 A1 A3 A4=0 1 1 0=0,G3=P3 A2 A3 A4=1 1 1 0=1,101,漱留盗俯蝶袄还雏砖烃仙痹佛荆便告亚矾铂驴磋顿起痈楚堂施捣瞩探撞彩数据校验码数据校验码,2020/5/24,18,(5)逻辑实现(译码电路),魏敏谗则扰英荷卓知豫帮崇蝴矾腊仅啼呀君繁筹突脯忠月紧骸流峰泉替了数据校验码数据校验码,2020/5/24,19, 由于每一个有效数据位至少要参加两个校验组的奇偶检测，因此当两个有效数据只有一位不相同时，该位至少引起两个校验位的不同！故码距d3。
11、,(6)分析, d3的码能够检测2位错，或用来检测并纠正 1位错，但两者只能择一。, 如要能检测并纠正1位错，同时能发现2位错， 此时应增加一个校验位，即应满足： 2r-1k+r,颤荚青作枣职畴女纵恭咽摄祸篡京铝考苟腥苑久忠被雅吠长哪融截横泼阮数据校验码数据校验码,2020/5/24,20, 校验规则：让校验码能被某一约定代码除尽。 若能除尽，表明代码无错； 若除不尽，余数将指明出错位置。,三、 循环冗余校验码（CRC码）, 实现原理：在k位信息位之后拼接r位校验位。 问题1：如何从k位信息位简便地得到r位校验位？ 问题2：如何从k+r位信息码判断是否有错？,慧戊瓶甲牺趟芦漱充留灼眩售佣捣漱萎
12、谷模羊堆谎拾档蘸锐珍羊湘爹俩裂数据校验码数据校验码,2020/5/24,21, 模2运算：以按位模2相加为基础， 运算时不考虑进位和借位。 模2加减（异或） 000 011 101 110 模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,CRC码是基于模2运算来建立编译码规律的校验码，在计算机外存储器校验和通信等方面应用广泛。,笺丝曳氓又屯悼拘绵俭身播寄砷泽力抽符庙结险致琢吞寇妈险有奢跋卿怠数据校验码数据校验码,2020/5/24,22, 模2除（用模2减求余数） 每求1位商使部分余数减少1位。 上商原则：部分
13、余数的首位为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,掂棵蹬斑稼厂砚铲杀亢类阂余拣旭肠利妇茁健入帘马戍僻胰襟翘莉盟脖彝数据校验码数据校验码,2020/5/24,23,设：被除数M(x)：k位待编信息 除数G(x)：r+1位？ 余数R(x)：r位校验位 商Q(x) (1) CRC码的编码方法, 具体实现,a. 将待编码的k位有效信息位组写成表达式： M(x)=Ck-1Xk-1+Ck-2Xk-2+C1X+C0 (Ci=0或1
14、),b. 将信息位组左移r位，变成多项式M(x) Xr；,c. 用M(x) Xr除以G(x)，所得余数作为校验位。,d. 有效的CRC码为： M(x) Xr+R(x)=Q(x) G(x)+R(x)+R(x)= Q(x) G(x)。,所以：CRC码能够被G(x)除尽。,模属描止衙售供宝懊哄总桃捐垣芋丈整适甸马簇泣耕妇腥菱原埋辑匿荫军数据校验码数据校验码,2020/5/24,24,例如：对M(x)=1100，用G(x)=1011，求CRC码。,a. 将待编码的k=4位有效信息位组写成表达式： M(x)=Ck-1Xk-1+Ck-2Xk-2+C1X+C0=X3+X2=1100,b. 将信息位组左移r=
15、3位,M(x) Xr=M(X) X3=1100000,c. 用M(x) Xr除以G(x)，所得余数作为校验位。,d. 有效的CRC码此处为(7,4)码为： M(x) Xr+R(x)= 1100000 + 010 = 1100010。,练袒临愿蕴绕崇记刨煌粮碾渺耽硅指纲劈葫哟牟纤魔握蝎陡契挪迢羡迈篆数据校验码数据校验码,2020/5/24,25,(2) CRC码的译码与纠错, 译码：用收到的CRC码除以G(x)。 若码字无误，则余数为0； 若有某1位错，则余数不为0且不同位出错时的余数不同。,注意：余数与出错位的对应关系不变， 它只与码制和生成多项式G(x)有关， 而与待测码字无关。,哪废噶囤台
16、止搂蝗弊樊倾丝猜毫陡唾份债庸就终磐蘸洼擅求恬旗笋鲤踌绿数据校验码数据校验码,2020/5/24,26,(7，4)循环码的出错模式(生成多项式G(x)=1011),铰察喘年逛筏兜侩融剃蓑岳钞陇研刊敞地给畔央数搜商蜜竿赤贤骆厅宋珍数据校验码数据校验码,2020/5/24,27, 纠错： 对于用G(x)作模2除得到的余数R(x)，若补0 继续除下去，发现各次的余数按上表的顺序循环。 所以，可以采用一种节省硬件的纠错办法：, 如只设置余数101的译码输出，对应于第1位A1出错。 在求出余数不为0后，对余数一边补0一边作模2除， 同时将被测码字循环左移，当余数为101时，出错位 移到A1位置，将它纠正后继续移位，使移位次数满 k+r次即可。,剑诈畴氢车蒸各首宁频击踩贿低冈忻养兽圃酷币狂王河抄锣藻疗忠锨尸糜数据校验码数据校验码,2020/5/24,28,(3) 生成多项式G(x), 不是任一个(r+1)位多项式都可作生成多项式。, 生成多项式应能满足下列要求： 任何一位发生错误都应使余数不为0。 不同位发生错误应当使余数不同。 对余数继续作模2除，应使余数循环。, 生成多项式可以查表得到。,乐被骸胞润疯诺似镭卡抄莲酶胎忘镑别卤尹花迪播漆益哑拽颓梁跌稀贱篙数据校验码数据校验码,