组成原理课程第二章(2011版)..ppt

* b)校验位的取值(偶校验为例) Hi 1 2 3 4 5 6 7 8 9 10 11 Pi 1 2 1,2 /b1 4 1,4 /b2 2,4 /b3 1,2,4 /b4 8 1,8 /b5 2,8 /b6 1,2,8 /b7 P1=b1? b2 ? b4 ? b5 ? b7 P2=b1? b3 ? b4 ? b6 ? b7 P3=b2 ? b3 ? b4 P4=b5 ? b6 ? b7 假设b1b2b3b4b5b6b7 = 1011000 则：P1= 1? 0 ?1 ? 0 ? 0 = 0 P2 = 1 ?1 ? 1 ? 0 ? 0=1 P3=0 ?1 ?1 = 0 P4=0 ? 0 ? 0 = 0 则H = 0 1 1 0 0 1 1 0 0 0 0 * c)指错、纠错原理 –指错字 P1= b1? b2 ? b4 ? b5 ? b7 P2= b1? b3 ? b4 ? b6 ? b7 P3=b2?b3 ? b4 P4=b5?b6 ? b7 则指错字由G4G3G2G1组成，其中： G4= P4 ? b5 ? b6 ? b7 G3 = P3 ? b2 ? b3 ? b4 G2= P2 ? b1? b3 ? b4 ? b6 ? b7 G1= P1 ? b1?b2 ? b4 ? b5 ? b7 上例中 发送方H = 0 1 1 0 0 1 1 0 0 0 0 如果接收到 H’ = 0 1 1 0 0 1 1 0 0 0 1 G4 = 0 ? 0 ? 0 ? 1 = 1 G3 = 0 ? 0 ? 1 ? 1 = 0 G2 = 1 ? 1 ? 1 ? 1 ? 0 ? 1 = 1 G1 = 0 ? 1 ? 0 ? 1 ? 0 ? 1 = 1 * G4G3G2G1= 1011 表明H11出错，改正该位的错误即可。 则错误字为： (5)海明校验的缺点 计算复杂 (6)关于扩展的海明编码(指出并纠正多位错误的海明编码)，请查阅相关资料。 * (1)CRC 是一种基于模2运算规则的校验码 ; (2)模2运算规则: a)加/减运算 (异或运算，或不带进位的加法，不带借位的减法) 0±0＝0，0±1＝1，1±0＝1，1±1＝0 b)乘法运算：按模2加求部分积之和 ，不进位 c)模2除法 ?按模2减,求部分余数，不借位。 ?上商原则是： ①部分余数首位为1时，商为1，减除数； ②部分余数首位为0时，商为0，减0； ③当部分余数的位数小于除数的位数时，该余数为最后余数。 8)循环冗余校验(Cyclic Redundancy Check) * ①部分余数首位为1时，商为1，减除数； ②部分余数首位为0时，商为0，减0； ③当部分余数的位数小于除数的位数时，该余数为最后余数。 * 3) CRC编码方法 (1)选择合适的生成多项式G(x),其最高位的权值r log2k,其中K为被校验信息的位数； 如K=4位时，r=3. (2)将待校验的二进制信息Q(X)逻辑左移r位,得到Q(X)’ (3)用Q(X)’ 按模2运算法则除G(x)，将得到的r位余数替换Q(X)’最后的r位，就得到Q(X)的CRC编码。 * 解： M(x)＝1100， r＝3 M(x)·23＝1100000 1100000 / 1011 按模2除法，得商Q(x)＝1110，余数R(x)＝010。 ∴ 该信息的CRC码 ：1100010 该CRC码称为(7,4）码 例8 求有效信息1100的CRC码，多项式G(x)＝1011。 * 4) CRC纠错 (1)检错 接收部件收到CRC码后，仍用约定的生成多项式G(x)去除收到的编码，若余数为0，表示传送正确；若余数不为0，表示出错，再由余数的值来确定哪一位出错，从而加以纠正。 * (2)纠错 ?不论错误出现在哪一位,均要通过将出错位循环左移到最左边的一位上被纠正；(定位) ?不为零的余数具有循环特性。 * ? CRC就是利用不为零余数的循环特性实现定位纠错并还原的 * 本 章 小 结 1)两类数据格式:定点与浮点(IEEE754为重点) 2)数值数据的机器数表示:以简单为线索,四类机器数 3)数据校验的基本原理 ?码距的概念 ?三类校验码的基本方法与特征 作业: 2.5 ,2.9(a),2.17,2.18 计算