——发明纠错码的大数学家和信息学专家

理查德·哈明 - 图灵奖

    一提起“哈明码”，恐怕很少有人不知道的。这种能找出并纠正数据块在传输过程中出现的错误的编码方法，对于计算机技术和通信技术来说真是太重要了。发明这种编码技术的理查德·哈明(Richard  Wesley  Hamming，1915—1998)因此而获得了第三届即1968年度的图灵奖。

理查德·哈明 - 简介

哈明到贝尔实验室后接受的第一个任务就是解决通信中令人头痛的误码问题。通信时发送方发出的信息在传输过程中由于信号的衰减和外界的电磁干扰，到接收方产生了畸变和失真，获得的是错误的信息。这在商业、军事等应用中都会产生严重的后果，有时简直会祸国殃民，因此迫切需要加以解决。但在相当一段时间里，这成了摆在许许多多科学家和工程师面前的一大难题，谁也找不出解决的好办法。哈明接受这个任务以后，意识到通信线路质量的改善是有限度的，外界干扰是客观存在也无法绝对避免，因此这个问题不可能通过让发送的代码不出错这条途径去解决，而只能通过一旦出错如何发现、如何纠正才能解决。这使哈明的研究沿着正确的路线进行。经过深入探讨，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页。他在演说中提出的以下一些观点，如计算机科学家必须具有良好的数学训练，应该由相关的系而不是由计算机系来教授计算机应用方面的课程，以及应该注重计算机程序设计风格的教育，等等，至今仍具有十分重要的意义。最后，他还指出与计算机有关的一些事是涉及伦理学与道德方面的棘手的问题，在盗版现象严重与黑客猖獗以及计算机犯罪、网站层出不穷的今天，真令人感慨于哈明的先知先觉。