Error Coding Basics

在儲存系統中，資料從寫入到讀出的過程中可能因為硬體老化、電磁干擾等因素而產生錯誤，因此我們需要 error coding 來保護資料的完整性。這個單元會介紹 error detection 與 error correction 的差異：detection 只負責發現錯誤（例如 CRC、checksum），而 correction 則能自動修復錯誤（例如 Hamming code）。我們會從最基本的 parity bit 與 XOR 運算開始，理解如何用少量的冗餘資料偵測單一 bit 錯誤，再延伸到 CRC 如何透過多項式除法偵測 burst error。最後我們會建立 Hamming distance 的觀念——兩個 codeword 之間至少有幾個 bit 不同——以及一個 code 的 minimum distance 如何決定它能偵測和更正多少個錯誤。這些基礎觀念是後續學習 Galois field arithmetic、RAID、erasure coding 以及 LDPC 等進階主題的必要前置知識。

Key Concepts

我理解 error detection 與 error correction 的根本差異：detection 只能發現資料中存在錯誤，而 correction 能夠自動定位並修復錯誤

我理解 parity bit 的運作原理，以及如何透過 XOR 運算來偵測單一 bit 錯誤

我理解 CRC 如何透過多項式除法（polynomial division）來偵測 burst error，以及為什麼它比簡單的 parity check 更適合偵測連續錯誤

我理解 Hamming distance 的定義——兩個 codeword 之間不同 bit 的數量——以及如何計算一個 code 的 minimum distance

我知道 minimum distance 如何決定一個 code 的偵錯與糾錯能力：minimum distance 為 d 的 code 能偵測 d-1 個錯誤，能更正 floor((d-1)/2) 個錯誤

Recommended Resources