資料連結層

漢明碼(Hamming code)

/ HAM-ing /

單一同位位元能告訴你有一個位元翻轉了,卻說不出是哪一個——所以它能偵測、不能修。理查・漢明(Richard Hamming)的洞見是改用好幾個同位位元,每一個各看著資料位元中一個彼此重疊的子集合,並安排成:當錯誤發生時,失敗的那些檢查所組成的樣式,會用二進位拼出壞掉那一位元的確切位置。知道了位置,你只要把那個位元翻回去就好。漢明碼就是這個能更正任何單一位元錯誤的經典順向錯誤更正碼。

以小小的 Hamming(7,4) 為例看其機制:送出 7 個位元,其中 4 個是資料、3 個是同位,分別放在位置 1、2、4(也就是 2 的次方)。每個同位位元各涵蓋一組特定且彼此重疊的位置。在接收端,每個同位檢查不是通過(0)就是失敗(1)。把三個結果讀成一個 3 位元的二進位數,稱為症候(syndrome)。若是 000,沒有錯;否則它的值,例如 101 = 5,就直接指出位置 5 是翻轉的位元,接收方只要把它反相即可。三個檢查就能區分全部七個位置外加「無錯誤」,因為三個位元可編出八種可能。

漢明碼的重要性在於,它最乾淨地示範了「花幾個冗餘位元就買到徹底更正」這件事,而這個想法可以放大成 RAM(ECC 記憶體)、儲存與通訊所用的強大碼。誠實的極限:純漢明碼每一塊「剛好」更正一個位元錯誤。同一塊裡有兩個錯誤,會把它誤導去更正錯的位元,反而越弄越糟。多加一個整體同位位元(SECDED 碼)能讓它至少「偵測」到雙位元錯誤,雖然仍無法更正。

在一塊 Hamming(7,4) 中,接收方跑三個同位檢查,得到結果 1、0、1。讀成二進位是 101 = 5,所以是第 5 位元翻轉了;接收方把第 5 位元反相,原本的 4 個資料位元就還原了——不必重送、不必多問。

失敗檢查所組成的樣式(症候),就是壞掉那一位元的二進位位址。

基本漢明碼每塊只更正一個錯誤;兩個錯誤會騙它去「修」錯位元。多加一個同位位元(SECDED)能讓它偵測、但仍無法更正雙位元錯誤。

又称
Hamming(7,4)海明碼