BasicError Coding Basics
Keywords
Prerequisites
None — this is a starting concept.
Related Papers
Progress
Sign in to track your progress.
在儲存系統中，資料從寫入到讀出的過程可能因為硬體老化、電磁干擾、bit flip 等因素產生錯誤，因此我們需要 error coding 在原始資料中加入 redundancy 來保護資料完整性。這個單元先區分 erasure 與 error 兩種壞掉方式，再建立 (n, k) codeword 與 minimum distance 的框架，依序介紹 parity、Hamming、CRC 三個經典 code，最後談 MDS code 與 Reed-Solomon，並走過 storage stack 各層 (NAND、DRAM、HDD、file system、RAID、分散式儲存) 各自選用什麼 code。
貢獻 HackMD 共筆 💲大抄Key Concepts
我理解 erasure 與 error 的差別，以及 detection 與 correction 的差異
我理解 (n, k) code 的框架， code rate R = k/n 的定義，以及 redundancy 與更正能力之間的 trade-off
我理解 Hamming distance 與 minimum distance d 的定義，並知道 d 如何決定一個 code 的能力
我能說出 parity bit、Hamming(7,4)、CRC 三個 code 各自的 (n, k, d) 參數、能力與典型用途
我理解 Hamming code 與 CRC 的用途
我理解 Singleton bound 與 MDS code 的概念，知道 Reed-Solomon 是最常用的 MDS code
我能用 Backblaze 的 17+3 RS 設計說明 erasure coding 相對於三副本的 storage overhead 優勢，以及 (n, k) 參數選擇的 trade-off
我能說明 error coding 在 storage stack 各層的分工