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 次の多項式が一意に決まるという数学的性質を利用して、余分な点 (誤り訂正コードワード) を追加しておくことで、一部の点が失われても元の曲線 (データ) を再構成できるのです。
誤り訂正レベルの 2 つの数字 - 復元率と冗長配分
誤り訂正レベル L・M・Q・H をめぐっては、混同されやすい 2 つの数字があります。ひとつは復元できる損傷の割合 (復元率) で、レベル L で約 7%、M で約 15%、Q で約 25%、H で約 30%。もうひとつは誤り訂正符号が占める割合 (冗長配分) で、QR コードに詰め込まれた符号語 (コードワード) のうち何個が誤り訂正のために確保されているかを表します。「レベル H なら 30% 壊れても読める」という説明は前者の話で、誤り訂正符号が全体の 30% を占めるという意味ではありません。
これは情報理論の根本的なトレードオフです。Claude Shannon が 1948 年に発表した「通信の数学的理論」で示したように、ノイズのある通信路で信頼性を高めるには、冗長性 (余分な情報) を追加する必要があります。QR コードの誤り訂正レベルは、まさにこの冗長性の量を制御するパラメータです。
冗長配分の実際の値は、規格 ISO/IEC 18004 が定めるコードワードの内訳に現れます。最小のバージョン 1 (21 × 21 モジュール) は全部で 26 コードワード。その内訳はレベル L がデータ 19 + 誤り訂正 7、レベル H がデータ 9 + 誤り訂正 17 です。誤り訂正符号の占める割合はレベル L で約 27%、レベル H で約 65% —— 復元率として語られる 7% や 30% よりも、ずっと多くの領域が誤り訂正のために使われています。
2 つの数字がずれるのは、Reed-Solomon 符号が誤りを直す手続きに理由があります。誤りを訂正するには「どのコードワードが」「どんな値に化けたか」の 2 つを突き止める必要があり、誤り 1 個あたり誤り訂正符号を 2 個消費します。さらに、化けた値を取り違えて別のデータへ「復元」してしまう事故を避けるため、訂正能力をぎりぎりまで使い切らない設計になっています。この 2 つが重なって、復元できる損傷の割合は誤り訂正符号の割合の半分以下に収まります。冗長性を足せば復元率は上がりますが、足した分がそのまま復元率になるわけではないのです。
配分の違いは、同じデータを入れたときの大きさに跳ね返ります。バージョン 1 で比べると、格納できるデータはレベル L で 19 コードワード、レベル H で 9 コードワード。同じ量を入れるならレベル H では約 2 倍のコードワードが必要になり、その分だけ大きなバージョンを選ぶことになります。たとえばレベル L ならバージョン 3 (29 × 29 モジュール) に収まるデータが、レベル H ではバージョン 5 (37 × 37 モジュール) を要する、という形で一辺が伸びていきます。印刷スペースが限られる場面ではレベル L や M、屋外や工場のように汚れや擦れのリスクが高い場面ではレベル H。復元率と冗長配分の両方を見て選ぶのが、実務での判断になります。
日常に潜む高等数学
QR コードをスキャンするたびに、スマートフォンの中では有限体上の多項式演算が高速に実行されています。コンビニの支払い、電車の乗車、イベントの入場、レストランのメニュー閲覧。これらの日常的な行為の裏側で、1960 年代に考案された符号理論と、19 世紀のエヴァリスト・ガロアが発見した有限体の理論が、毎秒何億回と計算されています。
ガロアは 20 歳で決闘により命を落とした天才数学者で、彼が残した理論は当時「理解できる人間がほとんどいない」と言われました。その理論が 200 年後に、世界中の人々が毎日使うテクノロジーの基盤になっているのは、数学の歴史における最も劇的なエピソードの一つです。