什麼是漢明碼

能更正1位元錯誤之錯誤更正碼的代表。使用r個檢查位元,長度 2^r − 1 位元的碼字中,有 2^r − 1 − r 位元用於資料。r = 3 的漢明碼(7, 4)是在4位元資料上附加3位元檢查位元。各檢查位元是彼此重疊之位元組的同位位元,接收端重新檢查的結果(症狀,syndrome)會以二進位表示出錯位元的位置。最小漢明距離為3,再加上1位元整體同位位元的SECDED,也能偵測2位元錯誤。用於伺服器用記憶體的ECC等。

日文名稱: ハミング符号

「漢明碼」出現在2領域的5道練習題中(資訊理論與編碼基礎, 邏輯電路等)。

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

(7, 4)碼的原理

把位元位置設為1~7,以2的冪次的位置1、2、4作為檢查位元。檢查1使位置編號以二進位表示時1的位數為1的位置(1、3、5、7),檢查2使2的位數為1的位置(2、3、6、7),檢查4使4的位數為1的位置(4、5、6、7)中1的個數為偶數。只有對應於出錯位置編號之二進位中為1之位數的檢查會不符,因此把不符之檢查的權重相加,就能得知出錯的位置。

碼率與長度

檢查位元為r個時,碼字為 2^r − 1 位元;像(7, 4)、(15, 11)、(31, 26)這樣越長,碼率越高,分別為 4/7 ≈ 0.57、11/15 ≈ 0.73、26/31 ≈ 0.84。相對地,1個碼字只能更正1位元,因此碼字越長,出現2位元以上錯誤的機率越高。

SECDED與記憶體

在漢明碼上加1位元整體同位位元,最小漢明距離就成為4,能做到1位元錯誤更正(SEC)與2位元錯誤偵測(DED)。64位元的資料需要8位元檢查位元,伺服器用記憶體的寬度為72位元就是這個原因。在要處理更多錯誤的快閃記憶體等,則使用BCH碼或LDPC碼。

練習漢明碼的題目

在漢明碼(7, 4)中,把7個位元從左起稱為第1~7位元,第1、2、4位元為檢查位元。檢查1使第1、3、5、7位元,檢查2使第2、3、6、7位元,檢查4使第4、5、6、7位元中1的個數分別為偶數。收到的 0110001 有1位元錯誤時,出錯的位元為下列何者?

  1. A第2位元
  2. B第3位元
  3. C第6位元
查看答案與解析

正確答案:C. 第6位元

收到的 0110001 中,第1、3、5、7位元為0、1、0、1,1的個數為偶數(檢查1的結果為0);第2、3、6、7位元為1、1、0、1,為奇數(檢查2的結果為1);第4、5、6、7位元為0、0、0、1,為奇數(檢查4的結果為1)。把檢查4、檢查2、檢查1的結果排成 110,以二進位讀出為6,因此第6位元出錯。把第6位元反轉後的 0110011 滿足全部3項檢查。

常見問題

發生2位元錯誤時,漢明碼會怎樣?

沒有整體同位位元的漢明碼,即使是2位元錯誤,症狀也會指向某個非0的位置,因而把正確的位元反轉,使錯誤增加為3位元。為了防止這種情形,記憶體等會使用加上整體同位位元的SECDED,2位元錯誤不加以更正,而是回報為錯誤。

漢明碼現在還在使用嗎?

仍在使用。計算簡單又快速,因此廣泛用於記憶體的ECC、快取與暫存器的保護等需要降低延遲的場合。在通訊這類想有效率地更正大量錯誤的場合,則使用LDPC碼等更強的碼。

解析中的「漢明碼」

出現「漢明碼」的題目(5題)

  1. 在4位元資料上附加3位元檢查位元,做成7位元碼字的漢明碼(7, 4),其碼率最接近下列何者?
  2. 在漢明碼(7, 4)中,把7個位元從左起稱為第1~7位元,第1、2、4位元為檢查位元。檢查1使第1、3、5、7位元,檢查2使第2、3、6、7位元,檢查4使第4、5、6、7位元中1的個數分別為偶數。收到的 0110001 有1位元錯誤時,出錯的位元為下列何者?
  3. 在32位元的資料上附加可更正1位元錯誤、偵測2位元錯誤的SECDED碼。漢明碼的檢查位元數r是滿足 2^r ≥ 資料位元數 + r + 1 的最小值,SECDED再加上1位元的整體同位位元。所需的檢查位元數為下列何者?
  4. 把5個漢明碼(7, 4)的碼字排在一起,依序送出5個碼字各自的第1位元,接著5個碼字各自的第2位元,依此類推(深度5的交錯)。接收端先恢復原本的順序,再對每個碼字更正1位元的錯誤。集中發生在連續位元上的叢發錯誤中,一定能更正的最大長度為下列何者?
  5. 對7位元的資料 1011001 加上偶同位元時,同位元的值是哪一個?

相關名詞

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

前往名詞解釋列表