QRコードのリードソロモン符号を計算してみる【QRコードを解読する第3回】

第1回で「割り算の余り（パリティ）を使ってエラーを直すアイデア」を学び、第2回で「数字が爆発しないデジタル世界の数学（ガロア体 \(GF(2^8)\)）」を手に入れました。

いよいよ今回が実践編です！

実際に私たちが普段使っている「文字」をデータに変換し、QRコードで使われている本物の生成多項式を使って、パリティ（エラー訂正コード）を計算してみましょう。

この記事からも読めますが、第１回から読んでいただけるとより流れを理解しやすくなります。
QRコードを解読する：エラーはどうやって直る？リード・ソロモン符号の基本【第1回】

1. 文字を数字（8ビットのバイト）に変換する

QRコードの世界では、すべてのデータは「8ビット（0〜255）の数字の集まり」として扱われます。
今回は一番シンプルな例として、アルファベットの 「A」 という1文字を符号化してみましょう。

QRコードにおける文字コードは、UTF-8が使われることが多いですが、今回はわかりやすくシンプルなASCII（アスキー）コードを用いて数字に読み替えてみます。

アルファベットの「A」は、ASCIIコードでは10進数で 65 です。

これを2進数で表すと 1000001（7ビット）になります。QRコードは8ビット単位（1バイト）でデータを扱う仕様のため、最上位（一番左）に 0 を付け足して8ビットに揃えます。

「A」 \(\rightarrow\) 01000001 （10進数で 65）

実際のQRコードでは、このデータの前に「これは文字データですよ」「長さは1文字ですよ」といったヘッダ情報が付くのですが、今回は純粋にリード・ソロモン符号の仕組みを理解するため、この [ 65 ] という1つの数字を「送りたいメッセージ」として計算を進めます。

ASCIIコード表
ASCIIコードは文字コードの１つです。コンピュータは数字しか扱えないため文字を数字で表現する必要があり、この読み替えの仕方を定義したものが文字コードです。このほかにもshift-JISやUTF-8などいろいろあります。ASCIIコード表の読み方は、”B”なら、まずBを探します。Bは表の２行４列目にあります。(便宜上0行目から数えることにします。)　
行はb1~b4(下位の４ビット)が割り当てられており2行目は(b4,b3,b2,b1) = (0,0,1,0)、列はb5~b7が割り当てられており、４行目は(b7,b,6,b5) = (1,0,0)です。よって”B”のASCIIコードはb7~b1を並べて\((1,0,0,0,0,1,0)_2 = (66)_{10}\)とわかります。

ASCIIコード表

引用：MILITARY STANDARD MILITARY COMMUNICATION SYSTEM TECHNICAL STAANDARDS ,MIL-STD-188c , https://www.google.de/books/edition/Military_Standard/um2cRERx4S4C?gbpv=1&pg=RA3-PA18

2. QRコード仕様の「生成多項式」を作る

第1回では、パリティを作るための割り算の基準として \(g(x) = x – 2\) という簡単な数式を使いました。

QRコードでも基本は同じですが、「パリティをいくつ作るか（どれくらいのエラーに耐えたいか）」によって、あらかじめ決められた公式を使って数式を組み立てます。

今回は「パリティを2つ（2バイト）作る」という設定で進めます。

パリティを2つ作るための生成多項式 \(g(x)\) は、ガロア体の原始元 \(\alpha\) （アルファ：QRコードでは数字の2 、前回軽く触れた logやexp表を作るときの元のことです。そういう表現をするんだな、くらいの理解で構いません。参考：原始元2のアルファの例¹）を使って、以下のように組み立てられます。

\[g(x) = (x – \alpha^0)(x – \alpha^1)\]

ここで、第2回で学んだガロア体のルールを思い出してください。「引き算は足し算（XOR）と同じ」なので、マイナスはプラスにしてしまってOKです。

\[g(x) = (x + \alpha^0)(x + \alpha^1)\]

\(\alpha^0\) は 1、 \(\alpha^1\) は 2 なので、普通の多項式の展開と同じように計算します（※ただし足し算はXOR、掛け算はガロア体のルールで行います）。

\[g(x) = x^2 + (1 \oplus 2)x + (1 \times 2)\]

\(1 \oplus 2\) は、2進数で 01 と 10 のXORなので 11 （10進数で 3）
\(1 \times 2\) は 2

よって、今回使う本物の生成多項式は、以下のようになります。
\[g(x) = x^2 + 3x + 2\]

3. ガロア体での割り算を実行する！

準備は整いました。データ [ 65 ] から、パリティを2つ作ります。

第1回でやったように、まずはデータにパリティ用の空きスペース（今回は2桁分）を作るため、多項式をシフトさせます。

シフトしたメッセージ多項式 \(M(x)\)
\[M(x) = 65x^2 + 0x + 0\]

これを、先ほど作った \(g(x) = x^2 + 3x + 2\) で割り算します。ガロア体の計算なので、引き算はすべてXORになることに注意してください。

【筆算のながれ】

割る式 \(g(x)\) に 65 を掛けて、引く（XORする）数を作ります。

\(65 \times x^2 = 65x^2\)
\(65 \times 3\) （ガロア体の掛け算） \(= \mathbf{195}\)
\(65 \times 2\) （ガロア体の掛け算） \(= \mathbf{130}\)

これを元のメッセージから引きます（XORします）。

         65
   -------------------
 1 3 2 | 65    0    0
       ^ 65  195  130  (※XORで引き算)
       ----------------
          0  195  130  <-- 余り！

