《计算机组成原理》课件第二章数据的表示-2.4.ppt

1、第2章数据表示2.4数据校验码2.4数据校验码 在数据编码中，能够发现错误的编码叫做检错码；能够纠正错误的编码叫做纠错码。能够检测或纠正编码中错误的信息编码，称为数据校验码，可以提高计算机的可靠性。目前的数据校验法大多采用“冗余校验”的思想，即除原数据信息外，还增加若干位新编码，这些编码称为校验码。常用的数据校验码有奇偶校验码、海明校验码和循环冗余校验码等。2.4.1奇偶校验码 奇偶校验法是在信息位中增加一位校验位代码，能够检测出代码中的奇数个位的错误，但不能纠正错误。常用于存储器读写检查或按字节传输数据过程中的数据校验。奇偶校验码包括奇校验码和偶校验码两种。（1）奇偶校验位生成过程 数据在存

2、储和传输时首先需要加上校验位P。奇（偶）校验位的生成过程如下：假设源数据为B=bn-1bn-2b1b0。若采用奇校验位，则P=bn-1 bn-2 b1 b0 1，即若源数据B有奇数个1，则P取0，否则取1，也就是保证加上校验位之后的数据编码中有奇数个1。若采用偶校验位，则P=bn-1 bn-2 b1 b0，即若源数据B有偶数个1，则P取0，否则取1，也就是保证加上校验位之后的数据编码中有偶数个1。（1）奇偶校验位生成过程 例2-36要从源部件发送数据01101010到终部件。请写出采用奇校验法的过程。解：P=0 1 1 0 1 0 1 0 1=1 数据增加奇校验位后的编码为：011010101

3、。（2）奇偶校验码的检错过程 假设源数据信息和校验位经存储或传送后读出的新编码中数据部分为B=bn-1bn-2b1b0，校验位部分为P”。为了判断源数据B是否在存储和传送后发生了错误，在奇偶校验电路中进行检错。1）首先对B求新校验码P。若采用奇校验法：P=bn-1 bn-2 b1 b0 1 若采用偶校验法：P=bn-1 bn-2 b1 b0 2）计算最终的校验位P*，根据其值判断有无奇偶错 P*=P P”。若P*=1，则表示数据存在有奇数位错。若P*=0，则表示数据正确或有偶数个错。（2）奇偶校验码的检错过程 例2-37在计算机中采用奇校验法，数据从源部件发送到终部件，校验位在新编码的最后一位

4、。若终部件得到的编码分别为011010100、011010110、011010111，判断这3个数据是否发生了错误。解：编码011010100检错过程:B=01101010，P”=0。P=0 1 1 0 1 0 1 0 1=1。P*=P P”=1。该编码有奇数位编码错。编码011010110检错过程:B=01101011，P”=0。P=0 1 1 0 1 0 1 1 1=0。P*=P P”=0。该编码无错或有偶数个错。编码011010111检错过程:B=01101011，P”=1。P=0 1 1 0 1 0 1 1 1=0。P*=P P”=1。该编码有奇数位编码错。2.4.2海明校验码海明校验

5、码 奇偶校验码检错能力差，并且没有纠错能力。如果将数据按某种规律分成若干组，对每组进行相应的奇偶检测，就能提供多位检错信息，从而对错误位置进行定位，并对其进行纠正。海明校验码实质上是一种多重奇偶校验码，是目前广泛被采用的校验法，主要用于存储器中数据存取校验。（1）校验位的位数的确定 海明校验码和奇偶校验码一样，都是通过对原校验码和新校验码进行异或操作生成的故障字来判断数据是否发生错误。要实现对某个数据发生的错误进行定位，则故障字应能体现数据可能出现的状态。假定数据位位数为n，校验位位数为k，则故障字位数也是k，k位故障字能够表示的状态有2k种，每种状态用来说明一种情况。数据会出现的状态有无错、

6、n位数据中某一位出错、k位校验位中有一位出错的情况（只考虑干扰造成一位出错的情况），共有1+n+k种情况。所以，n和k必须满足下列关系：2k1+n+k（2）分组方式的确定数据位和校验位一起存储构成n+k位的码字。若将校验位穿插在数据位中，使得某位出错时得到的故障字和出错的位置之间存在一个确定的关系，就可以根据故障字直接确定出错的位置，并容易地进行纠正了。根据上述基本思想，我们按以下规则来解释各故障字的值：1）如果故障字各位全0，则表示没有发生错误。2）如果故障字中有且仅有一位为1，则表示校验位中有一位出错。校验位出错不需要纠正。3）如果故障字中有多位为1，则表示有一个数据位出错。出错数据位的位

