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

はじめに

前回は、データを数式（多項式）に変換して割り算し、その「余り」を使うことでエラーを見つけ、さらに復元までしてしまう「リード・ソロモン符号」の全体像を見てきました。

前回 第１回：QRコードを解読する：エラーはどうやって直る？リード・ソロモン符号の基本 【第1回】
(今回の記事を読む前に前回の記事を読むことをお勧めします)

しかし、前回の最後で用意したシミュレーターで遊んでみた方は、ある「致命的な問題」に気がついたはずです。
そう、普通の数学のルールで掛け算や割り算を繰り返すと、数字がどんどん巨大化してしまうのです。

前回記事のシミュレータ計算結果の余りの例：\(260 > 255 = 2^8 -1 \)

前回のシミュレータの結果

QRコードは、データを「8ビット（0〜255の数字）」という小さな箱の集まりとして管理しています。計算途中で 1000 や 50000 といった巨大な数字が出てきては、箱に収まりきらずうまく割り当てられません。

そこで、リード・ソロモン符号では普通の足し算や掛け算を捨てます。代わりに使うのが、「どんなに計算しても、絶対に0〜255の範囲に収まる特殊な数学の世界」です。

それが、今回解説する「ガロア体（Galois Field）」です。
一般論的な話はほかのちゃんとした数学記事に任せるとして、QRコードで使われるガロア体について理解していきましょう。

1. そもそも「体（たい）」って何？

「ガロア体」なんていうと、いきなり大学の数学みたいで難しそうですよね。でも、考え方はとてもシンプルです。

数学の世界でいう「体（たい）」とは、簡単に言うと「足し算、引き算、掛け算、割り算が自由にできて、しかも計算結果が必ずその世界のルールの枠内に収まる（閉じている）」という性質を持ったグループのことです。

数学的に厳密な説明(難しいことを難しいまま説明)
乗法と加法と呼ばれる２つの演算が定義されている集合を体という。この２つの演算は、実数の集合における乗法と加法に類似の者であって、実数の集合自体も体の１つである。ただし実数の集合と一般の体では以下の２点が類似ではない
１．一般の体では乗法の可換性を仮定しない
２．有限個の要素からなる体もある(今回のガロア体も有限個)
参考文献 『ガロア理論入門』著 E・アルティン,訳 寺田文行 ,東京都書株式会社¹

身近な例で言うと「時計の文字盤」がこれに近いです。

12時間時計の世界では、「10時の3時間後」は「13時」ではなく、ぐるっと回って「1時」になりますよね。針を動かしてどんなに足しても引いても、絶対に「1〜12」の枠からはみ出しません。

ガロア体のイメージ：12時間時計

QRコードで使うガロア体は、コンピュータと最も相性が良い「8bit = 1 byte（\(2^8 = 256\)）」を基準に作られています。 つまり、「0から255までの256個の数字だけで、すべての計算がぐるぐると完結する世界（\(GF(2^8)\)）」を使うのです。体のイメージをつかんでもらいたいため、時計を例に挙げました。時計では通常の加算減算ができます、しかし、QRコードで使うガロア体は、「8つの独立したスイッチ」のようなイメージなので加減算にもすこし違う特徴があります。

この世界には、私たちが普段使っている数学とは違う「ルール」が2つあります。

2. ルール①：足し算と引き算は「XOR」で全く同じ！？

ガロア体 \(GF(2^8)\) の世界では、普通の足し算（5 + 8 = 13）は使いません。

代わりに、コンピュータが得意な「XOR（排他的論理和）」という計算を使います。

XORのルールはたった1つ。数字を2進数（ビット）に直して、縦に並べて比べたとき、

• 同じなら 0
• 違うなら 1とするだけです。

実際に計算してみよう

例えば、「10」と「20」をガロア体の世界で足し算してみましょう。

• 10を2進数にすると： 00001010
• 20を2進数にすると： 00010100

これを縦に並べてXORのルール（同じなら0、違うなら1）を適用します。

  00001010  (10)
+ 00010100  (20)
----------
  00011110  (30)

偶然にも普通の足し算と同じ「30」になりました。では、次に「10」と「10」を足してみましょう。

  00001010  (10)
+ 00001010  (10)
----------
  00000000  (0)

なんと、同じ数字を足すと「0」になって消滅してしまいます！

この世界には「繰り上がり」や「繰り下がり」という概念が存在しないため、枠をはみ出すことがありません。

そして最も驚くべきことは、「足し算と引き算が全く同じ結果になる」ということです。

プログラミングでQRコードを作る際、足し算も引き算も A ^ B （XOR記号）と書くだけで済んでしまうため、実は普通の数学よりずっと簡単に書くことができます。

3. ルール②：掛け算は「対数表」でチートする

足し算と引き算はXORで解決しました。では、掛け算はどうするのでしょうか？

普通に掛け算をして、あらかじめ決めた「生成多項式」で割り算をして余りを求める……という真面目な方法もあるのですが、コンピュータに毎回それをやらせるのは面倒です。

そこで、リード・ソロモン符号では「対数表（Log表）」と「逆対数表（Exp表）」という2つのチートアイテム（配列）を使います。

中学校の数学で、こんな法則を習ったのを覚えていますか？

\[x^2 \times x^3 = x^5\]

「掛け算は、肩の数字（指数）の足し算に変換できる」という指数の法則です。ガロア体の掛け算も、これと全く同じアイデアを使います。

1. Log表を見る： 掛けたい2つの数字を、Log表を使って「肩の数字（インデックス）」に変換します。
2. 足し算する： 変換した「肩の数字」同士を、普通の足し算で合計します。
3. Exp表を見る： 合計した数字を、Exp表を使って「元の数字」に戻します。

これだけで、複雑な掛け算が一瞬で終わってしまいます！

（※実際のプログラムで使うための具体的なLog表・Exp表の配列の中身については、今回は省略します。第5回ごろに詳しく扱う予定です。）

ガロア体 \(GF(2^8)\) 計算シミュレーター

「XORの足し算」や「Log表を使った掛け算」が、ガロア体の世界でどんな結果になるのか、実際に数字を入れて試してみましょう！どんな数字を入れても、絶対に「0〜255」に収まることを確認してください。
使い方
・数字Aと数字B(0~255)についてガロア体の計算をします
・計算を実行ボタンで計算します

次回：ついに実践 アルファベットを暗号化して直してみよう

ここまで読んでいただき、ありがとうございます。

「割り算の余りでエラーを見つける方法（第1回）」と、「0〜255の枠に収める魔法の計算ルール（今回）」を学んだことで、リード・ソロモン符号を操るための理論的な準備はすべて整いました！

次回（第3回）は、ついにこれらの知識を統合した実践編です。

実際にアルファベットをデータに変換し、ガロア体の計算を使ってパリティを作りエンコードしてみようと思います。

次回：リードソロモン符号のガロア体　実践編
QRコードのリードソロモン符号 を計算してみる【QRコードを解読する 第3回】

関連記事

第１回：CRCと比較してリードソロモン符号の仕組みを大まかに理解する。
QRコードを解読する：エラーはどうやって直る？リード・ソロモン符号の基本 【第1回】

参考文献

1. 参考文献 『ガロア理論入門』1990 第15版, 著 E・アルティン,訳 寺田文行 ,東京都書株式会社 ↩︎

一部書籍などは新装版として販売されている？ようです。

ガロア理論入門

今回扱ったガロア体についてちょっとレベルが高いですが紹介されています。

Amazonで購入 qr_code

広告