QRコードのデコード誤り位置を特定するチェン探索（Chien Search）【QRコードを解読する第10回】

0. はじめに

QRコードのデコード時に誤り位置を見つけるチェン探索について、実例を用いて解説するサムネイル

前回の「第9回：バーレカンプ・マッシー（BM）法」では、2箇所のノイズが混ざった複雑なシンドロームから、エラーの場所を隠し持つ方程式（エラー位置多項式）をジワジワと育て上げるアルゴリズムを体験しました。

Notebookで計算した結果、最終的に導き出されたエラー位置多項式 \(\sigma(x)\) の係数は [1, 40, 29] となりました。
これは、数学的に表すと \(1 + 40x + 29x^2 = 0\) という立派な二次方程式です。（※昇べきの順（次数の低い順）に並んでいるため見慣れない形かもしれませんが、性質は同じです）。

今回は、この完成した方程式を解き、エラーの正確な「場所」を突き止めるアルゴリズム、「チェン探索（Chien Search）」に挑みます！

1. チェン探索とは？

方程式を解く、と聞くと「解の公式」などを思い浮かべるかもしれませんが、ガロア体（有限体）の世界ではもっとシンプルで確実な方法が使われます。それが「総当たり（Brute-force search）」です。

チェン探索は、ガロア体の要素を順番に方程式の \(x\) に代入していき、「計算結果が 0 になった瞬間、その要素がエラーの場所である」と判定する極めてシンプルな力技のアルゴリズムです。

なぜ総当たりが可能なのか？

現実世界の数字（実数）は無限にあるため、総当たりで方程式の解を探すのは不可能です。しかし、QRコードで使われるガロア体 \(GF(2^8)\) は、要素が「256個」しかありません。今回のミニモデル \(RS(7, 3)\) に至っては、メッセージの長さである「7個」の要素（\(\alpha^0 \sim \alpha^6\)）だけを調べれば十分なのです！有限の世界だからこそできる、コンピュータの計算力を活かした力技です。

2. 逆元（マイナス乗）の代入

ここで1つだけ、数式のトリックがあります。
BM法で作られたエラー位置多項式 \(\sigma(x)\) には、「エラーが発生した位置 \(\alpha^i\) の逆元（\(\alpha^{-i}\)）を代入したときに 0 になる」という特徴があります。

そのため、チェン探索では \(x\) に \(\alpha^i\) をそのまま代入するのではなく、\(\alpha^{-i}\)（プログラム上は \(\alpha^{255-i}\)）を代入して 0 になるかを確認していきます。

補足：なぜ逆元を入れたら０になる？
【補足】なぜチェン探索では「逆元（マイナス乗）」を代入するのか？（エラー位置多項式の正体）

3. Jupyter Notebookでチェン探索を試す

それでは、実際にPythonコードでチェン探索を動かし、2つのエラーの居場所を突き止める総当たりの過程を見てみましょう！
以下のリンクからGoogle Colaboratoryを開き、ご自身のブラウザ上でコードを実行してみてください。

Qr from Scratch:Step4 チェン探索

QRコードの車輪の再発明。完成した方程式にガロア体の要素を総当たりで代入し、エラー位置を特定します。

github.com

github link : Qr from Scratch : チェン探索
(https://github.com/Tsukumo-999/qr-code-from-scratch/blob/master/Step3/chien_search.ipynb)

4. 計算の軌跡（結果の考察）

Notebookを実行すると、\(i = 0\) から \(6\) まで順番に代入と計算が行われます。

結果をみると。

\(i = 3\) のとき、計算結果が 0 になりました。
\(i = 5\) のとき、計算結果が 0 になりました。

この \(i\) は、多項式の \(x^i\)（後ろから \(i\) 乗目の位置）を表しています。
今回のメッセージは7バイトなので、配列のインデックスに直すと：

\(i = 3\) \(\rightarrow\) 後ろから4番目 \(\rightarrow\) インデックス 3
\(i = 5\) \(\rightarrow\) 後ろから6番目 \(\rightarrow\) インデックス 1

前回、私たちがわざとデータを壊した場所は、「2番目の ‘A'(インデックス1)」 と 「4番目のパリティ(インデックス3)」 でした。
見事に、チェン探索が犯人の居場所を正確に突き止めました！

5. まとめと次回予告

BM法が育てた「エラー位置多項式」という地図と、チェン探索の「総当たり」という足を使った捜査によって、ついに2つのエラーの正確な「場所」が判明しました。

場所が分かれば、あとは「その場所の数字が、どれくらいの強さで反転してしまったか（エラーの値）」を計算するだけです。
次回はいよいよエラー訂正の最終章、「フォルニー（Forney）法」に挑みます。特定したエラーの値を算出し、ノイズまみれの配列から「HAL」の文字を完全に復元する大団円をお見逃しなく！

次回：フォルニー（Forney）法
関連記事は、2026年6月21日に公開予定 (あと20時間)