海明码,海明码校验位怎么计算

http://www.itjxue.com  2023-01-18 00:02  来源:未知  点击次数: 

海明码的原理

海明码是一种可以纠正一位差错的编码。它是利用在信息位为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+12^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,因而m2^4-4-1=11,即数据位可以用到11位,共组成15位的码字,可检测出单个位置的错误。

关于海明码的原理和计算

综合上面我们求一下信息1011的海明码是多少?

答:

我们知道信息位有4位,即为n=4,求得公式中校验位K=3。所以海明码一共7位:H7-H1 ; 信息位:D3-D0; 校验位:P3-P1。

求P3-P1在海明码中的位置。根据图中下面这句话。我们可以求得位置。

p1= 2的(1-1)次方=1

p2=2

p3=4

校验位在海明码中的位置:P1----1 P2----2 P3----4

现在我们需要求得P1-P3的值,我们的海明码就出来了。

eg: H7 下标为7, 校验码下标有1,2,4。 则需要7=4+2+1 。所以P1,P2,P3都参与了D3的校验。

接下来我们统计一个各个校验位校验的信号位有哪些。

P1----P1,D0,D1,D3

P2----P2,D0,D2,D3

P3----P3,D1,D2,D3

进行异或运算(相同为0,相异为1)

P1=D0⊕D1⊕D3=1 1 1=1

P2=D0⊕D2⊕D3=1 0 1=0

P3=D1⊕D2⊕D3=1 0 1=0

所以海明码为:1010101。

检错计算: 本来是1011,假如传过来的是1001。(D1出错了)

则从又到左D0=1 D1=0, D2=0, D3=1

G1=P1⊕D0⊕D1⊕D3=1 1 0 1=1

G2=P2⊕D0⊕D2⊕D3=0 1 0 1=0

G3=P3⊕D1⊕D2⊕D3=0 0 0*1=1

G3G2G1=101

如果是偶校验,则需要全部为0,如果是奇校验全部为1。

101的10进制。则是海明码里面的第5位出错。H5(D1)出错。则D1取反,得到。1001--1011 。 这样就实现了检错,改错了。

考研408海明码删了吗

删除了。根据查询考研408相关信息得知,考研408海明码删除了。海明码指汉明码。 汉明码(Hamming Code),是在电信领域的一种线性调试码,以发明者理查德·卫斯里·汉明的名字命名。汉明码在传输的消息流中插入验证码,当计算机存储或移动数据时,可能会产生数据位错误,以侦测并更正单一比特错误。

什么是海明码呀?通俗一点,但又能深刻一点!谢谢了!!!

海明码其实也不难,相对于寄偶检验码 它不仅可以检验出错误,还能修正错误!但只能是检验、修正一位错误!说一大堆理论是没什么意思,下面将通过一个例子,尽可能的用最通俗易懂的方式进行讲解!最后大家会发现海明码很神奇!!

假设要传送的数据为:1011 0011

校验流程如下:

一:确定校验位并插入到有效数据位中。

相比奇偶校验只插入一个检验码,海明码需要插入多个检验码,插入的位数与有效数据位数相关,公式如下

公式:2^r-rk+1,其中r就是要插入检验码的个数,取满足条件的最小整数,k是有效数据位数。因为我们要传送的数据是:1011 0011,显然k=8,推出r=4。也就说我们要将4个校验位插入到有效数据中,怎么插入呢?按照如下规则:

插入位置固定为2^N(N:0,1,2,3,4,5……)处,因为r=4,即只需要取4个有{2^0,2^1,2^2,2^3},对应位置即是1,2,4,8,当然了,如果r=5,那么插入位置为:1,2,4,8,16.同类可以推出其他情况,不再啰嗦。(之所以选择这样的位置插入,是为了有效的分组,保证后面的校验分组能有效的错开,不会互相干扰,这句话不需要理解,到后面就能体会!)

通过分析得到待传送的数据为:xx1x 011x 0011,4位校验位+8为有效数据位。

