理查德·哈明 - 圖靈獎
一提起“哈明碼”，恐怕很少有人不知道的。這種能找出并糾正數(shù)據(jù)塊在傳輸過程中出現(xiàn)的錯誤的編碼方法，對于計算機(jī)技術(shù)和通信技術(shù)來說真是太重要了。發(fā)明這種編碼技術(shù)的理查德·哈明(Richard Wesley Hamming，1915—1998)因此而獲得了第三屆即1968年度的圖靈獎。理查德·哈明 - 簡介
哈明到貝爾實驗室后接受的第一個任務(wù)就是解決通信中令人頭痛的誤碼問題。通信時發(fā)送方發(fā)出的信息在傳輸過程中由于信號的衰減和外界的電磁干擾，到接收方產(chǎn)生了畸變和失真，獲得的是錯誤的信息。這在商業(yè)、軍事等應(yīng)用中都會產(chǎn)生嚴(yán)重的后果，有時簡直會禍國殃民，因此迫切需要加以解決。但在相當(dāng)一段時間里，這成了擺在許許多多科學(xué)家和工程師面前的一大難題，誰也找不出解決的好辦法。哈明接受這個任務(wù)以后，意識到通信線路質(zhì)量的改善是有限度的，外界干擾是客觀存在也無法絕對避免，因此這個問題不可能通過讓發(fā)送的代碼不出錯這條途徑去解決，而只能通過一旦出錯如何發(fā)現(xiàn)、如何糾正才能解決。這使哈明的研究沿著正確的路線進(jìn)行。經(jīng)過深入探討，1947年哈明終于發(fā)明了一種能糾錯的編碼，這種碼就叫“糾錯碼”(error-correcting-code)或“哈明碼”(Hamming code)。哈明碼是一種冗余碼，即在有效信息代碼中要加入校驗位，這是為糾錯而必須付出的代價。其基本原理是使每一信息位參與多個不同的奇偶校驗(parity check)。所謂奇偶校驗是在代碼中設(shè)置一個校驗位，通常置于代碼的最左邊。若整個代碼中“1”的個數(shù)為奇數(shù)認(rèn)為代碼正確，稱為奇校驗(odd check)；反之，若整個代碼中“1”的個數(shù)為偶數(shù)認(rèn)為正確，則稱為偶校驗(even check)。哈明碼就是有多個奇偶校驗位的一種代碼，在適當(dāng)安排下，通過這多個奇偶校驗位就可以檢查出代碼傳送中的錯誤并自動糾正。一般而言，對于長度為n位的代碼，其中應(yīng)包括r個校驗位，有效信息位為n-r，r的值應(yīng)滿足以下公式：2r-1≥n
下面我們舉一個例子簡單說明哈明碼的原理。以7位字組的二進(jìn)制編碼的十進(jìn)制數(shù)的傳送為例，根據(jù)以上公式，有效信息為4位，校驗位為3位。安排3、5、6、7四位為信息位，而1、2、4三位為校驗位，如下圖所示。
發(fā)送時，信息位的內(nèi)容當(dāng)然是根據(jù)所要發(fā)送的十進(jìn)制數(shù)是幾而定的，1、2、4三個校驗位的內(nèi)容是按以下規(guī)則自動生成的：
校驗位1：由1、3、5、7四位的偶校驗決定校驗位1的內(nèi)容；
校驗位2：由2、3、6、7四位的偶校驗決定校驗位2的內(nèi)容；
校驗位4：由4、5、6、7四位的偶校驗決定校驗位4的內(nèi)容。
也就是說，比如對校驗位1，若3、5、7三位中“1”的個數(shù)為奇數(shù)，則校驗位1置為“1”；若3、5、7三位中“l(fā)”的個數(shù)為偶數(shù)，則校驗位1置為“0”，其余類推。
這樣形成的7位代碼發(fā)送出去以后，若到了接收方發(fā)生錯誤，就能檢測出來并可自動糾正。舉例說，發(fā)送的數(shù)是“6”，應(yīng)為1100110，但接收到的卻是1110110，則通過對上述三組4位代碼的偶校驗，發(fā)現(xiàn)第l和第2兩組中“1”的個數(shù)都為奇可斷定發(fā)生錯誤；錯的是哪一位呢?這可通過如下辦法確定：哪一組的偶校驗通過，記為0；偶校驗出錯，記為1，第一組到第三組按從右到左的次序排列所形成的二進(jìn)制數(shù)就確定了出錯列的位置。這里是"01l”，即3，可斷定左起第3位出了錯，把它反過來(這里是把“廠變成“0”)就是了。同理，若接收結(jié)果為1100111，則三組偶校驗均出錯，記為“111”，指明第7位出錯，把它反過來即可。
大家看，多么巧妙!當(dāng)然這個例子僅僅是最簡單的情況�，F(xiàn)在，包括哈明碼在內(nèi)的整個編碼學(xué)已建立在十分復(fù)雜而嚴(yán)格的數(shù)學(xué)理論基礎(chǔ)之上，要用到抽象代數(shù)(abstract algebra)，包括伽洛瓦理論(Galois theory)等。
哈明碼的發(fā)明是為了解決通信中的誤碼問題，但對計算機(jī)同樣有用。因為計算機(jī)的CPU、內(nèi)外存、各種外部設(shè)備之間的代碼傳送同樣存在著誤碼的可能。例如，計算機(jī)的存儲器差錯校驗(memory error checking and correction)就常常采用哈明碼校驗。在計算機(jī)聯(lián)成網(wǎng)絡(luò)的情況下，數(shù)據(jù)通信的可靠性問題更為突出。ACM在將圖靈獎授予哈明的1968年，計算機(jī)網(wǎng)絡(luò)的研究剛剛開始不久，Internet的始祖ARPANET是1969年才將最早的4個站點連通的。從這點看，ACM在圖靈獎的評獎中是很有遠(yuǎn)見的。
作為一名數(shù)學(xué)家，哈明的專長是數(shù)值方法、編碼與信息論、統(tǒng)計學(xué)和數(shù)字濾波器等。這些學(xué)科中有不少名詞術(shù)語是由哈明定義，因此而用哈明命名的，除“哈明碼”外，常見的還有：
“哈明間距”(Hamming distance)：這指同樣長度的兩個碼中，對應(yīng)位不同的碼的個數(shù)。比如01010和11001，哈明間距為3。
“哈明權(quán)”(Hamming weight)。這指代碼中1的個數(shù)。如01110的哈明權(quán)為3。
“哈明窗口”(Hamming window)。這指一種濾波器的通頻帶，共傳遞函數(shù)的解析式為：
哈明的論著頗多，主要有：
《科學(xué)家和工程師用的數(shù)值方法》(Numerical Methods for Scientists and Engineers，McGraw-Hill，1973，第2版)
《數(shù)字濾波器》(Digital Filter，Prentice-Hall，1977，1983，1989)
〈編碼和信息論〉(Coding and Information Theory，Prentice-Hall，1980，1986)
《用于微積分、概率論和統(tǒng)計學(xué)的數(shù)學(xué)方法》(Methods of Mathematics Applied to Calculus，Probability，and Statistics，Prentice-Hall，1985)
《計算機(jī)與社會》(Computers and Society，McGraw-Hill，1972)
《實用數(shù)值分析導(dǎo)論》(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)
哈明有一句名言：“計算的目的不在于數(shù)據(jù)，而在于洞察事物”(“The purpose Of computing is insight，not numbers")。此外，他還非常欣賞孔子的話：“學(xué)而時習(xí)之，不亦悅乎”，把這句話印在他著的《科學(xué)家和工程師用的數(shù)值方法》那本書的卷首作為座右銘(英文是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獎(這是賓夕法尼亞大學(xué)所設(shè)立的一個獎項)，1996年獲得Rhein基金會獎。有趣的是，IEEE設(shè)立了一種以哈明命名的獎?wù)拢?991年把這種獎?wù)骂C給了哈明本人。
哈明在接受圖靈獎時發(fā)表了題為“我對計算機(jī)科學(xué)的看法”(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頁。他在演說中提出的以下一些觀點，如計算機(jī)科學(xué)家必須具有良好的數(shù)學(xué)訓(xùn)練，應(yīng)該由相關(guān)的系而不是由計算機(jī)系來教授計算機(jī)應(yīng)用方面的課程，以及應(yīng)該注重計算機(jī)程序設(shè)計風(fēng)格的教育，等等，至今仍具有十分重要的意義。最后，他還指出與計算機(jī)有關(guān)的一些事是涉及倫理學(xué)與道德方面的棘手的問題，在盜版現(xiàn)象嚴(yán)重與黑客猖獗以及計算機(jī)犯罪、色情網(wǎng)站層出不窮的今天，真令人感慨于哈明的先知先覺。
