计算机组成原理中的三种校验方式课件.ppt

1、a1计算机中的数据校验方法 采用冗余校验方法：采用冗余校验方法： 即在基本的有效数据外，再扩充部分即在基本的有效数据外，再扩充部分 位，增加部分（冗余部分）被称为校验位。位，增加部分（冗余部分）被称为校验位。 将校验位与数据位一起按某种规则编码，将校验位与数据位一起按某种规则编码， 写入存储器或向外发送。当从存储器读出或写入存储器或向外发送。当从存储器读出或 接收到外部传入的代码时，再按相应的规则接收到外部传入的代码时，再按相应的规则 进行判读。若约定的规则被破坏，则表示出进行判读。若约定的规则被破坏，则表示出 现错误。根据错误的特征进行修正恢复。现错误。根据错误的特征进行修正恢复。a2几个名

2、词概念：几个名词概念：码字：码字：由若干代码组成的一个字。由若干代码组成的一个字。 如如8421码中码中6（0110），），7（0111）码距：码距：一种码制中任意两个码字间的最小距离。一种码制中任意两个码字间的最小距离。距离：距离：两个码字之间不同的代码个数。两个码字之间不同的代码个数。 8421码中，最小的码字间的距离为码中，最小的码字间的距离为1，如，如0000和和 0001、0010和和0011等；最大码字间的距离为等；最大码字间的距离为4， 如如0111和和1000。所以。所以8421码制的码距为码制的码距为1。码距为码距为1码制，即不能查错也不能纠错。码制，即不能查错也不能纠错。码

3、距越大的码制，查错、纠错能力越强。码距越大的码制，查错、纠错能力越强。a31 1 奇偶校验法奇偶校验法 奇偶校验法是计算机中广泛采用的检查传输数据准奇偶校验法是计算机中广泛采用的检查传输数据准确性的方法。奇偶校验法的原理是：确性的方法。奇偶校验法的原理是： 在每组数据信息上附加一个校验位，校验位的取值在每组数据信息上附加一个校验位，校验位的取值（0或或1）取决于这组信息中）取决于这组信息中1的个数和校验方式（奇或的个数和校验方式（奇或偶校验）。偶校验）。 如果采用奇校验，则这组数据加上校验码位后数据如果采用奇校验，则这组数据加上校验码位后数据中中1的个数应为奇数个。奇校验位形成公式的个数应为奇

4、数个。奇校验位形成公式: C =X0 X1 Xn-1 如果采用偶校验，则这组数据加上校验码位后数据如果采用偶校验，则这组数据加上校验码位后数据中中1的个数应为偶数个。偶校验位形成公式的个数应为偶数个。偶校验位形成公式: C =X0 X1 Xn-1a4 在接收端校验检测： 偶校验：P=C X0 X1 Xn-1 奇校验：奇校验：P=C X0 X1 Xn-1 若若P=0则无错或有偶数位错，若则无错或有偶数位错，若P=1则有奇数位错则有奇数位错a5 例如：八位信息例如：八位信息10101011中共有中共有5个个1，附加校验位后变为九位。附加校验位后变为九位。 若采用奇校验，则附加的校验位应取若采用奇校

5、验，则附加的校验位应取0值，值，保证保证1的个数为奇数个即的个数为奇数个即 0 10101011 ； 若采用偶校验则附加的校验位应取若采用偶校验则附加的校验位应取1值即值即 1 10101011 。 奇偶校验的特点：奇偶校验的特点： 1、奇偶校验法可检出数据传送过程中奇数个、奇偶校验法可检出数据传送过程中奇数个数位出错的情况；数位出错的情况； 2、实际中两位同时出错的概率极低，奇偶校、实际中两位同时出错的概率极低，奇偶校验法简便可靠易行，但它只能发现错误，却不知错验法简便可靠易行，但它只能发现错误，却不知错在何处，因而不能自动纠正。在何处，因而不能自动纠正。a6码 能 力码距码距 检错检错 纠

6、错纠错 1 0 02 1 03 2 或 14 2 加 15 2 加 26 3 加 27 3 加 3为了使一个系统能检查和纠正一个差错，码间最小距离必须至为了使一个系统能检查和纠正一个差错，码间最小距离必须至少是少是“3”。最小距离为。最小距离为3时，或能纠正一个错，或能检二个错，时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。编码信息纠错和检错能力的但不能同时纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。进一步提高需要进一步增加码字间的最小距离。 码距越大，纠错能力越强，但数据码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。冗余

