计算机组成原理 计算机学院 2.9 数据校验码 l数据校验码是一种常用的带有发现错误或自动改错能力的 数据编码方法 l实现原理是在数据位中加入一些冗余码，使合法数据编码 出现错误时，就成为非法编码这样，就可以通过检测编 码的合法性来达到发现错误的目的合理地安排非法编码 数量和编码规则，就可以提高发现错误的能力，或达到自 动改正错误的目的 1 计算机组成原理 计算机学院 l码距是根据任意两个合法码之间至少有几个二进制位不 相同而确定的，仅有一位不同，其码距为1例如：用四 位二进制表示16种状态，则16种编码都用到了，此时码 距为1，就是说，任何一个状态的四位码中的一位或几位 出错，就变成另一个合法码，此时无查错能力若用四 个二进制位表示8种状态，就可以只用其中的8种编码， 而把另8种编码作为非法编码，此时码距为2 l常用的数据校验码有：奇偶校验码、海明校验码和循环 冗余校验码（CRC码） 2.9 数据校验码 2 计算机组成原理 计算机学院 2.9.1 奇偶校验码 l通常是为一个字节补充一个二进制位，称为校验 位，用设置校验位的值为0或1，使字节的8位和 该校验位含有1的个数为奇数或偶数。
在使用奇 数个1的方案进行校验时，称为奇校验，反之， 称为偶校验 3 计算机组成原理 计算机学院 数 据奇校验的编码偶校验的编码 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 00 0 1 0 1 0 1 0 01 0 1 0 1 0 1 0 0 0 1 1 1 0 1 1 11 0 1 1 1 0 1 1 10 0 1 1 1 0 1 1 1 2.9.1 奇偶校验码 4 计算机组成原理 计算机学院 奇偶校验位的形成及校验线路 5 计算机组成原理 计算机学院 2.9.2 海明校验码 l一、要解决的3个问题： l（1）海明校验码工作原理？ l（2）如何形成海明校验码？ l（3）已知海明校验码，如何对其进行校验？ 6 计算机组成原理 计算机学院 二、海明校验码的工作原理 l在数据中加入几个校验位，并把数据的每一个二 进制位分配在几个奇偶校验组中当某一位出错 后，就会引起有关的几个校验组的值发生变化， 这不但可以发现错误，还能指出是哪一位出错， 为自动纠错提供了依据 7 计算机组成原理 计算机学院 三、海明校验码的形成 l（1）数据位和校验位的关系 l假设校验位的个数为r，则它能表示2r个信息，用其中的一 个信息指出“没有错误”，其余的2r-1个信息指出错误发 生在哪一位。
然而错误也可能发生在校验位，因此只有 k=2r-1-r个信息能用于纠正被传送数据的位数，也就是说 要满足关系： 2r>=k+r+1 (发现一位错) 2r-1>=k+r (发现与自动校正一位错，并发现两位错） 8 计算机组成原理 计算机学院 数据位k与校验位r的对应关系 k值最小的r值 1～4 5～11 12～26 27～57 58～120 4 5 6 7 8 9 计算机组成原理 计算机学院 （2）海明码的编码规律 l若海明码的最高位号为m，最低位号为1， l即HmHm-1…H2H1，则海明码的编码规律通常是： la.校验位与数据位之和为m，每个校验位Pi在海明码中被 分在 2i-1的位置，其余各位为数据位，并按从低向高逐 位依次排列的关系分配各数据位 lb.海明码的每一位Hi（包含数据位和校验位本身）由多 个校验位校验，其关系是被校验的每一位位号要等于校 验它的各校验位的位号之和这样安排的目的，是希望 校验的结果能正确反映出出错位的位号 10 计算机组成原理 计算机学院 l举例：按上述规律讨论一个字节的海明码每个字节由8 个二进制位组成，此处的k为8，按照数据位和校验位的 对应关系，r应为5，故海明码的总位数为13， l可表示为：H13H12H11…H3H2H1 l5个校验位P5～P1对应的海明码位号分别为：H13，H8，H4 ，H2，H1 lP5只能放在H13一位上，它已经是海明码的最高一位了， 其它4位满足Pi的位号等于2i-1的关系。
其余为数据位Di， 则有如下排列关系：P5D8D7D6D5P4D4D3D2P3D1P2P1 （2）海明码的编码规律 11 出错的海明码位号和校验位位号的关系 海明码 位 号 数据位/ 校验位 参与校验的 校验位位号 被校验位的海明码位号 =校验位位号之和 H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13 P1 P2 D1 P3 D2 D3 D4 P4 D5 D6 D7 D8 P5 1 2 1,2 4 1,4 2,4 1,2,4 8 1,8 2,8 1,2,8 4,8 13 1=1 2=2 3=1+2 4=4 5=1+4 6=2+4 7=1+2+4 8=8 9=1+8 10=2+8 11=1+2+8 12=4+8 13=13 12 计算机组成原理 计算机学院 l（3）P函数的形成(偶校验) lP1=D1⊕D2⊕D4⊕D5⊕D7 lP2=D1⊕D3⊕D4⊕D6⊕D7 lP3=D2⊕D3⊕D4⊕D8 lP4=D5⊕D6⊕D7⊕D8 lP5=D1⊕D2⊕D3⊕D4⊕D5⊕D6⊕D7⊕D8⊕P4⊕P3⊕P2⊕P1 l在这种安排中，每一位数据位，都至少出现3个Pi值的形 成关系中，当任一位数据码发生变化时，必将引起3个或4 个Pi值跟着变化，该海明码的码距为4。
三、海明校验码的形成 13 计算机组成原理 计算机学院 若有效信息为11010011，求其海明码 课堂练习 14 计算机组成原理 计算机学院 四、海明码的校验 海明码校验函数（S函数）及校验过程 lS1=P1⊕D1⊕D2⊕D4⊕D5⊕D7 lS2=P2⊕D1⊕D3⊕D4⊕D6⊕D7 lS3=P3⊕D2⊕D3⊕D4⊕D8 lS4=P4⊕D5⊕D6⊕D7⊕D8 lS5=D1⊕D2⊕D3⊕D4⊕D5⊕D6⊕D7⊕D8⊕P5⊕P4⊕P3⊕P2⊕P1 15 计算机组成原理 计算机学院 (12,8)分组码海明校验线路 16 计算机组成原理 计算机学院 判1位/2位错的附加线路 17 计算机组成原理 计算机学院 2.9.3 循环冗余校验（CRC）码(自学) lCRC码可以发现并纠正信息在存储或传送过程中 连续出现的多位错误，因此在磁介质存储和计算 机之间通讯方面得到广泛应用 lCRC码一般是在k位信息码之后拼接r位校验码 应用CRC码的关键是如何从k位信息位简便地得到 r位校验位（编码），以及如何从k+r位信息码判 断是否出错 18 计算机组成原理 计算机学院 一、CRC码的编码方法 l1.模2运算方法 l模2加、减、乘、除运算法则介绍。
l2.CRC码的编码方法 l假设待编码的k位有效信息位组表达为多项式M(x) lM(x)=Ck-1xk-1+Ck-2xk-2+…+Cixi+…+C1x+C0 l式中Ci为0或1，若将信息位组左移r位，则可表示 为多项式M(x)xr这样就可以空出r位，以便拼 接r位校验位 19 计算机组成原理 计算机学院 lCRC码是用多项式M(x)xr除以生成多项式G(x)（产生校 验码的多项式）所得余数作为校验位为了得到r位余数 （校验位），G(x)必须是r+1位 l设所得余数表达式为R(x)，商为Q(x)将余数拼接在信息 位组左移r位空出的r位上，就构成这个有效信息的CRC码 这个CRC 码可用多项式表达为： l M(x)xr+R(x)=[Q(x)G(x)+R(x)]+R(x) l =[Q(x)G(x)]+[R(x)+R(x)]=Q(x)G(x) l因此所得CRC码可被G(x)表示的数码除尽 一、CRC码的编码方法 20 计算机组成原理 计算机学院 l例：对4位有效信息（1100），求其循环校验（CRC）码 l选择生成多项式（1011） lM(x)=x3+x2=1100 (k=4) lM(x)x3=x6+x5=1100000 (左移r=3位） lG(x)=x3+x+1=1011 (r+1=4位） l(M(x)x3)/G(x)=1100000/1011=1110+010/1011 (模2 除） l则R(x)=010 (模2除后的 余数) lM(x)x3+R(x)=1100000+010=1100010 (模2加） l将编好的循环校验码称为（7，4）码，即n=7，k=4。
一、CRC码的编码方法 21 计算机组成原理 计算机学院 二、CRC码的译码与纠错 l将收到的循环校验码用约定的生成多项式G(x)去 除，如果码字无误则余数应为0，如果某一位出 错，则余数不为0，不同位数出错余数不同，即 用余数表示出错位例子中生成的CRC码的出错 模式如下表所示 l如果循环校验码有一位出错，用G(x)做模2除将 得到一个不为0的余数，如果对余数补1个0继续 除下去，各次余数将按上表顺序循环 22 计算机组成原理 计算机学院 A1 A2 A3 A4 A5 A6 A7 余 数 出 错 位 正确 1 1 0 0 0 1 00 0 0无 错误 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 1 1 1 1 0 1 7 6 5 4 3 2 1 二、CRC码的译码与纠错 23 计算机组成原理 计算机学院 三、关于生成多项式 l并不是任何一个（r+1)位多项式都可以作为生成 多项式的，从检错及纠错的要求出发，生成多项 式应能满足下列要求： l（1）任何一位发生错误都应使余数不为0； l（2）不同位发生错误应当使余数不同； l（3）对余数继续作模2除，应使余数循环。
24 计算机组成原理 计算机学院 本节作业 lP151-4.17 25 。