漢明碼計算工具

將 0 與 1 的資料編成漢明碼,點選碼字的位元加入錯誤,即可確認接收端如何由校驗子求出錯誤位置並更正。可選擇 4 位元資料的(7,4)碼,到記憶體 ECC 使用的 64 位元 SECDED(72 位元),並以表格顯示各同位位元負責的位置。

輸入

碼字(點選位元即可加入錯誤)

同位(位置為 2 的冪次) 資料 整體同位(SECDED)

同位檢查(接收端)

同位負責的位置XOR 結果

解碼結果

校驗子
–
加入的錯誤數
0
更正後的資料
–

位置從 1 開始計算,在 2 的冪次(1、2、4、8…)的位置放同位位元,其餘位置由高位依序放入資料,這是教科書常用的排列。實際記憶體的 ECC 可能採用不同的位元排列。

同位位元的位置與負責的位元

漢明碼從 1 開始為位置編號,在 1、2、4、8 等 2 的冪次的位置放同位位元。位置 p 的同位位元負責所有「位置編號以二進位表示時 p 那一位為 1」的位置,並使這些位元的 XOR 為 0。例如(7,4)碼中,P1 負責位置 1、3、5、7,P2 負責 2、3、6、7,P4 負責 4、5、6、7。將資料 1011 編碼後,位置 1~7 為 0110011。請用表格的「負責的位置」確認各同位位元檢查哪些位元。

為什麼校驗子能指出錯誤的位置

接收端重新計算各同位位元所負責位置的 XOR。沒有錯誤時全部為 0;若位置 i 的位元反轉,只有 i 以二進位表示時為 1 的那些位所對應的檢查會變成 1。把這些檢查結果排在一起的數(校驗子)就正好是錯誤的位置 i。例如(7,4)碼中位置 5 反轉時,P1 與 P4 的檢查為 1,校驗子為 101(二進位)= 5。請在工具中點選碼字的 1 個位元,確認校驗子與點選的位置一致,且更正後的資料恢復原狀。

需要幾個同位位元

r 個同位位元可表示 2ʳ 種校驗子,其中 1 種用來表示「沒有錯誤」,因此能區分的錯誤位置有 2ʳ − 1 個。資料為 k 位元時,需要區分整個碼的 k + r 個位置,所以需要滿足 2ʳ ≥ k + r + 1 的最小 r。4 位元資料需要 3 個同位位元,8 位元需要 4 個,64 位元需要 7 個。資料越長,同位位元所佔的比例(冗餘度)越小,編碼率從(7,4)的約 57% 提高到 64 位元的約 90%。

SECDED:分辨 2 位元錯誤

一般的漢明碼可以更正 1 位元錯誤,但當 2 個位元反轉時,校驗子會指向無關的位置,造成錯誤的更正(誤更正)。在工具中關閉 SECDED 並點選 2 個位元,就能看到更正後的資料與原本不同。因此加上 1 位元整體同位的就是 SECDED(單一錯誤更正、雙重錯誤檢測)。整體同位不符且校驗子不為 0 時,視為 1 位元錯誤並更正;整體同位相符但校驗子不為 0 時,視為 2 位元錯誤,只通知檢測到而不更正。64 位元資料加上 7 + 1 位元共 72 位元,是伺服器 ECC 記憶體一直採用的構成。

使用場合與限制

漢明碼的 SECDED 用於伺服器的主記憶體、處理器的快取與暫存器檔案、SRAM 等,作為宇宙射線與輻射造成之軟錯誤的對策。優點是計算量少,可用 XOR 樹快速編碼與解碼。不過它無法處理 3 位元以上的錯誤,或同一顆晶片大量位元損壞的故障,因此記憶體也會使用能承受整顆晶片故障的方式;而像快閃記憶體這類錯誤較多的儲存媒體,則使用 BCH 碼或 LDPC 碼等更正能力更強的編碼。只需發現錯誤的通訊,則常使用 CRC。

練習計算機算術題目

關於記憶體所使用的錯誤更正碼(ECC)的作用,下列何者正確?

  1. A壓縮資料以增加容量
  2. B在資料中附加冗餘位元,以偵測並更正位元錯誤
  3. C將資料加密
查看答案與解析

正確答案:B. 在資料中附加冗餘位元,以偵測並更正位元錯誤

ECC是在資料中附加檢查用的位元,並在讀取時偵測、更正錯誤的機制。DDR4以前的伺服器用記憶體基本上是在64位元上加8位元,採用可更正1位元錯誤並偵測2位元錯誤的方式(SECDED)(DDR5的模組則是每條32位元子通道加8位元)。更高可靠度的伺服器還有即使整顆晶片故障也能挽救的Chipkill等。DDR5則在晶片內部也內建了ECC。

對7位元的資料 1011001 加上偶同位元時,同位元的值是哪一個?

  1. A1
  2. B0
  3. C無論資料為何都固定為1
查看答案與解析

正確答案:B. 0

偶同位使包含同位元在內的1的個數為偶數。1011001有4個1,已經是偶數,因此同位元為0。接收端若1的個數為奇數,即可偵測出1位元的錯誤,但無法偵測2位元同時錯誤,也不知道是哪一個位元錯了。在需要更正的記憶體中,則使用結合多個同位元的ECC(漢明碼等)。

常見問題

什麼是(7,4)漢明碼?

在 4 位元資料加上 3 位元同位、成為 7 位元的最小實用漢明碼。3 位元的校驗子能區分全部 7 個位置,因此任何 1 位元錯誤都能更正。將工具的資料位元數設為 4 即可確認。

發生 2 位元錯誤會怎樣?

一般的漢明碼中,校驗子會指向別的位置,因此會把正確的位元反轉,造成誤更正。SECDED 加上了整體同位,能分辨 2 位元錯誤,只通知檢測到而不更正。

同位位元與漢明碼有什麼不同?

1 位元的同位只能知道有奇數個位元反轉,無法得知是哪個位元。漢明碼組合多個負責位置略有不同的同位位元,因此能找出錯誤的位置並更正。

漢明碼與 CRC 有什麼不同?

漢明碼是為了求出錯誤位置並更正的編碼,主要用於記憶體。CRC 是為了以高機率發現錯誤的編碼,不做更正,通訊中發現錯誤時會重送。兩者都是以 XOR 為基礎的線性碼。

位置 0 的位元是什麼?

這是使用 SECDED 時加上的整體同位(P0),使所有位元的 XOR 為 0。若這個位元本身反轉,校驗子會維持 0 而只有整體同位不符,因此會當作 P0 的錯誤來更正。

相關術語

ECC(錯誤更正碼) 軟錯誤 CRC(循環冗餘檢查)

相關計算工具

半導體、電子電路與資訊計算工具 →