海明码的基本原理.doc

一、海明码的概念一、海明码的概念海明码是一种可以纠正一位差错的编码它是利用在信息位为 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= k+r+1，其中，k 为信息位数，r 为校验位数。

求出满足不等式的最小 r，即为校验位数2)计算机校验位公式表 1-3 校验位公式表…121110987654321位数…I8I7I6I5 I4I3I2 I1 信息位… r3 r2 r1r0校验位表 1-3 其实可以当成一个公式来套用，如有已经编码的数据 1100 1001 0111我们只需把这些数据填充到校验公式，即可得到信息位与校验位填充的方法是这样的，首先看数据的最低位(即右边第 1 位)，最低位为 1，把 1 填充在公式表的 r0 位置，接着取出数据的次低位数据(即右边第 2 位)，把它填充到 r1 位置，把右边第 3 位数填充到 I1 位置依此类推，我们可以得到表 1-4表 1-4 校验位公式实例表…121110987654321位数…1100 001 1 信息位… 1 0 11校验位表中第 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 校验位公式表…121110987654321位数…I8I7I6I5 I4I3I2 I1 信息位… r3 r2 r1r0校验位如有已经编码的数据 1100 1001 0111，则可以根据上表得到编码的信息为：1100 001 1;校验位为：1 011，详细过程在“编码步骤”已详细说明2) 接收端对校验位进行验证Sn= rn (校验) ⊕rn (接收)3) 判断校正因子是否有错，并改正Sn Sn-1 Sn-2……S0 二进制对应的是那位就是那位出错，将其改正完成纠错如 1001 为第九位，将第九位 1 变 0 (或 0 变 1) 即可海明码看似很复杂，但大家要细心研究，便会得到很多东西海明码看似很复杂，但大家要细心研究，便会得到很多东西。