7、也越大，即编码效率低了。所以，选择码距要取决于特定系统的参数。 a72 2 海明码校验方法海明码校验方法 海明码是一种比较常用的纠错码，它实际上是海明码是一种比较常用的纠错码，它实际上是一种多重奇偶校验码。其基本思想是将被检验一种多重奇偶校验码。其基本思想是将被检验码分成多个组，每组配备一个奇偶校验位完成码分成多个组，每组配备一个奇偶校验位完成该组的奇偶校验位的功能。当被校验码中某一该组的奇偶校验位的功能。当被校验码中某一位出错时，将会有相关的多个小组出现奇偶校位出错时，将会有相关的多个小组出现奇偶校验错，根据这些组的出错情况便可将错误定位验错，根据这些组的出错情况便可将错误定位到某一位上从而

8、即可纠正过来。到某一位上从而即可纠正过来。 a8强调指出：海明码校验方法以奇偶校验法为基础，强调指出：海明码校验方法以奇偶校验法为基础，其校验位不是一个而是一组。海明码校验方法能其校验位不是一个而是一组。海明码校验方法能够检测出具体错误并纠正。够检测出具体错误并纠正。 海明码的最低目标是能纠正一位错，因此要求海明码的最低目标是能纠正一位错，因此要求海明码的码距大于或等于海明码的码距大于或等于3。a9海明校验码是海明校验码是Richard HammingRichard Hamming于于19501950年提出的，目前仍年提出的，目前仍广泛使用的一种编码方法。广泛使用的一种编码方法。1 1、原理、

9、原理（1 1）特点：能检测出）特点：能检测出两位同时出错两位同时出错、亦能检测出一位出错并亦能检测出一位出错并能自动纠错。能自动纠错。（2 2）实现原理：）实现原理： 在在k k个数据位个数据位之外加上之外加上r r个校验位个校验位，从而形成一个，从而形成一个k k十十r r位位的的新码字新码字，当，当某一位出错某一位出错后，就会后，就会引起相关的几个校验位引起相关的几个校验位的值发生变化的值发生变化，从而达到检错、纠错的目的。，从而达到检错、纠错的目的。 k 位 （ 信 息 位 ） R 位 （ 校 验 位 ） a10kr(最小)12243511412265275762rk+r+1 (3.18

10、)(一位出错并纠错一位出错并纠错)数据位数据位k k与校验位与校验位r r的对应关系：的对应关系： a112r-1k+r (3.19) r (3.19) ( (一位出错并纠错并发现两位错一位出错并纠错并发现两位错) ) 码距为码距为4 4由由3.193.19式计式计算可得算可得a122 2、编码规则、编码规则 若海明码的最高位号为若海明码的最高位号为m m，最低位号为，最低位号为1 1，即：，即：H Hm mH Hm-1m-1HH2 2H H1 1，则此海明码的，则此海明码的编码规律编码规律： (1)(1)校验位与数据位之和为校验位与数据位之和为m m，每个校验位，每个校验位P Pi i在在海

11、明码中被分在位号海明码中被分在位号2 2i-1i-1的位置，其余各位为数据位的位置，其余各位为数据位，并按从低向高逐位依次排列的关系分配各数据位，并按从低向高逐位依次排列的关系分配各数据位。 (2)(2)海明码的每一位码海明码的每一位码H Hi i( (包括数据位和校验位包括数据位和校验位本身本身) )由多个校验位校验，其关系是被校验的每一位由多个校验位校验，其关系是被校验的每一位位号要等于校验它的位号要等于校验它的各校验位的位号之和各校验位的位号之和。这样安。这样安排的目的排的目的, ,是希望校验的结果能正确反映出出错位的是希望校验的结果能正确反映出出错位的位号位号。 a131 1、纠查一位

12、错的编码方法、纠查一位错的编码方法 （以四个校验位进行说明）（以四个校验位进行说明） 四个校验位最多可以校验四个校验位最多可以校验11位数据。设：位数据。设：D10D9D8D7D6D5D4D3D2D1D0为为11个数据位，个数据位，P4P3P2P1分别为四个校验码，则编码规则是：分别为四个校验码，则编码规则是： 海明码的总位数海明码的总位数H等于数据位与校验位之和；等于数据位与校验位之和； 每个校验位每个校验位Pi排放在排放在2i-1的位置，如的位置，如P4排放排放 在第在第24-1=8位，其余数据位依序排列。位，其余数据位依序排列。a14即：即： H15 H14 H13 H12 H11 H1

