海明码的原理

Question

如题所述

Answer 1

海明码是一种可以纠正一位差错的编码。它是利用在信息位为k位，增加r位冗余位，构成一个n=k+r位的码字，然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错。它必需满足以下关系式： r 2^r ≥ k r 1 或 2^r ≥ n 1海明码的编码效率为： R=k/(k+r) 式中 k为信息位位数 r为增加冗余位位数

目录

1.海明码的原理
2.海明码的生成与接收
3.海明码的计算
4.海明码校验程序设计原理分析参考

编辑本段1.海明码的原理
　　在数据中间加入几个校验码，码距均匀拉大，将数据的每个二进制位分配在几个奇偶校验组里，当某一位出错，会引起几个校验位的值发生变化。
　　海明不等式：
　　校验码个数为K，2的K次方个信息，1个信息用来指出“没有错误”，其余（2^K)-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
　　海明v传送到接受方后，将上三式的右边（b1,b2,b4)的逻辑表达式分别
　　异或上左边的值就得到了校验方程，如果上题采用偶校验
　　G1=b1 b3 b5 b7的异或
　　G2=b2 b3 b6 b7的异或
　　G3=b4 b5 b6 b7的异或
　　若G1G2G3为001是第一位错
　　若为011是第三位错
编辑本段2.海明码的生成与接收
　　特注：以下的+均代表异或
　　方法一：
　　1)海明码的生成。
　　例1.已知：信息码为："0010"。海明码的监督关系式为：
　　S2=a2+a4+a5+a6
　　S1=a1+a3+a5+a6
　　S0=a0+a3+a4+a6
　　求：海明码码字。
　　解：1)由监督关系式知冗余码为a2a1a0。
　　2)冗余码与信息码合成的海明码是："0010a2a1a0"。
　　设S2=S1=S0=0,由监督关系式得：
　　异或运算：
　　a2=a4+a5+a6=1
　　a1=a3+a5+a6=0
　　a0=a3+a4+a6=1
　　因此，海明码码字为："0010101"
　　对以上这道题目的第二问的疑问：
　　冗余码与信息码合成的海明码是："0010a2a1a0"。为什么a2a1a0直接加在信息码后面，而不是按照1,2,4,8位的顺序加在信息码后面【例如：001(a2)0(a1)(a0)=0011001】
　　2)海明码的接收。
　　例2.已知：海明码的监督关系式为：
　　S2=a2+a4+a5+a6
　　S1=a1+a3+a5+a6
　　S0=a0+a3+a4+a6
　　接收码字为："0011101"(n=7)
　　求：发送端的信息码。
　　解：1)由海明码的监督关系式计算得S2S1S0=011。
　　2)由监督关系式可构造出下面错码位置关系表：
　　S2S1S0
　　000
　　001
　　010
　　100
　　011
　　101
　　110
　　111
　　错码位置
　　无错
　　a0
　　a1
　　a2
　　a3
　　a4
　　a5
　　a6
　　3)由S2S1S0=011查表得知错码位置是a3。
　　4)纠错--对码字的a3位取反得正确码字："0 0 1 0 1 0 1"
　　5)把冗余码a2a1a0删除得发送端的信息码："0010"
　　方法二：(不用查表，方便编程)
　　1)海明码的生成（顺序生成法）。
　　例3.已知：信息码为：" 1 1 0 0 1 1 0 0 " (k=4代表冗余位数，即校验码位数)
　　求：海明码码字。
　　解：1)把冗余码A、B、C、…，顺序插入信息码中，得海明码
　　码字:" A B 1 C 1 0 0 D 1 1 0 0 "
　　码位: 1 2 3 4 5 6 7 8 9 10 11 12
　　其中A,B,C,D分别插于2的k次方位(k=0,1,2,3)。码位分别为1,2,4,8。
　　2)冗余码A,B,C,D的线性码位是：(相当于监督关系式)
　　监督关系式的推导：
　　D C B A
　　1 0 0 0 1
　　2 0 0 1 0
　　3 0 0 1 1
　　4 0 1 0 0
　　5 0 1 0 1
　　6 0 1 1 0
　　7 0 1 1 1
　　8 1 0 0 0
　　9 1 0 0 1
　　10 1 0 1 0
　　11 1 0 1 1
　　12 1 1 0 0
　　根据上面表格得到 A B C D
　　需要说明的是公式中参与计算的是表格中出现"1"的那个位 右边是数据位的二进制数,公式中的"+"表示异或
　　故此有如下表达式：
　　A->1,3,5,7,9,11；(这里的1 3 5 7 9 11均为A那一列出现1的位)
　　B->2,3,6,7,10,11；
　　C->4,5,6,7,12；(注 5=4+1；6=4+2；7=4+2+1；12=8+4)
　　D->8,9,10,11,12。
　　3)把线性码位的值的偶校验作为冗余码的值(设冗余码初值为0)：
　　A=∑(0,1,1,0,1,0)=1
　　B=∑(0,1,0,0,1,0)=0
　　C=∑(0,1,0,0,0) =1
　　D=∑(0,1,1,0,0) =0
　　4)海明码为:"1 0 1 1 1 0 0 0 1 1 0 0"
　　2)海明码的接收。
　　例4.已知：接收的码字为："1 0 0 1 1 0 0 0 1 1 0 0"(k=4代表冗余位数，即校验码位数)
　　求：发送端的信息码。
　　解：1)设错误累加器(err)初值=0
　　2)求出冗余码的偶校验和，并按码位累加到err中：
　　A=∑(1,0,1,0,1,0)=1 err=err+2^0=1
　　B=∑(0,0,0,0,1,0)=1 err=err+2^1=3
　　C=∑(1,1,0,0,0) =0 err=err+0 =3
　　D=∑(0,1,1,0,0) =0 err=err+0 =3
　　由err≠0可知接收码字有错，
　　3)码字的错误位置就是错误累加器(err)的值3。
　　4)纠错--对码字的第3位值取反得正确码字：
　　"1 0 1 1 1 0 0 0 1 1 0 0"
　　5)把位于2的k次方位的冗余码删除得信息码："1 1 0 0 1 1 0 0"
编辑本段3.海明码的计算
　　海明码(Hamming Code )编码的关键是使用多余的奇偶校验位来识别一位错误。
　　码字(Code Word) 按如下方法构建：
　　1、把所有2的幂次方的数据位标记为奇偶校验位(编号为1, 2, 4, 8, 16, 32, 64等的位置)
　　2、其他数据位用于待编码数据. (编号为3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17等的位置)
　　3、每个奇偶校验位的值代表了代码字中部分数据位的奇偶性，其所在位置决定了要校验和跳过的比特位顺序。
　　位置1：校验1位，跳过1位，校验1位，跳过1位(1,3,5,7,9,11,13,15,…)
　　位置2：校验2位，跳过2位，校验2位，跳过2位 (2,3,6,7,10,11,14,15,…)
　　位置4：校验4位，跳过4位，校验4位，跳过4位 (4,5,6,7,12,13,14,15,20,21,22,23,…)
　　位置8：校验8位，跳过8位，校验8位，跳过8位(8-15,24-31,40-47,…)
　　…
　　如果全部校验的位置中有奇数个1，把该奇偶校验位置为1；如果全部校验的位置中有偶数个1，把该奇偶校验位置为0.
　　举例说明：
　　一个字节的数据：10011010
　　构造数据字(Data Word),对应的校验位留空_ _ 1 _ 0 0 1 _ 1 0 1 0
　　计算每个校验位的奇偶性 ( ?代表要设置的比特位):
　　位置1检查1,3,5,7,9,11:
　　? _ 1 _ 0 0 1 _ 1 0 1 0. 偶数个1，因此位置1设为0，即: 0 _ 1 _ 0 0 1 _ 1 0 1 0
　　位置2检查2,3,6,7,10,11:
　　0 ? 1 _ 0 0 1 _ 1 0 1 0. 奇数个1，因此位置2设为1，即: 0 1 1 _ 0 0 1 _ 1 0 1 0
　　位置4检查4,5,6,7,12:
　　0 1 1 ? 0 0 1 _ 1 0 1 0. 奇数个1，因此位置4设为1，即: 0 1 1 1 0 0 1 _ 1 0 1 0
　　位置8检查8,9,10,11,12:
　　0 1 1 1 0 0 1 ? 1 0 1 0. 偶数个1，因此位置8设为0，即: 0 1 1 1 0 0 1 0 1 0 1 0
　　因此码字为: 011100101010.
　　查找并纠错一位错误
　　上例中构建了一个码字 011100101010，假定实际接收到的数据是011100101110. 则接收方可以计算出哪一位出错并对其进行更正。方法就是验证每一个校验位。记下所有出错的校验位，可以发现校验位2和8的数据不正确. 错误校验位 2 + 8 = 10, 则位置10的数据出错。一般说来，对所有校验位进行检查, 将所有出错的校验位置相加, 得到的就是错误信息所在的位置.
编辑本段4.海明码校验程序设计原理分析参考
　　海明码校验是为了保证数据传输正确而提出的，本来就是一串要传送的数据，如：D7,D6,D5,D4,D3,D2,D1,D0，这里举的是八位数据，可以是n位数据。就这样传送数据，不知道接收到后是不是正确的。所以，要加入校验位数据才能检查是否出错。这里涉及到一个问题，要多少位校验数据才能查出错误呢？
　　我们只要能检测出一位出错，则对于8位信息数据，校验位为4位。满足下列条件：2的k次方大于等于n+k+1，其中k为校验位位数，n为信息数据位位数。验证一下，2的4次方等于16，n+k+1等于8+4+1等于13。 8位信息数据与4位校验位总共有12位数据，怎么排列呢？我们先把校验位按P4,P3,P2,P1排列，用通式Pi表示校验位序列，i为校验位在校验序列中的位置。 传送的数据流用M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1表示，接下来的问题是如何用D7,D6,D5,D4,D3,D2,D1,D0与P4,P3,P2,P1来表M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1了。校验位在传送的数据流中位置为2的i－1次方，则P1在M1位，P2在M2位，P3在M4位，P4在M8位。其余的用信息数据从高到低插入。 传送的数据流为D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1。 接下来，我们要弄明白如何找出错误位的问题。引进4位校验和序列S4,S3,S2,S1。S4,S3,S2,S1等于0,0,0,0表示传送的数据流正确；如S4,S3,S2,S1等于0,0,1,0则表示传送的数据流中第2位出错；如S4,S3,S2,S1等于0,0,1,1则表示传送的数据流中第3位出错；依次类推。
　　用M12,M11,M10,M9,M8,M7,M6,M5,M4,M3,M2,M1如何表示S4,S3,S2,S1呢，简单的方法就是S1=1时，S4,S3,S2从0,0,0到1,1,1的所有的Mx异或。即S1等于M1异或M3异或M5异或M7异或M9异或M11。也就是S1等于P1异或D0异或D1异或D3异或D4异或D6。S2=1时，S4,S3,S1从0,0,0到1,1,1的所有的Mx异或。即S2等于M2异或M3异或M6异或M7异或M10异或M11。S3=1时，S4,S2,S1从0,0,0到1,1,1的所有的Mx异或。即S3等于M4异或M5异或M6异或M7异或M12。S4=1时，S3,S2,S1从0,0,0到1,1,1的所有的Mx异或。即S4等于M8异或M9异或M10异或M11异或M12。这样，对于一串码流，知道几位校验位，可以很快确定哪一位出错。而在发送端，可以根据S4,S3,S2,S1的表达式求出P4,P3,P2,P1的表达式，只要把式子右边的P4或P3或P2或P1移到左边替换掉S4或S3或S2或S1就可以了。面举例说明：用^表示异或
　　D7,D6,D5,D4,D3,D2,D1,D0=11010001
　　S4=M8^M9^M10^M11^M12=D7^D6^D5^D4^P4; P4=D7^D6^D5^D4;
　　S3=M4^M5^M6^M7^M12 =D7^D3^D2^D1^P3; P3=D7^D3^D2^D1;
　　S2=M2^M3^M6^M7^M10^M11 =D6^D5^D3^D2^D0^P2; P2=D6^D5^D3^D2^D0;
　　S1=M1^M3^M5^M7^M9^M11=D6^D4^D3^D1^D0^P1; P1=D6^D4^D3^D1^D0;
　　所以，
　　P4=D7^D6^D5^D4=1^1^0^1=1
　　P3=D7^D3^D2^D1=1^0^0^0=1
　　P2= D6^D5^D3^D2^D0=1^0^0^0^1=0 P1=D6^D4^D3^D1^D0=1^1^0^0^1=1
　　故，传送码流为D7,D6,D5,D4,P4,D3,D2,D1,P3,D0,P2,P1等于
　　110110001101
　　若接收端收到110110001101，则
　　S4=M8^M9^M10^M11^M12=1^1^0^1^1=0
　　S3=M4^M5^M6^M7^M12=1^0^0^0^1=0
　　S2=M2^M3^M6^M7^M10^M11=0^1^0^0^0^1=0
　　S1=M1^M3^M5^M7^M9^M11=1^1^0^0^1^1=0
　　故，接收码流正确。
　　若M6出错，由0变为1。则
　　S4=M8^M9^M10^M11^M12=1^1^0^1^1=0
　　S3=M4^M5^M6^M7^M12=1^0^1^0^1=1
　　S2=M2^M3^M6^M7^M10^M11=0^1^1^0^0^1=1 S1=M1^M3^M5^M7^M9^M11=1^1^0^0^1^1=0
　　即S4S3S2S1=0110，此为十进制的6，说明第六位出错，也就是M6出错。完全符合。
　　5.海明码的表格计算
　　如果对于m位的数据，增加k位冗余位，则组成位n=m+k位的纠错码。对于2^m个有效码字中的每一个，都有n个无效但可以纠错的码字。这些可纠错的码字与有效码字的距离是1，含单个错误位。这样，对于一个有效的消息总共有n+1个可识别的码字。这n+1个码字相对于其他2^m-1个有效消息的距离都大于1。这意味着总共有2^m（n+1）个有效的或是可纠错的码字。显然这个数应小于等于码字的所有的可能的个数2^n。于是我们有
　　2^m（n+1）<2^n
　　因为n=m+k，我们得出
　　m+k+1<2^k
　　对于给定的数据位m，上式给出了k的下界，即要纠正单个错误，k必须取最小的值。海明建议了一种方案，可以达到这个下界，并能直接指出错在哪一位。首先把码字的位从1到n编号，，并把这个编号表示成二进制数，即2的幂之和。然后对2的每一个幂设置一个奇偶位。例如对于6号位，由于6=110（二进制），所以6号位参加第2位和第4位的奇偶校验，而不参加第1位奇偶校验。类似的9号位参加第1位和第8位的奇偶校验而不参加第2位和第4位的奇偶校验。海明把奇偶校验分配在1,2,4,8等位置上，其他位置放数据。下面根据海明编码的例图，举例说明编码的方法
海明编码的例

