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

计算机组成原理中的三种校验方式 本文档共32页；当前第1页；编辑于星期六\17点9分 几个名词概念： 码字：由若干代码组成的一个字。 如8421码中6（0110），7（0111） 码距：一种码制中任意两个码字间的最小距离。 距离：两个码字之间不同的代码个数。 8421码中，最小的码字间的距离为1，如0000和 0001、0010和0011等；最大码字间的距离为4， 如0111和1000。所以8421码制的码距为1。 码距为1码制，即不能查错也不能纠错。 码距越大的码制，查错、纠错能力越强。 本文档共32页；当前第2页；编辑于星期六\17点9分 1 奇偶校验法 奇偶校验法是计算机中广泛采用的检查传输数据准确性的方法。奇偶校验法的原理是： 在每组数据信息上附加一个校验位，校验位的取值（0或1）取决于这组信息中‘1’的个数和校验方式（奇或偶校验）。 如果采用奇校验，则这组数据加上校验码位后数据中‘1’的个数应为奇数个。奇校验位形成公式: C =X0 ⊕X1 ⊕…⊕Xn-1 如果采用偶校验，则这组数据加上校验码位后数据中‘1’的个数应为偶数个。偶校验位形成公式: C =X0 ⊕X1 ⊕…⊕Xn-1 本文档共32页；当前第3页；编辑于星期六\17点9分 在接收端校验检测： 偶校验：P=C ⊕ X0 ⊕X1 ⊕…⊕Xn-1 奇校验：P=C ⊕ X0 ⊕X1 ⊕…⊕Xn-1 若P=0则无错或有偶数位错，若P=1则有奇数位错 本文档共32页；当前第4页；编辑于星期六\17点9分 例如：八位信息中共有5个‘1’，附加校验位后变为九位。 若采用奇校验，则附加的校验位应取‘0’值，保证1的个数为奇数个即 0； 若采用偶校验则附加的校验位应取‘1’值即 1。 奇偶校验的特点： 1、奇偶校验法可检出数据传送过程中奇数个数位出错的情况； 2、实际中两位同时出错的概率极低，奇偶校验法简便可靠易行，但它只能发现错误，却不知错在何处，因而不能自动纠正。 本文档共32页；当前第5页；编辑于星期六\17点9分 码 能 力 码距?检错 纠错?? 1 ???? 0?? ? 02 ???? 1??? ?03 ???? 2 或 14 ???? 2 加 15 ???? 2 加 26 ???? 3 加 27 ???? 3 加 3 为了使一个系统能检查和纠正一个差错，码间最小距离必须至少是“3”。最小距离为3时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。 码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。所以，选择码距要取决于特定系统的参数。 本文档共32页；当前第6页；编辑于星期六\17点9分 2 海明码校验方法 海明码是一种比较常用的纠错码，它实际上是一种多重奇偶校验码。其基本思想是将被检验码分成多个组，每组配备一个奇偶校验位完成该组的奇偶校验位的功能。当被校验码中某一位出错时，将会有相关的多个小组出现奇偶校验错，根据这些组的出错情况便可将错误定位到某一位上从而即可纠正过来。 本文档共32页；当前第7页；编辑于星期六\17点9分 强调指出：海明码校验方法以奇偶校验法为基础，其校验位不是一个而是一组。海明码校验方法能够检测出具体错误并纠正。 海明码的最低目标是能纠正一位错，因此要求海明码的码距大于或等于3。 本文档共32页；当前第8页；编辑于星期六\17点9分 　海明校验码是Richard Hamming于1950年提出的，目前仍广泛使用的一种编码方法。 1、原理 （1）特点：能检测出两位同时出错、亦能检测出一位出错并能自动纠错。 （2）实现原理： 　在k个数据位之外加上r个校验位，从而形成一个k十r位的新码字，当某一位出错后，就会引起相关的几个校验位的值发生变化，从而达到检错、纠错的目的。 本文档共32页；当前第9页；编辑于星期六\17点9分 k r(最小) 1 2 2~4 3 5~11 4 12~26 5 27~57 6 2r≥k+r+1 (3.18)(一位出错并纠错) 数据位k与校验位r的对应关系： 本文档共32页；当前第10页；编辑于星期六\17点9分 2r-1≥k+r (3.19) (一位出错并纠错并发现两位错) 码距为4 由3.19式计算可得 本文