[科普中國]-海明距離

在信息編碼中，兩個(gè)合法代碼對(duì)應(yīng)位上編碼不同的位數(shù)稱為碼距，又稱海明距離。舉例如下：10101和00110從第一位開始依次有第一位、第四、第五位不同，則海明距離為3。

簡介兩個(gè)碼字的對(duì)應(yīng)比特取值不同的比特?cái)?shù)稱為這兩個(gè)碼字的海明距離。一個(gè)有效編碼集中,任意兩個(gè)碼字的海明距離的最小值稱為該編碼集的海明距離。

簡單理解在信息編碼中，兩個(gè)合法代碼對(duì)應(yīng)位上編碼不同的位數(shù)稱為碼距，又稱海明距離。

幾何意義n位的碼字可以用n維空間的超立方體的一個(gè)頂點(diǎn)來表示。兩個(gè)碼字之間的海明距離就是超立方體兩個(gè)頂點(diǎn)之間的一條邊，而且是這兩個(gè)頂點(diǎn)之間的最短距離。

作用用于編碼的檢錯(cuò)和糾錯(cuò)

為了檢測d個(gè)錯(cuò)誤，需要一個(gè)海明距離為d+1的編碼方案。因?yàn)樵谶@樣的編碼方案中，d個(gè)1位錯(cuò)誤不可能將一個(gè)有效碼字改編成另一個(gè)有效碼字。當(dāng)接收方看到一個(gè)無效碼字的時(shí)候，它就知道已經(jīng)發(fā)生了傳輸錯(cuò)誤。類似地，為了糾正d個(gè)錯(cuò)誤，需要一個(gè)距離為2d+1的編碼方案，因?yàn)樵谶@樣的編碼方案中，合法碼字之間的距離足夠遠(yuǎn)，因而即使發(fā)生了d位變化，則還是原來的碼字離它最近，從而可以確定原來的碼字，達(dá)到糾錯(cuò)的目的。1

計(jì)算方法計(jì)算海明距離的一種方法，就是對(duì)兩個(gè)位串進(jìn)行異或（xor）運(yùn)算，并計(jì)算出異或運(yùn)算結(jié)果中1的個(gè)數(shù)。例如110和011這兩個(gè)位串，對(duì)它們進(jìn)行異或運(yùn)算，其結(jié)果是：2

110⊕011=101

異或結(jié)果中含有兩個(gè)1，因此110和011之間的海明距離就等于2。3

本詞條內(nèi)容貢獻(xiàn)者為:

李嘉騫 - 博士 - 同濟(jì)大學(xué)