出ました！余りは 195 と 130 です。
つまり、文字「A」をエラーから守るためのパリティデータは [195, 130] となります。

最終的にQRコードに書き込まれるデータブロックは、元のデータとパリティを繋げた [65, 195, 130] になります。これが、世界中で毎日スマホが読み取っているデータの正体です！

【ツール】1文字限定！リード・ソロモン符号エンコーダー

ASCII表にある好きな文字（半角英数字）を1文字入力してみてください。その文字のASCIIコードから、QRコード仕様のガロア体計算を使って、実際に2バイトのパリティを生成する様子をシミュレーションできます。

1文字限定！リード・ソロモン符号エンコーダー

文字入力

ASCIIコード選択（スライダー）

クイック選択:

最終的なQRコードのデータブロック

[ 65, 195, 130 ]

データ: 65 / パリティ: 195, 130

使い方
1. 上側のスライダーかテキスト入力でASCII表にある文字を打ち込む
2. 自動的に２byteのリードソロモン符号が計算される。

4. 壊れたデータをどうやって直すの？（復元の全容）

「パリティの作り方はわかった。でも、QRコードが汚れてデータが書き換わってしまったら、どうやって直すの？」

実際のQRコードリーダーの内部では、第1回で少し触れた「シンドローム（エラーの兆候）」を計算したあと、以下の数学アルゴリズムたちがリレー形式で活躍しています。

シンドローム計算： 受け取ったデータをもう一度割り算して、ズレがないか確認する。
バーレカンプ・マッシー法（Berlekamp-Massey algorithm）： シンドロームから、「エラーがいくつ起きているか」と「エラーの位置を示す多項式」を高速で弾き出す最強のアルゴリズム。
チェン探索（Chien search）： 弾き出された多項式に総当たりで数字を代入し、「具体的に何番目のデータが壊れているか」を特定する。
フォーニーのアルゴリズム（Forney algorithm）： エラーの場所が分かったら、「本来の正しい数字が何だったのか」をズバリ計算して復元する。

これらのアルゴリズムをすべてゼロから手書きで実装しようとすると、数学の専門書が1冊書けてしまうほどのボリュームになります。

しかし、素晴らしいことに現代では、これらの複雑な復元処理は各プログラミング言語のライブラリ（Pythonの reedsolo など）で簡単に呼び出すことができます。

「中身がどういう理屈で動いているのか（ガロア体の割り算）」を知っているだけでも、エラーが出たときの対処や、自分でライブラリを活用する際の解像度が劇的に変わるはずです。

このシリーズでは、次回からこの深淵の淵ギリギリくらいまで行ってみようと思います。

今回、私たちはプログラムと計算でQRコードの仕組みを追っていますが、世の中にはこの計算とマス目塗りを「すべて手作業（手書き）」でやってのけた猛者がいらっしゃいます。

真心のこもった手づくりQRコードの作り方（本編）https://marich1224.hatenablog.com/entry/2023/11/01/000006

（※勝手ながらリンク失礼いたします。手作業でQRを作る情熱と根気に脱帽です！）
コンピュータがどれだけありがたい存在か、こちらの記事を読むとさらに実感できるはずです。

5. 実際のQRコードのマス目にどう配置されるの？

QRコードでは、角に置いたファインダパタンに加えて、アライメントパタンやタイミングパタンなど検出精度を上げるための固定のマークがあり、それ以外の部分にデータを配置しています。

データ [65, 195, 130] を空いた部分に配置していきます。

数字をすべて8桁の2進数に戻します。

データ：01000001 (65)
パリティ1：11000011 (195)
パリティ2：10000010 (130)

QRコードの仕様では、右下の角からスタートして、2マス幅でジグザグに上に向かって進みながら、 1 を黒マス、 0 を白マスとして順番に塗りつぶしていきます（※実際には、読み取りやすくするための「マスク処理」という反転作業や規格により配置が決まっていますが、基本はこのまま並べていくだけです）。

QRコードのbyte配置例 (右下から埋めていく※文字数情報などは簡単のため略しています)

おわりに

これまでの3回にわたる「QRコードの符号化と復元（基礎編）」、いかがだったでしょうか。

一見ただのランダムな白黒のノイズに見えるQRコードの裏側には、

多項式の割り算（CRC）のアイデア
枠からはみ出さないガロア体の魔法
リード・ソロモン符号という究極の復元技術 という、人類の知恵の結晶が詰め込まれていました。

基礎的な仕組みの解説は、これにて完結となります。ここまでの知識があれば、既存のライブラリを使ってQRコードを生成したり解読したりする分における理解としては全く困らないはずです。

……しかし。

「バーレカンプ・マッシー法とか、チェン探索とか、魔法みたいなアルゴリズムをライブラリ任せにするのは悔しい！」「本当に自分の手で、ゼロからエラーを直すコードを書いてみたい！」

そんな知的好奇心に溢れる方のために、次回（第4回）からは【深淵編】へ突入します。ブラックボックス化されている復元アルゴリズムの内部構造を解き明かし、スクラッチで実装していくマニアックな世界へご案内する予定です。

ここまでお付き合いいただき、ありがとうございました。では、また次の記事（深淵の入り口）で。 lumenHero

次回：QRのバージョンとレベルなど仕様を知る
関連記事は、2026年6月17日に公開予定 (あと9時間)

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