计算机组成原理第3章 运算方法与运算部件3校验码

1、1 3.7 计算机中的数据校验方法 2 3.7.1 3.7.1 奇偶校验法奇偶校验法 3.7.2 3.7.2 海明码校验方法海明码校验方法 3.7.3 3.7.3 循环冗余校验方法循环冗余校验方法(crc(crc码码) ) 3 3.7.1 3.7.1 奇偶校验法奇偶校验法 4 例如：八位信息例如：八位信息10101011中共有中共有5个个1， 附加校验位后变为九位。附加校验位后变为九位。 若采用奇校验，则附加的校验位应取若采用奇校验，则附加的校验位应取0值，值， 保证保证1的个数为奇数个即的个数为奇数个即 0 10101011 ； 若采用偶校验则附加的校验位应取若采用偶校验则附加的校验位应取1

2、值即值即 1 10101011 。 奇偶校验的特点：奇偶校验的特点： 1、奇偶校验法使数据的码距为、奇偶校验法使数据的码距为2，因而可检出，因而可检出 数据传送过程中奇数个数位出错的情况；数据传送过程中奇数个数位出错的情况； 2、实际中两位同时出错的概率极低，奇偶校、实际中两位同时出错的概率极低，奇偶校 验法简便可靠易行，但它只能发现错误，却不知验法简便可靠易行，但它只能发现错误，却不知 错在何处，因而不能自动纠正。错在何处，因而不能自动纠正。 5 奇校验 1出错 偶校验 1出错 偶形成 奇形成 d校为校验位 d校 d0 d1 d2 d3 d4 d5 d6 d7 8位数据的奇偶校验码形成电路及

3、检码电路 6 3.7.2 3.7.2 海明码校验方法海明码校验方法 7 r k+r+1, k 是被传送数据的位数。是被传送数据的位数。 8 2 2r-1 r-1 k k 9 1 1、纠查一位错的编码方法、纠查一位错的编码方法 （以四个校验位进行说明）（以四个校验位进行说明） 四个校验位最多可以校验四个校验位最多可以校验11位数据。设：位数据。设： d10d9d8d7d6d5d4d3d2d1d0为为11个数据位，个数据位， p4p3p2p1分别为四个校验码，则编码规则是：分别为四个校验码，则编码规则是： 海明码的总位数海明码的总位数h等于数据位与校验位之和；等于数据位与校验位之和； 每个校验位每

4、个校验位pi排放在排放在2i-1的位置，如的位置，如p4排放排放 在第在第24-1=8位，其余数据位依序排列。即：位，其余数据位依序排列。即： h15 h14 h13 h12 h11 h10 h9 h8 h7 h6 h5 h4 h3 h2 h1 d10 d9 d8 d7 d6 d5 d4 p4 d3 d2 d1 p3 d0 p2 p1 海明码的每一位用多个校验位一起进行校验，海明码的每一位用多个校验位一起进行校验， 被校验的位号等于校验它的各校验位位号和；被校验的位号等于校验它的各校验位位号和； 各校验位的值为它参与校验的数据位的异或。各校验位的值为它参与校验的数据位的异或。 10 11 n各

5、校验位形成公式：各校验位形成公式： 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连同数据位一起形成了海明码的各位。连同数据位一起形成了海明码的各位。 n例如，对一个例如，对一个8位的字节组成的数据，如果要能发现位的字节组成的数据，如果要能发现2位错，位错， 并发现

6、和纠正并发现和纠正1位错，则校验位需要有位错，则校验位需要有5位，即整个海明码为位，即整个海明码为13 位，可以表示为位，可以表示为h13h12h11h1。 n5位校验位位校验位p5p1对应的是对应的是h13,h8,h4,h2和和h1。（。（p5只能用只能用 h13表示，因为它已经是海明码的最高位了）。也就是说，按表示，因为它已经是海明码的最高位了）。也就是说，按 上述规则（上述规则（1），海明编码中，校验位和数据位的关系是），海明编码中，校验位和数据位的关系是 p5d8d7d6d5p4d4d3d2p3d1p2p1 12 2 2、检查纠错（以四个校验位进行说明）、检查纠错（以四个校验位进行说明

7、） 海明码数据传送到接收方后，再将各校验海明码数据传送到接收方后，再将各校验 位的值与它所参与校验的数据位的异或结果进位的值与它所参与校验的数据位的异或结果进 行异或运算。行异或运算。 运算结果称为校验和。校验和共运算结果称为校验和。校验和共 有四个。有四个。 对偶校验来说，如果校验和不为零则传输对偶校验来说，如果校验和不为零则传输 过程中间有错误。而错误的具体位置则由四个过程中间有错误。而错误的具体位置则由四个 校验和依序排列后直接指明。如果四个校验和校验和依序排列后直接指明。如果四个校验和 s4s3s2s1 依序排列后等于依序排列后等于(1001)2=(9)10 时，就时，就 表明海明码的

8、第九位也就是表明海明码的第九位也就是d4发生了错误，此发生了错误，此 时只要将时只要将d4取反，也就纠正了错误。取反，也就纠正了错误。 13 14 解：已知解：已知d10d9d8d7d6d5d4d3d2d1d0=10110100110 由于被校验位的位号等于校验它的各校验位位号之和以由于被校验位的位号等于校验它的各校验位位号之和以 及各校验位的取值等于它参与校验的数据位取值的异或。所及各校验位的取值等于它参与校验的数据位取值的异或。所 以校验位的取值以及以校验位的取值以及所求所求海明码为：海明码为： p1=d0 d1 d3 d4 d6 d8 d10 =1 p2=d0 d2 d3 d5 d6 d

