有关海明码问题的探讨

作者简介：田华，（1980年--）女，山东德州人，烟台南山学院软件工程学院，教师。1有关海明码问题的探讨田华遇广修（烟台南山学院软件工程学院，山东龙口265706）摘要：海明码是一种多重奇偶检错系统。它将信息用逻辑形式编码，以便能够检错和纠错。用在海明码中的全部传输码字是由原来的信息和附加的奇偶校验位组成的。每一个这种奇偶位被编在传输码字的特定位置上。这个系统对于错误的数位无论是原有信息位中的，还是附加校验位中的都能指示出来。关键词：海明码，码距，校验方法Abstract:Hammingcodeisamultipleparityerror-detectingsystem,whichencodedatalogicallysoastodetectandcorrecterrors.AllcodewordstransmittedinHammingcodeareoriginaldatawithparitycheckdigitsappendedtotheend.Everysuchparitydigitisencodedonaparticularpositioninthecodewordsbeingtransmitted.Hammingcodeiscapableofindicatingincorrectdigitsbothinoriginaldataandinappendedcheckdigits.Keywords:Hammingcode,codedistance,meansofchecking海明码是由R.Hamming在1950年提出的，是一种可以纠错的编码。用在海明码中的全部传输码字是由原来的信息和附加的奇偶校验位组成的。每一个这种奇偶位被编在传输码字的特定位置上。这个系统对于错误的数位无论是原有信息位中的，还是附加校验位中的都能指示出来。海明码的纠错能力和最小码距有关。一、码距一个编码系统中任意两个合法编码之间不同的二进制位数叫这两个码字的码距，而整个编码系统中任意两个码字的最小码距就是该编码系统的码距。如图1所示的一个编码系统，用三位二进制来表示八个不同信息。在这个系统中，两个码字之间不同的位数从1到3不等，但最小值为1，故这个系统的码距为1。如果任何码字中一位或多位出了差错，结果这个码字就不能与其它码字区分。例如，如果传送信息001，而被误收为011，因011仍是表中的合法码字，接收方仍将认为011是正确的信息。但是，如果用四个二进数字来编8个码字，那么在码字间的最小距离可以增加到2，如图2的表中所示。图1图2注意，图2的8个码字相互间最少有两位的差异。因此，如果任何码字的一个数位出差错，就成为一个不用的码字，就能检查出来。例如信息是1001，误收为1011，接收方知道发生了一个差错，因为1011表中没有，不是一个码字。然而，差错不能被纠正。因为，正确码字可以是1001，1111，0011或1010。信息序号二进码字a3a2a1a00000011001210103001141100501016011071111信息序号二进码字a2a1a000001001201030114100510161107111作者简介：田华，（1980年--）女，山东德州人，烟台南山学院软件工程学院，教师。2接收方不能确定原来到底是这4个码字中的哪一个。同时，在这个系统中，偶数个（2位或4位）差错也无法发现。为了使一个系统能纠正一位差错，码距最小是3。最小距离为3时，或能纠正一位错，或能检测二位错，但不能同时纠正一位错并检测二位错。编码信息纠错和检错能力的提高需要进一步增大编码系统的码距。图3的表概括了编码系统的码距为1至7时，码的纠错和检错能力。在海明码系统中有关系：L-1=C+D。其中L为码距，D为可以检测出的错误位数，C为可以纠正的错误位数，并且有D≥C。码距码能力检错纠错123456700102或12并12并23并23并3图3由此可见，码距越大，纠错能力越强，但数据冗余也越大，即编码效率低了。所以，选择码距要取决于特定系统的要求。数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素。二、海明码海明码的基本思想：在k个信息位上加r个冗余位，构成n=k+r位的码字，其中每个冗余位和某几个特定的信息位构成偶校验的关系。接收端对这r个偶关系进行校验，即将每个冗余位与它关联的信息位进行异或加，相异或地结果称为校正因子。如果没有错的话，这r个校正因子都为0；如果有一个错则校正因子不会全为0，根据校正因子的不同取值，可以知道错误发生在码字的哪一个位置上。海明码的构造方法：1、r与k满足以下关系式：2r≥k+r+1;2、确定信息位与冗余位的位置关系；2i（i=0，1…i）的位置上放ri，其余位置上放Ij(j=1,..j)；3、找出冗余位与信息位的校验关系。三、海明码使用实例以k=4为例，来构造海明码。要满足上述不等式，则有r≥3,取r=3，于是n=k+r=7。下面以7比特的海明码为例，介绍海明码的构造方法及校验方法。按照上述方法确定信息位与冗余位的位置关系，如下：I4I3I2r2I1r1r07654321将每个信息位的位置写成用2的幂次之和的形式，即7=22+21+206=22+215=22+203=21+20作者简介：田华，（1980年--）女，山东德州人，烟台南山学院软件工程学院，教师。3从上式可得，I4要参与r2,r1和r0的生成，I3参与r2和r1的生成，I2参与r2,r0的生成，I1参与r1和r0的生成。即r2和I4，I3，I2构成偶校验；r1和I4，I3，I1构成偶校验；r0和I4，I2，I1构成校验；于是有以下公式：r2=I4+I3+I2r1=I4+I3+I1r0=I4+I2+I1于是，接收端使用以下关系式对这三个偶校验关系进行验证：s2=r2+I4+I3+I2s1=r1+I4+I3+I1s0=r0+I4+I2+I1其中s2，s1，s0称为校正因子。若没有错，三个校正因子都为0，若不全为0，则有错误发生，错误的位置在S=S2S1S0处，将该位取反即得到正确的数据。例：海明码中信息位为7位，接收端收到的码字为11110111011，请问此码字是否出错，并求发送端发送的信息位。解：因为k=7，n=11，所以r=4，信息位与冗余位的位置如下：I7I6I5r3I4I3I2r2I1r1r0111098765432111101101111由此可得：I7=r3+r1+r0I6=r3+r1I5=r3+r0I4=r2+r1+r0I3=r2+r1I2=r2+r0I1=r1+r0于是得到每个冗余位与某几个信息位的关系：r3=I7+I6+I5r2=I4+I3+I2r1=I7+I6+I4+I3+I1r0=I7+I5+I4+I2+I1从而得校正因子如下：s3=r3+I7+I6+I5s2=r2+I4+I3+I2s1=r1+I7+I6+I4+I3+I1s0=r0+I7+I5+I4+I2+I1将各位代入以上各式可得：s=s3s2s1s0=0100因此该码字出错，错误的位置在第4位。即r2错，于是得到正确的码字为：11110110011发送端发送的信息位为：1110110。四、结束语总之，海明码是一种多重奇偶检错系统。它将信息用逻辑形式编码，以便能够检错和纠错。若海明码的码长为7，信息位为4，则称为7—4海明码，编码效率为4/7；若海明码码长为11，可得信息位为7，称为11—7海明码，编码效率为7/11；所以，信息位越长，编码效率越高。参考文献冯博琴主编：《计算机网络与通信》，经济科学出版社，2000年