13、0 H9 H8 H7 H6 H5 H4 H3 H2 H1D10 D9 D8 D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1海明码的每一位用多个校验位一起进行校验，海明码的每一位用多个校验位一起进行校验，被校验的位号等于校验它的各校验位位号和；被校验的位号等于校验它的各校验位位号和；各校验位的值为它参与校验的数据位的异或。各校验位的值为它参与校验的数据位的异或。a15海明码校验表海明码校验表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,

14、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 P4 4,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) H15 D10P3 4 H4 P3P2 P1 2,1 (3=2+1) H3 D0P2 2 H2 P2 P1 1 H1 P1参与的校验位参与的校验位参与校验的校验位位号参与校验的校验位位号海明码位号海明码位号

15、a16 各校验位形成公式：各校验位形成公式： P1=D0 D1 D3 D4 D6 D8 D10 (1) P2 =D0 D2 D3 D5 D6 D9 D10 (2) P3=D1 D2 D3 D7 D8 D9 D10 (3) P4=D4 D5 D6 D7 D8 D9 D10 (4) 按上述方式按上述方式Pi的取值是采用偶校验时的取值，当采用的取值是采用偶校验时的取值，当采用奇校验奇校验时，时，Pi则取反。这样则取反。这样Pi连同数据位一起形成了海明码的各位。连同数据位一起形成了海明码的各位。 用海名位号改写用海名位号改写P P4 4P P1 1：P1= H3 H5 H7 H9 H11 H13 H1

16、5P2= H3 H6 H7 H10 H11 H14 H15P3= H5 H6 H7 H12 H13 H14 H15P4= H9 H10 H11 H12 H13 H14 H15a172 2、检查纠错（以四个校验位进行说明）、检查纠错（以四个校验位进行说明） 海明码数据传送到接收方后，再将各校验海明码数据传送到接收方后，再将各校验位的值与它所参与校验的数据位的异或结果进位的值与它所参与校验的数据位的异或结果进行异或运算。行异或运算。 运算结果称为校验和。校验和共运算结果称为校验和。校验和共有四个。有四个。 对偶校验来说，如果校验和不为零则传输对偶校验来说，如果校验和不为零则传输过程中间有错误。而错

17、误的具体位置则由四个过程中间有错误。而错误的具体位置则由四个校验和依序排列后直接指明。如果四个校验和校验和依序排列后直接指明。如果四个校验和 S4S3S2S1 依序排列后等于依序排列后等于(1001)2=(9)10 时，就时，就表明海明码的第九位也就是表明海明码的第九位也就是D4发生了错误，此发生了错误，此时只要将时只要将D4取反，也就纠正了错误。取反，也就纠正了错误。 a18 校验和校验和Si的表达式：的表达式： S1 =D0 D1 D3 D4 D6 D8 D10 P1 S2 =D0 D2 D3 D5 D6 D9 D10 P2 S3 =D1 D2 D3 D7 D8 D9 D10 P3 S4

18、=D4 D5 D6 D7 D8 D9 D10 P4 用海名位号改写用海名位号改写S S4 4S S1 1：S1=H1 H3 H5 H7 H9 H11 S2=H2 H3 H6 H7 H10 H11 S3=H4 H5 H6 H7 H12S4=H8 H9 H10 H11 H12a19当采用偶校验方式其传送数据正确时，校当采用偶校验方式其传送数据正确时，校验和验和 S1 S4的值分别都为的值分别都为0；当采用；当采用奇校验奇校验方式方式其传送数据正确时，校验和其传送数据正确时，校验和 S1 S4的的值分别都为值分别都为1。当不为上述值时，传送就发。当不为上述值时，传送就发生了错误。生了错误。a20解：

19、已知解：已知D10D9D8D7D6D5D4D3D2D1D0=10110100110 由于被校验位的位号等于校验它的各校验位位号之和以由于被校验位的位号等于校验它的各校验位位号之和以 及各校验位的取值等于它参与校验的数据位取值的异或。所及各校验位的取值等于它参与校验的数据位取值的异或。所 以校验位的取值以及所求海明码为：以校验位的取值以及所求海明码为： P1=D0 D1 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 D10D9D8D7D6D5D

