理察·哈明

理察·哈明

理察·哈明,發明糾錯碼的大數學家和信息學專家。一提起“哈明碼”,恐怕很少有人不知道的。這種能找出並糾正數據塊在傳輸過程中出現的錯誤的編碼方法,對於計算機技術和通信技術來說真是太重要了。發明這種編碼技術的理察·哈明因此而獲得了第三屆即1968年度的圖靈獎。

基本介紹

  • 中文名:理察·哈明
  • 外文名:RichardWesleyHamming
  • 國籍:美國
  • 出生地:芝加哥
  • 出生日期: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在圖靈獎的評獎中是很有遠見的。

論著

《科學家和工程師用的數值方法》(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)

成就及榮譽

哈明是美國工程院院士,1958—1960年曾出任ACM的第七屆主席。除獲得圖靈獎外,1979年他獲得IEEE的Piore獎,1981年獲得H.Pender獎(這是賓夕法尼亞大學所設立的一個獎項),1996年獲得Rhein基金會獎。有趣的是,IEEE設立了一種以哈明命名的獎章,1991年把這種獎章頒給了哈明本人。
作為一名數學家,哈明的專長是數值方法、編碼與資訊理論、統計學和數字濾波器等。這些學科中有不少名詞術語是由哈明定義,因此而用哈明命名的,除“哈明碼”外,常見的還有:
“哈明間距”(Hamming distance):這指同樣長度的兩個碼中,對應位不同的碼的個數。比如01010和11001,哈明間距為3。
“哈明權”(Hamming weight)。這指代碼中1的個數。如01110的哈明權為3。
“哈明視窗”(Hamming window)。這指一種濾波器的通頻帶。

其他信息

哈明有一句名言:“計算的目的不在於數據,而在於洞察事物(“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?)。縱觀哈明的一生,他自己就是實踐這兩句話的一生。
哈明在接受圖靈獎時發表了題為“我對計算機科學的看法”(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頁。他在演說中提出的以下一些觀點,如計算機科學家必須具有良好的數學訓練,應該由相關的系而不是由計算機系來教授計算機套用方面的課程,以及應該注重電腦程式設計風格的教育,等等,至今仍具有十分重要的意義。最後,他還指出與計算機有關的一些事是涉及倫理學與道德方面的棘手的問題,在盜版現象嚴重與黑客猖獗以及計算機犯罪、色情網站層出不窮的今天,真令人感慨於哈明的先知先覺。

相關詞條

熱門詞條

聯絡我們