汉明码及其算法.doc

汉明码编辑（重定向自Hamming code）汉明码（Hamming Code），是在电信领域的一种线性调试码，以发明者理查德卫斯里汉明的名字命名。汉明码在传输的消息流中插入验证码，以侦测并更正单一比特错误。由于汉明编码简单，它们被广泛应用于内存（RAM）。其SECDED（single error correction, double error detection）版本另外加入一检测比特，可以侦测两个或以下同时发生的比特错误，并能够更正单一比特的错误。因此，当发送端与接收端的比特样式的汉明距离（Hamming distance）小于或等于1时（仅有1 bit发生错误），可实现可靠的通信。相对的，简单的奇偶检验码除了不能纠正错误之外，也只能侦测出奇数个的错误。在数学方面，汉明码是一种二元线性码。对于每一个整数，存在一个编码，带有个奇偶校验位个数据位。该奇偶检验矩阵的汉明码是通过列出所有米栏的长度是两两独立。目录 1历史 1.1汉明码之前 1.1.1奇偶 2汉明码 2.1通用算法 2.2例子 3带附加奇偶校验码的汉明码（SECDED） 4汉明(7,4)码 5创建奇偶检验矩阵 6编码 7汉明(8,4)码 8汉明(11,7)码 9相关条目 10参考文献 11外部链接历史编辑1940年，汉明于贝尔实验室（Bell Labs）工作，运用贝尔模型V（Bell Model V）电脑，一个周期时间在几秒钟内的机电继电器机器。输入端是依靠打孔卡（Punched Card），这不免有些读取错误。在平日，特殊代码将发现错误并闪灯（flash lights），使得操作者能够纠正这个错误。在周末和下班期间，在没有操作者的情况下，机器只会简单地转移到下一个工作。汉明在周末工作，他对于不可靠的读卡机发生错误后，总是必须重新开始项目变得愈来愈沮丧。在接下来的几年中，他为了解决调试的问题，开发了功能日益强大的调试算法。在1950年，他发表了今日所称的汉明码。现在汉明码有着广泛的应用。汉明码之前编辑人们在汉明码出现之前使用过多种检查错误的编码方式，但是没有一个可以在和汉明码在相同空间消耗的情况下，得到相等的效果。奇偶编辑主条目：奇偶校验位奇偶校验是一种添加一个奇偶位用来指示之前的数据中包含有奇数还是偶数个1的检验方式。如果在传输的过程中，有奇数个位发生了改变，那么这个错误将被检测出来（注意奇偶位本身也可能改变）。一般来说，如果数据中包含有奇数个1的话，则将奇偶位设定为1；反之，如果数据中有偶数个1的话，则将奇偶位设定为0。换句话说，原始数据和奇偶位组成的新数据中，将总共包含偶数个1.奇偶校验并不总是有效，如果数据中有偶数个位发生变化，则奇偶位仍将是正确的，因此不能检测出错误。而且，即使奇偶校验检测出了错误，它也不能指出哪一位出现了错误，从而难以进行更正。数据必须整体丢弃并且重新传输。在一个噪音较大的媒介中，成功传输数据可能需要很长时间甚至不可能完成。虽然奇偶校验的效果不佳，但是由于他只需要一位额外的空间开销，因此这是开销最小的检测方式。并且，如果知道了发生错误的位，奇偶校验还可以恢复数据。汉明码如果一条信息中包含更多用于纠错的位，且通过妥善安排这些纠错位使得不同的出错位产生不同的错误结果，那么我们就可以找出出错位了。在一个7位的信息中，单个位出错有7种可能，因此3个错误控制位就足以确定是否出错及哪一位出错了。汉明研究了包括五取二码在内的编码方案，并归纳了他们的想法。通用算法下列通用算法可以为任意位数字产生一个可以纠错一位（英语：SingleErrorCorrecting）的汉明码。1. 从1开始给数字的数据位（从左向右）标上序号, 1，2，3，4，5.2. 将这些数据位的位置序号转换为二进制，1, 10, 11, 100, 101,等。3. 数据位的位置序号中所有为二的幂次方的位（编号1，2，4，8，等，即数据位位置序号的二进制表示中只有一个1）是校验位4. 所有其它位置的数据位（数据位位置序号的二进制表示中至少2个是1）是数据位5. 每一位的数据包含在特定的两个或两个以上的校验位中，这些校验位取决于这些数据位的位置数值的二进制表示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的数。采用奇校验还是偶校验都是可行的。偶校验从数学的角度看更简单一些，但在实践中并没有区别。校验位一般的规律可以如下表示：数据位位置1234567891011121314151617181920.编码后数据位置p1p2d1p4d2d3d4p8d5d6d7d8d9d10d11p16d12d13d14d15奇偶校验位覆盖率p1XXXXXXXXXXp2XXXXXXXXXXp4XXXXXXXXXp8XXXXXXXXp16XXXXX观察上表可发现一个比较直观的规律：第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位例子对11000010进行汉明编码，求编码后的码字。1.列出表格，从左往右（或从右往左）填入数字，但2的次方的位置不填。位置1234567891011121314数据110000102.把数据行有1的列的位置写为二进制。位置1234567891011121314数据11000010二进制0011010110113.收集所有二进制数字，求异或。4.把1101依次填入表格中2的次方的位置（低位在左）。位置1234567891011121314数据11000010二进制001101011011校验10115.所以编码后的码字是101110010010。带附加奇偶校验码的汉明码（SECDED）汉明(7,4)码Graphical depiction of the 4 data bits and 3 parity bits and which parity bits apply to which data bits主条目：汉明(7,4)码1950年，汉明介绍了(7,4)代码。其编码由4数据比特到7位，增加三个奇偶校验码。汉明(7,4)可以检测并纠正单比特错误，且也能检测双比特错误。创建奇偶检验矩阵矩阵被称为（标准）生成矩阵线性(n,k)码。和被称为奇偶检验矩阵。编码编辑示例从上述矩阵我们有2k=24=16码词。二进制码的码词可以从得到。对和存在(一个只有0和1的二元域）。故此码表即是所有4个三元组（k个三元组）。因而，（1,0,1,1）编码为（0,1,1,0,0,1,1）。汉明(8,4)码编辑The same (7,4) example from above with an extra parity bit汉明(7,4)码可以很容易地编码为一个(8,4)码，通过在(7,4)编码词（参见汉明(7,4)码）上附加一个额外的奇偶位。这可以用下面修正的矩阵相加：和。注意，并非用标准形式表示。为了得到，原子行操作能够被用来获得一个等价的矩阵对陈形式的：。参考文献 Moon, Todd K.Error Correction Coding.New Jersey:John Wiley & Sons. 2005.ISBN978-0-471-64800-0. MacKay, David J.C.Information Theory, Inference and Learning Algorithms.Cambridge:Cambridge University Press. 2003-09.ISBN0-521-64298-1. D.K. Bhattacharryya,