二、确定校验位的数值。

显然X只能取0,1,下面确定x的值:

由一可知待传送数据为:xx1x 011x 0011。

规则:以X的位置为长度,依次从待传送数据中取X个数,然后跳过X个数,再取X个数,直到待传送数据串尾,得到一个子串,然后统计子串中1的个数,如果为奇数,则x=0,为偶数,x=1(当然,反过来也行,其实这就是奇偶校验的规则,想了解奇偶校验可以参见我以前的回答的,这里不了解也行)

第1个X:位置为1,从第1个位置开始依次取1个数据,并跳过1个数据再取,直到串尾得到一个子串:

{x 1 0 1 0 1},这个串可记为第1个校验组, 因为1的个数是3个为奇数,故x=0.

第2个X:位置为2,故从第2个位置开始依次取2个数据,并跳过2个数据再取,直到串尾得到一个子串:

{x1 ?11 ?01} ,记为第2个校验组,因为1的个数为4是偶数,故x=1.

第3个X:位置是4,故从第4个位置开始依次取4个数据,并跳过4个数据再取,直到串尾得到一个子串:

{x011 ? ? 1},记为第3个校验组,因为1的个数为3是奇数,故x=0.

第4个X:位置是8,故从第8个位置开始依次取8个数据,并跳过8个数据再取,直到串尾得到一个子串:

{x0011 },记为第4个校验组,……,X=1。

故得到最终的待传送的数据串为:0110?0111?0011。

这里其实就可以看到了,为什么X的位置要取2^N,这样才能保证各个校验位不会相互干扰。

经过以上一、二步骤就完整了海明码的构造过程,下面讲解校验过程:

三、根据步骤二中的构造规则,取出各校验组

发送的数据串为:0110?0111?0011。

假设接受到的数据串为:0110?0111?1011(注意和传送数据串相比,第9为出现了错误!)

规则:以X的位置为长度,依次从待传送数据中取X个数,然后跳过X个数,再取X个数,直到待传送数据串尾,得到一个子串,然后统计子串中1的个数,如果为奇数,则x=0,为偶数,x=1(规则必须和步骤二中一样)

根据二中制定的规则再次取出各个校验组。

第1个校验组:从第1个位置开始依次取1个数据,并跳过1个数据再取,直到串尾得到一个子串:{0 1 0 1 1 1}。

第2个校验组:从第2个位置开始依次取2个数据,并跳过2个数据再取,直到串尾得到一个子串:{11 ?11 ?01}

第3个校验组:从第4个位置开始依次取4个数据,并跳过4个数据再取,直到串尾得到一个子串:{0011 ? ?1}

第4个校验组:从第8个位置开始依次取8个数据,并跳过8个数据再取,直到串尾得到一个子串:{11011}.

四、根据步骤二的构造规则,确定存在错误的校验组,并通过错误校验组的交集,最终确定出错的位置。

由步骤三得到4个校验组:

1:{0 1 0 1 1 1}。 ?对应位置为{1 3 5 7 9 11}

2:{11 ?11 ?01}。?对应位置为{2 3 6 7 10 11}

3:{0011 ? ?1} ?。对应位置为{4567 ? ?12}

4:{11011}。 ??对应位置为{8 9 10 11 12}

因为我们的构造规则是:统计子串中1的个数,如果为奇数,则x=0,为偶数,x=1。

所以正确的校验组中1的个数绝对是奇数!(好好琢磨,很容易就想通了,如果我们的规则是为奇数,则x=1,为偶数,x=0。那么正确的校验组中1的个数绝对是偶数),所以如果校验组1的个数不是奇数,那么这个校验组就存在问题。因而可以判断第1个和第4个校验组出现问题了。

确定了第1个和第4个校验组出现问题后,找到这两个校验组的交集即第9个位置和第11个位置是它们交集,即共同校验的位置。于是判断出现问题的位置要么就是第9个位置,要么就是第11个位置!因为在第2个校验组中有第11个位置,故第11个位置绝对没有出错,因为就可以判断是第9个位置出现错误!

