繁體中文
選單

什麼是漢明距離

長度相同的兩個位元串（或字串）中，相同位置的值不同之處的個數。等於兩個位元串取互斥或後1的個數。例如 1011010 與 0110011 的漢明距離為4。碼中任兩個碼字間距離的最小值稱為最小漢明距離；最小漢明距離為d的碼，可以偵測 d − 1 位元以下的錯誤，並更正 (d − 1) ÷ 2 無條件捨去之位元數以下的錯誤。

日文名稱: ハミング距離

「漢明距離」出現在1領域的3道練習題中（資訊理論與編碼基礎等）。

這個名詞所屬的領域: 資訊理論與編碼基礎

錯誤偵測與更正的能力

碼字彼此相距越遠，越不容易因錯誤而變成其他碼字。最小漢明距離為d的碼，d − 1 位元以下的錯誤不會變成其他碼字，因此可以偵測；錯誤若在 (d − 1) ÷ 2 以下，最接近收到之字的碼字就是原本的碼字，因此可以更正。例如把同一位元送3次的重複碼 d = 3，可以用多數決更正1位元的錯誤。

線性碼的求法

在任兩個碼字的互斥或也是碼字的線性碼中，兩個碼字的距離等於其互斥或所得碼字中1的個數。因此，最小漢明距離可以用非0碼字中1的個數（權重）的最小值求得，不必比較所有組合。

其他領域的用法

漢明距離也被當作計算兩筆資料差異的一般尺度。在PUF（物理不可複製功能）的評估中，不同晶片回應之間的漢明距離越接近全部位元的50%，就越容易區分個體。此外，在狀態機的編碼中，使相鄰狀態的漢明距離為1，就能減少轉移時改變的位元。

練習漢明距離的題目

某碼的最小漢明距離（任兩個碼字間漢明距離的最小值）為5。考慮只用於偵測錯誤，以及只用於更正錯誤的情形。一定能偵測的錯誤位元數與一定能更正的錯誤位元數，下列組合何者正確？

  1. A偵測到4位元為止，更正到2位元為止
  2. B偵測到5位元為止，更正到2位元為止
  3. C偵測到4位元為止，更正到4位元為止
查看答案與解析

正確答案：A. 偵測到4位元為止，更正到2位元為止

最小漢明距離為d的碼，d − 1 位元以下的錯誤不會使碼字變成其他碼字，因此可以偵測。更正是把收到的位元串改為最接近的碼字，因此錯誤若在 (d − 1) ÷ 2 無條件捨去以下，原本的碼字仍是最接近的。d = 5 時，偵測到4位元為止，更正到2位元為止。

常見問題

漢明距離與漢明碼是同一個東西嗎？

不是。漢明距離是計算兩個位元串差異的尺度，漢明碼則是設計成最小漢明距離為3、能更正1位元錯誤的碼。兩者都源自漢明的名字。

能求出長度不同之位元串的漢明距離嗎？

漢明距離只對長度相同者之間定義。若要連字元的插入與刪除也計入差異，則使用編輯距離（萊文斯坦距離）。

解析中的「漢明距離」

出現「漢明距離」的題目（3題）

  1. 兩個7位元碼字 1011010 與 0110011 的漢明距離為下列何者？
  2. 某碼的最小漢明距離（任兩個碼字間漢明距離的最小值）為5。考慮只用於偵測錯誤，以及只用於更正錯誤的情形。一定能偵測的錯誤位元數與一定能更正的錯誤位元數，下列組合何者正確？
  3. 由4個碼字 00000、01011、10101、11110 構成之碼的最小漢明距離，與一定能更正的錯誤位元數，下列組合何者正確？

相關名詞

二元對稱通道 互資訊 平均碼長 同位位元 有失真壓縮 行程長度編碼（RLE） 克拉夫特不等式 前向錯誤更正（FEC） 前綴碼 無失真壓縮

前往名詞解釋列表