ガロア体

ガロア体 (有限体、Galois Field) は、有限個の要素で四則演算 (加減乗除) が矛盾なく成立する代数構造です。19 世紀のフランスの数学者エヴァリスト・ガロアにちなんで名付けられました。要素数が素数のべき乗 p^n のときに存在し、GF(p^n) と表記します。

QR コードのエラー訂正で使われるリード・ソロモン符号は、GF(2^8) = GF(256) 上で動作します。GF(256) は 0 から 255 までの 256 個の要素を持ち、これはちょうど 1 バイトで表現できる値の範囲と一致します。QR コードのデータはバイト単位で処理されるため、GF(256) との相性が完璧なのです。

通常の整数演算では、たとえば 200 + 100 = 300 となり 1 バイトの範囲を超えてしまいます。しかし GF(256) の加算は XOR (排他的論理和) で定義されるため、結果は常に 0〜255 の範囲に収まります。乗算も原始多項式を法とする多項式演算で定義され、オーバーフローが発生しません。この「閉じた演算」の性質が、固定長のデータブロックに対する誤り訂正を数学的に保証します。

実装面では、GF(256) の乗算を毎回多項式演算で計算すると遅いため、対数表・逆対数表 (それぞれ 256 エントリ) を事前に計算しておき、乗算を「対数の加算 + 逆対数の参照」に変換するのが一般的です。QR コードのエンコーダー・デコーダーの内部には、この 256 バイトのテーブルが組み込まれています。