到这里,应该懂了吧?但是不是觉得找出错位置有点麻烦啊?下面就给出一个具体的实现方法,理解了上面的描述,再了解下面实现的方法,立马就能确定出错误的位置:

首先:我们对各个校验组求异或。

第一个校验组:{0 1 0 1 1 1} 异或的结果为:0

第二个校验组:{11 ?11 ?01}异或的结果为:1

第三个校验组:{0011 ? ?1}?异或的结果为:1

第四个校验组:{11011}异或的结果为:0

接着:倒置拼接异或结果,得到:0110,

最后:按位取反的到:1001,。

大家有没有惊奇的发现1001的十进制数就是9,这不就是出错的位置吗?这是巧合吗?

不急再看一个例子:

传送的数据串为: ?0110?0111?0011(还是我们开始的那个串)

接受到的数据串为:0110?1111?0011(和正确数据串相比,第5个位置出错了)

第一个校验组:{0 1 1 1 0 1} 异或的结果为:0

第二个校验组:{11 ?11 ?01}异或的结果为:1

第三个校验组:{0111 ? ?1}?异或的结果为:0

第四个校验组:{10011}异或的结果为:1

倒置拼接:1010 ?反转为:0101 ?对应十进制数为5!

也就是说方法是真确的!!不用怀疑!!这也就是海明码的奇妙之处!

再来看看一个例子:

传送的数据串为: ?0110?0111?0011(还是我们开始的那个串)

接受到的数据串为:0110?0110?0011(和正确数据串相比,第8个位置校验位出错了)

显然这是校验位出错了,那么能不能校验出来呢?

第一个校验组:{0 1 0 1 0 1} 异或的结果为:1

第二个校验组:{11 ?11 ?01}异或的结果为:1

第三个校验组:{0011 ? ?1}?异或的结果为:1

第四个校验组:{00011}异或的结果为:0

倒置反转结果为1000 正好是8,所以也没问题。

下面我们来说下规则:(其实就是说异或与奇偶的关系,想拓展的就可以看看)

上面的例子中,我们规定: 统计子串中1的个数,如果为奇数,则x=0,为偶数,x=1。如果是按这样的规定,那么校验组中1的个数必定是奇数,正是因为如此,所以校验组中如果1的个数不是奇数那么肯定出现了错误!而如果一个串中1的个数是奇数,那么串异或的结果一定为1,其实这个规则对应的就是奇校验!反之,如果为奇数,则x=1,为偶数,x=0,那么对应的就是偶校验!

故得到以下结论:

如果采用奇检验构造海明码,那么出错校验组中的1的个数必为偶数,即异或的结果必定为0!

如果采用奇检验构造海明码,那么出错的位置是校验组异或结果倒置拼接并反转的十进制数

如果采用偶检验构造海明码,那么出错校验组中的1的个数必为奇数,即异或的结果必定为1!

如果采用偶检验构造海明码,那么出错位置是校验组异或结果直接倒置拼接的十进制数!

关于偶检验构造海明码这里就不再详细展开,如果你能用偶检验的方法在把上面的例子都做一遍,那么海明码你就已经完全弄懂了!试试吧!

关于奇偶检验码 建议还是看看,因为海明码是基于奇偶校验的改进!而且奇偶校验更简单!

简单理解海明校验码

二进制数据经过传送、存取等环节,会发生误码(1变成0或0变成1),这就有如何发现及纠正误码的问题。所有解决此类问题的方法就是在原始数据(数码位)基础上增加几位校验位。我们常使用的检验码有三种. 分别是奇偶校验码、海明校验码和循环冗余校验码(CRC)。

海明校验码是由RichardHamming于1950年提出、目前还被广泛采用的一种很有效的校验方法。它的实现原理,是在k个数据位之外加上r个校验位,从而形成一个k+r位的新的码字,使新的码字的码距比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中,当某一位出错后,就会引起相关的几个校验位的值发生变化,这不但可以发现出错,还能指出是哪一位出错,为进一步自动纠错提供了依据。但是因为这种海明校验的方法只能检测和纠正一位出错的情况。所以如果有多个错误,就不能查出了。