9、9 d10=1 p3=d1 d2 d3 d7 d8 d9 d10=1 p4=d4 d5 d6 d7 d8 d9 d10=0 d10d9d8d7d6d5d4p4d3d2d1p3d0p2p1 =101101000111011 传送正确时校验和的值为传送正确时校验和的值为0 0，如果不等于，如果不等于0 0，则是几就是，则是几就是 第几位出错，是第几位出错，是7 7则是第则是第7 7位位d3出错，此时将其取反即可纠正出错，此时将其取反即可纠正 错误。错误。 例题：采用例题：采用4 4位校验位、偶校验方式，位校验位、偶校验方式， 写出写出1011010011010110100110的海明码。的海明码。

10、 15 译 码 器 无 错 有 错 寄 偶 形 成 线 路寄 偶 形 成 线 路寄 偶 形 成 线 路寄 偶 形 成 线 路 奇偶形成线路 奇偶形成线路 奇偶形成线路 奇偶形成线路 16 17 c1 c2 . c k r 1 r 2 r i 3.7.3 3.7.3 循环冗余校验方法循环冗余校验方法(crc(crc码码) ) 环冗余校验方式：通过某种数学公式环冗余校验方式：通过某种数学公式 建立信息位和校验位之间的约定关系建立信息位和校验位之间的约定关系 能够校验传送信息的对错，并且能自动修能够校验传送信息的对错，并且能自动修 正错误。广泛用于通信和磁介存储器中。正错误。广泛用于通信和磁介存储器

11、中。 crc编码格式是在编码格式是在k位信息后加位信息后加r位检验码。位检验码。 n n-1 2 1 信息位（信息位（k位）位） 校验位（校验位（r位）位） 18 1 1、crccrc码的编码方法码的编码方法 crc整个编码长度为整个编码长度为 n=k+r 位，故位，故crc码又码又 叫（叫（n，k）码。其编码方法如下：）码。其编码方法如下： 假设被传送的假设被传送的k位二进制信息位用位二进制信息位用c(x)表示表示, 系统选定的生成多项式用系统选定的生成多项式用g(x)表示，将表示，将c(x)左移左移 g(x)的最高次幂的最高次幂(即等于需要添加的校验位的位数即等于需要添加的校验位的位数 r

12、)，写作，写作 c(x) 2 r 然后将其然后将其c(x) 2 r除以生成多项式除以生成多项式g(x)，所，所 得商用得商用q(x)表示，余数用表示，余数用r(x)表示。则：表示。则： 两边同时乘以两边同时乘以g(x)并左移并左移 r(x) 得到：得到： )()()()(2)(xgxrxqxgxc r )()()(2)(xgxqxrxc r 19 )()()(2)( 011 , 101 , 110 ,000 xgxqxrxc r 由于由于crc编码采用的加、减法是按位加编码采用的加、减法是按位加 减法，即不考虑进位与借位，运算规则为：减法，即不考虑进位与借位，运算规则为： 0 0=0，0 1=

13、1，1 0=1，1 1=0 20 例：有一个（例：有一个（7,4）码（即）码（即crc码为码为7位，信息码位，信息码 为为4位），已确定生成多项式为：位），已确定生成多项式为： g（x）=x3+x+1= 1011 被传输的信息被传输的信息c(x)=1001，求，求c(x)的的crc码。码。 1001000210012)( 3 r xc 10011101101001000)(2)( 3 xrxc 21 110 1011 1000 1011 1010 10010001011 1 1011 1011 1011 1010 10011111011 (a) (b) 22 r0 + crc编码电路：移位寄存

14、器中插进异或门 m(x) r(x) g1 g(x)=xr+ gr-1xr-1+ + g2x2+g1x1+1 1 （多项式系数多项式系数） r1+ + g2gr-1 rr-1 信息输入：由高位到低位串行输入。信息输入：由高位到低位串行输入。 kr km k r t(x) 23 r0r1r2+ crc编码电路：移位寄存器中插进异或门 m(x) r(x) 110 g(x)=x3+x+1的crc编码电路 1 （多项式系数多项式系数） 信息输入：由高位到低位串行输入。 r2 r1 r0 m(x) 0 0 0 0 1 1 1 1 1 0 0 1 0 0 1 0 0 0 1 m(x) =x3+x+1时 r(

15、x)=0 24 2 2、crccrc码的查错表码的查错表 crca7a6a5a4a3a2a1余数 出错 正确1001110000 1001111001a1 1001100010a2 1001010100a3 1000110011a4 1011110110a5 1101110111a6 某 一 位 出 错 0001110101a7 收到的收到的crc码除以约定的生成多项式码除以约定的生成多项式g(x)，如果，如果 余数为余数为0则传输无误，否则传输错误，根据所得余数值则传输无误，否则传输错误，根据所得余数值 就可找出错误并取反纠正。就可找出错误并取反纠正。 上表详细说明了上表详细说明了crc码码1001110在传送时某一位出在传送时某一位出 错后的判断与纠正方法错后的判断与纠正方法 c(x) = 1001、 g (x) =1011 。 25 3 3、生成多项式、生成多项式g g（x x）的确定）的确定 16152 16125 26 27 r0 + crc的译码与纠错的译码与纠错(crc译码电路译码电路) r(x) g1 g(x)=xr+ gr-1xr-1+ + g2x2+g1x1+1 1 （多项式系数多项式系数） r1+ + g2gr-1 rr-1 r t (x) 1 e e=0 正确正确 e=1