理察·衛斯里·漢明

理察·衛斯里·漢明

理察·衛斯里·漢明(英語:Richard Wesley Hamming,1915年2月11日-1998年1月7日),美國數學家,主要貢獻在計算機科學電訊

基本介紹

  • 中文名:理察·衛斯里·漢明
  • 外文名:Richard Wesley Hamming
  • 國籍美國
  • 出生日期:1915年2月11日
  • 逝世日期:1998年1月7日
簡介,獎項,漢明距離,漢明重量,高效實現,

簡介

1937年芝加哥大學學士學位畢業,1939年內布拉斯加大學碩士學位畢業,1942年伊利諾伊大學香檳分校博士學位畢業,博士論文為《一些線性微分方程邊界值理論上的問題》(Some Problems in the Boundary Value Theory of Linear Differential Equations)。二戰期間在路易斯維爾大學當教授,1945年參加曼哈頓計畫,負責編寫電腦程式,計算物理學家所提供方程的解。該程式是判斷引爆核彈會否燃燒大氣層,結果是不會,於是核彈便開始試驗。
1946至76年在貝爾實驗室工作。他曾和約翰·懷爾德·杜奇、克勞德·艾爾伍德·香農合作。1956年他參與了IBM 650的程式語言發展工作。
1976年7月23日起在海軍研究院當兼任教授,1997年成為名譽教授。
他是美國電腦協會(ACM)的創立人之一,曾任該組織的主席。

獎項

1968年ACM圖靈獎1968年IEEE院士1979年Emanuel R. Piore獎1980年美國國家工程學院院士1981年賓夕法尼亞大學Harold Pender獎1988年IEEE理查·衛斯里·漢明獎

漢明距離

資訊理論中,兩個等長字元串之間的漢明距離是兩個字元串對應位置的不同字元的個數。換句話說,它就是將一個字元串變換成另外一個字元串所需要替換的字元個數。 例如:
理察·衛斯里·漢明理察·衛斯里·漢明
10111011001001之間的漢明距離是 2。21438962233796之間的漢明距離是 3。"toned" 與 "roses" 之間的漢明距離是 3。 漢明重量是字元串相對於同樣長度的零字元串的漢明距離,也就是說,它是字元串中非零的元素個數:對於二進制字元串來說,就是 1 的個數,所以 11101 的漢明重量是 4。

漢明重量

漢明重量是一串符號中非零符號的個數。因此它等同於同樣長度的全零符號串的漢明距離。在最為常見的數據位符號串中,它是 1 的個數。

高效實現

在密碼學以及其它套用中經常需要計算數據位中 1 的個數,針對如何高效地實現人們已經廣泛地進行了研究。一些處理器使用單個的命令進行計算,另外一些根據數據位向量使用並行運算進行處理。對於沒有這些特性的處理器來說,已知的最好解決辦法是按照樹狀進行相加。例如,要計算二進制數 A=0110110010111010 中 1 的個數,這些運算可以表示為:
符號
二進制
十進制
注釋
A
0110110010111010
原始數據
B = A & 01 01 01 01 01 01 01 01
01 00 01 00 00 01 00 00
1,0,1,0,0,1,0,0
A 隔一位檢驗
C = (A >> 1) & 01 01 01 01 01 01 01 01
00 01 01 00 01 01 01 01
0,1,1,0,1,1,1,1
A 中剩餘的數據位
D = B + C
01 01 10 00 01 10 01 01
1,1,2,0,1,2,1,1
A 中每個雙位段中 1 的個數列表
E = D & 0011 0011 0011 0011
0001 0000 0010 0001
1,0,2,1
D 中數據隔一位檢驗
F = (D >> 2) & 0011 0011 0011 0011
0001 0010 0001 0001
1,2,1,1
D 中剩餘數據的計算
G = E + F
0010 0010 0011 0010
2,2,3,2
A 中 4 位數據段中 1 的個數列表
H = G & 00001111 00001111
00000010 00000010
2,2
G 中數據隔一位檢驗
I = (G >> 4) & 00001111 00001111
00000010 00000011
2,3
G 中剩餘數據的計算
J = H + I
00000100 00000101
4,5
A 中 8 位數據段中 1 的個數列表
K = J & 0000000011111111
0000000000000101
5
J 中隔一位檢驗
L = (J >> 8) & 0000000011111111
0000000000000100
4
J 中剩餘數據的檢驗
M = K + L
0000000000001001
9
最終答案

相關詞條

熱門詞條

聯絡我們