海明码 海明码确定校验码位置

海明码是一种纠错码，是在数据位中添加若干冗余位组成新的码字。海明码的理论太深奥了，就不说了。

海明码的两个结论：

1. 如果任意两个码字之间的海明距离是d，则所有少于等于d-1位的错误都可以检查出来，所有少于d/2位的错误都可以纠正。
2. 对于某长度的错误串，要纠正它就要用比仅仅检测它多一倍的冗余位。

码字长度（n）、数据位长度（k）和冗余位长度（r)之间的关系式：

n=k+r  ……………………①

2^r>=n+1=k+r+1 …………②

海明码的编码效率R=k/(k+r)

一个码字的海明距离d=2^r（r是冗余位长度）

冗余位的长度可以根据式②来确定，冗余位各位的值由监督关系式（S₀，S₁，……，S_r-1)计算而得。监督关系式一般是给出的，监督关系式确定了冗余位各位的值和各个冗余位在码字中的具体位置。在监督关系式中只出现一次的码位即是冗余位，如：

S₀=a₀a₃a₄a₆

S₁=a₁a₃a₅a₆

S₂=a₂a₄a₅a₆

根据以上三式，可 以得出该码字中的a₀a₁a₂为冗余位。

海明码的计算

一、给出监督关系式

（一）、生成

1. 根据监督关系式得出冗余位
2. 根据监督关系式各式为0计算出各冗余位的值
3. 根据冗余位的值和位置生成已知信息位的海明码字

例：已知信息位：0010，监督关系式为

S₀=a₀a₃a₄a₆

S₁=a₁a₃a₅a₆

S₂=a₂a₄a₅a₆

求海明码码字。答案：0010101

（二）、接收

1. 根据接收码字计算监督关系式各式的值
2. 如果监督关系式各式值不全为零，那么值为1的各式共同出现的码位即为出错位
3. 将出错位取反得到正确的码字
4. 删除冗余位，剩余位即为信息位

例：已知监督关系式为

S₀=a₀a₃a₄a₆

S₁=a₁a₃a₅a₆

S₂=a₂a₄a₅a₆

接收码字：0011101

求发送的信息位。答案：0010

二、未给出监督关系式，即冗余位是按照1，2，4，……，2^r-1（r为冗余位长度）确定位置的，监督关系式S₀,S₁,……，S_r-1的下标可与冗余位的冥指数相对应。各监督关系有如下规律：从该冗余位开始，取2^r-1位，间隔2^r-1位,……，直到最后一位,如S₀就是取1，3，5，9，……；S₁就是取2，3，6，7，10，11，……。

（一）、生成

1. 按照规律计算各个监督关系式的值
2. 根据值和位置形成海明码

例：已知信息位11001100，求海明码。答案：101110001100

（二）、接收

1. 根据接收码字计算各监督关系式的值
2. 如果不全为零，将值为1的关系式下标做为2的冥指数，累加得到出错位
3. 将出错位取反得到正确的接收码字
4. 删除冗余位得到发送的信息位

例：已知接收码字100110001100，求发送的信息码。答案：11001100

爱华网本文地址 » http://www.413yy.cn/a/25101015/251703.html