QR コードを支える数学 - 有限体と Reed-Solomon 符号のしくみ
なぜ汚れた QR コードが読めるのか
QR コードの最大の特長は、コードの一部が汚れたり破損したりしても正しくデータを復元できることです。誤り訂正レベル H では、全体の約 30% が失われても元のデータを完全に復元できます。この「魔法」のような機能を支えているのが、Reed-Solomon 符号という誤り訂正アルゴリズムです。
Reed-Solomon 符号は 1960 年に Irving S. Reed と Gustave Solomon によって発表されました。QR コードだけでなく、CD/DVD、デジタル放送、深宇宙通信 (NASA のボイジャー探査機)、RAID ストレージなど、データの信頼性が求められるあらゆる場面で使われています。60 年以上前に考案されたアルゴリズムが、世界中のスマートフォンで毎日使われているという事実は、優れた数学の普遍性を物語っています。
有限体 (ガロア体) - QR コードの数学的基盤
Reed-Solomon 符号を理解するには、まず「有限体」(ガロア体、Galois Field) という数学的構造を知る必要があります。日常の算数では、数は無限に続きます (1, 2, 3, ...) が、有限体では決められた個数の要素だけで四則演算が完結します。
QR コードが使う有限体は GF(28)、つまり 256 個の要素を持つ体です。0 から 255 までの 256 個の数で、足し算・引き算・掛け算・割り算がすべて閉じた世界を作ります。「閉じている」とは、どんな演算をしても結果が必ず 0〜255 の範囲に収まるということです。
なぜ 256 なのか。コンピュータが扱うデータの基本単位は 1 バイト (8 ビット) で、1 バイトで表現できる値は 0〜255 の 256 通りです。QR コードのデータを 1 バイト単位で処理するために、ちょうど 256 個の要素を持つ有限体が選ばれました。数学の抽象的な構造と、コンピュータの物理的な制約が、GF(28) という一点で美しく交差しています。
Reed-Solomon 符号のしくみ - 多項式で守るデータ
Reed-Solomon 符号の核心は、データを「多項式」として扱うことです。たとえば、3 バイトのデータ [65, 118, 42] があるとき、これを多項式 65x2 + 118x + 42 と見なします。
この多項式に対して、GF(28) 上で「生成多項式」を使った割り算を行い、余りとして得られる値が「誤り訂正コードワード」です。元のデータにこの誤り訂正コードワードを付加して QR コードに格納します。
読み取り時には、受信した多項式を生成多項式で割り、余りが 0 なら「エラーなし」、0 でなければ「エラーあり」と判定します。エラーがある場合、余りのパターンから「どの位置が」「どのように」間違っているかを逆算し、元のデータを復元します。この逆算プロセスには、Berlekamp-Massey アルゴリズムや Forney アルゴリズムといった高度な数学的手法が使われています。
直感的に言えば、Reed-Solomon 符号は「データの点を通る曲線を描き、一部の点が消えても残りの点から元の曲線を復元する」仕組みです。n 個の点があれば n-1 次の多項式が一意に決まるという数学的性質を利用して、余分な点 (誤り訂正コードワード) を追加しておくことで、一部の点が失われても元の曲線 (データ) を再構成できるのです。
誤り訂正レベルと冗長性のトレードオフ
QR コードの誤り訂正レベルは L、M、Q、H の 4 段階で、それぞれ約 7%、15%、25%、30% の損傷を復元できます。レベルが高いほど安心ですが、代償として QR コードのサイズが大きくなります。
これは情報理論の根本的なトレードオフです。Claude Shannon が 1948 年に発表した「通信の数学的理論」で示したように、ノイズのある通信路で信頼性を高めるには、冗長性 (余分な情報) を追加する必要があります。QR コードの誤り訂正レベルは、まさにこの冗長性の量を制御するパラメータです。
レベル L では、データ領域の約 7% が誤り訂正に使われ、残り 93% がユーザーデータです。レベル H では約 30% が誤り訂正に使われ、ユーザーデータは 70% に減ります。同じデータ量を格納する場合、レベル H はレベル L の約 1.4 倍のモジュール数が必要になり、QR コードの物理的なサイズが大きくなります。印刷スペースが限られる場面ではレベル L、屋外や工場など汚れのリスクが高い場面ではレベル H を選ぶのが実務上の判断基準です。
日常に潜む高等数学
QR コードをスキャンするたびに、スマートフォンの中では有限体上の多項式演算が高速に実行されています。コンビニの支払い、電車の乗車、イベントの入場、レストランのメニュー閲覧。これらの日常的な行為の裏側で、1960 年代に考案された符号理論と、19 世紀のエヴァリスト・ガロアが発見した有限体の理論が、毎秒何億回と計算されています。
ガロアは 20 歳で決闘により命を落とした天才数学者で、彼が残した理論は当時「理解できる人間がほとんどいない」と言われました。その理論が 200 年後に、世界中の人々が毎日使うテクノロジーの基盤になっているのは、数学の歴史における最も劇的なエピソードの一つです。
数学と日常技術の意外なつながりに興味がある方には、符号理論の入門書がおすすめです。Reed-Solomon 符号の数学的背景から実装まで、段階的に理解を深められます。