QRコードの誤り訂正を支えるガロア体 GF(2^8) とは？乗法表の作り方と実装を解説【QRコードを解読する第5回】

はじめに

前回までの「基礎編」では、QRコードのバージョンや誤り訂正レベルといった仕様の全体像を俯瞰してきました。今回からの「理論編」では、いよいよ具体的なエンコード（文字列からQRコードのビット列への変換）とデコード（読み取り）のプログラム実装に向けた理論を扱います。

QRコードの誤り訂正機能の根幹をなす「リード・ソロモン符号」は、

ガロア体（有限体） \(GF(2^8)\)

という特殊な数学の世界の上で計算されます。今回は、この \(GF(2^8)\) における加減算と乗算の定義、そしてプログラム上で高速に計算処理を行うための「指数表・対数表（乗法表）」の導出方法について解説します。

大学等で代数学を学んだことがある方向けに、厳密な定義を交えながら進めていきます。

ガロア体 GF(2^8) の多項式表現

\(GF(2^8)\) は、\(2^8 = 256\) 個の元を持つ有限体です。この体の元は、\(GF(2)\) （すなわち \({0, 1}\)）を係数とする 7 次以下の多項式として表現されます。

体とは？ざっくり理解編→ デジタル世界の数学「ガロア体」を超ざっくり理解しよう！【QRコードを解読する第2回】

QRコードの仕様において、この体を構成するための既約多項式 \(P(x)\) は以下のように定義されています。※JIS X 0510（日本産業規格）で定義。ちなみに、8次の既約多項式はこれを含めて16種類あり、理論上どれを使っても問題はないですが、歴史的にバーコードなどで使われていたことなどから以下の式が一般的に用いられます。
\[P(x) = x^8 + x^4 + x^3 + x^2 + 1\]

この多項式は \(GF(2)\) 上で既約（因数分解できない）です。したがって、\(GF(2^8)\) は多項式環 \(GF(2)[x]\) をイデアル \((P(x))\) で割った剰余環として定義されます。

\[GF(2^8) \cong GF(2)[x] / (x^8 + x^4 + x^3 + x^2 + 1)\]

コンピュータ上では、多項式の係数 \((a_7, a_6, \dots, a_0)\) をそのまま8ビット（1バイト）のデータに対応させて扱います。例えば、多項式 \(x^6 + x^2 + 1\) は、2進数で 01000101（16進数で 0x45）となります。

用語：既約多項式

既約多項式とは、それ以上因数分解できない多項式のことを言います。
具体的な例としては、 \(g(x) = (x -3)(x+2)\)などです。

より一般化すると \(a_0,a_2 \dots a_n\)が体 \(K\)の要素で、\(a_0 \neq 0\)であるとき、
\( a_0 x^n + a_1 x^{n -1} + \dots + a_n\)の形をしている式を\(K\)内の次数\(n\)の多項式という。
\(K\)内の多項式は、それが\(K\)内の正の字数を持つ２つの多項式の積として表せるとき可約であるといい、定数でない多項式が\(K\)内で可約でないとき、\(K\)内で既約という。

GF(2^8) における加算と減算（XOR）

\(GF(2)\) 上の演算であるため、係数の足し算・引き算はすべて「2を法とする演算（\(\bmod 2\)）」となります。

すなわち、\(1 + 1 = 0\) であり、\(1 – 1 = 0\) です。この世界では加算と減算は全く同じ操作になります。

2つの多項式 \(A(x), B(x)\) の加算は、同じ次数の係数同士を加算（\(\bmod 2\)）するだけです。これをビット演算の視点で見ると、単なるビットごとの排他的論理和（XOR）に他なりません。

加算・減算の実装: A ^ B （XOR演算）

手元で試せる加減算ツールがある記事：デジタル世界の数学「ガロア体」を超ざっくり理解しよう！【QRコードを解読する第2回】

GF(2^8) における乗算と「アルファ」の導入

加減算はXOR一発で終わりますが、乗算は少し複雑です。

基本的には多項式同士の通常の乗算を行いますが、結果が8次以上になった場合は、先ほどの既約多項式 \(P(x)\) で割った「余り」をとる必要があります。

ここで、多項式 \(x\) （ビット列表記で 00000010 = 0x02）を特別な元 \(\alpha\)（原始元） と定義します。

