汉明码纠错算法介绍.doc

汉明码纠错算法介绍 汉明码纠错算法介绍 1 一、汉明码历史背景 1 二、汉明码原理介绍 1 （一） 奇偶校验 1 （二） 汉明码 2 （三）汉明编码方案通用算法 4 例子 5 （三）汉明距离和汉明重量 7 （四）汉明码编码数学原理 7 一、汉明码历史背景 汉明码是在电信领域的一种线性调试码，以发明者理查德·卫斯里·汉明的名字命名。汉明码在传输的消息流中插入验证码，以侦测并更正单一比特错误。由于汉明编码简单，它们被广泛应用于内存（RAM）。其SECDED版本另外加入一检测比特，可以侦测两个或以下同时发生的比特错误，并能够更正单一比特的错误。 1940年，汉明于贝尔实验室工作，运用贝尔模型电脑，输入端依靠打孔卡，这不免有些读取错误。在平日，特殊代码将发现错误并闪灯，使得操作者能够纠正这个错误。在周末和下班期间，在没有操作者的情况下，机器只会简单地转移到下一个工作，汉明在周末工作，他对于不可靠的读卡机发生错误后，总是必须重新开始方案变得愈来愈沮丧。在接下来的几年中，他为了解决调试的问题，开发了功能日益强大的调试算法。在1950年，他发表了今日所称的汉明码。现在汉明码有着广泛的应用。 人们在汉明码出现之前使用过多种检查错误的编码方式，但是没有一个可以在和汉明码在相同空间消耗的情况下，得到相等的效果。 二、汉明码原理介绍 （一） 奇偶校验 奇偶校验是一种添加一个奇偶位用来指示之前的数据中包含有奇数还是偶数个1的检验方式。如果在传输的过程中，有奇数个位发生了改变，那么这个错误将被检测出来（注意奇偶位本身也可能改变）。一般来说，如果数据中包含有奇数个1的话，则将奇偶位设定为1；反之，如果数据中有偶数个1的话，则将奇偶位设定为0。换句话说，原始数据和奇偶位组成的新数据中，将总共包含偶数个1. 奇偶校验并不总是有效，如果数据中有偶数个位发生变化，则奇偶位仍将是正确的，因此不能检测出错误。而且，即使奇偶校验检测出了错误，它也不能指出哪一位出现了错误，从而难以进行更正。数据必须整体丢弃并且重新传输。在一个噪音较大的媒介中，成功传输数据可能需要很长时间甚至不可能完成。虽然奇偶校验的效果不佳，但是由于他只需要一位额外的空间开销，因此这是开销最小的检测方式。并且，如果知道了发生错误的位，奇偶校验还可以恢复数据。 如果一条信息中包含更多用于纠错的位，且通过妥善安排这些纠错位使得不同的出错位产生不同的错误结果，那么我们就可以找出出错位了。在一个7位的信息中，单个数据位出错有7种可能，因此3个错误控制位就足以确定是否出错及哪一位出错了。 如果这种纠错码的纠错能力为纠正1个差错，则应满足如下基本条件: 当上式取等号时则称汉明码(Hamming Code)。干扰不仅使原代码的每一位(k比特)可能出错，而且附加纠错位(r比特)也可能出错，故“一个差错”的情况共有k+r种，加上“正常”状态共有k+r+l种状态，而r比特的附加纠错位要能分辨这k+r+l种状态。。 （二） 汉明码 汉明码是怎么知道二进制信息在传输过程中哪一位传错的呢？究竟是什么支配着这种编码纠错的可靠性呢。首先我们要知道的是，汉明码是只具有一位纠错能力的编码，那么二进制信息的传输校验可以在最多只有一位发生误传这个假设下讨论。 这个问题的一个数学模型是：发送方将一串任意长度的01代码通过一定的处理，使得代码的在只有一位发生传送错误（不包括一位代码的增加或者缺失）或者完全正确的传输送达接收方的前提下，接收方能还原发送方发送的代码。 汉明码给出了一个完美的解答。它的解决方案如下：设欲检测的二进制代码有n位，为使其具有纠错能力，需要增加k位检测为。为了能准确对错误定位以及指出代码没错，新增添的检测位数k应满足 k的位数确定以后，便可由它们所承担的检测任务设定设定它们在被检测代码中的位置以及它们的取值。 设位代码自左向右依次编为第1,2,3,4，....，位，而将k为检测为记作（这里的C应该是check的首字母把。。。），重点来了： 检测的小组包含1,3,5,7,9,11............位。 检测的小组包含2,3,6,7,10,11,14,15......位 检测的小组包含4,5,6,7,12,13,14,15,......位 检测的小组包含8,9,10,11,12,13,14,15,24,......位 1 3 5 7 9 11 13 二进制 1 11 101 111 1001 1011 1101 小组二进制表示次低位为1 2 3 6 7 10 11 14 二进制 10 11 110 111 1010 1011 1110 小组二进制表示倒数第三位为1,因为 4 5 6 7 12 13 14 二进制 100 101 110 111 1100 1101