汉明码编码原理介绍
- 格式：pdf
- 大小：354.41 KB
- 文档页数：6
汉明码编码原理介绍
汉明码是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。汉明码
在传输的消息流中插入验证码，以侦测并更正单一比特错误。由于汉明编码简单，它们被广泛应用
于内存（RAM）。其SECDED版本另外加入一检测比特，可以侦测两个或以下同时发生的比特错误，并能
够更正单一比特的错误。
1940年，汉明于贝尔实验室工作，运用贝尔模型电脑，输入端依靠打孔卡，这不免有些读取
错误。在平日，特殊代码将发现错误并闪灯，使得操作者能够纠正这个错误。在周末和下班期间，在
没有操作者的情况下，机器只会简单地转移到下一个工作，汉明在周末工作，他对于不可靠的读卡机
发生错误后，总是必须重新开始方案变得愈来愈沮丧。在接下来的几年中，他为了解决调试的问题
，开发了功能日益强大的调试算法。在1950年，他发表了今日所称的汉明码。现在汉明码有着广泛
的应用。
人们在汉明码出现之前使用过多种检查错误的编码方式，但是没有一个可以在和汉明码在相
同空间消耗的情况下，得到相等的效果。
汉明码原理介绍：
奇偶校验是一种添加一个奇偶位用来指示之前的数据中包含有奇数还是偶数个1的检验方式。
如果在传输的过程中，有奇数个位发生了改变，那么这个错误将被检测出来（注意奇偶位本身也可
能改变）。一般来说，如果数据中包含有奇数个1的话，则将奇偶位设定为1；反之，如果数据中
有偶数个1的话，则将奇偶位设定为0。换句话说，原始数据和奇偶位组成的新数据中，将总共包含
偶数个1.
奇偶校验并不总是有效，如果数据中有偶数个位发生变化，则奇偶位仍将是正确的，因此不能
检测出错误。而且，即使奇偶校验检测出了错误，它也不能指出哪一位出现了错误，从而难以进行
更正。数据必须整体丢弃并且重新传输。在一个噪音较大的媒介中，成功传输数据可能需要很长时
间甚至不可能完成。虽然奇偶校验的效果不佳，但是由于他只需要一位额外的空间开销，因此这是
开销最小的检测方式。并且，如果知道了发生错误的位，奇偶校验还可以恢复数据。
如果一条信息中包含更多用于纠错的位，且通过妥善安排这些纠错位使得不同的出错位产生不
同的错误结果，那么我们就可以找出出错位了。在一个7位的信息中，单个数据位出错有7种可能，
因此3个错误控制位就足以确定是否出错及哪一位出错了。
汉明编码方案通用算法
下列通用算法可以为任意位数字产生一个可以纠错一位的汉明码。
一、1开始给数字的数据位（从左向右）标上序号, 1，2，3，4，5...
二、将这些数据位的位置序号转换为二进制，1, 10, 11, 100, 101,等。
三、数据位的位置序号中所有为二的幂次方的位（编号1，2，4，8，等，即数据位位置序号的
二进制表示中只有一个1）是校验位
四、有其它位置的数据位（数据位位置序号的二进制表示中至少2个是1）是数据位
五、每一位的数据包含在特定的两个或两个以上的校验位中，这些校验位取决于这些数据位的位置数值的二进制表示
1.校验位1覆盖了所有数据位位置序号的二进制表示倒数第一位是1的数据：1（校验位自身，
这里都是二进制，下同），11，101，111，1001，等
2.校验位2覆盖了所有数据位位置序号的二进制表示倒数第二位是1的数据：10（校验位自身
），11，110，111，1010，1011，等
3.校验位4覆盖了所有数据位位置序号的二进制表示倒数第三位是1的数据：100（校验位自身
），101，110，111，1100，1101，1110，1111，等
4.校验位8覆盖了所有数据位位置序号的二进制表示倒数第四位是1的数据：1000（校验位自
身），1001，1010，1011，1100，1101，1110，1111，等
5.简而言之，所有校验位覆盖了数据位置和该校验位位置的二进制与的值不为0的数。
采用奇校验还是偶校验都是可行的。偶校验从数学的角度看更简单一些，但在实践中并没有
区别。
从编码形式上，我们可以发现汉明码是一个校验很严谨的编码方式。在这个例子中，通过对4
个数据位的3个位的3次组合检测来达到具体码位的校验与修正目的(不过只允许一个位出错，两个
出错就无法检查出来了，这从下面的纠错例子中就能体现出来)。在校验时则把每个汉明码与各自对
应的数据位值相加，如果结果为偶数(纠错代码为0)就是正确，如果为奇数(纠错代码为1)则说明当
前汉明码所对应的三个数据位中有错误，此时再通过其他两个汉明码各自的运算来确定具体是哪个
位出了问题。
· 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
编码后数据位置 p1 p2 d1 p4 d2 d3 d4 p8 d5 d6 d7 d8 d9 d10 d11 p16 d12 d13 d14 d15
奇偶校验位 覆盖率 p1 X X X X X X X X X X p2 X X X X X X X X X X p4 X X X X X X X X X
p8 X X X X X X X X p16 X X X X X
观察上表可发现一个比较直观的规律：第i个检验位是第2i-1位，从该位开始，检验2i-1位，
跳过2i-1位……依次类推。例如上表中第3个检验位p4从第23-1=4位开始，检验4、5、6、7共4
位，然后跳过8、9、10、11共4位，再检验12、13、14、15共4位……
在数学方面，汉明码是一种二元线性码。对于每一个整数m>2，存在一个编码，带有m个奇偶校验位2m- m-1个数据位。 例子
对11000010进行汉明编码，求编码后的码字。
1.列出表格，从左往右（或从右往左）填入数字，但2的次方的位置不填。 位置 1 2 3 4 5 6 7 8 9 10 11 12 13 14
数据 1 1 0 0 0 0 1 0
2.把数据行有1的列的位置写为二进制。 位置 1 2 3 4 5 6 7 8 9 10 11 12 13 14
数据 1 1 0 0 0 0 1 0 二进制 0011 0101 1011
3.收集所有二进制数字，求异或。
4.把1101依次填入表格中2的次方的位置（低位在左）。 位置 1 2 3 4 5 6 7 8 9 10 11 12 13 14
数据 1 1 0 0 0 0 1 0
二进制 0011 0101 1011 校验 1 0 1 1
5.所以编码后的码字是101110010010。
以数据码1101为例再次码的编码原理，此时D8=1、D4=1、D2=0、D1=1，在P1编码时，先将D8、D4、D1的二进制码相加，结果为奇数3，汉明码对奇数结果编码为1，偶数结果为0，因此P1值为1，D8+D2+D1=2，为偶数，那么P2值为0，D4+D2+D1=2，为偶数，P3值为0。这样，参照上文的位置表，汉明码处理的结果就是1010101。在这个4位数据码的例子中，我们可以发现每个汉明码都是以三个数据码为基准进行编码的。下面就是它们的对应表:
编码用的数据码
P1 （D8、D4、D1）
P2 （D8、D2、D1）
P3 （D4、D2、D1）
从编码形式上，我们可以发现汉明码是一个校验很严谨的编码方式。在这个例子中，通过对4个
数据位的3个位的3次组合检测来达到具体码位的校验与修正目的(不过只允许一个位出错，两个出
错就无法检查出来了，这从下面的纠错例子中就能体现出来)。在校验时则把每个汉明码与各自对应
的数据位值相加，如果结果为偶数(纠错代码为0)就是正确，如果为奇数(纠错代码为1)则说明当前
汉明码所对应的三个数据位中有错误，此时再通过其他两个汉明码各自的运算来确定具体是哪个位
出了问题。
1950年，汉明介绍了(7,4)代码。其编码由4数据比特到7位，增加三个奇偶校验码。汉明(7,4)
可以检测并纠正单比特错误，且也能检测双比特错误。
带附加奇偶校验码的汉明码（SECDED），汉明(8,4)码：汉明(7,4)码可以很容易地编码为一个(8,4)
码 汉明距离：
在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句
话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：
1011101与1001001之间的汉明距离是2。
2143896与2233796之间的汉明距离是3。 "toned"与"roses"之间的汉明距离是3。
汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元
素个数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。
Hamming码编译码器的设计
Hamming码编译码器的设计
首先构造最佳奇权码的校验矩阵即H矩阵，最佳奇权码的H矩阵应满足：
(1)每列含有奇数个1，且无相同列；
(2)总的1的个数少，所以校验位、伴随式生成表达式中的半加项数少，从而生成逻辑所需的半加
器少，可以节约器材、降低成本和提高可靠性。
(3)每行中1的个数尽量相等或接近某个平均值，这种决定了生成逻辑及其级数的一致性，不仅
译码速度快，同时线路匀称。
译码时把数据再次编码所得到的新校验位与原校验位模二加，便得到伴随式S，由其可判别错误
类型。
