海明距離
海明距離 |
在信息編碼中,兩個合法代碼對應位上編碼不同的位數稱為碼距,又稱海明距離。舉例如下:10101和00110從第一位開始依次有第一位、第四、第五位不同,則海明距離為3。
目錄
簡介
為了檢測d個錯誤,需要一個海明距離為d+1的編碼方案。因為在這樣的編碼方案中,d個1位錯誤不可能將一個有效碼字改編成另一個有效碼字。當接收方看到一個無效碼字的時候,它就知道已經發生了傳輸錯誤。類似地,為了糾正d個錯誤,需要一個距離為2d+1的編碼方案,因為在這樣的編碼方案中,合法碼字之間的距離足夠遠,因而即使發生了d位變化,則還是原來的碼字離它最近,從而可以確定原來的碼字,達到糾錯的目的。
評價
兩個碼字的對應比特取值不同的比特數稱為這兩個碼字的海明距離。一個有效編碼集中,任意兩個碼字的海明距離的最小值稱為該編碼集的海明距離。在信息編碼中,兩個合法代碼對應位上編碼不同的位數稱為碼距,又稱海明距離。兩個碼字的對應比特取值不同的比特數稱為這兩個碼字的海明距離。一個有效編碼集中,任意兩個碼字的海明距離的最小值稱為該編碼集的海明距離。計算海明距離的一種方法,就是對兩個位串進行異或(xor)運算,並計算出異或運算結果中1的個數。例如110和011這兩個位串,對它們進行異或運算,其結果是:110⊕011=101 異或結果中含有兩個1,因此110和011之間的海明距離就等於2。[1]