QRコードのデコードに挑む！バーレカンプ・マッシー（BM）法【QRコードを解読する第9回】

0. はじめに

エラー位置多項式を求めるバーレカンプ・マッシー（BM）法の実装を解説する記事のサムネイル

前回の「第8回：シンドローム計算」では、7バイトのミニモデル「HAL」を用いて、データに1箇所だけエラー（ノイズ）が混入した場合の復元を体験しました。エラーが1つであれば、シンドローム同士の「割り算」というシンプルな計算だけで、一瞬にしてエラーの場所と値を特定することができました。

しかし、記事の最後で触れたように、エラーが2箇所、3箇所と増えると、変数が混ざり合ってしまい、単純な割り算では手も足も出なくなってしまいます。

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

1. 2箇所のノイズを持つ受信データ

今回も、ガロア体 \(GF(2^8)\) をベースにした7バイトのミニモデルを使用します。
送信された完璧なデータは「HAL」のASCIIコードとパリティを含めた以下の配列です。
[72, 65, 76, 97, 162, 112, 246]

今回は、意図的に2箇所のデータを壊してみましょう。
2番目の ‘A'(65) を 99 に、4番目のパリティ(97) を 200 に化けさせます。

受信メッセージ：[72, 99, 76, 200, 162, 112, 246]

このデータから4つのシンドローム \(S_0, S_1, S_2, S_3\) を計算し、それをBM法に渡します。

2. バーレカンプ・マッシー（BM）法とは？

BM法（Berlekamp-Massey algorithm）は、一言で言えば「過去の失敗から学び、予測モデルをアップデートしていく機械学習のようなアルゴリズム」です。

具体的には以下のような動きをします。

予測する: 現在持っている「エラー位置多項式 \(C(x)\)」と過去のシンドロームを使って、次のシンドロームがどんな値になるかを予測（計算）します。
ズレ（ディスクレパンシー）を測る: 実際のシンドロームと、予測値との差（ズレ）を計算します。これをディスクレパンシー（d）と呼びます。
式を修正する: もしズレが 0（予測成功）なら、式はそのまま。もしズレが 0 以外（予測失敗）なら、過去の古い式 \(B(x)\) を使って現在の式 \(C(x)\) を正しい形に修正（アップデート）します。

これをシンドロームの数（今回は4回）だけ繰り返すことで、最終的に「すべてのシンドロームの動きを完璧に説明できる最強の方程式（エラー位置多項式）」が完成します。

3. Jupyter NotebookでBM法を試す

参考資料：Berlekamp Massey法

今回の記事で紹介するプログラムは以下で公開しています。
リンクを開き、ページ上部の「Open in Colab」ボタンを押せば、Googleアカウントがあればブラウザ上で実際に動かして試すことができます。

Qr from Scratch:Step3 BR

QRコードの車輪の再発明をしながらＱＲコードを深く理解する。バーレカンプ・マッシー法について手順を追いながら試せます。

github.com

github link : Qr from Scratch:Step3 BR
(https://github.com/Tsukumo-999/qr-code-from-scratch/blob/master/Step3/2_berlekamp_massey.ipynb)

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

Notebookを実行すると、ステップごとにディスクレパンシー（d）が計算され、多項式 \(C(x)\) が成長していく様子が分かります。

初期状態の \(C(x) = [1]\) から始まり、予測が外れるたびに新しい係数が追加されていきます。
最終ステップ（ステップ3）が終わったときに出力される配列こそが、求めていた「エラー位置多項式 \(\sigma(x)\)」です。

配列のインデックスが \(x\) の次数を表しているため、例えば結果が [1, 40, 29] となった場合、それは方程式 \(1 + 40x + 29x^2 = 0\) を意味しています。（※昇べきの順（次数の低い順）に並んでいるため見慣れない形かもしれませんが、立派な二次方程式です）。

エラーが2個あるため、最も高い次数が \(x^2\) になっている点にも注目してください。

5. まとめと次回予告

今回は、複数のエラーが絡み合ったシンドロームから、エラーの場所を特定するための「方程式の係数」を導き出すBM法を実装しました。

方程式が完成したということは、「この方程式の解（根）が、そのままエラーの発生した場所を示している」ということです。

次回は、今回完成したエラー位置多項式 \(\sigma(x)\) を解くためのアルゴリズム、「チェン探索（Chien Search）」に挑みます。ガロア体の要素を総当たりで代入して犯人の居場所を突き止める、極めてシンプルかつ爽快なアルゴリズムです。お楽しみに！

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