海明校验码
海明校验码的准则:
- 1.校验码必须放在2的幂次上(2n),n为0,1,2,3,....
- 2.满足 k+r+1 <= 2r,k为信息位的长度,r为校验码长度
例:求信息 1011 的海明码。
已知:k为4,则需要满足 4+r+1 <= 2r , 可知 r=3 时公式成立,校验码长度为3。校验码的位置为 20、21、22(1、2、4),海明码长度(信息位+校验位)为4+3=7。
当前信息位由那几个校验位决定?其规律是:第i位信息位,由校验位位号之和等于i的那些校验位所校验。
例如:I0是由r1和r0决定的。3=21+20=2+1
可得信息位7、6、5、3的校验位分别是哪几个。
7=22+21+20=4+2+1,6=22+21=4+2,5=22+20=4+1,3=21+20=2+1
可见下表:
信息位-位数 | 校验位-位数 |
---|---|
7 | 4、2、1 |
6 | 4、2 |
5 | 4、1 |
3 | 2、1 |
校验位的值与数据位相关,例如:r2(位号:4)与信息位I4 、 I3 、 I2 有关。
异或⊕(xor)运算(同为0,异为1)
r2 = I4 ⊕ I3 ⊕ I2 = 1 ⊕ 0 ⊕ 1 = 0
r1 = I4 ⊕ I3 ⊕ I1 = 1 ⊕ 0 ⊕ 1 = 0
r0 = I4 ⊕ I2 ⊕ I1 = 1 ⊕ 1 ⊕ 1 = 1
多个异或运算规律:
算式中1的个数为奇数,结果为1;算式中1的个数为偶数,结果为0(注:0个也是偶数个)
可得海明码为:1010101
校验1:若收到的信息为1011101(第4位出错,从左往右数)
接收方需要采用上面的方法进行计算,并加上校验位自身,则:
r2 ⊕ I4 ⊕ I3 ⊕ I2 = 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1
r1 ⊕ I4 ⊕ I3 ⊕ I1 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
r0 ⊕ I4 ⊕ I2 ⊕ I1 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
100代表第 22 = 4 位置出错,取反就可以得到正确的值了。
校验2:若收到的信息为1010100(第1位出错,从左往右数)
r2 ⊕ I4 ⊕ I3 ⊕ I2 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
r1 ⊕ I4 ⊕ I3 ⊕ I1 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
r0 ⊕ I4 ⊕ I2 ⊕ I1 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1
001代表第 20 = 1 位置出错,取反就可以得到正确的值了。
参考
- 王勇老师的软件设计师考试-考前培训视频
- 海明校验码-百度百科
- 程序员教程第五版
感谢
创作十分不易,转载请注明出处及作者(wybing),十分感谢!
标签:校验位,20,必看,海明,I3,I2,软考,I4,校验码 From: https://www.cnblogs.com/wybing/p/17043774.html