20、4P4D3D2D1P3D0P2P1 =101101000111011 传送正确时校验和的值为传送正确时校验和的值为0 0，如果不等于，如果不等于0 0，则是几就是，则是几就是 第几位出错，是第几位出错，是7 7则是第则是第7 7位位D3出错，此时将其取反即可纠正出错，此时将其取反即可纠正 错误。错误。例题：采用例题：采用4 4位校验位、偶校验方式，位校验位、偶校验方式，写出写出1011010011010110100110的海明码。的海明码。a21例4.5 按配奇原则配置1100101 的汉明码。解：根据1100101，得n = 7。根据2kn + k + 1，可求出需增添k = 4 位检测位，

21、各位的安排如下：二进制序号 1 2 3 4 5 6 7 8 9 10 11 海明码 C1 C2 1 C4 1 0 0 C8 1 0 1按配奇原则配置，则C1 = 3 5 7 9 11=1C2 = 3 6 7 10 11=1C4 =5 6 7 =0C8 = 9 10 11=1故新配置的汗明码为11101001101。a22例4.4 已知接收到的海明码为0110101（按配偶原则配置），试问欲传送的信息是什么？解：由于要求出欲传送的信息，必须是正确的信息，因此不能简单地从接收到的7 位海明码中去掉C1、C2、C4 三位检测位来求得。首先应该判断收到的信息是否出错。纠错过程如下：s1=1 3 5 7

22、=1s2=2 3 6 7=1s3=4 5 6 7=0所以，s3s2s1=011，第3 位出错，可纠正为0100101，故欲传送的信息为0101。a23C1 C2 . C K r 1 r 2 r i 3.7.3 3.7.3 循环冗余校验方法循环冗余校验方法(CRC(CRC码码) ) 循环冗余校验方式：通过某种数学公循环冗余校验方式：通过某种数学公式建立信息位和校验位之间的约定关系式建立信息位和校验位之间的约定关系能够校验传送信息的对错，并且能自动能够校验传送信息的对错，并且能自动修正错误。广泛用于通信和磁介存储器中。修正错误。广泛用于通信和磁介存储器中。CRC编码格式是在编码格式是在k位信息后加