海明编码的例
　　例如传送的消息为：1001011
　　我们把数据放在3,5,6,7,9,10,11等位置上，1,2,4,8则为校验位。
　　

1
0 0 1
0 1 1
　1 2 3 4 5 6 7 8 9 10 11
　　根据海明编码的例，3、5、7、9、11的二进制编码的第一位为1，所以3、5、7、9、11号位参加第一位校验位，若按偶校验计算，1号位应为1
　　
1
1
0 0 1
0 1 1
　1 2 3 4 5 6 7 8 9 10 11
　　类似的，3、6、7、10、11号位参加2号位校验，5、6、7号位参加4号位校验，9、10、11号位参加8号位校验，全部按偶校验计算，最终得到如下结果
　　
1 0 1 1 0 0 1 0 0 1 1
　1 2 3 4 5 6 7 8 9 10 11
　　如果这个码字传输中有错误，比如说6号位出错。就会变成
　　√ ╳ ╳ √
　　
1 0 1 1 0 1 1 0 0 1 1
　1 2 3 4 5 6 7 8 9 10 11
　　当接收端按照同样的规则计算奇偶位时，就会发现1号位和8号位的奇偶性正确而2号位和4号位的奇偶性不对，于是2+4=6,，立即可以判断错在6号位。
　　上例中k=4，因而m<2^4-4-1=11,即数据位可以用到11位，共组成15位的码字，可检测出单个位置的错误。

Answer 2

海明码校验位数与信息验位数关系

海明码简单的说就是对数据进行检验和纠错时按照图中的规则理解就好了。比如，需要检验/纠错8位数据时需要4位校验码。