您现在的位置: 首页 > 网站导航收录 > 百科知识百科知识
海明校验码(海明校验码校验位怎么计算出来的)
余数,多项式,校验码海明校验码(海明校验码校验位怎么计算出来的)
发布时间：2016-12-08加入收藏来源：互联网点击：
很多朋友想了解关于海明校验码的一些资料信息，下面是小编整理的与海明校验码相关的内容分享给大家，一起来看看吧。
软件设计师的考试中，海明检验码是如何计算的？
下面这个，但是我没看懂！
奇偶校验码,海明校验码和循环冗余校验码(CRC)
奇偶校验码是奇校验码和偶校验码的统称.
它们都是通过在要校验的编码上加一位校验位组成.
如果是奇校验加上校验位后,编码中1的个数为奇数个
如果是偶校验加上校验位后,编码中1的个数为偶数个
原编码奇校验偶校验
00000000100000
00100010000101
11001100111000
10101010110100
如果发生奇数个位传输出错,那么编码中1的个数就会发生变化.
从而校验出错误.要求从新传输数据.
目前应用的奇偶校验码有3种.
水平奇偶校验码
对每一个数据的编码添加校验位,使信息位与校验位处于同一行.
垂直奇偶校验码
把数据分成若干组,一组数据排成一行,再加一行校验码.
针对每一行列采用奇校验或偶校验
例:有32位数据10100101001101101100110010101011
垂直奇校验垂直偶校验
数据1010010110100101
0011011000110110
1100110011001100
1010101110101011
校验为0000101111110100
水平垂直奇偶校验码
就是同时用水平校验和垂直校验
奇校验奇水平偶校验偶水平
数据101001011101001010
001101101001101100
110011001110011000
101010110101010111
校验000010110111101001
然后是海明校验码
海明码也是利用奇偶性来校验数据的.
它是一种多重奇偶校验检错系统,它通过在数据位之间插入k个校验位,来扩大码距,从而实现检错和纠错.
设原来数据有n位,要加入k位校验码.怎么确定k的大小呢?
k个校验位可以有pow(2,k)(代表2的k次方)个编码,其中有一个代表是否出错.
剩下pow(2,k)-1个编码则用来表示到底是哪一位出错.
因为n个数据位和k个校验位都可能出错
所以k满足pow(2,k)-1>=n+k
设k个校验码为P1,P2...Pk,n个数据位为D0,D1...Dn
产生的海明码为H1,H2...H(n+k)
如有8个数据位,根据pow(2,k)-1>=n+k可以知道k最小是4
那么得到的海明码是
H12H11H10H9H8H7H6H5H4H3H2H1
D7D6D5D4P4D3D2D1P3D0P2P1
然后怎么知道Pi校验哪个位呢.
自己可以列个校验关系表
海明码下标校验位组
H1(P1)1P1
H2(P2)2P2
H3(D0)1+2P1,P2
H4(P3)4P3
H5(D1)1+4P1,P2
H6(D2)2+4P2,P3
H7(D3)1+2+4P1,P2,P3
H8(P4)8P4
H9(D4)1+8P1,P4
H10(D5)2+8P2,P4
H11(D6)1+2+8P1,P2,P4
H12(D7)4+8P3,P4
从表中可以看出
P1校验P1,D0,D1,D3,D4,D6
P2校验P2,D0,D2,D3,D5,D6
P3校验P3,D1,D2,D3,D7
P4校验P4,D4,D5,D6,D7
其实上表很有规律很容易记
要知道海明码Hi由哪些校验组校验
可以把i化成二进制数数中哪些位k是1,就有哪些Pk校验
如H77=0111所以由P1,P2,P3
H1111=1011所以由P1,P2,P4
H33=0011所以由P1,P2
那看看Pi的值怎么确定
如果使用偶校验,则
P1=D0xorD1xorD3xorD4xorD6
P2=D0xorD2xorD3xorD5xorD6
P3=D1xorD2xorD3xorD7
P4=D4xorD5xorD6xorD7
其中xor是异或运算
奇校验的话把偶校验的值取反即可.
那怎么校验错误呢.
其实也很简单.先做下面运算.
G1=P1xorD0xorD1xorD3xorD4xorD6
G2=P2xorD0xorD2xorD3xorD5xorD6
G3=P3xorD1xorD2xorD3xorD7
G4=P4xorD4xorD5xorD6xorD7
如果用偶校验那么G4G3G2G1全为0是表示无错误(奇校验全为1)
当不全为0表示有错G4G3G2G1的十进制值代表出错的位.
如G4G3G2G1=1010表示H10(D5)出错了.
把它求反就可以纠正错误了.
下面举一个比较完全的例子:
设数据为01101001,试用4个校验位求其偶校验方式的海明码.
传输后数据为011101001101,是否有错?
P1=D0xorD1xorD3xorD4xorD6
=1xor0xor1xor0xor1
P2=D0xorD2xorD3xorD5xorD6
=1xor0xor1xor1xor1
P3=D1xorD2xorD3xorD7
=0xor0xor1xor0
P4=D4xorD5xorD6xorD7
=0xor1xor1xor0
所以得到的海明码为
011001001101
传输后为011101001101
G1=P1xorD0xorD1xorD3xorD4xorD6
G2=P2xorD0xorD2xorD3xorD5xorD6
G3=P3xorD1xorD2xorD3xorD7
G4=P4xorD4xorD5xorD6xorD7
所以1001代表9即H9出错了,对它求反
011001001101和我们算的一样.
由此可见海明码不但有检错还有纠错能力
下面说下最后一种CRC即循环冗余校验码
CRC码利用生成多项式为k个数据位产生r个校验位进行编码,其编码长度为n=k+r所以又称(n,k)码.
CRC码广泛应用于数据通信领域和磁介质存储系统中.
CRC理论非常复杂,一般书就给个例题,讲讲方法.
现在简单介绍下它的原理:
在k位信息码后接r位校验码,对于一个给定的(n,k)码
可以证明(数学高手自己琢磨证明过程)存在一个最高次幂为n-k=r的多项式g(x)
根据g(x)可以生成k位信息的校验码,g(x)被称为生成多项式
用C(x)=C(k-1)C(k-2)...C0表示k个信息位
把C(x)左移r位,就是相当于C(x)*pow(2,r)
给校验位空出r个位来了.
给定一个生成多项式g(x),可以求出一个校验位表达式r(x)
C(x)*pow(2,r)/g(x)=q(x)+r(x)/g(x)
用C(x)*pow(2,r)去除生成多项式g(x)商为q(x)余数是r(x)
所以有C(x)*pow(2,r)=q(x)*g(x)+r(x)
C(x)*pow(2,r)+r(x)就是所求的n位CRC码,由上式可以看出它是生成多项式g(x)的倍式.
所以如果用得到的n位CRC码去除g(x)如果余数是0,就证明数据正确.
否则可以根据余数知道出错位.
在CRC运算过程中,四则运算采用mod2运算(后面介绍),即不考虑进位和借位.
所以上式等价于C(x)*pow(2,r)+r(x)=q(x)*g(x)
继续前先说下基本概念吧.
1.多项式和二进制编码
x的最高次幂位对应二进制数的最高位.以下各位对应多项式的各幂次.
有此幂次项为1,无为0.x的最高幂次为r时,对应的二进制数有r+1位
例如g(x)=pow(x,4)+pow(x,3)+x+1
对应二进制编码是11011
2.生成多项式
是发送方和接受方的一个约定,也是一个二进制数,在整个传输过程中,这个数不会变.
在发送方,利用生成多项式对信息多项式做模2运算生成校验码.
在接受方利用生成多项式对收到的编码多项式做模2运算校验和纠错.
生成多项式应满足:
a.生成多项式的最高位和最低位必须为1
b.当信息任何一位发生错误时,被生成多项式模2运算后应该使余数不为0
c.不同位发生错误时,应该使余数不同.
d.对余数继续做模2除,应使余数循环.
生成多项式很复杂
不过不用我们生成
下面给出一些常用的生成多项式表
nk二进制码(自己根据多项式和二进制编码的介绍转)
741011或1101
7311011或10111
15111011
3126100101
3.模2运算
a.加减法法则
0+/-0=0
0+/-1=1
1+/-0=1
1+/-1=0
注意:没有进位和借位
b.乘法法则
利用模2加求部分积之和,没有进位
c.除法法则
利用模2减求部分余数
每商1位则部分余数减1位
余数最高位是1就商1,不是就商0
当部分余数的位数小于余数时,该余数就是最后余数.
例1110
1011)1100000
0010(每商1位则部分余数减1位,所以前两个0写出)
010(当部分余数的位数小于余数时,该余数就是最后余数)
上一篇：寿字纹(寿字纹足金元宝的价格)
下一篇：返回列表
相关链接 |
||
| 网友回复（共有 0 条回复） |