23、位信息后加r位检验码。位检验码。 N N-1 2 1 信息位（信息位（k位）位） 校验位（校验位（r位）位）a241 1、CRCCRC码的编码方法码的编码方法 CRC整个编码长度为整个编码长度为 n=k+r 位，故位，故CRC码又叫（码又叫（n，k）码。其编码方法如下：）码。其编码方法如下： 假设被传送的假设被传送的k位二进制信息位用位二进制信息位用C(x)表示表示, 系统选系统选定的生成多项式用定的生成多项式用G(X)表示，将表示，将C(x)左移左移 G(X)的最高次的最高次幂幂(即等于需要添加的校验位的位数即等于需要添加的校验位的位数r)，写作，写作 C(x) 2 r 然后将其然后将其C(

24、x) 2 r除以生成多项式除以生成多项式G(x)，所得商用，所得商用Q(x)表示，余数用表示，余数用R(x)表示。则：表示。则： 两边同时乘以两边同时乘以G(x)并左移并左移 R(x) 得到：得到：)()()()(2)(xGxRxQxGxCr)()()(2)(xGxQxRxCra25故有： 上式中，等式左边即为所求的上式中，等式左边即为所求的n位位CRC码，码，其中余数表达式其中余数表达式R(x)就是校验位就是校验位(r位位)。且等。且等式两边都是式两边都是G(x)的倍数。的倍数。 发送信息时将等式左边生成的发送信息时将等式左边生成的n位位CRC码码送给对方。当接收方接到送给对方。当接收方接到

25、n位编码后，同样除位编码后，同样除以以G(x)，如果传输正确则余数为，如果传输正确则余数为0，否则则可，否则则可以根据余数的数值确定是哪位数据出错。以根据余数的数值确定是哪位数据出错。)()()(2)(011 , 101 , 110 ,000 xGxQxRxCr 由于由于CRC编码采用的加、减法是按位加编码采用的加、减法是按位加减法，即不考虑进位与借位，运算规则为：减法，即不考虑进位与借位，运算规则为： 0 0=0，0 1=1，1 0=1，1 1=0模2加a26 例：有一个（例：有一个（7,4）码（即）码（即CRC码为码为7位，信息码位，信息码为为4位），已确定生成多项式为：位），已确定生成多

26、项式为： 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码码1001000210012)(3rxC10011101101001000)(2)(3xRxCa27 110 1011 1000 1011 101010010001011a28 2 2、CRCCRC码的查错表码的查

27、错表CRCA7A6A5A4A3A2A1余数 出错正确10011100001001111001A11001100010A21001010100A31000110011A41011110110A51101110111A6某一位出错0001110101A7 收到的收到的CRC码除以约定的生成多项式码除以约定的生成多项式G(x)，如果余，如果余数为数为0则传输无误，否则传输错误，根据所得余数值就可则传输无误，否则传输错误，根据所得余数值就可找出错误并取反纠正。找出错误并取反纠正。 上表详细说明了上表详细说明了CRC码码1001110在传送时某一位出在传送时某一位出错后的判断与纠正方法错后的判断与纠正方

28、法 C(X) = 1001、 G (x) =1011 。a29 3 3、生成多项式、生成多项式G G（x x）的确定）的确定 G(x)是一个约定的除数，用来产生校验码。从是一个约定的除数，用来产生校验码。从检错和纠错的要求出发，它并不是随意选择的，它检错和纠错的要求出发，它并不是随意选择的，它应满足下列要求：应满足下列要求： 任何一位发生错误都应使余数不为任何一位发生错误都应使余数不为0 ； 不同位发生错误应使余数不同；不同位发生错误应使余数不同； 余数继续模余数继续模2 除，应使余数循环。除，应使余数循环。 在计算机和通信系统中，广泛使用下述两种标准：在计算机和通信系统中，广泛使用下述两种标

29、准： 国际电报电话咨询委员会国际电报电话咨询委员会CCITT推荐推荐 G(X)=X16+X15+X2+1 美国电气和电子工程师协会美国电气和电子工程师协会IEEE推荐推荐 G(X)=X16+X12+X5+1a30 4 4、CRCCRC的译码与纠错的译码与纠错 将收到的循环校验码用约定的生成多项式将收到的循环校验码用约定的生成多项式G（x）去除，如）去除，如果码字无误则余数应为果码字无误则余数应为0,如有某一位出错，则余数不为如有某一位出错，则余数不为0,不同位不同位数出错余数不同。通过上例数出错余数不同。通过上例 求出其出错模式如表求出其出错模式如表 3.10所示、更所示、更换不同的待测码字可

30、以证明换不同的待测码字可以证明:余数与出错位的对应关系是不变的，余数与出错位的对应关系是不变的，只与码制和生成多项式有关，只与码制和生成多项式有关，因此表因此表 3.10给出的关系可作为给出的关系可作为（7,4）码的判别依据，对于其他码制或选用其他生成多项式，）码的判别依据，对于其他码制或选用其他生成多项式，出错模式将发生变化。出错模式将发生变化。 a31 如果循环码有一位出错，用如果循环码有一位出错，用G（x）作模）作模2除将得到一个不除将得到一个不为为0的余数，如果对余数补的余数，如果对余数补1个个0继续除下去我们将发现一继续除下去我们将发现一个现象：各次余数将按表个现象：各次余数将按表3

31、.10顺序循环，例如第一位出错，顺序循环，例如第一位出错，余数将为余数将为001，补，补0后再除，第二次余数为后再除，第二次余数为010，以后依次，以后依次为为100，011,.，反复循环，这是一个有价值的特点。如，反复循环，这是一个有价值的特点。如果我们在求出余数不为果我们在求出余数不为0后，一边对余数补后，一边对余数补0继续做模继续做模2除，除，同时让被检错的校验码字循环左移。表同时让被检错的校验码字循环左移。表 3.10说明当出现余说明当出现余数（数（101）时，出错位也移到）时，出错位也移到A7位置、对通过异或门将它位置、对通过异或门将它纠正后在下一次移位时送回纠正后在下一次移位时送回

32、A1。继续移满一个循环（对。继续移满一个循环（对74码共移七次），就得到一个纠正后的码字。这样我们就码共移七次），就得到一个纠正后的码字。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件、不必像海明校验那样用译码电路对每一位提供纠正条件、当位数增多时循环码校验能有效地降低硬件代价。当位数增多时循环码校验能有效地降低硬件代价。a32例（7，4）CRC码中，G(X)=1011，通过余数循环添0法获得余数与出错位对应关系a33 【例】对图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。