原始元とは、その冪乗 \(\alpha^0, \alpha^1, \dots, \alpha^{254}\) を計算していくと、\(GF(2^8)\) の 0 以外のすべての元（255個）を一度ずつ生成できる特別な元のことです。
つまり、原始元を用いればデータと符号が１対１対応します。(同じパタンが出てこない）

乗算を劇的に高速化する「対数の性質」

プログラム上で毎回多項式の掛け算と \(P(x)\) による割り算（剰余）を行うのは非常に計算コストがかかります。そこで、実数の世界での対数法則 \(e^a \cdot e^b = e^{a+b}\) と同じ性質を利用します。

\(GF(2^8)\) の任意の非零元 \(A, B\) は、原始元 \(\alpha\) の冪乗として表せます。

\[A = \alpha^i\]
\[B = \alpha^j\]

このとき、2つの元の積は次のように計算できます。

\[A \cdot B = \alpha^i \cdot \alpha^j = \alpha^{(i + j) \bmod 255}\]

（※ \(\alpha^{255} = 1\) となるため、指数部の加算は \(255\) を法とします）

つまり、「整数を \(\alpha\) の指数に変換する表（対数表）」と、「\(\alpha\) の指数から元の整数に戻す表（指数表）」の2つをあらかじめメモリ上に用意しておけば、乗算は「配列の参照」と「整数の足し算」だけで爆速で処理できるようになります。これは、実数の世界では表を作るのが不可能（すべての実数に対して作るのは大きさ無限の表を作らないといけない）ですが、ガロア体（有限体）だからこそできる高速化・効率化の工夫です。

指数表と対数表の生成アルゴリズム

では、その2つの表（要素数256の配列 exp と log）を生成するアルゴリズムを追ってみましょう。

前回の結果を \(\alpha\) 倍（すなわち \(x\) 倍）していくことで、順番に表を埋めていきます。

多項式に \(x\) を掛ける操作は、ビット演算では左シフト（<< 1）に相当します。

もしシフトした結果、8ビット目（\(x^8\) の項）に 1 があふれ出た場合は、既約多項式 \(P(x)\) に対応する値 0x11D （\(x^8 + x^4 + x^3 + x^2 + 1\)）でXORをとって剰余を計算します。（※実際には8ビットの枠に収めるため、あふれた \(x^8\) を無視して下位8ビットに対して 0x1D とXORをとります）

【生成の手順】

初期値 \(V = 1\) （\(\alpha^0\) に相当）とする。
\(i = 0\) から \(254\) まで以下を繰り返す：
- exp[i] = V
- log[V] = i
- \(V\) を左に1ビットシフトする（\(V = V \times 2\)）。
- もし \(V \ge 256\) （8ビットを超えた）なら、\(V = V \oplus \text{0x11D}\) とする。

これで、リード・ソロモン符号を計算するための強力な「武器（乗法表）」が手に入ります。

表プログラムで作成した乗法表

乗法表作成プログラム

乗法表を作成するプログラムや乗法表を用いた乗法の計算を行うシミュレータなどをgithubにて公開しています。(今回の内容はStep０のフォルダにあります)

Qr from Scratch

QRコードの車輪の再発明をしながらＱＲコードを深く理解する。

github.com

QRコードをフルスクラッチすることで、QRコードを深く理解するためのGithubリポジトリ

リポジトリリンク：https://github.com/Tsukumo-999/qr-code-from-scratch.git

表を用いた乗法計算

表を用いた乗法の計算について説明します。説明といっても。計算結果がわかっているので、それをとってくるだけです。githubで公開しているシミュレータでは、表から読み出したものと逐次計算したときの速度比較を行っています。
実装は、手元で試しやすくするため環境作成が簡単なpythonで作成しています。コンパイル言語と比較するととても遅いですが、アルゴリズム的な高速化(2倍程度)を確認できます。

githubで公開している計算速度シミュレータのUI
例では 255 ^ 248 について対数をとり指数計算をガロア体で計算して、
速度が約2.6倍になっていることを確認できます。

まとめと次回予告

今回は、大学数学の抽象代数学を背景とするガロア体 \(GF(2^8)\) の演算定義と、それをプログラムで効率的に実装するための指数表・対数表の構築手法について解説しました。数学の理論が、シフト演算とXORという極めて物理的・ハードウェア的な処理に鮮やかに落とし込まれる美しさを感じていただけたかと思います。

次回は、今回準備した演算テーブルを片手に、実際の文字列「HELLO」を対象として、バージョン2・誤り訂正レベルQの形式に合わせてQRコードのデータ領域（ビット列）を作り出していく「エンコード」の具体的な手順に挑みます。

次回：HELLOをエンコードする
QRコードの作り方を徹底解説｜”HELLO”を例にエンコーダをゼロから実装する【QRコードを解読する第6回】

ここまで読んでいただきありがとうございます。では、次の記事で Lumen Hero.

第１回：CRCと比較してリードソロモン符号の仕組みを大まかに理解する。
QRコードを解読する：エラーはどうやって直る？リード・ソロモン符号の基本【第1回】
第２回：デジタル世界の数学「ガロア体」を超ざっくり理解しよう！
デジタル世界の数学「ガロア体」を超ざっくり理解しよう！【QRコードを解読する第2回】