计算机组成原理中的三种校验方式

计算机组成原理中的三种校验方式目前一页\总数三十二页\编于十八点几个名词概念：码字：由若干代码组成的一个字。如8421码中6（0110），7（0111）码距：一种码制中任意两个码字间的最小距离。距离：两个码字之间不同的代码个数。8421码中，最小的码字间的距离为1，如0000和0001、0010和0011等；最大码字间的距离为4，如0111和1000。所以8421码制的码距为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⊕X1⊕…⊕Xn-1若P=0则无错或有偶数位错，若P=1则有奇数位错目前四页\总数三十二页\编于十八点例如：八位信息‘10101011’中共有5个‘1’，附加校验位后变为九位。若采用奇校验，则附加的校验位应取‘0’值，保证1的个数为奇数个即010101011；若采用偶校验则附加的校验位应取‘1’值即

110101011。

奇偶校验的特点：1、奇偶校验法可检出数据传送过程中奇数个数位出错的情况；2、实际中两位同时出错的概率极低，奇偶校验法简便可靠易行，但它只能发现错误，却不知错在何处，因而不能自动纠正。目前五页\总数三十二页\编于十八点码能力码距

检错纠错

1

0

0

2

1

0

3

2或1

4

2加1

5

2加2

6

3加2

7

3加3

为了使一个系统能检查和纠正一个差错，码间最小距离必须至少是“3”。最小距离为3时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。

码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。所以，选择码距要取决于特定系统的参数。目前六页\总数三十二页\编于十八点2海明码校验方法

海明码是一种比较常用的纠错码，它实际上是一种多重奇偶校验码。其基本思想是将被检验码分成多个组，每组配备一个奇偶校验位完成该组的奇偶校验位的功能。当被校验码中某一位出错时，将会有相关的多个小组出现奇偶校验错，根据这些组的出错情况便可将错误定位到某一位上从而即可纠正过来。

目前七页\总数三十二页\编于十八点强调指出：海明码校验方法以奇偶校验法为基础，其校验位不是一个而是一组。海明码校验方法能够检测出具体错误并纠正。海明码的最低目标是能纠正一位错，因此要求海明码的码距大于或等于3。目前八页\总数三十二页\编于十八点海明校验码是RichardHamming于1950年提出的，目前仍广泛使用的一种编码方法。1、原理（1）特点：能检测出两位同时出错、亦能检测出一位出错并能自动纠错。（2）实现原理：在k个数据位之外加上r个校验位，从而形成一个k十r位的新码字，当某一位出错后，就会引起相关的几个校验位的值发生变化，从而达到检错、纠错的目的。目前九页\总数三十二页\编于十八点kr(最小)122~435~11412~26527~5762r≥k+r+1(3.18)(一位出错并纠错)数据位k与校验位r的对应关系：

目前十页\总数三十二页\编于十八点2r-1≥k+r(3.19)(一位出错并纠错并发现两位错)码距为4由3.19式计算可得目前十一页\总数三十二页\编于十八点2、编码规则

若海明码的最高位号为m，最低位号为1，即：HmHm-1…H2H1，则此海明码的编码规律：(1)校验位与数据位之和为m，每个校验位Pi在海明码中被分在位号2i-1的位置，其余各位为数据位，并按从低向高逐位依次排列的关系分配各数据位。(2)海明码的每一位码Hi(包括数据位和校验位本身)由多个校验位校验，其关系是被校验的每一位位号要等于校验它的各校验位的位号之和。这样安排的目的,是希望校验的结果能正确反映出出错位的位号。

目前十二页\总数三十二页\编于十八点1、纠查一位错的编码方法

（以四个校验位进行说明）四个校验位最多可以校验11位数据。设：

D10D9D8D7D6D5D4D3D2D1D0为11个数据位，

P4P3P2P1分别为四个校验码，则编码规则是：海明码的总位数H等于数据位与校验位之和；每个校验位Pi排放在2i-1的位置，如P4排放在第24-1=8位，其余数据位依序排列。目前十三页\总数三十二页\编于十八点即：

H15H14H13H12H11H10H9H8H7H6H5H4H3H2H1D10D9D8D7D6D5D4P4

D3D2D1P3

D0

P2P1海明码的每一位用多个校验位一起进行校验，被校验的位号等于校验它的各校验位位号和；各校验位的值为它参与校验的数据位的异或。目前十四页\总数三十二页\编于十八点

海明码校验表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)H15D10P34H4P3P2P12,1(3=2+1)H3D0P22H2P2P11H1P1参与的校验位参与校验的校验位位号海明码位号目前十五页\总数三十二页\编于十八点

各校验位形成公式：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连同数据位一起形成了海明码的各位。

用海名位号改写P4～P1：P1=H3⊕H5⊕H7⊕H9⊕H11

⊕H13

⊕H15P2=H3⊕H6⊕H7⊕H10⊕H11

⊕H14

⊕H15P3=H5⊕H6⊕H7⊕H12⊕H13⊕H14⊕H15P4=H9⊕H10⊕H11⊕H12⊕H13⊕H14⊕H15目前十六页\总数三十二页\编于十八点2、检查纠错（以四个校验位进行说明）

