海明码的检测出错介绍
2007-11-10 14:57:33| 分类： 电脑 | 标签： |举报 |字号大中小 订阅
1. 如果传输的数据位是m 位，加了r 位冗余位，那么总共传输的数据单元是m+r位。
为了能够发现这m+r位数据单元在传输到目的端后是否出错，并能够指明是在哪一位出错，
那么r 至少应该能够代表m+r+1种状态。
r 比特能够代表2^r不同状态。
因此，2^r>=m+r
若m=7，则满足上式的最小r 值为：4。
海明码的纠错原理
海明码的接收端的公式:
S3= P3⊕ D4⊕D3 ⊕D2
S2= P2⊕D4 ⊕D3 ⊕D1
S1= P1⊕D4 ⊕D2 ⊕D1
假定 海明码1010101在传送中变成了1000101
S3= P3⊕ D4⊕D3 ⊕D2=0⊕1⊕0 ⊕0 =1
S2= P2⊕D4 ⊕D3 ⊕D1=0⊕1⊕ 0 ⊕1=0
S1= P1⊕D4 ⊕D2 ⊕D1=1⊕1⊕ 0 ⊕1=1
因此, 由S3S2S1= 101,指出第5位错, 应由0变1
2. 海明码是一位纠错码，即如果数据在传输过程中有一位出错，
则可以知道出错的位数并通过取反将其改正过来。
海明码的基本意思是给传输的数据增加r 个校验位，从而增加两个合法消息（合法码字）的
不同位的个数（海明距离）。
假设要传得信息有m 位，则经海明编码的码字就有n=m+r位。
3. 例题1
设被校验数据是二进制数01101101, 求其海明码
二进制存放位置： A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12
数据存放的位置： D1 D2 D3 D4 D5 D6 D7 D8
在你的例子中： 0 1 1 0 1 1 0 1
海明码： C1 C2 C3 C4
C1 = D1 + D2 + D4 + D5 + D7
C2 = D1 + D3 + D4 + D6 + D7
C3 = D2 + D3 + D4 + D8
C4 = D5 + D6 + D7 + D8
至于为什么，看那个数据的位置编号，D1 在 3 的位置上，而这个的话可以用C1 + C2得到，
所以在计算C1的话就可以用这些计算位置码需要用到C1的数据二进制码来加，当1的个数为偶数时，值为0，否则为1。
就你的数据来说，C1 = 0 ＋ 1 ＋ 0 ＋ 1 ＋ 0 = 0
c2 = 0 + 1 + 0 + 1 + 0 = 0
c3 = 1 + 1 + 0 + 1 = 1
c4 = 1 + 1 + 0 + 1 = 1
C1 C2 C3 C4= 0 0 1 1
例题2
32位2进制数 需要6位校验位
假如有k 位数据 需要n 位校验位 满足关系k+n
假设32位2进制编码为[***********][1**********]111 (假设全1) 增添的校验位位abcdef
按以下方法将校验位插入原有代码ab1c111d1111111e[**************]f111111 即就是将校验位插入第1位 第2位 第4位 第8位 第16位……
建立一个表以获得海明码的监督关系式：
ab1c111d1111111e[**************]f111111
[***********][***********]10
[***********][***********]01
[***********][***********]11
[***********][***********]00
[***********][***********]00
[***********][***********]11
看出来这个表是如何建出来的么 第一行是插入检验位的38位海明码 第二行开始都是从检验位开始做1和0的循环
比如说第2行是从a 开始做1个1与1个0的循环，第3行是从b 开始做2个1与2个0的循环，
第3行是从c 开始做4个1与4个0的循环，依次类推……
将每行有1的码位挑出来求异或便是实际的监督关系方程了
比如：
第2行所有奇数位为1 即是挑取源码中所有奇数位上的码值取异或 s1=a+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
(+在这里代表异或)
同理第3行 2位3位6位7位10位11位……为1 则取在源码中对应位的码值取异或
s2=b+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
s3=c+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
s4=d+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
s5=e+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
s6=f+1+1+1+1+1+1
以上6个公式便是38位海明码的监督方程式了
要求各个校验位的实际值 只需要6个监督方程式均等于0 即
s1=s2=s3=s4=s5=s6=0
解方程得出 a=0 b=0 c=0 d=1 e=1 f=0
带入各回到各自的校验码位上 则这个38位海明码为
[***********][***********]11
若需要校验此海明码 只需要求出监督方程中s1 s2 s3 s4 s5 s6的值 然后由高到低排列s6s5s4s3s2s1 得出的数据即是第几位出错
对该位求反便可以达到纠错的目的了
例如 上段海明码第11位出错 码段变为
[***********][***********]11
监督方程解得
s1=0+1+1+1+1+0+1+1+1+1+1+1+1+1+1+1+1+1+1=1
s2=0+1+1+1+1+0+1+1+1+1+1+1+1+1+1+1+1+1+1=1
s3=0+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=0
s4=1+1+1+0+1+1+1+1+1+1+1+1+1+1+1+1=1
s5=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=0
s6=0+1+1+1+1+1+1=0
由高到低排列 得01011 即是2进制的第11位出错 11位取反便可以纠错了 大家可以看出来海明码代码越长 校验位数相对数据位数比例越低 即传输效率越高 但是如果出现多位出错时海明码就失去纠错能力
所以适合传输误码率低的线路
例题3
例如：
一段源码110011， 为了传输具有纠错能力，需要追加4位检验位abcd ，检验位按如下方法插入源码中：
ab1c100d11
即是插入在 第1位 第2位 第4位 第8位……
海明码的监督关系式按如下方法获得
插入后的码 a b 1 c 1 0 0 d 1 1 都是从检验位abcd 上开始取1
监督关系式 s1 1 0 1 0 1 0 1 0 1 0 第一行是1个1 1个0地循环
s2 0 1 1 0 0 1 1 0 0 1 第二行是2个1 2个0地循环
s3 0 0 0 1 1 1 1 0 0 0 第三行是4个1 4个0地循环
s4 0 0 0 0 0 0 0 1 1 1 第四行是8个1 8个0地循环……
监督关系式为
s1=a+1+1+0+1 +为按位异或运算
s2=b+1+0+0+1 每行在取1的位置上取出相应的位码做按位异或运算 s3=c+1+0+0
s4=d+1+1
由监督关系式就算出检测位的值 即在s1 s2 s3 s4分别等于0时解方程的各检测位的值
a=1+1+0+1=1
b=1+0+0+1=0
c=1+0+0=1
d=1+1=0
所以 获得的实际海明码是 1011100011
当需要纠错数据时只需判断s1 s2 s3 s4的值是否为0 为1即存在错误位 错误的具体位数为 s4s3s2s1
举例：1011100011的第7位错误 得误码 1011101011
s1=1+1+1+1+1=1
s2=0+1+0+1+1=1
s3=1+1+0+1=1
s4=0+1+1=0
由高到低排列位 得0111 即检测到第7位是错误位 随后就可以对该位取反纠正错误了
海明码的检测出错介绍
2007-11-10 14:57:33| 分类： 电脑 | 标签： |举报 |字号大中小 订阅
1. 如果传输的数据位是m 位，加了r 位冗余位，那么总共传输的数据单元是m+r位。
为了能够发现这m+r位数据单元在传输到目的端后是否出错，并能够指明是在哪一位出错，
那么r 至少应该能够代表m+r+1种状态。
r 比特能够代表2^r不同状态。
因此，2^r>=m+r
若m=7，则满足上式的最小r 值为：4。
海明码的纠错原理
海明码的接收端的公式:
S3= P3⊕ D4⊕D3 ⊕D2
S2= P2⊕D4 ⊕D3 ⊕D1
S1= P1⊕D4 ⊕D2 ⊕D1
假定 海明码1010101在传送中变成了1000101
S3= P3⊕ D4⊕D3 ⊕D2=0⊕1⊕0 ⊕0 =1
S2= P2⊕D4 ⊕D3 ⊕D1=0⊕1⊕ 0 ⊕1=0
S1= P1⊕D4 ⊕D2 ⊕D1=1⊕1⊕ 0 ⊕1=1
因此, 由S3S2S1= 101,指出第5位错, 应由0变1
2. 海明码是一位纠错码，即如果数据在传输过程中有一位出错，
则可以知道出错的位数并通过取反将其改正过来。
海明码的基本意思是给传输的数据增加r 个校验位，从而增加两个合法消息（合法码字）的
不同位的个数（海明距离）。
假设要传得信息有m 位，则经海明编码的码字就有n=m+r位。
3. 例题1
设被校验数据是二进制数01101101, 求其海明码
二进制存放位置： A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12
数据存放的位置： D1 D2 D3 D4 D5 D6 D7 D8
在你的例子中： 0 1 1 0 1 1 0 1
海明码： C1 C2 C3 C4
C1 = D1 + D2 + D4 + D5 + D7
C2 = D1 + D3 + D4 + D6 + D7
C3 = D2 + D3 + D4 + D8
C4 = D5 + D6 + D7 + D8
至于为什么，看那个数据的位置编号，D1 在 3 的位置上，而这个的话可以用C1 + C2得到，
所以在计算C1的话就可以用这些计算位置码需要用到C1的数据二进制码来加，当1的个数为偶数时，值为0，否则为1。
就你的数据来说，C1 = 0 ＋ 1 ＋ 0 ＋ 1 ＋ 0 = 0
c2 = 0 + 1 + 0 + 1 + 0 = 0
c3 = 1 + 1 + 0 + 1 = 1
c4 = 1 + 1 + 0 + 1 = 1
C1 C2 C3 C4= 0 0 1 1
例题2
32位2进制数 需要6位校验位
假如有k 位数据 需要n 位校验位 满足关系k+n
假设32位2进制编码为[***********][1**********]111 (假设全1) 增添的校验位位abcdef
按以下方法将校验位插入原有代码ab1c111d1111111e[**************]f111111 即就是将校验位插入第1位 第2位 第4位 第8位 第16位……
建立一个表以获得海明码的监督关系式：
ab1c111d1111111e[**************]f111111
[***********][***********]10
[***********][***********]01
[***********][***********]11
[***********][***********]00
[***********][***********]00
[***********][***********]11
看出来这个表是如何建出来的么 第一行是插入检验位的38位海明码 第二行开始都是从检验位开始做1和0的循环
比如说第2行是从a 开始做1个1与1个0的循环，第3行是从b 开始做2个1与2个0的循环，
第3行是从c 开始做4个1与4个0的循环，依次类推……
将每行有1的码位挑出来求异或便是实际的监督关系方程了
比如：
第2行所有奇数位为1 即是挑取源码中所有奇数位上的码值取异或 s1=a+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
(+在这里代表异或)
同理第3行 2位3位6位7位10位11位……为1 则取在源码中对应位的码值取异或
s2=b+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
s3=c+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
s4=d+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
s5=e+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
s6=f+1+1+1+1+1+1
以上6个公式便是38位海明码的监督方程式了
要求各个校验位的实际值 只需要6个监督方程式均等于0 即
s1=s2=s3=s4=s5=s6=0
解方程得出 a=0 b=0 c=0 d=1 e=1 f=0
带入各回到各自的校验码位上 则这个38位海明码为
[***********][***********]11
若需要校验此海明码 只需要求出监督方程中s1 s2 s3 s4 s5 s6的值 然后由高到低排列s6s5s4s3s2s1 得出的数据即是第几位出错
对该位求反便可以达到纠错的目的了
例如 上段海明码第11位出错 码段变为
[***********][***********]11
监督方程解得
s1=0+1+1+1+1+0+1+1+1+1+1+1+1+1+1+1+1+1+1=1
s2=0+1+1+1+1+0+1+1+1+1+1+1+1+1+1+1+1+1+1=1
s3=0+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=0
s4=1+1+1+0+1+1+1+1+1+1+1+1+1+1+1+1=1
s5=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=0
s6=0+1+1+1+1+1+1=0
由高到低排列 得01011 即是2进制的第11位出错 11位取反便可以纠错了 大家可以看出来海明码代码越长 校验位数相对数据位数比例越低 即传输效率越高 但是如果出现多位出错时海明码就失去纠错能力
所以适合传输误码率低的线路
例题3
例如：
一段源码110011， 为了传输具有纠错能力，需要追加4位检验位abcd ，检验位按如下方法插入源码中：
ab1c100d11
即是插入在 第1位 第2位 第4位 第8位……
海明码的监督关系式按如下方法获得
插入后的码 a b 1 c 1 0 0 d 1 1 都是从检验位abcd 上开始取1
监督关系式 s1 1 0 1 0 1 0 1 0 1 0 第一行是1个1 1个0地循环
s2 0 1 1 0 0 1 1 0 0 1 第二行是2个1 2个0地循环
s3 0 0 0 1 1 1 1 0 0 0 第三行是4个1 4个0地循环
s4 0 0 0 0 0 0 0 1 1 1 第四行是8个1 8个0地循环……
监督关系式为
s1=a+1+1+0+1 +为按位异或运算
s2=b+1+0+0+1 每行在取1的位置上取出相应的位码做按位异或运算 s3=c+1+0+0
s4=d+1+1
由监督关系式就算出检测位的值 即在s1 s2 s3 s4分别等于0时解方程的各检测位的值
a=1+1+0+1=1
b=1+0+0+1=0
c=1+0+0=1
d=1+1=0
所以 获得的实际海明码是 1011100011
当需要纠错数据时只需判断s1 s2 s3 s4的值是否为0 为1即存在错误位 错误的具体位数为 s4s3s2s1
举例：1011100011的第7位错误 得误码 1011101011
s1=1+1+1+1+1=1
s2=0+1+0+1+1=1
s3=1+1+0+1=1
s4=0+1+1=0
由高到低排列位 得0111 即检测到第7位是错误位 随后就可以对该位取反纠正错误了