运算方法和运算部件乘除及校验.ppt

采用冗余校验方法：即在基本的有效数据外，再扩充部分位，增加部分（冗余部分）被称为校验位。将校验位与数据位一起按某种规则编码，写入存储器或向外发送。当从存储器读出或接收到外部传入的代码时，再按相应的规则进行判读。若不符合约定的规则，则表示出现错误。根据错误的特征进行修正恢复。第62页，共94页，星期日，2025年，2月5日几个名词概念码字：由若干代码组成的一个字。如8421码中0110（6），0111（7）距离：两个码字之间不同的代码个数。8421码中，最小的距离为1，如0000和0001、0010和0011等；最大距离为4，如0111和1000。码距(最小码距)：一种码制中任意两个码字间的最小 距离。（合法码到合法码变动的最小位数） 8421码的码距为1。码距为1，即不能查错也不能纠错。码距越大，查错、纠错能力越强。第63页，共94页，星期日，2025年，2月5日码距与检纠错的关系①为了检测e个误码，要求最小码距d0应满足： d0≥e+1②为了纠正t个误码，要求最小码d0距应满足： d0≥2t+1③为了纠正t个误码，同时能检测e个误码(e＞t)，要求最小码距d0应满足： d0≥e+t+1**第64页，共94页，星期日，2025年，2月5日3.7.1奇偶校验码奇偶校验码是计算机中广泛采用的检查传输数据准确性的方法。奇偶校验的原理是： 在每组数据信息上附加一个校验位，使码距由1增加到2（合法码到合法码变动的最小位数为2）。若编码中有奇数个二进制位出错了，这个码将变成非法编码。如果采用奇校验，则这组数据加上校验码位后数据中‘1’的个数应为奇数个。奇校验位形成公式:C=X0⊕X1⊕…⊕Xn-1如果采用偶校验，则这组数据加上校验码位后数据中‘1’的个数应为偶数个。偶校验位形成公式:C=X0⊕X1⊕…⊕Xn-1第65页，共94页，星期日，2025年，2月5日 下面给出对几个字节值的奇偶校验的编码结果： 数据奇校验的编码偶校码的编码000000000010l0l000010l0100l01010l0001ll1lll0011l111110l111l1l 其中，最高一位为校验位，其余低八位为数据位。从中可以看到，校验位的值取O还是1，是由数据位中1的个数决定的。第66页，共94页，星期日，2025年，2月5日缺点:这种方案只能发现一位错或奇数个位错，但不能确定是哪一位错，也不能发现偶数个位错。优点:该方案还是有很好的实用价值。偶校验位形成第67页，共94页，星期日，2025年，2月5日奇偶校验的特点：1、奇偶校验码使数据的码距为2，因而可检出数据传送过程中奇数个数位出错的情况（一位变动会使校验位改变，d0≥e+1=2）；2、实际中两位同时出错的概率极低，奇偶校验法简便可靠易行，但它只能发现错误，却不知错在何处，因而不能自动纠正。3、奇偶校验码是一种开销最小，能发现数据代码中一位出错情况的编码。 常用于存储器读写检查，或ASCII字符传送过程中的检查。第68页，共94页，星期日，2025年，2月5日3.7.2海明校验码海明校验码是RichardHamming于1950年提出的，目前仍广泛使用的一种编码方法。1、原理（1）特点：能检测出两位同时出错、亦能检测出一位出错并能自动纠错。(码距d0≥e+t+1=2+1+1=4)（2）实现原理：在k个数据位之外加上r个校验位，从而形成一个k+r位的新码字，当某一位出错后，就会引起相关的几个（d0个）校验位的值发生变化，从而达到检错、纠错的目的。第69页，共94页，星期日，2025年，2月5日* 设某步得到余数Ri≥0，得到下步除法的新余数Ri+1： Ri+1=2Ri-|B| 若Ri是假余数，即Ri0，要得到下步除法的新余数Ri+1，要先恢复余数，而后左移一位再减|B|才能得到新余数。即： Ri+1=2(Ri+|B|)-|B| 将上式变换一下，得： Ri+1=2Ri+|B|去掉恢复步！?加减交替法第30页，共94页，星期日，2025年，2月5日* 若某步除法Ri0，要得到下步除法的新余数Ri+1，不必恢复余数，