《计算机组成原理(校验码)》由会员分享，可在线阅读，更多相关《计算机组成原理(校验码)（22页珍藏版）》请在金锄头文库上搜索。
1、校验码o 具有发现错误或者同时能给出错误所在位置 的数据编码，就称为数据校验码。 o 纠错的关键是确定错误位置，然后取反即可 。n 将数据分组，每一组数据后附加一个校验位， 使得该组数据(包括校验位)中1的个数为偶数( 偶校验)或奇数(奇校验)。 n 三种方式： o 垂直奇偶校验 o 水平奇偶校验 o 水平垂直奇偶校验 只有在所有列都发送完毕后，错误才能够完全检测出来， 而且接收方可能不知道哪个列是不正确，只有重发所有列 ，对于单个错误，会给通信设备增加很大负担 奇偶校验码垂直奇偶校验o 编码规则 n对一组字符各对应位（ 垂直方向）加校验位构 成校验单元 位数字0 1 2 3 4 5 6 7
2、8 9C10 1 0 1 0 1 0 1 0 1C20 0 1 1 0 0 1 1 0 0C30 0 0 0 1 1 1 1 0 0C40 0 0 0 0 0 0 0 1 1C51 1 1 1 1 1 1 1 1 1C61 1 1 1 1 1 1 1 1 1C7 0 0 0 0 0 0 0 0 0 0 偶C00 0 1 0 1 0 0 1 1 0奇1 1 0 1 0 1 1 0 0 1水平奇偶校验 o 编码规则 n以一组字符中对应位（ 水平方向）作为校验单 元进行奇偶校验 位数字0 1 2 3 4 5 6 7 8 9偶校验C10 1 0 1 0 1 0 1 0 11C20 0 1 1 0 0
3、1 1 0 00C30 0 0 0 1 1 1 1 0 00C40 0 0 0 0 0 0 0 1 10C51 1 1 1 1 1 1 1 1 10C61 1 1 1 1 1 1 1 1 10C7 0 0 0 0 0 0 0 0 0 0 0 水平垂直奇偶校验o 编码规则 n将前面两种校验方式相 结合而成位数字0 1 2 3 4 5 6 7 8 9偶校验C10 1 0 1 0 1 0 1 0 11C20 0 1 1 0 0 1 1 0 00C30 0 0 0 1 1 1 1 0 00C40 0 0 0 0 0 0 0 1 10C51 1 1 1 1 1 1 1 1 01C61 1 1 1 1 1
4、 1 1 0 11C7 0 0 0 0 0 0 0 0 0 0 0 偶校验0 1 1 0 1 0 0 1 0 11海明码o 海明码的组成： 由数据位及校验位组合而成的 ，数据位和校验位 交叉排列。o 实现原理：在数据中加入校验位，并把数据的每一个二进制位分配在几个奇偶校验组中。海明码计算步骤o 根据信息位的位数n确定校验码的位数k o 确定校验码的位置 o 求出校验位的值与的关系8 8信息位位数校验验位位数43514265776872k=n+k+1确定校验码的位置o 在海明码中，位号数为2的权的那些位作为 校验位，记作P1，P2，P3，Pk，余下各 位则为有效信息位，或者说，校验位穿插的 原则
5、是，第位校验位占据第2i-1的位置。位号海明码码位参加检验检验 的校验验位1234567P1P2I1P3I2I3I4P1P2P1、P2P3P1、P3P2、P3P1、P2、P3校验位的确定第i位 由校验 位位号 之和等 于i的 那些校 验位进 行校验 。校验位Pi的计算公式o 校验位Pi的取值等于它所参与检验的各位信 息位的异或值。oP3位编码应满足I4、 I3 、I2 、P3为偶校验， 即：P3 I4 I3 I2 oP2位编码应满足I4、 I3 、I1 、P2为偶校验， 即：P2 I4 I3 I1 oP1位编码应满足I4、 I2 、I1 、P2为偶校验， 即：P1 I4 I2 I1校验方法o
6、求3个检验和：S3I4 I3 I2 P3S2I4 I3 I1 P2S1I4 I2 I1 P1o 若（S3 S2 S1）2 0，则说明传送无错，即接收的代码是正确的；若（S3 S2 S1）2 0，则说明传送有错，且（S3 S2 S1）2的十进制数值就是出错的位置。海明码举例o 例：0100 o 解题步骤如下： n n=4，k取3即可 n I4=0，I3=1，I2=0，I1=0 n 各个位的排列规则如下：7654321I4I3I2P3I1P2P1o按如下公式计算校验位的值： P3 I4 I3 I2 P2 I4 I3 I1 P1 I4 I2 I1得 P3 1 P2 1 P1 0 o 则最终传输的信息
7、为：0101010海明码举例o假如实际接收到的信息为：0100010o按如下公式计算校验和的值：S3I4 I3 I2 P3S2I4 I3 I1 P2S1I4 I2 I1 P1得 S3 1 S2 0 S1 0 o 结果为4，说明第4位错，取反即可：0101010海明码举例7654321I4I3I2P3I1P2P1o 具有多位检错能力 o 具有一位纠错能力海明码总结o 校验原理：CRC（cyclic redundancy check）循环冗 余校验码是在n位有效信息后边加上k位校验 位而形成的编码，该编码被生成多项式除， 若余数为0，表示传送正确，若余数不为0， 表示传送发生错误。循环冗余校验码C
8、RC2k=n+k+1校验码的生成o 第一步信息码的权展开式乘以xk，也就是信息码左移k位。o 第二步 给出生成多项式。注意，生成多项式的最高次幂就是校验位的位数，最低次幂必须为0。o 第三步 第一步所得的多项式除以生成多项式。所得余数就是校验位的权展开式。注意，该除法运算是模2运算，即加减时按“异或”进行。生成多项式应满足以下条件：o 生成多项式的最高位和最低位必须为1。 o 当被传送信息（CRC码）任何一位发生错误 时，被生成多项式做除后应该使余数不为0 。 o 不同位发生错误时，应该使余数不同。 o 对余数继续做除，应使余数循环。 CRC举例o 信息码为101，生成多项式为：11101，求
9、 其CRC。 o 解题步骤如下： 1、左移4位得1010000 2、模2除生成多项式得余数为：0011 3、生成传输码为：1010011CRC举例o 假如实际接收到的信息为：1010011 o 生成多项式为：11101 o 模2除生成多项式得余数为：0000，无错 o 假如实际接收到的信息为：1010111 o 生成多项式为：11101 o 模2除生成多项式得余数为：0100，有错CRC举例o 对于特定的生成多项式，通过计算可以得出不同 位出错时各自所对应的余数，列出一个余数与出 错位之间的对应关系，根据不同的余数即可确定 错误的位置。 o 若某位出错，则余数不为0，对此余数补零后继 续作模2除法，又得到一个不为0的余数。反复这 样，将得到一个循环的余数队列。所以称为循环 冗余校验码。 o 多位检错能力 o 一位纠错能力
