QRコードを読み解く：シンドロームの計算とエラー検出【QRコードを解読する 第8回】

0. はじめに

前回の「Happy Path編」では、汚れや欠損が一切ない完璧なQRコードから、見事に「HELLO」という文字列を復元することができました。

しかし、現実世界で読み取るQRコードには、カメラのブレ、光の反射、汚れなどの「ノイズ（読み取りエラー）」がつきものです。もし1マスでも白黒が反転してしまうと、前回のような単純な逆再生ではデータが文字化けしてしまいます。

そこで今回から、QRコードを最強のインフラたらしめている「リード・ソロモン符号によるエラー訂正」の仕組みを、数回に分けて自作していきます。

1. 今回から扱う実験用モデル

汎用デコーダで扱う実際のQRコードデータ（長さ44バイトなど）は、ステップバイステップの計算（特にチェン探索の総当たりなど）を追うには長すぎます。
そこで、ガロア体は実際のQRコードと同じ \(GF(2^8)\) を使いつつ、データサイズを極限まで小さくした「実験用モデル」を定義します。

• データ長: 3バイト（例：”H”, “A”, “L” \(\rightarrow\) [72, 65, 76]）
• 誤り訂正コード長: 4バイト（最大2つのエラーを訂正可能）
• 総メッセージ長: 7バイト

4byteの誤り訂正が必要なので、エンコード時の生成多項式も4次になります。

生成多項式 G(x) の係数（高次から低次へ）
[‘0x01’, ‘0x0F’, ‘0x36’, ‘0x78’, ‘0x40’]
(項数: 5 -> 最高次数は 4次)

これを用いて、[72, 65, 76]をエンコードすると以下の通りです。
データコード(3byte) ＋ 誤り訂正 (4byte)
[72, 65, 76, 97, 162, 112, 246]

2. シンドロームとは何か？

エラー訂正の最初のステップは、「データに破損があるかどうか」を検知し、その兆候を集めることです。この兆候となる数値をシンドローム（Syndrome：症候群、症状）と呼びます。

受信した7バイトの配列を、ひとつの多項式 \(R(x)\) とみなします。

この \(R(x)\) の \(x\) に対して、ガロア体の要素である \(\alpha^0, \alpha^1, \alpha^2, \alpha^3\) を順番に代入して計算した結果が、4つのシンドローム \(S_0, S_1, S_2, S_3\) となります。

シンドロームの計算式は以下の通りです。
\[ S_i = R(\alpha^i)\]

データに一切のエラーがなければ、これらを代入した結果はすべて「0」になります（前回体験したHappy Pathの状態です）。逆に言えば、1つでも「0ではない値」が出現すれば、即座に「エラーが発生している！」と検知できます。

3. Pythonによるシンドローム計算

今回は、誤りとして3つ目を”99″に置き換えてシンドロームがどのようになるのか見てみます。
誤ったデータ [72, 65, 99, 97, 162, 112, 246]

このデータに対して、上で説明したようなシンドロームを計算すると以下のようになります。
\(S_0 = 47\)
\(S_1 = 202\)
\(S_2 = 60\)
\(S_3 = 231\)

データに誤りがある為シンドロームは0にならず、一見すると脈絡のない上記のような数になっています。

1_syndrome

4. エラーが1個なら「割り算」で場所がわかる！？

シンドロームは単なるエラー検知機ではありません。「どこで、どのようなエラーが起きたか」という情報が暗号のように隠されています。

実は、エラーが「1箇所」だけの場合、連立方程式を解くように値を復元することができます。

エラーの値を \(e\)、エラーの起きた場所を \(\alpha^j\) とすると、シンドロームは以下のシンプルな式で表されます。

• \(S_0 = e \cdot (\alpha^j)^0 = e\)
• \(S_1 = e \cdot (\alpha^j)^1 = e \cdot \alpha^j\)

\(S_1\) を \(S_0\) で割り算（ガロア体上の割り算）すると、エラーの値 \(e\) が打ち消され、エラーの場所である \(\alpha^j\) を導くことができます。

エラーが1つであれば、このようにシンドローム同士の計算だけで一瞬で犯人を特定・修復できてしまいます。

復元してみた

【解析結果】
・エラーの値 (e): 47
・エラーの場所 (j): 後ろから 4 乗の位置
・配列のインデックス: 2 番目

▼ 修復結果 ▼
壊れたメッセージ: [72, 65, 99, 97, 162, 112, 246]
修復後メッセージ: [72, 65, 76, 97, 162, 112, 246]

復元された文字列: HAL

5. 次回予告：複数のエラーに立ち向かう「BM法」

エラーが1つなら簡単な割り算で解決できました。

しかし、エラーが2つ、3つと増えると、シンドロームの式は複雑に絡み合い、単純な割り算では手も足も出なくなってしまいます。

そこで次回は、複数のエラーが絡み合ったシンドロームから「エラーの場所を示す方程式（エラー位置多項式）」をシステマチックに解き明かす最強のアルゴリズム、「バーレカンプ・マッシー（BM）法」に挑みます！

過去の失敗を学習しながら、正しい方程式を「育てていく」という、プログラミング的にも非常に胸熱なアルゴリズムです。お楽しみに！

次回：バーレカンプ・マッシー（BM）法
関連記事は、2026年6月20日に公開予定 (あと8時間)