Hamming.doc

理查德·哈明——发明纠错码的大数学家和信息学专家一提起“哈明码”，恐怕很少有人不知道的这种能找出并纠正数据块在传输过程中出现的错误的编码方法，对于计算机技术和通信技术来说真是太重要了发明这种编码技术的理查德·哈明(Richard Wesley Hamming，1915—1998)因此而获得了第三届即1968 年度的图灵奖哈明 1915 年 2 月 11 日生于芝加哥1937 年在芝加哥大学获得数学学士学位，1939 年在内布拉斯加大学获得硕士学位，接着又于 1942 年在伊利诺伊大学获得博士学位，成为一名数学专家学成以后，他留校工作两年，然后转入肯塔基州位于俄亥俄河畔的路易斯维尔大学任教，两年后来到洛斯阿拉莫斯国家实验室，参与了著名的曼哈顿计划但在那里哈明也只呆了两年，就又转到贝尔实验室工作正是在这里，哈明遇到了他感兴趣和能发挥他特长的课题，也有一个适宜的工作环境，因此一千就是 30 年(1946—1976) 这期间，他曾长期担任贝尔实验室计算机科学部的主任1976 年他离开贝尔，到美国海军研究生院(Naval Postgraduate School，在加利福尼亚州的蒙特雷) 工作，直到 1997 年 82 岁高龄时才退休，第二年 1 月 7 日去世，享年 83 岁。

哈明到贝尔实验室后接受的第一个任务就是解决通信中令人头痛的误码问题通信时发送方发出的信息在传输过程中由于信号的衰减和外界的电磁干扰，到接收方产生了畸变和失真，获得的是错误的信息这在商业、军事等应用中都会产生严重的后果，有时简直会祸国殃民，因此迫切需要加以解决但在相当一段时间里，这成了摆在许许多多科学家和工程师面前的一大难题，谁也找不出解决的好办法哈明接受这个任务以后，意识到通信线路质量的改善是有限度的，外界干扰是客观存在也无法绝对避免，因此这个问题不可能通过让发送的代码不出错这条途径去解决，而只能通过一旦出错如何发现、如何纠正才能解决这使哈明的研究沿着正确的路线进行经过深入探讨，1947 年哈明终于发明了一种能纠错的编码，这种码就叫“纠错码”(error-correcting-code) 或“ 哈明码”(Hamming code)哈明码是一种冗余码，即在有效信息代码中要加入校验位，这是为纠错而必须付出的代价其基本原理是使每一信息位参与多个不同的奇偶校验(parity check)所谓奇偶校验是在代码中设置一个校验位，通常置于代码的最左边若整个代码中“1”的个数为奇数认为代码正确，称为奇校验(odd check)；反之，若整个代码中“1”的个数为偶数认为正确，则称为偶校验(even check)。

哈明码就是有多个奇偶校验位的一种代码，在适当安排下，通过这多个奇偶校验位就可以检查出代码传送中的错误并自动纠正一般而言，对于长度为 n位的代码，其中应包括 r 个校验位，有效信息位为 n-r，r 的值应满足以下公式：2r-1≥n下面我们举一个例子简单说明哈明码的原理以 7 位字组的二进制编码的十进制数的传送为例，根据以上公式，有效信息为 4 位，校验位为 3 位安排 3、5 、6 、7 四位为信息位，而 1、2、4 三位为校验位，如下图所示发送时，信息位的内容当然是根据所要发送的十进制数是几而定的，1、2、4 三个校验位的内容是按以下规则自动生成的：校验位 1：由 1、3、5、7 四位的偶校验决定校验位 1 的内容；校验位 2：由 2、3、6、7 四位的偶校验决定校验位 2 的内容；校验位 4：由 4、5、6、7 四位的偶校验决定校验位 4 的内容也就是说，比如对校验位 1，若 3、5、7 三位中“1”的个数为奇数，则校验位 1 置为“1”；若 3、5、7 三位中“l”的个数为偶数，则校验位 1 置为“0”，其余类推这样形成的 7 位代码发送出去以后，若到了接收方发生错误，就能检测出来并可自动纠正。

