已知海明码的监督关系式为：S2=a2+a3+a4+a6 S1=a1+a4+a5+a6 S0=a0+a3+a4+a5

海明码的原理~

海明码是一种可以纠正一位差错的编码。它是利用在信息位为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
001
011
　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
001
011
　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号位校验，全部按偶校验计算，最终得到如下结果
　　
10110010011
　1 2 3 4 5 6 7 8 9 10 11
　　如果这个码字传输中有错误，比如说6号位出错。就会变成
　　√ ╳ ╳ √
　　
10110110011
　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位的码字，可检测出单个位置的错误。

错码位置 无错 a0 a1 a2 a3 a4 a5 a6

.(1)根据海明码的监督关系式

S2=a2+a3+a4+a6

S1=a1+a4+a5+a6

S0=a0+a3+a4+a5，得下表：

S2S1S0
000
001
010
011
100
101
110
111

错误位置
无错
a0
A1
a5
a2
a3
a6
a4

(2)将a6a5a4a3a2a1a0=1010100分别代入海明码的监督关系式

得：(其中“+”号表示异或运算)；

s2=1+0+1+1=1

s1=0+1=0+1=0

s0=0+0+1+0=1

即s2s1s0=101

(3)查表可知：接收到的比特序列第4位有错，正确的应是：

a6a5a4a3a2a1a0=1011100

---

四方区15020483321： 已知海明码的监督关系式为:S2=a2+a3+a4+a6 S1=a1+a4+a5+a6 S0=a0+a3+a4+a5接收端收到的码字为a6a5a4a3a2a1a0=1010100,问在最多一位错的情... - ？
俞弦依苏：[答案] .(1)根据海明码的监督关系式 S2=a2+a3+a4+a6 S1=a1+a4+a5+a6 S0=a0+a3+a4+a5,得下表: S2S1S0 000 001 010 011 100 101 110 111 错误位置 无错 a0 A1 a5 a2 a3 a6 a4 (2)将a6a5a4a3a2a1a0=1010100分别代入海明码的监督关系式 得:(...

四方区15020483321： 海明码的运算规则是怎样的? - ？
俞弦依苏： 1)海明码的生成. 例1.已知:信息码为:＂0010＂.海明码的监督关系式为: S2=a2+a4+a5+a6 S1=a1+a3+a5+a6 S0=a0+a3+a4+a6 求:海明码码字. 解:1)由监督关系式知冗余码为a2a1a0. 2)冗余码与信息码合成的海明码是...

四方区15020483321： 关于海明码如果信息字长为5位,要纠正1位错,按照海明码,需要增加的校验位是几位 - ？
俞弦依苏：[答案] 1.海明码的概念 海明码是一种可以纠正一位差错的编码.它是利用在信息位为k位,增加r位冗余位,构成一个n=k+r位的码字,然后用r个监督关系式产生 的r个校正因子 来区分无错和在码字中的n个不同位置的一位错.它必需满足以下关系式: 2r>=n...

四方区15020483321： 海明码 监督关系式的计算(50分) - ？
俞弦依苏： 海明码序号:1 2 3 4 5 6 7 含 义:P1 P2 b1 P3 b2 b3 b4 码 字:1 0 0 0 1 0 1 C3 = P3异或b2异或b3异或b4 = 0 C2 = P2异或b1异或b3异或b4 = 0 C1 = P1异或b1异或b2异或b4 = 1 C3C2C1 = 001 对应的是第1位即P1出错 所以纠错后的码字是 0000101

四方区15020483321： 海明码的信息位的计算 - ？
俞弦依苏： a2=a3+a5+a6=1 a1=a4+a5+a6=0 a0=a3+a4+a5=1 s2s1s0=101 s2s1s0 000 001 010 011 100 101 110 111 最多错一位 查表a0错 所以答案是 1010101

四方区15020483321： 海明码生成问题海明码的生成.例1.已知:信息码为:＂0010＂.海明码的监督关系式为:S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6求:海明码码... - ？
俞弦依苏：[答案] 信息位:0010;海明码的每个校验位是所有在二的幂次方的位(编号1,2,4,8,等,这些位置的数值)是校验位;那么校验位就是:010(信息码0010中的第四位、第二位、第一位、对应2的平方=4,2的一次方=2,2的0次方=1);4个信息...

四方区15020483321： 海明码监督位怎么确定? - ？
俞弦依苏： 假设出错位为e1,e2,e3,e4,现在我们需要做的就是将M1、M2……Mn和e1,e2,e3,e4,的关系对应出来,只要这个关系出来了,所有的问题都解决了.演示几个,剩下的你自己推导(看了肯定会).M1下标中的1可以表示成0001,这里的0001分别对应(倒过来看),由于的值为1,所以只和e1有关.M3下标中的3可以表示成0011,所以e1和e2有关;下M7标中的7可以表示成0111,所以和e1、e2,e3有关;其他以此类推,只需要将这些有关的用异或符号连接起来即可

四方区15020483321： 这是一道例题:例1.已知:信息码为:＂0010＂.海明码的监督关系式为:S2=a2+a4+a5+a6 S1=a1+a3+a5+a6 S0=这是一道例题:例1.已知:信息码为:＂... - ？
俞弦依苏：[答案] 若海明码的监督关系为:S0=a0+a3+a4+a6 ;S1=a1+a3+a5+a6 ;S2=a2+a4+a5+a6 .

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

四方区15020483321： 海明码纠错运算 - ？
俞弦依苏： 根据你所给出的信息,X1...X7对应的位为:X7 X6 X5 X4 X3 X2 X11 0 0 0 1 0 1 这样,C0=1⊕1⊕0⊕1=1;C2=0⊕1⊕0⊕1=0;C3=0⊕0⊕0⊕1=1 结果为1表示这几项中有一项出现错误,所以(X1+X3+X5+X7)有一项错误,(X2+X3+X6+X...