什么是码距?

两个码组对应位上数字的不同位的个数称为码组的距离,简称码距,又称海明(Hamming)距离。例如00110和00100码距为1,12345和13344码距为2,Caus和Daun码距为2。

海明校验码公式(假设为k个数据位设置r个校验位)

公式怎么得出来的呢?

假设有r个校验位,一个位子有0或1两种情况,r个位子就有2 r种排列情况,能表示2 r种状态。其中一个状态用来表示正确(没有错误发生)的这种情况。其余的2 r-1种状态来表示错误发生在哪一位。总共有k+r位,所以2 r-1一定要=总位子k+r。

按照该不等可以得出k与r的对应关系

注意:海明校验码是放在2的幂次位上的,即“1,2,4,8,16,32······”

实战求1011的海明码

第一步:求r的值(即校验位数)

直接根据公式代入得:

2^r-1 ≥ 4 + r

2^r-r ≥ 5

得到r最小为3

所以海明码的位数是4+3=7位

第二步:校验位和信息位对号入座

注意: 信息位的位置分配是从高位到低位依次存放

注意: 海明校验码是放在2的幂次位上的

位数|1|2|3|4|5|6|7

:-:|:-:|:-:|:-:|:-:|:-:|:-:

信息位|||1||1|0|1

校验位|r1|r2||r3|||

第三步:确定校验位的值

校验原则:被校验的海明位的下标等于所有参与校验该为的校验位的下标之和

然后将校验码校验的信息位的位置记录下来:

然后做对应信息位的异或运算(异或的运算法则为:0⊕0=0,1⊕0=1,0⊕1=1,1⊕1=0(同为0,异为1))

代入表格得到

注意:按照从低位到高位的排列顺序得到海明码:1010101

已知有效信息位为01101110,求海明码的生成和校验过程?

将K位检测位记作Ci(i=1,2,4,8...)分别安插在n+k位代码编号的第1,2,4,8,16...位上.

01101110(n=8)根据2的k次方大于等于n+k+1,可求出配置成海明码需增添检测位k=4,

原码01101110记作B8,B7,B6,B5,B4,B3,B2,B1.

则原码同检测位的位置安排如下:

二进制序号:1 2 3 4 5 6 7 8 9 10 11 12

名称 C1 C2 B8 C4 B7 B6 B5 C8 B4 B3 B2 B1

如果按配偶原则来配置海明码,则

C1应使1,3,5,7,9,11位中的“1”的个数为偶数;

C2应使2,3,6,7,10,11位中的“1”的个数为偶数;

C4应使4,5,6,7,12位中的“1”的个数为偶数;

C8应使8,9,10,11,12位中的“1”的个数为偶数;

故C1应为3位⊕5位⊕7位⊕9位⊕11位,即C1=B8⊕B7⊕B5⊕B4⊕B2

故C2应为3位⊕6位⊕7位⊕10位⊕11位,即C2=B8⊕B6⊕B5⊕B3⊕B2

故C4应为5位⊕6位⊕7位⊕12位,即C4=B7⊕B6⊕B5⊕B1

故C8应为9位⊕10位⊕11位⊕12位,即C8=B4⊕B3⊕B2⊕B1

即,

C1=B8⊕B7⊕B5⊕B4⊕B2=0⊕1⊕0⊕1⊕1=1

C2=B8⊕B6⊕B5⊕B3⊕B2=0⊕1⊕0⊕1⊕1=1

C4=B7⊕B6⊕B5⊕B1=1⊕1⊕0⊕0=0

C8=B4⊕B3⊕B2⊕B1=1⊕1⊕1⊕0=1

故01101110的海明校验码为C1 C2 B8 C4 B7 B6 B5 C8 B4 B3 B2 B1=110011011110

(责任编辑:IT教学网)

更多

推荐windows vista文章