海明码原理说明

海明码原理说明

海明码：是由R·Hamming在1950年首次提出的，它也是一种可以纠正一位差错的编码，但它的编码效率要比正反码高得多（当信息位足够长时）。基础知识：二进制数表示二进制逻辑运算数的表示方法奇偶校验奇偶校验码；若信息的位数为k＝n－1位，可表示为an-1an-2…a1，加上一位偶校验位a0，构成一个n位的码字an-1an-2…a1a0

。在接收端校验时，可按下列关系式来计算：

S=an-1+an-2+…a1+a0（a0

用以凑成偶数个“1”）结果：若S＝0，则无错，若S＝1，则有错。上式可称为监督关系式，S称为校正因子。在奇偶校验情况下，只有一个监督关系式，一个校正因子，其取值只有两种（0或l），分别代表了无错和有错两种情况，而不能指出差错所在的位置。可以增加冗余位，就相应地增加监督关系式和校正因子，就能区分更多的情况。例如，若有两个（2位）校正因子，则其取值就有4种可能：00、01、10或11，就能区分4种不同情况。若其中一种表示无错，另外三种不但可以用来指出有错，还可用来区分错误的情况，如指出是哪一位错等。一般而言，信息位为k位，增加r位冗余位，构成n＝k＋r位码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错，则要求：

2r≥n＋1或者2r≥k＋r＋1注:(n=k+r)如果用k＝4为例来说明，要满足上述不等式，则r＞3。假设取r＝3则n＝k＋r＝7，即在4位信息位a6a5a4a3后面加上3位冗余位a2a1a0，构成7位码字a6a5a4a3a2a1a0

。a2、

a1和a0分别由4位信息位中某几位半加得到。校验时，a2、

a1和a0

就分别和这些位半加构成三个不同的监督关系式。规定：无错时，这三个关系式的值S2、S1和S0全为“0”。若a2错，则S2＝1，而S1

＝S0＝0；若a1错，则S1＝1，而S2＝S0＝0；若a0错，则S0＝1，而S2＝S1＝0。S2S1S0这三个校正因子其它4种编码值可用来区分a6a5a4a3一位错，该对应关系可以规定如表1．3S2S1S0000

001

010100011101110111

错码位置 无a0a1a2a3a4a5a6由表可见，a2、a4、a5或a6的一位错都应使S2＝1，由此得到监督关系式：S2

＝a2＋a4十a5十a6同理还有：

S1

＝a1＋a3十a5十a6S0

＝a0＋a3十a4十a6在发送端编码时，信息位a6a5a4和a3的值取决于输入信号，是随机值。冗余位a2a1和a0的值应根据信息位的取值按监督关系式来决定，便上述三式中的S2S1

和S0

取值为零，即：

a2＋a4＋a5

＋a6

＝0 a1＋a3

＋a5

＋a6

＝0 a0

＋a3

＋a4

＋a6

＝0由此可求得：

a2＝a4十a5十a6 a1＝a3十a5十a6 a0＝a3十a4十a6已知信息位后，按此三式即可算出各冗余位。a6a5a4a3a2ala0a6a5a4a3a2ala00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111对于各种信息位算出的冗余位如表：在接收端收到每个码字后，按监督关系式算出S2、S1和S0，若全为“0”则认为无错。若不全为“0”，在一位错的情况下，可查表来判定是哪一位错，从而纠正之。例如码字0010101传输中发生一位错，在接收端收到的为0011101，代入监督关系式：

S2

＝a2＋a4十a5十a6 S1

＝a1＋a3十a5十a6 S0

＝a0＋a3十a4十a6可算得S2＝0、S1＝1和S0

＝1，由表：S2S1S0000

001

010100011101110111

错码位置 无a0a1a2a3a4a5a6可查得S2S1和S0

＝011对应于a3错，因而可将0011101纠正为0010101。上述海明码的编码效率为4／7。若K＝7，按2r≥k十r＋1可算得r至少为4，此时编码效率为7／11。结论：信息位长度越长时编码效率越高。照例海明码只能纠正一位错，若用下述方法排列可以纠正传输中出现的突发性错误。将连续P个码字排成一个矩阵，每行一个码字，如图所示 信息位冗余位

0001 011 1010 010 1011 001 0100 110 P个码字组成矩阵

0100 110 每