海明码，汉明码，hamming
- 格式：pdf
- 大小：81.33 KB
- 文档页数：1
海明码，汉明码，hamming code--计算法则
最近最海明码很感兴趣，查了些资料，有⼀篇资料极好，所以贴出来，希望供有需求的⼈能有个参考。
1 海明码原理概述
海明码是R. Hamming提出的, ⼀种可以纠正⼀位错的差错控制编码。了解海明码之前, 先回顾⼀下简单的奇偶校验码的情
况。若信息位为K=n- 1位, 表⽰为a1～an- 1, 加上⼀位偶校验位(冗余位)a0, 构成⼀个n位的码字a0～an- 1, 在接收端校验时, 可
按关系式: s=a0+a1+a2+…an- 1来计算, 若S=0, 则⽆错, 若S=1, 则有错。上式可称为监督关系式, S称为校正因⼦。在奇偶校验
情况下, 只有⼀个监督关系式和⼀个校正因⼦, 其取值只有两种(0或1),分别代表了⽆错和有错的情况, ⽽不能指出差错所在的位
置。不难想象, 若增加冗余位, 也相应地增加监督关系式和校正因⼦, 就能区分更多的情况。如, 若有两个校正因⼦, 则其取值就
有4种可能: 00、01、10或11, 就能区分4种不同情况。若其中⼀种表⽰⽆错, 另外三种不但可以⽤来指出有错, 还可以⽤来区分
错误的情况, 如指出是哪⼀位错等。
⼀般⽽⾔, 信息位为K位, 增加r位冗余位, 构成n=k+ r位码字。若希望⽤r个监督关系式产⽣的r个校正因⼦来区分⽆错和在码
字中的n个不同位置的⼀位错, 则表⽰: 或。
2 构造海明码的冗余位和监督关系式的⽅法
按上述设计思路, 为了叙述清楚, 下⾯以信息位K=7来讨论海明码的冗余位和监督关系
式的具体构造过程和⽅法。
因为且k=7, 所以≥4, 即⾄少需要4位冗余位(对应产⽣4个校正因⼦和4
个监督关系式), 形成24=16种不同取值, ⽤其中11种分别表⽰⽆错和a0～a10中⼀位错的情况。构造表如表1:
冗余码如下:
a0=a8+a9+a10 (1)
a1=a5+a6+a7 (2)
a2=a4+a6+a7+a9 (3)
a3=a4+a5+a7+a8+a10 (4)
监督关系式如下:
s0=a0+a8+a9+a10 (5)
s1=a1+a5+a6+a7 (6)
s2=a2+a4+a6+a7+a9 (7)
s3=a3+a4+a5+a7+a8 (8)3 构造校正因⼦和监督关系式时应遵循的原则
上表1中, 构造4个校正因⼦和4个监督关系式的过程中, 为了体现前⾯所述设计思想,应遵循如下原则: 图1中共有11列, 每⼀
列应保证各不相同, 即s0 s1 s2 s3 的16种组合中, 取“0000”组合表⽰⽆错, 剩下15种中取其中11种⽤来表⽰a0～a10中某⼀位出
错的情况, 所以,下表2有错, 因为a5 和a7 两列均为“0111”。
4 错码与s0 s1 s2 s3 的对应关系
因为每⼀个校正因⼦都是由⼀个冗余码和构成该冗余码的表达式构成, 如: a0=a8+a9+a10且s0=a0+a8+a9+a10正好是由两个
相等的两部分构成的, 所以在所接收的码字是正确的情况下, 每⼀个校正因⼦都应该是“0”, 当然s0 s1 s2 s3 的16种组合
中,“0000”组合表⽰⽆错, ⽽当⼀位出错时, 如a7 出错时, 因为a7 同时出现在(6)、(7)、(8)三个表达式中, 所以s1 s2s3 同时都受
到影响, 都由“0”变成了“1”, ⽽s0 没变, 仍是“0”, 在接收⽅, 正是通过重新计算s0s1 s2 s3, 根据s0 s1 s2 s3=0111, 可知是a7 错。5 实例
设发送⽅发送信息位为a4a5a6a7a8a9a10=“1001011”, 则根据表达式(1)、(2)、(3)、(4)计算, 冗余码是a0a1a2a3=“0111”,
则发送码字a0a1a2a3a4a5a6a7a8a9a10=“01111001011”, 若接收⽅所收码字a0a1a2a3a4a5a6a7a8a9a10=“01111001001”,
计算s0s1s2s3=“1010”, 查表3知是a9 错。
