Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3882016
  • 博文数量: 408
  • 博客积分: 10227
  • 博客等级: 上将
  • 技术积分: 9820
  • 用 户 组: 普通用户
  • 注册时间: 2009-04-17 21:48
个人简介

非淡泊无以明志,非宁静无以致远

文章存档

2022年(1)

2021年(1)

2020年(2)

2019年(5)

2018年(4)

2017年(3)

2016年(24)

2015年(8)

2014年(7)

2013年(3)

2012年(1)

2011年(23)

2010年(179)

2009年(147)

分类: C/C++

2010-04-27 21:54:13

海明码是奇偶校验的一种扩充。它采用多位校验码的方式,在这些校验位中的每一位都对不同的信息数据位进行奇偶校验,通过合理地安排每个校验位对原始数据进行校验位组合,可以达到发现错误,纠正错误的目的。

 1.编码步骤

  (1)根据信息位数,确定校验位数,2r次方≥k+r+1,其中,k为信息位数,r为校验位数。求出满足不等式的最小r,即为校验位数。

  (2)计算机校验位公式。

  1-3 校验位公式表

12

11

10

9

8

7

6

5

4

3

2

1

位数

I8

I7

I6

I5

 

I4

I3

I2

 

I1

 

 

信息位

 

 

 

 

r3

 

 

 

r2

 

r1

r0

校验位

  表1-3其实可以当成一个公式来套用,如有已经编码的数据 1100 1001 0111。我们只需把这些数据填充到校验公式,即可得到信息位与校验位。填充的方法是这样的,首先看数据的最低位(即右边第1),最低位为1,把1填充在公式表的r0位置,接着取出数据的次低位数据(即右边第2),把它填充到r1位置,把右边第3位数填充到I1位置。依此类推,我们可以得到表1-4

  1-4 校验位公式实例表

12

11

10

9

8

7

6

5

4

3

2

1

位数

1

1

0

0

 

0

0

1

 

1

 

 

信息位

 

 

 

 

1

 

 

 

0

 

1

1

校验位

  表中第2行数据为1100 001 1,这就是数据1100 1001 0111的编码信息,而表格第3行是1 011,这便是较验位。

  注意:

  ·校验位rn 所在位数为2n次方位置,其余由信息位填充;

  ·信息位下标从1开始,而校验位下标从0开始。

(3)求校验位(成功与否的关键)

用我自己的话写(带有局限性):海明码的位号拆分成校验码位号的2N-1次幂的和 如图2.6 备注说明 然后校验码的值就等于所校验的所有位值的异或值。over 下面是从网上找的详细解答。

在海明码中, 位号数(123、……、n)为2的权值的那些位,即:

1(20)2(21)4(22)8(23)、…2r-1位,作为奇偶校验位

并记作: P1P2P3 P4、…Pr,余下各位则为有效信息位。

例如: N=11 K=7 r=4 相应海明码可示意为

位号   1  2   3   4   5   6   7   8   9   10   11

P占位 P1 P2 × P3 × × × P4   ×   ×   ×

其中×均为有效信息,海明码中的每一位分别被P1P2P3P4 Pr 中的一至若干位所校验,其规律是:

i位由校验位位号之和等于i的那些校验位所校验

如:海明码的位号为3,它被P1P2(位号分别为1,2)所校验

海明码的位号为5,它被P1P3(位号分别为1,4)所校验

归并起来: 形成了4个小组,每个小组一个校验位,校验位的取值,仍采用奇偶校验方式确定。

 

海明码每位所占用的校验位(K=7

海明码位号

占用的校验位号

备注

1

1

1=1

2

2

2=2

3

12

3=1+2

4

4

4=4

5

14

5=1+4

6

24

6=2+4

7

124

7=1+2+4

8

8

8=8

9

18

9=1+8

10

28

10=2+8

11

128

10=1+2+8

             每个校验位所校验的数位(K=7

校验位位号

被校验位位号

1P1

1357911

2P2

23671011

4P3

4567

8P4

691011

 (自我认知:感觉就是码位的拆分,拆分成校验码的2N1次方幂的和)

其次,校验位rn由信息码对应位数的幂之和形式中包含有n的信息码异或而得,p1的值由I11(信息码为1)、I9(信息码为0)、I7位(信息码为1)、I5位(信息码为0)、I3(信息码为1)对应的信息码异或而得,

(4)求海明码。根据上面的表格填充后,写出海明码。

  2.纠错步骤

  (1)根据海明码的信息位和校验位的分布规则,找出接收到的数据的信息位以及校验位。

  1-5校验位公式表

12

11

10

9

8

7

6

5

4

3

2

1

位数

I8

I7

I6

I5

 

I4

I3

I2

 

I1

 

 

信息位

 

 

 

 

r3

 

 

 

r2

 

r1

r0

校验位

  如有已经编码的数据 1100 1001 0111,则可以根据上表得到编码的信息为:1100 001 1;校验位为:1 011,详细过程在编码步骤已详细说明。

(2)接收端对校验位进行验证

  Sn= rn ( 校验)+ rn (接收)

  (3)判断校正因子是否有错,并改正。

  Sn Sn-1 Sn-2……S0二进制对应的是那位就是那位出错,将其改正完成纠错。如1001为第九位,将第九位10 (01) 即可。

  例题1

  若海明码的监督关系式为:

  S0=a0+a3+a4+a5

  S1=a1+a4+a5+a6

  S2=a2+a3+a5+a6

  接收端收到的码字为:a6a5a4a3a2a1a0=1010100

  那最多一位错的情况下发送端的发送信息位是什么?

  解答:按监督关系式

  S0=0+0+1+0=1

  S1=0+1+0+1=0

  S2=1+0+0+1=0

  得出S2S1S0=001 根据值与错码位置的对应关系所以a0错误,发送端的发送信息应为1010101

 

 

阅读(3741) | 评论(0) | 转发(0) |
0

上一篇:哈希表与哈希函数

下一篇:UML-类图详解

给主人留下些什么吧!~~