不要温和的走进那个良夜
Do not go gentle into that good night

海明码校验

小林子不想说这是为了准备考试而写的一篇文章。为了加深记忆,全部用手打0.0

海明码用于数据传送,能检测所有一位和双位差错并纠正所有一位差错的二进制代码。简单点说就是水果供销商每天给顾客送水果。但是在运输过程中不能确保水果是否坏了(当然人家供销商不是奸商,给你的水果都是好的)。然后顾客不够专业压坏了的苹果也照样吃,吃坏肚子多不好。于是这个时候增加了一道工序,在运输水果的工作人员里面添加了一个检测员,当水果送到目的地之后会有检测员当着顾客检测水果(我表示这是真实的事情0.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为增加冗余位位数(←这一段来自于百度百科,如果你觉得不是很深奥,很好、一看你就是搞学问的人,那么这个估计你就已经明白了;如果觉得很深奥,不要急,咱们慢慢分析)

首先原来海明码是可以纠正以为差错的编码的,信息位K意思是有K个有意义的信息 比如00000001这个就是十进制的1(这个比方可能不恰当)。增加冗余位就是为了校验。这里比较关键的就是那个关系式至少说明了怎样才能满足校验。就是2的r次方≥n+1即(k+r+1)≤2的r次方,例如K=4 r≥3

信息位跟校验位的关系   I为信息位  R为校验位

I4 I3  I2 R2 I1 R1 R0

7   6   5   4     3   2   1

7 = R0+R1+R2 = 2^0+2^1+2^2

6 =R1+R2 = 2^1+2^2

5 =R0+R2

3 =R1+R0 = 2^0+2^1

(Z^X为Z的X次方)

计算校验位(以下+代表异或)

R2=I4+I3+I2

R1=I4+I3+I1

R0=I4+I2+I1

计算校正因子

S2=R2+I4+I3+I2

S1=R1+I4+I3+I1

S0=R0+I4+I2+I1 如果没有错误的话校正因子都为0如果有错的话错位在S=S2S1S0

举例1如I=1001

发送的为1001100

如果接收到1011011

S2=1

S1=0

S0=1

S=101 错误位在I5

异或规则:

0+0=0,0+1=1
1+0=1,1+1=0
赞(0)
未经允许不得转载:林枫紫涵 » 海明码校验

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址