漢明碼計算工具
將 0 與 1 的資料編成漢明碼,點選碼字的位元加入錯誤,即可確認接收端如何由校驗子求出錯誤位置並更正。可選擇 4 位元資料的(7,4)碼,到記憶體 ECC 使用的 64 位元 SECDED(72 位元),並以表格顯示各同位位元負責的位置。
碼字(點選位元即可加入錯誤)
同位(位置為 2 的冪次) 資料 整體同位(SECDED)
同位檢查(接收端)
解碼結果
- 校驗子
- –
- 加入的錯誤數
- 0
- 更正後的資料
- –
位置從 1 開始計算,在 2 的冪次(1、2、4、8…)的位置放同位位元,其餘位置由高位依序放入資料,這是教科書常用的排列。實際記憶體的 ECC 可能採用不同的位元排列。
以圖表檢視
其他輸入維持目前的值,只讓選擇的輸入在目前值的 1/4 到 4 倍之間變化時的結果。紅點是目前的值。
同位位元的位置與負責的位元
漢明碼從 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。
練習計算機算術題目
- A壓縮資料以增加容量
- B在資料中附加冗餘位元,以偵測並更正位元錯誤
- C將資料加密
查看答案與解析
正確答案:B. 在資料中附加冗餘位元,以偵測並更正位元錯誤
ECC是在資料中附加檢查用的位元,並在讀取時偵測、更正錯誤的機制。DDR4以前的伺服器用記憶體基本上是在64位元上加8位元,採用可更正1位元錯誤並偵測2位元錯誤的方式(SECDED)(DDR5的模組則是每條32位元子通道加8位元)。更高可靠度的伺服器還有即使整顆晶片故障也能挽救的Chipkill等。DDR5則在晶片內部也內建了ECC。
- A1
- B0
- 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 的錯誤來更正。