海明码原理.pptVIP

海明码原理说明 海明码： 是由R·Hamming在1950年首次提出的，它也是一种可以纠正一位差错的编码，但它的编码效率要比正反码高得多（当信息位足够长时）。 基础知识： 二进制数表示 二进制逻辑运算 数的表示方法 奇偶校验 奇偶校验码； 若信息的位数为k＝n－1位，可表示为an-1an-2…a1，加上一位偶校验位a0，构成一个n位的码字an-1a n-2…a1 a0 。 在接收端校验时，可按下列关系式来计算： S= an-1+a n-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。 S2 S1 S0这三个校正因子其它4种编码值可用来区分a6a5a4a3一位错，该对应关系可以规定如表1．3 S2S1S0 000 001 010 100 011 101 110 111 错码位置 无 a0 a1 a2 a3 a4 a5 a6 由表可见， a2、a4、a5或a6的一位错都应使S2＝1，由此得到监督关系式： S2 ＝a2＋a4十a5十a6 同理还有： S1 ＝a1＋a3十a5十a6 S0 ＝a0＋a3十a4十a6 在发送端编码时，信息位a6a5a4和a3的值取决于输入信号，是随机值。冗余位a2a1和a0的值应根据信息位的取值按监督关系式来决定，便上述三式中的S2 S1 和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 已知信息位后，按此三式即可算出各冗余位。 在接收端收到每个码字后，按监督关系式算出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， 由表： S2S1S0 000 001 010 100 011 101 110 111 错码位置 无 a0 a1 a2 a3 a4 a5