《计算机组成原理中的三种校验方式课件.ppt》由会员分享，可在线阅读，更多相关《计算机组成原理中的三种校验方式课件.ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机中的数据校验方法采用冗余校验方法：采用冗余校验方法：即在基本的有效数据外，再扩充部分即在基本的有效数据外，再扩充部分位，增加部分（冗余部分）被称为校验位。位，增加部分（冗余部分）被称为校验位。将校验位与数据位一起按某种规则编码，将校验位与数据位一起按某种规则编码，写入存储器或向外发送。当从存储器读出或写入存储器或向外发送。当从存储器读出或接收到外部传入的代码时，再按相应的规则接收到外部传入的代码时，再按相应的规则进行判读。若约定的规则被破坏，则表示出进行判读。若约定的规则被破坏，则表示出现错误。根据错误的特征进行修正恢复。现错误。根据错误的特征进行修正恢复。1a几个名词概念：几个名词概念
2、：码字：码字：由若干代码组成的一个字。由若干代码组成的一个字。如如8421码中码中6（0110），），7（0111）码距：码距：一种码制中任意两个码字间的最小距离。一种码制中任意两个码字间的最小距离。距离：距离：两个码字之间不同的代码个数。两个码字之间不同的代码个数。8421码中，最小的码字间的距离为码中，最小的码字间的距离为1，如，如0000和和0001、0010和和0011等；最大码字间的距离为等；最大码字间的距离为4，如如0111和和1000。所以。所以8421码制的码距为码制的码距为1。码距为码距为1码制，即不能查错也不能纠错。码制，即不能查错也不能纠错。码距越大的码制，查错、纠错能力
3、越强。码距越大的码制，查错、纠错能力越强。2a1 1 奇偶校验法奇偶校验法奇偶校验法是计算机中广泛采用的检查传输数据准奇偶校验法是计算机中广泛采用的检查传输数据准确性的方法。奇偶校验法的原理是：确性的方法。奇偶校验法的原理是：在每组数据信息上附加一个校验位，校验位的取值在每组数据信息上附加一个校验位，校验位的取值（0或或1）取决于这组信息中）取决于这组信息中1的个数和校验方式（奇或的个数和校验方式（奇或偶校验）。偶校验）。如果采用奇校验，则这组数据加上校验码位后数据如果采用奇校验，则这组数据加上校验码位后数据中中1的个数应为奇数个。奇校验位形成公式的个数应为奇数个。奇校验位形成公式:C=X0X
4、1Xn-1如果采用偶校验，则这组数据加上校验码位后数据如果采用偶校验，则这组数据加上校验码位后数据中中1的个数应为偶数个。偶校验位形成公式的个数应为偶数个。偶校验位形成公式:C=X0X1Xn-13a在接收端校验检测：偶校验：P=CX0X1Xn-1奇校验：奇校验：P=CX0X1Xn-1若若P=0则无错或有偶数位错，若则无错或有偶数位错，若P=1则有奇数位错则有奇数位错4a 例如：八位信息例如：八位信息10101011中共有中共有5个个1，附，附加校验位后变为九位。加校验位后变为九位。若采用奇校验，则附加的校验位应取若采用奇校验，则附加的校验位应取0值，值，保证保证1的个数为奇数个即的个数为奇数个
5、即 0 10101011；若采用偶校验则附加的校验位应取若采用偶校验则附加的校验位应取1值即值即 1 10101011。奇偶校验的特点：奇偶校验的特点：1、奇偶校验法可检出数据传送过程中奇数个、奇偶校验法可检出数据传送过程中奇数个数位出错的情况；数位出错的情况；2、实际中两位同时出错的概率极低，奇偶校、实际中两位同时出错的概率极低，奇偶校验法简便可靠易行，但它只能发现错误，却不知错验法简便可靠易行，但它只能发现错误，却不知错在何处，因而不能自动纠正。在何处，因而不能自动纠正。5a码能力码距码距检错检错纠错纠错10021032或142加152加263加273加3为了使一个系统能检查和纠正一个差错
6、，码间最小距离必须至为了使一个系统能检查和纠正一个差错，码间最小距离必须至少是少是“3”。最小距离为。最小距离为3时，或能纠正一个错，或能检二个错，时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。编码信息纠错和检错能力的但不能同时纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。进一步提高需要进一步增加码字间的最小距离。码距越大，纠错能力越强，但数据码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。冗余也越大，即编码效率低了。所以，选择码距要取决于特定系统的参数。6a2 2 海明码校验方法海明码校验方法海明码是一种比较常用的纠错码，它
7、实际上是海明码是一种比较常用的纠错码，它实际上是一种多重奇偶校验码。其基本思想是将被检验一种多重奇偶校验码。其基本思想是将被检验码分成多个组，每组配备一个奇偶校验位完成码分成多个组，每组配备一个奇偶校验位完成该组的奇偶校验位的功能。当被校验码中某一该组的奇偶校验位的功能。当被校验码中某一位出错时，将会有相关的多个小组出现奇偶校位出错时，将会有相关的多个小组出现奇偶校验错，根据这些组的出错情况便可将错误定位验错，根据这些组的出错情况便可将错误定位到某一位上从而即可纠正过来。到某一位上从而即可纠正过来。7a强调指出：海明码校验方法以奇偶校验法为基础，强调指出：海明码校验方法以奇偶校验法为基础，其校
8、验位不是一个而是一组。海明码校验方法能其校验位不是一个而是一组。海明码校验方法能够检测出具体错误并纠正。够检测出具体错误并纠正。海明码的最低目标是能纠正一位错，因此要求海明码的最低目标是能纠正一位错，因此要求海明码的码距大于或等于海明码的码距大于或等于3。8a海明校验码是海明校验码是Richard HammingRichard Hamming于于19501950年提出的，目前仍年提出的，目前仍广泛使用的一种编码方法。广泛使用的一种编码方法。1 1、原理、原理（1 1）特特点点：能能检检测测出出两两位位同同时时出出错错、亦亦能能检检测测出出一一位位出出错错并并能自动纠错。能自动纠错。（2 2）实
9、现原理：）实现原理：在在k k个数据位个数据位之外加上之外加上r r个校验位个校验位，从而形成一个，从而形成一个k k十十r r位位的的新码字新码字，当，当某一位出错某一位出错后，就会后，就会引起相关的几个校验位引起相关的几个校验位的值发生变化的值发生变化，从而达到检错、纠错的目的。，从而达到检错、纠错的目的。9akr(最小)12243511412265275762rk+r+1(3.18)(一位出错并纠错一位出错并纠错)数据位数据位k k与校验位与校验位r r的对应关系：的对应关系：10a2r-1k+r (3.19)r (3.19)(一位出错并纠错并发现两位错一位出错并纠错并发现两位错)码距为
10、码距为4 4由由3.193.19式计式计算可得算可得11a2 2、编码规则、编码规则 若若海海明明码码的的最最高高位位号号为为m m，最最低低位位号号为为1 1，即即：H Hm mH Hm-1m-1HH2 2H H1 1，则此海明码的，则此海明码的编码规律编码规律：(1)(1)校校验验位位与与数数据据位位之之和和为为m m，每每个个校校验验位位P Pi i在在海海明明码码中中被被分分在在位位号号2 2i-1i-1的的位位置置，其其余余各各位位为为数数据据位位，并按从低向高逐位依次排列的关系分配各数据位。并按从低向高逐位依次排列的关系分配各数据位。(2)(2)海海明明码码的的每每一一位位码码H
11、Hi i(包包括括数数据据位位和和校校验验位位本本身身)由由多多个个校校验验位位校校验验，其其关关系系是是被被校校验验的的每每一一位位位位号号要要等等于于校校验验它它的的各各校校验验位位的的位位号号之之和和。这这样样安安排排的的目目的的,是是希希望望校校验验的的结结果果能能正正确确反反映映出出出出错错位位的的位号位号。12a1 1、纠查一位错的编码方法、纠查一位错的编码方法 （以四个校验位进行说明）（以四个校验位进行说明）四个校验位最多可以校验四个校验位最多可以校验11位数据。设：位数据。设：D10D9D8D7D6D5D4D3D2D1D0为为11个数据位，个数据位，P4P3P2P1分别为四个校
12、验码，则编码规则是：分别为四个校验码，则编码规则是：海明码的总位数海明码的总位数H等于数据位与校验位之和；等于数据位与校验位之和；每个校验位每个校验位Pi排放在排放在2i-1的位置，如的位置，如P4排放排放 在第在第24-1=8位，其余数据位依序排列。位，其余数据位依序排列。13a即：即：H15H14H13H12H11H10H9H8H7H6H5H4H3H2H1D10D9D8D7D6D5D4P4D3D2D1P3D0P2P1海明码的每一位用多个校验位一起进行校验，海明码的每一位用多个校验位一起进行校验，被校验的位号等于校验它的各校验位位号和；被校验的位号等于校验它的各校验位位号和；各校验位的值为它
13、参与校验的数据位的异或。各校验位的值为它参与校验的数据位的异或。14a海明码校验表海明码校验表P4,P3,P28,4,2(14=8+4+2)H14D9P4,P3,P18,4,1(13=8+4+1)H13D8P4,P38,4(12=8+4)H12D7P4,P2,P18,2,1(11=8+2+1)H11D6P4,P28,2(10=8+2)H10D5P4,P18,1(8=8+1)H9D4P48H8P44,2,1(7=4+2+1)P3,P2,P1H7D3P3,P24,2(6=4+2)H6D2P3,P14,1(5=4+1)H5D1P4,P3,P2,P18,4,2,1(15=8+4+2+1)H15D10P
14、34H4P3P2P12,1(3=2+1)H3D0P22H2P2P11H1P1参与的校验位参与的校验位参与校验的校验位位号参与校验的校验位位号海明码位号海明码位号15a各校验位形成公式：各校验位形成公式：P1=D0D1D3D4D6D8D10(1)P2=D0D2D3D5D6D9D10(2)P3=D1D2D3D7D8D9D10(3)P4=D4D5D6D7D8D9D10(4)按上述方式按上述方式Pi的取值是采用偶校验时的取值，当采用的取值是采用偶校验时的取值，当采用奇校验奇校验时，时，Pi则取反。这样则取反。这样Pi连同数据位一起形成了海明码的各位。连同数据位一起形成了海明码的各位。用海名位号改写用海
15、名位号改写P P4 4P P1 1：P1=H3 H5 H7 H9 H11 H13 H15P2=H3 H6 H7 H10 H11 H14 H15P3=H5 H6 H7 H12 H13H14H15P4=H9 H10 H11 H12H13H14H1516a2 2、检查纠错（以四个校验位进行说明）、检查纠错（以四个校验位进行说明）海明码数据传送到接收方后，再将各校验海明码数据传送到接收方后，再将各校验位的值与它所参与校验的数据位的异或结果进位的值与它所参与校验的数据位的异或结果进行异或运算。行异或运算。运算结果称为校验和。校验和共运算结果称为校验和。校验和共有四个。有四个。对偶校验来说，如果校验和不为
16、零则传输对偶校验来说，如果校验和不为零则传输过程中间有错误。而错误的具体位置则由四个过程中间有错误。而错误的具体位置则由四个校验和依序排列后直接指明。如果四个校验和校验和依序排列后直接指明。如果四个校验和 S4S3S2S1 依序排列后等于依序排列后等于(1001)2=(9)10 时，就时，就表明海明码的第九位也就是表明海明码的第九位也就是D4发生了错误，此发生了错误，此时只要将时只要将D4取反，也就纠正了错误。取反，也就纠正了错误。17a校验和校验和Si的表达式：的表达式：S1=D0D1D3D4D6D8D10P1S2=D0D2D3D5D6D9D10P2S3=D1D2D3D7D8D9D10P3S
17、4=D4D5D6D7D8D9D10P4用海名位号改写用海名位号改写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 H1218a当采用偶校验方式其传送数据正确时，校当采用偶校验方式其传送数据正确时，校验和验和S1S4的值分别都为的值分别都为0；当采用；当采用奇校验奇校验方式方式其传送数据正确时，校验和其传送数据正确时，校验和S1S4的的值分别都为值分别都为1。当不为上述值时，传送就发。当不为上述值时，传送就发生了错误。生了错误。19a解：已知解：已知D10D9
18、D8D7D6D5D4D3D2D1D0=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 D10D9D8D7D6D5D4P4D3D2D1P3D
19、0P2P1 =101101000111011 传送正确时校验和的值为传送正确时校验和的值为0 0，如果不等于，如果不等于0 0，则是几就是，则是几就是 第几位出错，是第几位出错，是7 7则是第则是第7 7位位D3出错，此时将其取反即可纠正出错，此时将其取反即可纠正 错误。错误。例题：采用例题：采用4 4位校验位、偶校验方式，位校验位、偶校验方式，写出写出1011010011010110100110的海明码。的海明码。20a例4.5按配奇原则配置1100101的汉明码。解：根据1100101，得n=7。根据2kn+k+1，可求出需增添k=4位检测位，各位的安排如下：二进制序号1234567891
20、011海明码C1C21C4100C8101按配奇原则配置，则C1=357911=1C2=3671011=1C4=567=0C8=91011=1故新配置的汗明码为11101001101。21a例4.4已知接收到的海明码为0110101（按配偶原则配置），试问欲传送的信息是什么？解：由于要求出欲传送的信息，必须是正确的信息，因此不能简单地从接收到的7位海明码中去掉C1、C2、C4三位检测位来求得。首先应该判断收到的信息是否出错。纠错过程如下：s1=1357=1s2=2367=1s3=4567=0所以，s3s2s1=011，第3位出错，可纠正为0100101，故欲传送的信息为0101。22aC1 C
21、2 .C K r 1 r 2 r i 3.7.3 3.7.3 循环冗余校验方法循环冗余校验方法(CRC(CRC码码)循环冗余校验方式：通过某种数学公循环冗余校验方式：通过某种数学公式建立信息位和校验位之间的约定关系式建立信息位和校验位之间的约定关系能够校验传送信息的对错，并且能自动能够校验传送信息的对错，并且能自动修正错误。广泛用于通信和磁介存储器中。修正错误。广泛用于通信和磁介存储器中。CRC编码格式是在编码格式是在k位信息后加位信息后加r位检验码。位检验码。NN-121信息位（信息位（k位）位）校验位（校验位（r位）位）23a1 1、CRCCRC码的编码方法码的编码方法CRC整个编码长度为
22、整个编码长度为n=k+r位，故位，故CRC码又叫（码又叫（n，k）码。其编码方法如下：）码。其编码方法如下：假设被传送的假设被传送的k位二进制信息位用位二进制信息位用C(x)表示表示,系统选系统选定的生成多项式用定的生成多项式用G(X)表示，将表示，将C(x)左移左移G(X)的最高次的最高次幂幂(即等于需要添加的校验位的位数即等于需要添加的校验位的位数r)，写作，写作C(x)2r然后将其然后将其C(x)2r除以生成多项式除以生成多项式G(x)，所得商用，所得商用Q(x)表示，余数用表示，余数用R(x)表示。则：表示。则：两边同时乘以两边同时乘以G(x)并左移并左移R(x)得到：得到：24a故有
23、：上式中，等式左边即为所求的上式中，等式左边即为所求的n位位CRC码，码，其中余数表达式其中余数表达式R(x)就是校验位就是校验位(r位位)。且等。且等式两边都是式两边都是G(x)的倍数。的倍数。发送信息时将等式左边生成的发送信息时将等式左边生成的n位位CRC码码送给对方。当接收方接到送给对方。当接收方接到n位编码后，同样除位编码后，同样除以以G(x)，如果传输正确则余数为，如果传输正确则余数为0，否则则可，否则则可以根据余数的数值确定是哪位数据出错。以根据余数的数值确定是哪位数据出错。由于由于CRC编码采用的加、减法是按位加编码采用的加、减法是按位加减法，即不考虑进位与借位，运算规则为：减法
24、，即不考虑进位与借位，运算规则为：0 0=0，0 1=1，1 0=1，1 1=0模2加25a例：有一个（例：有一个（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码码26a27a 2
25、2、CRCCRC码的查错表码的查错表 收到的收到的CRC码除以约定的生成多项式码除以约定的生成多项式G(x)，如果余，如果余数为数为0则传输无误，否则传输错误，根据所得余数值就可则传输无误，否则传输错误，根据所得余数值就可找出错误并取反纠正。找出错误并取反纠正。上表详细说明了上表详细说明了CRC码码1001110在传送时某一位出在传送时某一位出错后的判断与纠正方法错后的判断与纠正方法 C(X)=1001、G(x)=1011。28a 3 3、生成多项式、生成多项式G G（x x）的确定）的确定G(x)是一个约定的除数，用来产生校验码。从是一个约定的除数，用来产生校验码。从检错和纠错的要求出发，它
26、并不是随意选择的，它检错和纠错的要求出发，它并不是随意选择的，它应满足下列要求：应满足下列要求：任何一位发生错误都应使余数不为任何一位发生错误都应使余数不为0；不同位发生错误应使余数不同；不同位发生错误应使余数不同；余数继续模余数继续模2除，应使余数循环。除，应使余数循环。在计算机和通信系统中，广泛使用下述两种标准：在计算机和通信系统中，广泛使用下述两种标准：国际电报电话咨询委员会国际电报电话咨询委员会CCITT推荐推荐G(X)=X16+X15+X2+1美国电气和电子工程师协会美国电气和电子工程师协会IEEE推荐推荐G(X)=X16+X12+X5+129a 4 4、CRCCRC的译码与纠错的译
27、码与纠错将收到的循环校验码用约定的生成多项式将收到的循环校验码用约定的生成多项式G（x）去除，如）去除，如果码字无误则余数应为果码字无误则余数应为0,如有某一位出错，则余数不为如有某一位出错，则余数不为0,不同位不同位数出错余数不同。通过上例数出错余数不同。通过上例求出其出错模式如表求出其出错模式如表3.10所示、更所示、更换不同的待测码字可以证明换不同的待测码字可以证明:余数与出错位的对应关系是不变的，余数与出错位的对应关系是不变的，只与码制和生成多项式有关，只与码制和生成多项式有关，因此表因此表3.10给出的关系可作为给出的关系可作为（7,4）码的判别依据，对于其他码制或选用其他生成多项式
28、，）码的判别依据，对于其他码制或选用其他生成多项式，出错模式将发生变化。出错模式将发生变化。30a如果循环码有一位出错，用如果循环码有一位出错，用G（x）作模）作模2除将得到一个不除将得到一个不为为0的余数，如果对余数补的余数，如果对余数补1个个0继续除下去我们将发现一继续除下去我们将发现一个现象：各次余数将按表个现象：各次余数将按表3.10顺序循环，例如第一位出错，顺序循环，例如第一位出错，余数将为余数将为001，补，补0后再除，第二次余数为后再除，第二次余数为010，以后依次，以后依次为为100，011,.，反复循环，这是一个有价值的特点。如，反复循环，这是一个有价值的特点。如果我们在求出
29、余数不为果我们在求出余数不为0后，一边对余数补后，一边对余数补0继续做模继续做模2除，除，同时让被检错的校验码字循环左移。表同时让被检错的校验码字循环左移。表3.10说明当出现余说明当出现余数（数（101）时，出错位也移到）时，出错位也移到A7位置、对通过异或门将它位置、对通过异或门将它纠正后在下一次移位时送回纠正后在下一次移位时送回A1。继续移满一个循环（对。继续移满一个循环（对74码共移七次），就得到一个纠正后的码字。这样我们就码共移七次），就得到一个纠正后的码字。这样我们就不必像海明校验那样用译码电路对每一位提供纠正条件、不必像海明校验那样用译码电路对每一位提供纠正条件、当位数增多时循环
30、码校验能有效地降低硬件代价。当位数增多时循环码校验能有效地降低硬件代价。31a例（7，4）CRC码中，G(X)=1011，通过余数循环添0法获得余数与出错位对应关系32a【例】对图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。33a