海明码的原理

海明码编码及校验原理详析~

纠错码——海明码
如果传输的数据位是m位，加了r位冗余位，那么总共传输的数据单元是m+r位。
为了能够发现这m+r位数据单元在传输到目的端后是否出错，并能够指明是在哪一位出错，那么r至少应该能够代表m+r+1种状态。r比特能够代表2r不同状态。
因此，2r>=m+r+1
若m=7，则满足上式的最小r值为：4。

海明码的纠错原理
海明码的接收端的公式:
S3= P3⊕ D4⊕D3 ⊕D2
S2= P2⊕D4 ⊕D3 ⊕D1
S1= P1⊕D4 ⊕D2 ⊕D1
假定 海明码1010101在传送中变成了1000101
S3= P3⊕ D4⊕D3 ⊕D2=0⊕1⊕0 ⊕0 =1
S2= P2⊕D4 ⊕D3 ⊕D1=0⊕1⊕ 0 ⊕1=0
S1= P1⊕D4 ⊕D2 ⊕D1=1⊕1⊕ 0 ⊕1=1
因此,由S3S2S1= 101,指出第5位错,应由0变1

首先从海明码的校验位说起，8位二进制，应当设置8+r<=(2^r)-1位，也就是最少4个，分别第一第二第四第八位（2^(r-1)），生成码的排列顺序为P1、P2、A1、P3、A2、A3、A4、P4、A5、A6、A7、A8（这个你应该明白是什么意思，书上讲的很清楚），所谓的校验码，即是求出P1 P2 P3 P4，而对于原来的数据保持不变，第6位第7位，是A3、A4，从你给出的数据看正好是1和0

海明码是一种可以纠正一位差错的编码。它是利用在信息位为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位的码字，可检测出单个位置的错误。

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

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

---

奉节县19334963128： 海明码编码及校验原理详析 - ？
墨婷盐酸： 纠错码——海明码 如果传输的数据位是m位,加了r位冗余位,那么总共传输的数据单元是m+r位. 为了能够发现这m+r位数据单元在传输到目的端后是否出错,并能够指明是在哪一位出错,那么r至少应该能够代表m+r+1种状态.r比特能够代表2...

奉节县19334963128： 什么是海明码呀?通俗一点,但又能深刻一点!谢谢了!!! - ？
墨婷盐酸： 海明码其实也不难,相对于寄偶检验码 它不仅可以检验出错误,还能修正错误!但只能是检验、修正一位错误!说一大堆理论是没什么意思,下面将通过一个例子,尽可能的用最通俗易懂的方式进行讲解!最后大家会发现海明码很神奇!! 假...

奉节县19334963128： 怎么理解海明码? - ？
墨婷盐酸： 海明码是一种可以纠正一位差错的编码.它是利用在信息位为k位,增加r位冗余位,构成一个n=k+r位的码字,然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错

奉节县19334963128： 求教海明码 - ？
墨婷盐酸： 再学学哦 1.海明码的概念海明码是一种可以纠正一位差错的编码.它是利用在信息位为k位,增加r位冗余位,构成一个n=k+r位的码字,然后用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错.它必需满足以下关...

奉节县19334963128： 100分求高手讲解海明码! - ？
墨婷盐酸： 海明码是一位纠错码,即如果数据在传输过程中有一位出错,则可以知道出错的位数并通过取反将其改正过来.e68a84e799bee5baa6e79fa5e9819331333236393735 海明码的基本意思是给传输的数据增加r个校验位,从而增加两个合法消息(...

奉节县19334963128： 海明码是如何编码的? - ？
墨婷盐酸： 楼上的说的是海明距离,也叫码距.海明码是怎么编码的在这里是说不清楚,举个简单的例子.信息为1110,求它的海明码.首先我们知道数据位是4,根据数据位+冗余位(n)+1小于等于2的n次方,可以得出校验位为3.假设数据位1111对应b1b2b3b4,校验位分别是a1a2a4.又因为校验位在2的幂次位上,所以海明码为a1a2b1a4b2b3b4. a1=b1+b2+b4=1+1+0=0 a2=b1+b3+b4=1+1+0=0 a4=b2+b3+b4=1+1+0=0 所以海明码为0010110

奉节县19334963128： 什么是海明码的配偶原则??? - ？
墨婷盐酸： 海明码是由Richard Hanming于1950年提出的,它具有一位纠错能力. 由编码纠错理论得知,任何一种编码是否具有检测能力和纠错能力,都与编码的最小距离有关.所谓编码最小距离是指在一种编码系统中,任意两组合法代码之间的最少二...

奉节县19334963128： 详细的解释海明码是怎么用的 - ？
墨婷盐酸： 海明码的编码规则: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 校验位的取值,就是他所能校验的数据位的异或

奉节县19334963128： 计算机组成原理中 汉明码的应用 - ？
墨婷盐酸： 这题中若在第六位出错是说假设传输时第六位由0变成了1,即变成10100111101,前面课本不是讲怎么纠错了嘛,算出P8P4P2P1,是0110,十进制是六,即表示第六位出错,不知这样说你明白没?

奉节县19334963128： 计算机组成 海明码问题,P1=D0 xor D1 xor D3 xor D4 xor D6 为什么这样求海明校验码海明码也是利用奇偶性来校验数据的.它是一种多重奇偶校验检错系统... - ？
墨婷盐酸：[答案] p1处在第一个位置,所以位置码是0001,只要后面的数据位的位置码的最低位是1的都异或起来.比如说D0位置号是3也就是0011,D1位置号是5也就是0101,D3位置号是7也就是0111,D4位置号是9也就是1001,D6位置号是11也就是1011,...