海明码的基本原理.docVIP

一、海明码的概念 海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式： 　　2^r=n+1 或 2^r=k+r+1 　　海明码的编码效率为： 　　R=k/(k+r) 　　式中 k为信息位位数 　　r为增加冗余位位数 二、海明码的原理 海明码是一种多重奇偶检错系统。它将信息用逻辑形式编码，以便能够检错和纠错。用在海明码中的全部传输码字是由原来的信息和附加的奇偶校验位组成的。每一个这种奇偶位被编在传输码字的特定位置上。这个系统对于错误的数位无论是原有信息位中的，还是附加校验位中的都能指示出来 在数据中间加入几个校验码，将玛距均匀拉大，将数据的每个二进制位分配在几个奇偶校验组里，当某一位出错，会引起几个校验位的值发生变化。 　　海明不等式： 　　校验码个数为K，2的K次幂个信息，1个信息用来指出“没有错误”，其余2K-1个指出错误发生在那一位，但也可能是校验位错误，故有N=2的K次-1-K能被校验。 　　海明码的编码规则： 　　1.每个校验位Ri被分配在海明码的第2的i次的位置上， 　　2.海明玛的每一位（Hi)是由多个/1个校验值进行校验的，被校验玛的 　　位置玛是所有校验这位的校验位位置玛之和。 　　一个例题： 　　4个数据位d0,d1,d2,d3, 3个校验位r0,r1,r2，对应的位置为： 　　d3 d2 d1 r2 d0 r1 r0 ======b7 b6 b5 b4 b3 b2 b1 　　校验位的取值，就是他所能校验的数据位的异或 　　b1为b3,b5,b7的异或，b2为b3,b6,b7 b4为b5,b6,b7 　　海明玛传送到接受方后，将上三式的右边（b1,b2,b4)的逻辑表达式分别 　　异或上左边的值就得到了校验方程，如果上题采用偶校验 　　G1=b1 b3 b5 b7的异或 　　G2=b2 b3 b6 b7的异或 　　G3=b4 b5 b6 b7的异或 　　若G1G2G3为001是第四位错 　　若为011是第六位错 三、编码步骤 　　(1)根据信息位数，确定校验位数，2^r = k+r+1，其中，k为信息位数，r为校验位数。求出满足不等式的最小r，即为校验位数。 　　(2)计算机校验位公式。 　　表1-3 校验位公式表 … 12 11 10 9 8 7 6 5 4 3 2 1 位数 … I8 I7 I6 I5 ? I4 I3 I2 ? I1 ? ? 信息位 … ? ? ? ? r3 ? ? ? r2 ? r1 r0 校验位 　　表1-3其实可以当成一个公式来套用，如有已经编码的数据 1100 1001 0111。我们只需把这些数据填充到校验公式，即可得到信息位与校验位。填充的方法是这样的，首先看数据的最低位(即右边第1位)，最低位为1，把1填充在公式表的r0位置，接着取出数据的次低位数据(即右边第2位)，把它填充到r1位置，把右边第3位数填充到I1位置。依此类推，我们可以得到表1-4。 　　表1-4 校验位公式实例表 … 12 11 10 9 8 7 6 5 4 3 2 1 位数 … 1 1 0 0 ? 0 0 1 ? 1 ? ? 信息位 … ? ? ? ? 1 ? ? ? 0 ? 1 1 校验位 　　表中第2行数据为1100 001 1，这就是数据1100 1001 0111的编码信息，而表格第3行是1 011，这便是校验位。 　　注意： n?校验位rn 所在位数为2^n，其余由信息位填充; n?信息位下标从1开始，而校验位下标从0开始。 　　例如：I8 对应的第十二位12=2^3+2^2，I7对应的第十一位11=2^3+2^1+2^0，I6 对应的第十位10=2^3+2^1，I5 对应的第九位9=2^3+2^0，一直写到I1对应的第三位。 　　校验位rn 由前面位数写成2的幂之和中包含2^n 的位数对应的信息位之和构成 　　例如： r3=I8⊕I7⊕ I6⊕ I5 　　(3)求校验位。根据上面我们所说的计算公式可以求出校验位。 　　(4)求海明码。根据上面的表格填充后，写出海明码。 四、纠错步骤 1)??????? 根据海明码的信息位和校验位的分布规则，找出接收到的数据的信息位以及校验位。 　　表1-5校验位公式表 … 12 11 10 9 8 7 6 5 4 3 2 1 位数 … I8 I7 I6 I5 ? I4 I3 I2 ? I1 ? ? 信息位 … ? ? ? ? r3 ? ? ? r2 ? r1 r0 校验位 　　如有已经编码的数据 1100 1001 0111，则可以根据上表得到编码的信息为：1