计算机组成原理中的三种校验方式课件.ppt
a,1,计算机中的数据校验方法,采用冗余校验方法：即在基本的有效数据外，再扩充部分 位，增加部分（冗余部分）被称为校验位。将校验位与数据位一起按某种规则编码，写入存储器或向外发送。当从存储器读出或 接收到外部传入的代码时，再按相应的规则 进行判读。若约定的规则被破坏，则表示出 现错误。根据错误的特征进行修正恢复。,a,2,几个名词概念：码字：由若干代码组成的一个字。如8421码中6（0110），7（0111）码距：一种码制中任意两个码字间的最小距离。距离：两个码字之间不同的代码个数。8421码中，最小的码字间的距离为1，如0000和 0001、0010和0011等；最大码字间的距离为4，如0111和1000。所以8421码制的码距为1。码距为1码制，即不能查错也不能纠错。码距越大的码制，查错、纠错能力越强。,a,3,1 奇偶校验法,奇偶校验法是计算机中广泛采用的检查传输数据准确性的方法。奇偶校验法的原理是：在每组数据信息上附加一个校验位，校验位的取值（0或1）取决于这组信息中1的个数和校验方式（奇或偶校验）。如果采用奇校验，则这组数据加上校验码位后数据中1的个数应为奇数个。奇校验位形成公式:C=X0 X1 Xn-1 如果采用偶校验，则这组数据加上校验码位后数据中1的个数应为偶数个。偶校验位形成公式:C=X0 X1 Xn-1,a,4,在接收端校验检测：偶校验：P=C X0 X1 Xn-1奇校验：P=C X0 X1 Xn-1若P=0则无错或有偶数位错，若P=1则有奇数位错,a,5,例如：八位信息10101011中共有5个1，附加校验位后变为九位。若采用奇校验，则附加的校验位应取0值，保证1的个数为奇数个即 0 10101011；若采用偶校验则附加的校验位应取1值即 1 10101011。奇偶校验的特点：1、奇偶校验法可检出数据传送过程中奇数个数位出错的情况；2、实际中两位同时出错的概率极低，奇偶校验法简便可靠易行，但它只能发现错误，却不知错在何处，因而不能自动纠正。,a,6,码 能 力码距检错 纠错 1 0 02 1 03 2 或 14 2 加 15 2 加 26 3 加 27 3 加 3,为了使一个系统能检查和纠正一个差错，码间最小距离必须至少是“3”。最小距离为3时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。,码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。所以，选择码距要取决于特定系统的参数。,a,7,2 海明码校验方法,海明码是一种比较常用的纠错码，它实际上是一种多重奇偶校验码。其基本思想是将被检验码分成多个组，每组配备一个奇偶校验位完成该组的奇偶校验位的功能。当被校验码中某一位出错时，将会有相关的多个小组出现奇偶校验错，根据这些组的出错情况便可将错误定位到某一位上从而即可纠正过来。,a,8,强调指出：海明码校验方法以奇偶校验法为基础，其校验位不是一个而是一组。海明码校验方法能够检测出具体错误并纠正。海明码的最低目标是能纠正一位错，因此要求海明码的码距大于或等于3。,a,9,海明校验码是Richard Hamming于1950年提出的，目前仍广泛使用的一种编码方法。,1、原理（1）特点：能检测出两位同时出错、亦能检测出一位出错并能自动纠错。（2）实现原理：在k个数据位之外加上r个校验位，从而形成一个k十r位的新码字，当某一位出错后，就会引起相关的几个校验位的值发生变化，从而达到检错、纠错的目的。,a,10,2rk+r+1(3.18)(一位出错并纠错),数据位k与校验位r的对应关系：,a,11,2r-1k+r(3.19)(一位出错并纠错并发现两位错)码距为4,由3.19式计算可得,a,12,2、编码规则 若海明码的最高位号为m，最低位号为1，即：HmHm-1H2H1，则此海明码的编码规律：(1)校验位与数据位之和为m，每个校验位Pi在海明码中被分在位号2i-1的位置，其余各位为数据位，并按从低向高逐位依次排列的关系分配各数据位。(2)海明码的每一位码Hi(包括数据位和校验位本身)由多个校验位校验，其关系是被校验的每一位位号要等于校验它的各校验位的位号之和。这样安排的目的,是希望校验的结果能正确反映出出错位的位号。,a,13,1、纠查一位错的编码方法（以四个校验位进行说明）,四个校验位最多可以校验11位数据。设：D10D9D8D7D6D5D4D3D2D1D0为11个数据位，P4P3P2P1分别为四个校验码，则编码规则是：海明码的总位数H等于数据位与校验位之和；每个校验位Pi排放在2i-1的位置，如P4排放 在第24-1=8位，其余数据位依序排列。,a,14,即：H15 H14 H13 H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1D10 D9 D8 D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1海明码的每一位用多个校验位一起进行校验，被校验的位号等于校验它的各校验位位号和；各校验位的值为它参与校验的数据位的异或。,a,15,海明码校验表,P4,P3,P2,8,4,2(14=8+4+2),H14 D9,P4,P3,P1,8,4,1(13=8+4+1),H13 D8,P4,P3,8,4(12=8+4),H12 D7,P4,P2,P1,8,2,1(11=8+2+1),H11 D6,P4,P2,8,2(10=8+2),H10 D5,P4,P1,8,1(8=8+1),H9 D4,P4,8,H8 P4,4,2,1(7=4+2+1)P3,P2,P1,H7 D3,P3,P2,4,2(6=4+2),H6 D2,P3,P1,4,1(5=4+1),H5 D1,P4,P3,P2,P1,8,4,2,1(15=8+4+2+1),H15 D10,P3,4,H4 P3,P2 P1,2,1(3=2+1),H3 D0,P2,2,H2 P2,P1,1,H1 P1,参与的校验位,参与校验的校验位位号,海明码位号,a,16,各校验位形成公式：P1=D0D1D3D4D6D8D10(1)P2=D0D2D3D5D6D9D10(2)P3=D1D2D3D7D8D9D10(3)P4=D4D5D6D7D8D9D10(4)按上述方式Pi的取值是采用偶校验时的取值，当采用奇校验时，Pi则取反。这样Pi连同数据位一起形成了海明码的各位。,用海名位号改写P4P1：,P1=H3H5H7H9H11 H13 H15P2=H3H6H7H10H11 H14 H15P3=H5H6H7H12 H13 H14 H15P4=H9H10H11H12H13 H14 H15,a,17,2、检查纠错（以四个校验位进行说明）,海明码数据传送到接收方后，再将各校验位的值与它所参与校验的数据位的异或结果进行异或运算。运算结果称为校验和。校验和共有四个。对偶校验来说，如果校验和不为零则传输过程中间有错误。而错误的具体位置则由四个校验和依序排列后直接指明。如果四个校验和 S4S3S2S1 依序排列后等于(1001)2=(9)10 时，就表明海明码的第九位也就是D4发生了错误，此时只要将D4取反，也就纠正了错误。,a,18,校验和Si的表达式：S1=D0D1D3D4D6D8D10 P1 S2=D0D2D3D5D6D9D10 P2 S3=D1D2D3D7D8D9D10 P3 S4=D4D5D6D7D8D9D10 P4,用海名位号改写S4S1：,S1=H1 H3H5H7H9H11 S2=H2 H3H6H7H10H11 S3=H4 H5H6H7H12S4=H8 H9H10H11H12,a,19,当采用偶校验方式其传送数据正确时，校验和 S1 S4的值分别都为0；当采用奇校验方式其传送数据正确时，校验和 S1 S4的值分别都为1。当不为上述值时，传送就发生了错误。,a,20,解：已知D10D9D8D7D6D5D4D3D2D1D0=10110100110 由于被校验位的位号等于校验它的各校验位位号之和以 及各校验位的取值等于它参与校验的数据位取值的异或。所 以校验位的取值以及所求海明码为：P1=D0D1 D3 D4 D6 D8 D10=1 P2=D0 D2 D3 D5 D6 D9 D10=1 P3=D1 D2 D3 D7 D8 D9 D10=1 P4=D4 D5 D6 D7 D8 D9 D10=0 D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1=101101000111011 传送正确时校验和的值为0，如果不等于0，则是几就是 第几位出错，是7则是第7位D3出错，此时将其取反即可纠正 错误。,例题：采用4位校验位、偶校验方式，写出10110100110的海明码。,a,21,例4.5 按配奇原则配置1100101 的汉明码。解：根据1100101，得n=7。根据2kn+k+1，可求出需增添k=4 位检测位，各位的安排如下：二进制序号 1 2 3 4 5 6 7 8 9 10 11 海明码 C1 C2 1 C4 1 0 0 C8 1 0 1按配奇原则配置，则C1=35 7 911=1C2=3 6 71011=1C4=5 6 7=0C8=91011=1故新配置的汗明码为11101001101。,a,22,例4.4 已知接收到的海明码为0110101（按配偶原则配置），试问欲传送的信息是什么？解：由于要求出欲传送的信息，必须是正确的信息，因此不能简单地从接收到的7 位海明码中去掉C1、C2、C4 三位检测位来求得。首先应该判断收到的信息是否出错。纠错过程如下：s1=1357=1s2=2367=1s3=4567=0所以，s3s2s1=011，第3 位出错，可纠正为0100101，故欲传送的信息为0101。,a,23,C1 C2.C K r 1 r 2 r i,3.7.3 循环冗余校验方法(CRC码),循环冗余校验方式：通过某种数学公式建立信息位和校验位之间的约定关系能够校验传送信息的对错，并且能自动修正错误。广泛用于通信和磁介存储器中。CRC编码格式是在k位信息后加r位检验码。N N-1 2 1 信息位（k位）校验位（r位）,a,24,1、CRC码的编码方法,CRC整个编码长度为 n=k+r 位，故CRC码又叫（n，k）码。其编码方法如下：假设被传送的k位二进制信息位用C(x)表示,系统选定的生成多项式用G(X)表示，将C(x)左移 G(X)的最高次幂(即等于需要添加的校验位的位数r)，写作 C(x)2 r 然后将其C(x)2 r除以生成多项式G(x)，所得商用Q(x)表示，余数用R(x)表示。则：两边同时乘以G(x)并左移 R(x)得到：,a,25,故有：上式中，等式左边即为所求的n位CRC码，其中余数表达式R(x)就是校验位(r位)。且等式两边都是G(x)的倍数。发送信息时将等式左边生成的n位CRC码送给对方。当接收方接到n位编码后，同样除以G(x)，如果传输正确则余数为0，否则则可以根据余数的数值确定是哪位数据出错。,由于CRC编码采用的加、减法是按位加减法，即不考虑进位与借位，运算规则为：00=0，01=1，10=1，11=0,模2加,a,26,例：有一个（7,4）码（即CRC码为7位，信息码为4位），已确定生成多项式为：G（X）=X3+X+1=1011被传输的信息C(x)=1001，求C(x)的CRC码。,解：C（x）左移 r=nk=3 位 即：将上式模2采用除法 除以给定的 G(x)=1011：1001000/1011=1010+110/1011 得到余数表达式：R(x)=110 所求CRC码,a,27,a,28,2、CRC码的查错表,收到的CRC码除以约定的生成多项式G(x)，如果余数为0则传输无误，否则传输错误，根据所得余数值就可找出错误并取反纠正。上表详细说明了CRC码1001110在传送时某一位出错后的判断与纠正方法 C(X)=1001、G(x)=1011。,a,29,3、生成多项式G（x）的确定,G(x)是一个约定的除数，用来产生校验码。从检错和纠错的要求出发，它并不是随意选择的，它应满足下列要求：任何一位发生错误都应使余数不为0；不同位发生错误应使余数不同；余数继续模2 除，应使余数循环。在计算机和通信系统中，广泛使用下述两种标准：国际电报电话咨询委员会CCITT推荐 G(X)=X16+X15+X2+1 美国电气和电子工程师协会IEEE推荐 G(X)=X16+X12+X5+1,a,30,4、CRC的译码与纠错 将收到的循环校验码用约定的生成多项式G（x）去除，如果码字无误则余数应为0,如有某一位出错，则余数不为0,不同位数出错余数不同。通过上例 求出其出错模式如表 3.10所示、更换不同的待测码字可以证明:余数与出错位的对应关系是不变的，只与码制和生成多项式有关，因此表 3.10给出的关系可作为（7,4）码的判别依据，对于其他码制或选用其他生成多项式，出错模式将发生变化。,a,31,如果循环码有一位出错，用G（x）作模2除将得到一个不为0的余数，如果对余数补1个0继续除下去我们将发现一个现象：各次余数将按表3.10顺序循环，例如第一位出错，余数将为001，补0后再除，第二次余数为010，以后依次为100，011,.，反复循环，这是一个有价值的特点。如果我们在求出余数不为0后，一边对余数补0继续做模2除，同时让被检错的校验码字循环左移。表 3.10说明当出现余数（101）时，出错位也移到A7位置、对通过异或门将它纠正后在下一次移位时送回A1。继续移满一个循环（对74码共移七次），就得到一个纠正后的码字。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件、当位数增多时循环码校验能有效地降低硬件代价。,a,32,例（7，4）CRC码中，G(X)=1011，通过余数循环添0法获得余数与出错位对应关系,a,33,【例】对图10的CRC码（G(x)1011，C(x)1010），若接收端收到的码字为1010111，用G(x)1011做模2除得到一个不为0的余数100，说明传输有错。将此余数继续补0用G(x)1011作模2除，同时让码字循环左移1010111。做了4次后，得到余数为101，这时码字也循环左移4位，变成1111010。说明出错位已移到最高位A7，将最高位1取反后变成0111010。再将它循环左移3位，补足7次，出错位回到A3位，就成为一个正确的码字1010011。,
