《计算机组成与体系结构》赵姝、陈洁、段震、陈付龙、刘路路 第3章 运算方法与运算器.ppt

3.8.3 海明校验码 * (2)若海明码不仅能实现一位检错纠错,还能够实现两位检错。 此时，需要在校验位中用1位表示不出错/偶数位出错或奇数位出错,配合用剩下的r-1位的 个状态分别表示k 位数据位和r 位校验位中的哪位出错(一位错),因此有: 下表给出了此种方式下数据位k与校验位r的对应关系。 3.8.3 海明校验码 * k值 最小的r值 1~4 4 5~11 5 12~26 6 27~57 7 58~120 8 3.8.3 海明校验码 * 设数据位为D,共k位,记为Dk…D1; 校验位为P,共r 位,记为Pr…P1; 编码所得的海明码为H ,共m位,记为Hm …H1,显然有m=k+r,且位号1表示最低位。此海明码的编码规则通常是: (1)每个校验位Pi在海明码H中被分配在位号 的位置,H 中的空余位上放置数据位,并按从低向高的顺序逐位依次排列分配各数据位; (2)海明码的每一位码Hi(包括数据位和校验位)由多个校验位校验,其关系是被校验的每一位的位号等于校验该位的各校验位的位号之和,这样安排的目的是希望校验的结果能正确反映出出错位的位号。 3.8.3 海明校验码 * 例:K=8 　按式(3．19)求出r=5 　故海明码的总位数为13，可表示：　 H13H12H11...H3H2H1 P5只能放在H13一位上，它已经是海明码的最高位了，其他4位满足Pi的位号等于2i-1的关系。其余为数据位Di，则有如下排列关系： 位号 13 12 11 10 9 8 7 6 5 4 3 2 1 信息 P5 D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1 3.8.3 海明校验码 * 海明码 位 号 数据位/ 校验位 参与校验的 校验位位号 被校验位的海明码位号=校验位位号之和 H1 P1 1 1=1 H2 P2 2 2=2 H3 D1 1,2 3=1+2 H4 P3 4 4=4 H5 D2 1,4 5=1+4 H6 D3 2,4 6=2+4 H7 D4 1,2,4 7=1+2+4 H8 P4 8 8=8 H9 D5 1,8 9=1+8 H10 D6 2,8 10=2+8 H11 D7 1,2,8 11=1+2+8 H12 D8 4,8 12=4+8 H13 P5 13 13=13 3.8.3 海明校验码 * 校验位的编码规则(发送端): P1=D1⊕D2⊕D4⊕D5⊕D7 P2=D1⊕D3⊕D4⊕D6⊕D7 P3=D2⊕D3⊕D4⊕D8 P4=D5⊕D6⊕D7⊕D8 P5=D1⊕D2⊕D3⊕D4⊕D5⊕D6⊕D7⊕D8 ⊕P4⊕P3⊕P2⊕P1 3.8.3 海明校验码 * 译码规则（接受端）: Si=Pi ⊕形成Pi的编码规则 S1=P1 ⊕ D1⊕D2⊕D4⊕D5⊕D7 S2=P2 ⊕ D1⊕D3⊕D4⊕D6⊕D7 S3=P3 ⊕ D2⊕D3⊕D4⊕D8 S4=P4 ⊕ D5⊕D6⊕D7⊕D8 S5=P5 ⊕P4⊕P3⊕P2⊕P1⊕D1⊕D2⊕D3 ⊕D4 ⊕D5⊕D6⊕D7⊕D8 则校验得到的结果值S5～S1能反映13位海明码的出错情况。 任何偶数个数出错，S5一定为0，因此可区分两位出错或一位出错。 3.8.3 海明校验码 * 3.8.4 循环冗余校验码 * 循环冗余校验码(CyclicRedundancyCheck,CRC)是一种在待检验的数据位后添加若干位冗余位形成的校验码,可以发现并纠正信息串行读写、存储或传送过程中连续出现的一位、多位错误。 CRC码是在k 位数据位之后拼接r 位校验位得到的。 关键在于如何从k 位数据位简便的得到r 位校验位,以及接收方如何判断是否出错。 3.8.4 循环冗余校验码 * 1. 模2运算 模2运算是指以按位模2相加为基础的四则运算,运算时不考虑进位和借位。 (1)模2加减: 按位加,可用异或逻辑实现, 即 0±0=0,0±1=1,1±0=1,1±1=0。 (2)模2乘: 按模2加求部分积之和。 (3)模2除:按模2减求部分余数,不借位,每求一位商应使部分余数减少1位。 注意: 一是模2加与模2减的结果相同; 二是两个相同的数据进行模2加时,其和为0。 上商的原则:当部分余数的首位为1时,商1;