海明码数据传送到接收方后，再将各校验位的值与它所参与校验的数据位的异或结果进行异或运算。运算结果称为校验和。校验和共有四个。对偶校验来说，如果校验和不为零则传输过程中间有错误。而错误的具体位置则由四个校验和依序排列后直接指明。如果四个校验和S4S3S2S1

依序排列后等于(1001)2=(9)10时，就表明海明码的第九位也就是D4发生了错误，此时只要将D4取反，也就纠正了错误。目前十七页\总数三十二页\编于十八点

校验和Si的表达式：S1=D0⊕D1⊕D3⊕D4⊕D6⊕D8⊕D10⊕P1

S2=D0⊕D2⊕D3⊕D5⊕D6⊕D9⊕D10⊕P2S3=D1⊕D2⊕D3⊕D7⊕D8⊕D9⊕D10⊕P3S4=D4⊕D5⊕D6⊕D7⊕D8⊕D9⊕D10⊕P4

用海名位号改写S4～S1：S1=H1⊕H3⊕H5⊕H7⊕H9⊕H11

S2=H2⊕H3⊕H6⊕H7⊕H10⊕H11

S3=H4⊕H5⊕H6⊕H7⊕H12S4=H8⊕H9⊕H10⊕H11⊕H12目前十八页\总数三十二页\编于十八点当采用偶校验方式其传送数据正确时，校验和S1~S4的值分别都为0；当采用奇校验方式其传送数据正确时，校验和S1~S4的值分别都为1。当不为上述值时，传送就发生了错误。目前十九页\总数三十二页\编于十八点解：已知D10D9D8D7D6D5D4D3D2D1D0

由于被校验位的位号等于校验它的各校验位位号之和以及各校验位的取值等于它参与校验的数据位取值的异或。所以校验位的取值以及所求海明码为：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=传送正确时校验和的值为0，如果不等于0，则是几就是第几位出错，是7则是第7位D3出错，此时将其取反即可纠正错误。例题：采用4位校验位、偶校验方式，目前二十页\总数三十二页\编于十八点例4.5按配奇原则配置1100101的汉明码。解：根据1100101，得n=7。根据2k≥n+k+1，可求出需增添k=4位检测位，各位的安排如下：二进制序号1234567891011海明码C1C21C4100C8101按配奇原则配置，则C1=3⊕5⊕7⊕9⊕11=1C2=3⊕6⊕7⊕10⊕11=1C4=5⊕6⊕7=0C8=9⊕10⊕11=1目前二十一页\总数三十二页\编于十八点例4.4已知接收到的海明码为0110101（按配偶原则配置），试问欲传送的信息是什么？解：由于要求出欲传送的信息，必须是正确的信息，因此不能简单地从接收到的7位海明码中去掉C1、C2、C4三位检测位来求得。首先应该判断收到的信息是否出错。纠错过程如下：s1=1⊕3⊕5⊕7=1s2=2⊕3⊕6⊕7=1s3=4⊕5⊕6⊕7=0所以，s3s2s1=011，第3位出错，可纠正为0100101，故欲传送的信息为0101。目前二十二页\总数三十二页\编于十八点C1C2…...CK

r1r2……ri

3.7.3循环冗余校验方法(CRC码)循环冗余校验方式：通过某种数学公式建立信息位和校验位之间的约定关系——能够校验传送信息的对错，并且能自动修正错误。广泛用于通信和磁介存储器中。CRC编码格式是在k位信息后加r位检验码。NN-121

信息位（k位）校验位（r位）目前二十三页\总数三十二页\编于十八点1、CRC码的编码方法CRC整个编码长度为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)得到：目前二十四页\总数三十二页\编于十八点故有：上式中，等式左边即为所求的n位CRC码，其中余数表达式R(x)就是校验位(r位)。且等式两边都是G(x)的倍数。发送信息时将等式左边生成的n位CRC码送给对方。当接收方接到n位编码后，同样除以G(x)，如果传输正确则余数为0，否则则可以根据余数的数值确定是哪位数据出错。由于CRC编码采用的加、减法是按位加减法，即不考虑进位与借位，运算规则为：00=0，01=1，10=1，11=0模2加目前二十五页\总数三十二页\编于十八点

例：有一个（7,4）码（即CRC码为7位，信息码为4位），已确定生成多项式为：

G（X）=X3+X+1=1011

被传输的信息C(x)=1001，求C(x)的CRC码。解：C（x）左移r=n–k=3位即：将上式模2采用除法除以给定的G(x)=1011：1001000/1011=1010+110/1011得到余数表达式：R(x)=110所求CRC码目前二十六页\总数三十二页\编于十八点目前二十七页\总数三十二页\编于十八点2、CRC码的查错表收到的CRC码除以约定的生成多项式G(x)，如果余数为0则传输无误，否则传输错误，根据所得余数值就可找出错误并取反纠正。上表详细说明了CRC码1001110在传送时某一位出错后的判断与纠正方法[C(X)=1001、G(x)=1011]。目前二十八页\总数三十二页\编于十八点3、生成多项式G（x）的确定G(x)是一个约定的除数，用来产生校验码。从检错和纠错的要求出发，它并不是随意选择的，它应满足下列要求：任何一位发生错误都应使余数不为0；不同位发生错误应使余数不同；余数继续模2除，应使余数循环。在