举例说，发送的数是“6”，应为 1100110，但接收到的却是 1110110，则通过对上述三组 4 位代码的偶校验，发现第 l 和第 2 两组中 “1”的个数都为奇可断定发生错误；错的是哪一位呢?这可通过如下办法确定：哪一组的偶校验通过，记为 0；偶校验出错，记为 1，第一组到第三组按从右到左的次序排列所形成的二进制数就确定了出错列的位置这里是"01l”，即 3，可断定左起第 3 位出了错，把它反过来(这里是把“ 厂变成“0”)就是了同理，若接收结果为 1100111，则三组偶校验均出错，记为“111”，指明第 7 位出错，把它反过来即可大家看，多么巧妙!当然这个例子仅仅是最简单的情况现在，包括哈明码在内的整个编码学已建立在十分复杂而严格的数学理论基础之上，要用到抽象代数(abstract algebra)，包括伽洛瓦理论(Galois theory)等哈明码的发明是为了解决通信中的误码问题，但对计算机同样有用因为计算机的 CPU、内外存、各种外部设备之间的代码传送同样存在着误码的可能例如，计算机的存储器差错校验(memory error checking and correction)就常常采用哈明码校验。

在计算机联成网络的情况下，数据通信的可靠性问题更为突出ACM 在将图灵奖授予哈明的 1968 年，计算机网络的研究刚刚开始不久，Internet 的始祖ARPANET 是 1969 年才将最早的 4 个站点连通的从这点看，ACM 在图灵奖的评奖中是很有远见的作为一名数学家，哈明的专长是数值方法、编码与信息论、统计学和数字滤波器等这些学科中有不少名词术语是由哈明定义，因此而用哈明命名的，除“哈明码” 外，常见的还有：“哈明间距”(Hamming distance)：这指同样长度的两个码中，对应位不同的码的个数比如 01010 和11001，哈明间距为 3哈明权”(Hamming weight)这指代码中 1 的个数如 01110 的哈明权为 3哈明窗口”(Hamming window)这指一种滤波器的通频带，共传递函数的解析式为：哈明的论著颇多，主要有： 《科学家和工程师用的数值方法》(Numerical Methods for Scientists and Engineers，McGraw-Hill， 1973，第 2 版)《数字滤波器》(Digital Filter，Prentice-Hall，1977 ，1983，1989)〈编码和信息论〉(Coding and Information Theory，Prentice-Hall ，1980，1986)《用于微积分、概率论和统计学的数学方法》(Methods of Mathematics Applied to Calculus，Probability ，and Statistics，Prentice-Hall，1985)《计算机与社会》(Computers and Society，McGraw-Hill，1972)《实用数值分析导论》(Introduction to Applied Numerical Analysis，Hemisphere Pub.,1989)《概率论的技巧》(The Art of Probability，Addison-Wesley，1991)《从事科技工作的技巧》(The Art of Doing Science and Engineering，Gorden and Breach Science Pub.，1997)哈明有一句名言：“计算的目的不在于数据，而在于洞察事物 ”(“The purpose Of computing is insight，not numbers")。

此外，他还非常欣赏孔子的话：“学而时习之，不亦悦乎”，把这句话印在他著的《科学家和工程师用的数值方法》那本书的卷首作为座右铭(英文是 To study，and when the occasion arises to what one has learned into practice is that not deeply satisfying?)纵观哈明的一生，他自己就是实践这两句话的一生哈明是美国工程院院士，1958—1960 年曾出任 ACM 的第七届主席除获得图灵奖外，1979 年他获得 IEEE 的 Piore 奖，1981 年获得 H．Pender 奖(这是宾夕法尼亚大学所设立的一个奖项 )，1996 年获得 Rhein 基金会奖有趣的是，IEEE 设立了一种以哈明命名的奖章，1991 年把这种奖章颁给了哈明本人哈明在接受图灵奖时发表了题为“我对计算机科学的看法”(On Man、View of Computer Science)的演说，刊载于 Journal of ACM，1969 年 1 月，3-12 页，也可见《前 20 年的图灵奖演说集》(ACM Turing Award Lectures—The First 20 Years：1966—1985，ACM Pr．)，207 —218 页。

他在演说中提出的以下一些观点，如计算机科学家必须具有良好的数学训练，应该由相关的系而不是由计算机系来教授计算机应用方面的课程，以及应该注重计算机程序设计风格的教育，等等，至今仍具有十分重要的意义最后，他还指出与计算机有关的一些事是涉及伦理学与道德方面的棘手的问题，在盗版现象严重与黑客猖獗以及计算机犯罪、色情网站层出不穷的今天，真令人感慨于哈明的先知先觉。