chapter 2-计算机中的数据表示方法.ppt

* (3)具有指出并纠正一位错误的海明校验需要的位数 设有r位校验位，共能表示2r种不同的状态，用一种状态表 示无差错，剩余的可以表示2r -1种错误，由于差错可能出 现在数据位和校验位，因此必须满足： 2r - 1 = k + r （k — 数据位的位数； r — 校验位的位数） ?校验位在海明码中的分布规则： k+r位海明码中，校验位Pi分布在海明码的H2i-1 位上，i=1...r 二、校验码 * (4)海明码的形成方法 海明码位号 Hj 1 2 3 4 5 6 7 8 9 10 11 P和b的分布 P1 P2 b1 P3 b2 b3 b4 P4 b5 b6 b7 a)分组原则： ?确定海明码每位数据位所用的校验位 Hi 1 2 3 4 5 6 7 8 9 10 11 Pi 1 2 1,2 4 1,4 2,4 1,2,4 8 1,8 2,8 1,2,8 ?根据每个校验位校验的位分组： P1:H3,H5,H7,H9,H11 P2:H3,H6,H7,H10,H11 P3: H5,H6,H7 P4: H9,H10,H11 二、校验码 * 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)循环冗余校验（CRC，Cyclic Redundancy Check） 二、校验码 * ①部分余数首位为1时，商为1，减除数； ②部分余数首位为0时，商为0，减0； ③当部分余数的位数小于除数的位数时，该余数为最后余数。 二、校验码 * 3) CRC编码方法 (1)选择合适的生成多项式G(x),其最高位的权值r log2K，其中K为被校验信息的位数；如K=4位时，r=3。 (2)