7、置，由故障字的数值确定。只需根据故障字的值找到出错位进行取反纠正就可以了。（2）分组方式的确定（3）校验位的生成 根据故障字和出错情况对应关系表，对12位码字分成了4组，每组进行奇（偶）校验生成一位校验位。在上面的分组方式中，可以看到每个数据位至少参与两组奇（偶）校验位的生成。（3）校验位的生成 例2-39对8位数据01101010，完成海明校验位生成过程，每组采用偶校验。解：采用前一例题的分组表，则得到校验位和数据位之间的关系，对每组数据进行偶校验运算。P1=M1 M2 M4 M5 M7=1 P2=M1 M3 M4 M6 M7=1 P3=M2 M3 M4 M8=0 P4=M5 M6 M7 M

8、8=0 将数据位和校验位一起存储，得到的码字为 M8M7M6M5P4M4M3M2P3M1P2P1=011001010011（4）海明校验码的检错和纠错 数据位M和校验位P一起存储或传送后，读出的数据为M，读出的校验位为P。对M采用同样的分组校验，得到新校验位P。将P和P”进行异或得到故障字S。根据故障字可以确定码字是否发生错误，若发生错误，根据故障字确定的错误位置，若是数据位出错，则取反纠错，若是校验位出错可以不进行纠错。海明校验码具有发现两位错，纠正一位错的能力，又称为单纠错码。（4）海明校验码的检错和纠错 例2-40 在终部件处接收到（8，4）海明码数据011001010011，已知校验分

9、组表如表2-4，完成该数据检错以及纠错过程。解：根据海明码字排列顺序，可知M=01101010，P”=0011。对M数据进行海明校验位生成过程，生成新校验位P。P1=M1 M2 M4 M5 M7=1P2=M1 M3 M4 M6 M7=1P3=M2 M3 M4 M8=0P4=M5 M6 M7 M8=0将P和P”异或得到故障字S。S=P P=0011 0011=0000根据分组表，故障字为0000，表明所有位都无错。（4）海明校验码的检错和纠错 例2-41在终部件处接收到（8，4）海明码数据011101010011，已知校验分组表如表2-4，完成该数据检错以及纠错过程。解：根据海明码字排列顺序，可

10、知M=01111010，P”=0011。对M数据进行海明校验位生成过程，生成新校验位P。P1=M1 M2 M4 M5 M7=0P2=M1 M3 M4 M6 M7=1P3=M2 M3 M4 M8=0P4=M5 M6 M7 M8=1将P和P”异或得到故障字S。S=P P=1010 0011=1001根据分组表，故障字为1001，表明第9位出错。第9位是数据位M5，所以只需将M5取反纠正即可得到原正确数据01101010。2.4.3循环冗余校验码 循环冗余校验码(CRC)，简称循环码，是一种具有检错、纠错能力的校验码。循环冗余校验码常用于外存储器和计算机同步通信的数据校验。奇偶校验码和海明校验码都是

11、采用奇偶检测为手段检错和纠错的，而循环冗余校验则是通过某种数学运算来建立数据位和校验位的约定关系的。（1）校验位的生成 循环冗余校验码由信息码n位和校验码k位构成。K位校验位拼接在n位数据位后面，n+k为循环冗余校验码的字长，又称这个校验码(n+k，n)码。n位信息位可以表示成为一个报文多项式M(x)，最高幂次是Xn-1。约定的生成多项式G(x)是一个k+1 位的二进制数，最高幂次是Xk。将M(x)乘以Xk，即左移k位后，除以G(x)，得到的k位余数就是校验位。这里的除法运算是模2除法，即上商的原则是当部分余数首位是1时商取1，反之商取0。然后每一位的减法运算是按位减，不产生借位。（1）校验位

12、的生成（2）CRC检错和纠错 CRC码存储或传送后，在接收方进行校验过程，以判断数据是否有错，若有错则进行纠错。一个CRC码一定能被生成多项式整除，所以在接收方对码字用同样的生成多项式相除，如果余数为0，则码字没有错误；若余数不为0，则说明某位出错，不同的出错位置余数不同。对（n，k）码制，在生成多项式确定时，出错位置和余数的对应关系是确定的。（2）CRC检错和纠错（2）CRC检错和纠错 CRC码有以下特点：1）任何一个CRC码循环右移一位，仍是CRC码。校验码放在信息位的右边，形成信息码的多余部分，所以称为循环冗余校验码。2）将表中的CRC码按位异或，得到的结果依然是一个CRC码。（2）CR

13、C检错和纠错 例2-44(7，4)循环码中，G(x)=1011时，码字中出错位和余数的对应关系是怎样的？若接收方的码字为1001000，完成数据检错和纠错过程。（2）CRC检错和纠错（3）生成多项式的选取 并不是所有的k位多项式都能作为生成多项式。为了能够检错和纠错，选取的生成多项式应具备如下条件：1）当任何一位出错时，都能使余数不为0 2）不同的位发生错误，得到的余数互不相同 3）对余数继续做模2除法，余数是循环的 下面是几种常用的生成多项式：CRC-CCITT：G（X）=x16+x12+x5+1 CRC-16：G（X）=x16+x15+x2+1 CRC-12：G（X）=x12+x11+x3+x2+x+1 CRC-32：G（X）=x32+x26+x23+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1