Galois Field Arithmetic

在 error-coding-basics 中我們學到了 XOR 和 Hamming distance 等基礎概念，但要建構更強大的編碼技術（如 Reed-Solomon），我們需要一套能在有限元素上做四則運算的數學工具，這就是 Galois field。我們會聚焦在 GF(2^w) 這類 finite field：它的加法就是 XOR，而乘法則透過 primitive polynomial 定義，實務上可以用 log/antilog table 來加速計算。理解 GF(2^w) 的運算規則後，我們就能在這個 field 上建構矩陣運算，這是 Reed-Solomon 編碼與解碼的核心。同時 LDPC code 中的 sparse parity-check matrix 也建立在 finite field 的代數結構之上。掌握 Galois field arithmetic 讓我們能把 error coding 從簡單的 bit-level XOR 推展到 symbol-level 的強大糾錯能力，是連結基礎理論與實際儲存系統編碼方案的關鍵橋梁。

Key Concepts

我理解為什麼進階編碼技術（如 Reed-Solomon）需要 finite field arithmetic，而不能直接使用一般的整數運算

我理解 GF(2^w) 中的加法就是 XOR 運算，而且任何元素與自己相加等於零

我理解 GF(2^w) 中的乘法如何透過 primitive polynomial 定義，以確保運算結果始終落在有限個元素之內

我了解如何使用 log table 和 antilog table 將 GF(2^w) 的乘法轉換為加法來加速計算

我理解 Galois field 上的 matrix operation 如何支撐 Reed-Solomon 的 encoding 與 decoding 流程

Recommended Resources