漢明距離

漢明距離是使用在數據傳輸差錯控制編碼裡面的，漢明距離是一個概念，它表示兩個（相同長度）字對應位不同的數量，我們以d（x,y）表示兩個字x,y之間的漢明距離。對兩個字元串進行異或運算，並統計結果為1的個數，那么這個數就是漢明距離。

介紹

漢明距離是以理察·衛斯里·漢明的名字命名的。在資訊理論中，兩個等長字元串之間的漢明距離是兩個字元串對應位置的不同字元的個數。換句話說，它就是將一個字元串變換成另外一個字元串所需要替換的字元個數。例如：

1011101 與 1001001 之間的漢明距離是 2。

2143896 與 2233796 之間的漢明距離是 3。

"toned" 與 "roses" 之間的漢明距離是 3。

漢明重量

漢明重量是字元串相對於同樣長度的零字元串的漢明距離，也就是說，它是字元串中非零的元素個數：對於二進制字元串來說，就是 1 的個數，所以 11101 的漢明重量是 4。

特性

對於固定的長度 n，漢明距離是該長度字元向量空間上的度量，很顯然它滿足非負、唯一及對稱性，並且可以很容易地通過完全歸納法證明它滿足三角不等式。

如果把a和b兩個單詞看作是向量空間中的元素，則它們之間的漢明距離等於它們漢明重量的差a-b。如果是二進制字元串a和b，漢明距離等於它們漢明重量的和a+b或者a和b漢明重量的異或a XOR b。漢明距離也等於一個n維的超立方體上兩個頂點間的曼哈頓距離，n指的是單詞的長度。

給予兩個任何的字碼，10001001和10110001，即可決定有多少個相對位是不一樣的。在此例中，有三個位不同。要決定有多少個位不同，只需將exclusive OR運算加諸於兩個字碼就可以，並在結果中計算有多個為1的位。例如：

10001001

Xor 10110001

00111000

兩個字碼中不同位值的數目稱為漢明距離(Hamming distance) 。它的重要性在於如果有兩個字碼的漢明距離為d的話，就需要d的單一位錯誤已將其中一個字碼轉換為另一個。

最小漢明距離

在一個碼組集合中，任意兩個碼字之間對應位上碼元取值不同的位的數目定義為這兩個碼字之間的漢明距離。即

d(x,y)=∑x[i]⊕y[i]

這裡i=0,1,..n-1，x,y都是n位的編碼，⊕表示異或

例如：(00)與(01)的距離是1，(110)和(101)的距離是2。在一個碼組集合中，任意兩個編碼之間漢明距離的最小值稱為這個碼組的最小漢明距離。最小漢明距離越大，碼組越具有抗干擾能力。

下面我們用d表示碼組的最小漢明距離。

1． 當碼組用於檢測錯誤時，設可檢測e個位的錯誤，則

d>=e+1
設有兩個距離為d的碼字A和B，如果A出現了e個錯誤，則A變成了以A為圓心，e位半徑的球體表面的碼字。為了能夠準確地分辨出這些碼字既不是A也不是B，那么A誤碼後變成的球面上的點與B至少應該有一位距離（如果B在球面上或在球面內部則無法分辨出到底B是不是A的錯誤碼），即A與B之間的最小距離d>=e+1。

2． 若碼組用於糾錯，設可糾錯t個位的錯誤，則

d>=2t+1

設有碼字A和B，如果A出現了t個錯誤，B也出現了t各錯誤，則A碼變成以A為圓心，t為半徑的球面上的碼字；B碼變成以B為圓心，t為半徑的球面上的碼字。為了在出現t個錯之後仍能分辨一個碼字到底是屬於A的錯碼還是屬於B的錯碼，A,B為球心的兩個球面應該不相交，即球心A，B之間距離應該大於2t，所以d>=2t+1。

3.如果碼組用於糾正t個錯，檢測e個錯，則

d>=e+t+1

這裡e>t，這種檢錯糾錯方式結合的情況同上述兩個情況類似。當碼字出現t個或者小於t個錯時，系統按照糾錯方式工作。當碼字出現超過t個錯而小於等於e個錯時，系統按照檢錯方式工作；當A出現e個錯，B出現t個錯時，既要糾正B的錯，又要發現A的錯，則以A為球心，e為半徑的球和以B為球心，t為半徑的球應該不相交，所以A,B之間的距離應該大於等於e+t+1，即d>=e+t+1。

歷史及套用

漢明距離是以理察·衛斯里·漢明的名字命名的，漢明在誤差檢測與校正碼的基礎性論文中首次引入這個概念。在通信中累計定長二進制字中發生翻轉的錯誤數據位，所以它也被稱為信號距離。

漢明距離更多的用於信號處理，表明一個信號變成另一個信號需要的最小操作（替換位），實際中就是比較兩個比特串有多少個位不一樣，簡潔的操作時就是兩個比特串進行異或之後包含1的個數。漢明距在圖像處理領域也有這廣泛的套用，是比較二進制圖像非常有效的手段。計算一個數字的比特位包含1的個數有個小技巧：value &= value - 1這個運算的結果就是把value最後一個1去掉，循環進行運算直到value等於0（所有的1都被去掉）就可以知道vaule擁有多少個1了。其在包括資訊理論、編碼理論、密碼學等領域都有套用。但是，如果要比較兩個不同長度的字元串，不僅要進行替換，而且要進行插入與刪除的運算，在這種場合下，通常使用更加複雜的編輯距離等算法。