《计算机组成原理中的三种校验方式》由会员分享，可在线阅读，更多相关《计算机组成原理中的三种校验方式（33页珍藏版）》请在金锄头文库上搜索。
1、计算机中的数据校验方法采用冗余校验方法：即在基本的有效数据外，再扩充部分 位，增加部分（冗余部分）被称为校验位。将校验位与数据位一起按某种规则编码，写入存储器或向外发送。当从存储器读出或接收到外部传入的代码时，再按相应的规则进行判读。若约定的规则被破坏，则表示出现错误。根据错误的特征进行修正恢复。几个名词概念：码字：由若干代码组成的一个字。如8421码中6（0110），7（0111）码距：一种码制中任意两个码字间的最小距离。距离：两个码字之间不同的代码个数。8421码中，最小的码字间的距离为1，如0000和0001、0010和0011等；最大码字间的距离为4，如0111和1000。所以8421
2、码制的码距为1。码距为1码制，即不能查错也不能纠错。码距越大的码制，查错、纠错能力越强。1 奇偶校验法奇偶校验法是计算机中广泛采用的检查传输数据准 确性的方法。奇偶校验法的原理是：在每组数据信息上附加一个校验位，校验位的取值 （0或1）取决于这组信息中1的个数和校验方式（奇或 偶校验）。如果采用奇校验，则这组数据加上校验码位后数据 中1的个数应为奇数个。奇校验位形成公式: C =X0 X1 Xn-1如果采用偶校验，则这组数据加上校验码位后数据 中1的个数应为偶数个。偶校验位形成公式: C =X0 X1 Xn-1 在接收端校验检测： 偶校验：P=C X0 X1 Xn-1 奇校验：P=C X0 X
3、1 Xn-1 若P=0则无错或有偶数位错，若P=1则有奇数位错例如：八位信息10101011中共有5个1，附 加校验位后变为九位。若采用奇校验，则附加的校验位应取0值， 保证1的个数为奇数个即 0 10101011 ；若采用偶校验则附加的校验位应取1值即 1 10101011 。奇偶校验的特点：1、奇偶校验法可检出数据传送过程中奇数个 数位出错的情况；2、实际中两位同时出错的概率极低，奇偶校验法简便可靠易行，但它只能发现错误，却不知错在何处，因而不能自动纠正。码 能 力 码距 检错 纠错 1 0 02 1 03 2 或 14 2 加 15 2 加 26 3 加 27 3 加 3为了使一个系统能
4、检查和纠正一个差错，码间最小距离必须至 少是“3”。最小距离为3时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。编码信息纠错和检错能力的 进一步提高需要进一步增加码字间的最小距离。 码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。所以，选择码距要取决于特定系统的参数。 2 海明码校验方法 海明码是一种比较常用的纠错码，它实际上是一种多重奇偶校验码。其基本思想是将被检验码分成多个组，每组配备一个奇偶校验位完成该组的奇偶校验位的功能。当被校验码中某一位出错时，将会有相关的多个小组出现奇偶校验错，根据这些组的出错情况便可将错误定位到某一位上从而即可纠正过来。 强调指出：海明
5、码校验方法以奇偶校验法为基础，其校验位不是一个而是一组。海明码校验方法能够检测出具体错误并纠正。 海明码的最低目标是能纠正一位错，因此要求海明码的码距大于或等于3。海明校验码是Richard Hamming于1950年提出的，目前仍 广泛使用的一种编码方法。1、原理 （1）特点：能检测出两位同时出错、亦能检测出一位出错并 能自动纠错。 （2）实现原理：在k个数据位之外加上r个校验位，从而形成一个k十r位 的新码字，当某一位出错后，就会引起相关的几个校验位 的值发生变化，从而达到检错、纠错的目的。kr(最小) 12 243 5114 12265 275762rk+r+1 (3.18)(一位出错并
6、纠错)数据位k与校验位r的对应关系： 2r-1k+r (3.19) (一位出错并纠错并发现两位错) 码距为4由3.19式计 算可得2、编码规则 若海明码的最高位号为m，最低位号为1，即： HmHm-1H2H1，则此海明码的编码规律：(1)校验位与数据位之和为m，每个校验位Pi在 海明码中被分在位号2i-1的位置，其余各位为数据位 ，并按从低向高逐位依次排列的关系分配各数据位 。(2)海明码的每一位码Hi(包括数据位和校验位 本身)由多个校验位校验，其关系是被校验的每一位 位号要等于校验它的各校验位的位号之和。这样安 排的目的,是希望校验的结果能正确反映出出错位的 位号。1、纠查一位错的编码方法
7、（以四个校验位进行说明）四个校验位最多可以校验11位数据。设：D10D9D8D7D6D5D4D3D2D1D0为11个数据位，P4P3P2P1分别为四个校验码，则编码规则是： 海明码的总位数H等于数据位与校验位之和； 每个校验位Pi排放在2i-1的位置，如P4排放在第24-1=8位，其余数据位依序排列。即：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海明码的每一位用多个校验位一起进行校验，被校验的位号等于校验它的各校验位位号和；各校验位的值为它参与校验
8、的数据位的异或。海明码校验表P4,P3,P2 8,4,2 (14=8+4+2) H14 D9P4,P3,P1 8,4,1 (13=8+4+1) H13 D8P4,P3 8,4 (12=8+4) H12 D7P4,P2,P1 8,2,1 (11=8+2+1) H11 D6P4,P2 8,2 (10=8+2) H10 D5P4,P1 8,1 (8=8+1) H9 D4P4 8 H8 P44,2,1 (7=4+2+1) P3,P2,P1 H7 D3P3,P2 4,2 (6=4+2) H6 D2P3,P1 4,1 (5=4+1) H5 D1P4,P3,P2,P1 8,4,2,1 (15=8+4+2+1
9、) H15 D10P3 4 H4 P3P2 P1 2,1 (3=2+1) H3 D0P2 2 H2 P2 P1 1 H1 P1参与的校验位参与校验的校验位位号海明码位号 各校验位形成公式：P1=D0D1D3D4D6D8D10 (1) P2 =D0D2D3D5D6D9D10 (2)P3=D1D2D3D7D8D9D10 (3)P4=D4D5D6D7D8D9D10 (4)按上述方式Pi的取值是采用偶校验时的取值，当采用奇校验 时，Pi则取反。这样Pi连同数据位一起形成了海明码的各位。用海名位号改写P4P1：P1= H3H5H7H9H11 H13 H15 P2= H3H6H7H10H11 H14 H1
10、5 P3= H5H6H7H12 H13 H14 H15 P4= H9H10H11H12H13 H14 H152、检查纠错（以四个校验位进行说明）海明码数据传送到接收方后，再将各校验 位的值与它所参与校验的数据位的异或结果进 行异或运算。 运算结果称为校验和。校验和共 有四个。对偶校验来说，如果校验和不为零则传输 过程中间有错误。而错误的具体位置则由四个 校验和依序排列后直接指明。如果四个校验和S4S3S2S1 依序排列后等于(1001)2=(9)10 时，就 表明海明码的第九位也就是D4发生了错误，此 时只要将D4取反，也就纠正了错误。 校验和Si的表达式：S1 =D0D1D3D4D6D8D1
11、0 P1 S2 =D0D2D3D5D6D9D10 P2 S3 =D1D2D3D7D8D9D10 P3S4 =D4D5D6D7D8D9D10 P4用海名位号改写S4S1：S1=H1 H3H5H7H9H11 S2=H2 H3H6H7H10H11 S3=H4 H5H6H7H12 S4=H8 H9H10H11H12当采用偶校验方式其传送数据正确时，校验和 S1 S4的值分别都为0；当采用奇校验方式其传送数据正确时，校验和 S1 S4的值分别都为1。当不为上述值时，传送就发生了错误。解：已知D10D9D8D7D6D5D4D3D2D1D0=10110100110由于被校验位的位号等于校验它的各校验位位号之
12、和以 及各校验位的取值等于它参与校验的数据位取值的异或。所以校验位的取值以及所求海明码为：P1=D0D1 D3 D4 D6 D8 D10 =1P2=D0 D2 D3 D5 D6 D9 D10=1P3=D1 D2 D3 D7 D8 D9 D10=1P4=D4 D5 D6 D7 D8 D9 D10=0D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1=101101000111011传送正确时校验和的值为0，如果不等于0，则是几就是第几位出错，是7则是第7位D3出错，此时将其取反即可纠正 错误。例题：采用4位校验位、偶校验方式， 写出10110100110的海明码。例4.5 按配奇原则配
13、置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=1 C2 = 3 6 71011=1 C4 =5 6 7 =0 C8 = 91011=1 故新配置的汗明码为11101001101。例4.4 已知接收到的海明码为0110101（按配偶原则 配置），试问欲传送的信息是什么？ 解： 由于要求出欲传送的信息，必须是正确的信息，因 此不能
14、简单地从接收到的7 位海明码中去 掉C1、C2、C4 三位检测位来求得。首先应该判断 收到的信息是否出错。纠错过程如下： s1=1357=1 s2=2367=1 s3=4567=0 所以，s3s2s1=011，第3 位出错，可纠正为 0100101，故欲传送的信息为0101。C1 C2 . C K r 1 r 2 r i 3.7.3 循环冗余校验方法(CRC码)循环冗余校验方式：通过某种数学公 式建立信息位和校验位之间的约定关系 能够校验传送信息的对错，并且能自动 修正错误。广泛用于通信和磁介存储器中 。 CRC编码格式是在k位信息后加r位检验码 。N N-1 2 1信息位（k位） 校验位（r位）1、CRC码的编码方法CRC整个编码长度为 n=k+r 位，故CRC码又叫（n ，k）码。其编码方法如下：假设被传送的k位二进制信
