QRコードのデコード：フォルニー（Forney）法でエラーを完全修復する！【QRコードを解読する第11回】

0. はじめに

フォルニー法で破損情報を復元する。QRコードのロバスト性を担保するアルゴリズムを実例をもとに開設する記事のサムネイル

QRコードの車輪の再発明、ついにエラー訂正の最終ステップに到達しました！
前回の「第10回：チェン探索」では、BM法で育てたエラー位置多項式にガロア体の要素を総当たりで代入し、エラーが発生した正確な場所が、「2番目の ‘A'(インデックス1)」 と 「4番目のパリティ(インデックス3)」 であることを突き止めました。

場所が分かれば、あとは「その場所の数字が、どれくらいの強さで反転してしまったか（エラーの値）」を計算し、元に戻すだけです。
今回は、リード・ソロモン復号の最後のピース、「フォルニー（Forney）法」に挑み、ノイズまみれの配列から「HAL」の文字を完全に復元する大団円を迎えます！

1. フォルニー法とは？

フォルニー法（Forney algorithm）は、エラーの「場所」と「シンドローム」から、エラーの「値（マグニチュード）」を算出する強力なアルゴリズムです。

数式の詳細は非常に奥深いですが、やっていることは主に以下の3ステップです。

エラー評価多項式 \(\Omega(x)\) を作る: シンドローム \(S(x)\) と、BM法で作ったエラー位置多項式 \(\sigma(x)\) を掛け合わせることで、エラーの「大きさ」に関する情報が詰まった新しい多項式を作ります。
エラー位置多項式を「微分」する:
高校数学で習う「微分」を、ガロア体の多項式に対して行います。ガロア体における微分（形式的微分）は非常にシンプルで、「偶数乗の項が消滅し、奇数乗の項だけが残る」という面白い性質を持っています。
割り算をしてエラー値を出す:
チェン探索で見つけたエラーの場所を、1と2で作った式に代入し、「\(\Omega(x)\) の結果 \(\div\) 微分した式の結果」を計算します。これがエラーの真の値（XORで反転すべき値）になります！

2. Jupyter Notebookでフォルニー法を試す

それでは、実際にPythonコードでフォルニー法を動かし、2つのエラー値を算出してデータを修復してみましょう！
以下のリンクからGoogle Colaboratoryを開き、ご自身のブラウザ上でコードを実行してみてください。

Qr from Scratch:Step5 フォルニー法

QRコードの車輪の再発明、ここに完結。フォルニー法でエラー値を算出し、傷ついたデータから「HAL」を復元します！

github.com

github link : Qr from Scratch : フォルニー法
(https://github.com/Tsukumo-999/qr-code-from-scratch/blob/master/Step3/4_forney_algorithm.ipynb)

3. 計算の軌跡と大団円（結果の考察）

Notebookを実行すると、私たちが意図的に壊した2箇所のインデックスに対して、エラー値が計算されます。
結果を見てみましょう！

フォルニー法による値の復元結果、破損した情報の位置から値を復元して元の文字列 "HAL"を復元できている様子

インデックス 1 のエラー値: 34
受信データは 99 でした。99 に 34 をXOR演算すると……なんと本来のデータである 65 ('A') に戻ります！
インデックス 3 のエラー値: 169
受信データ（パリティ）は 200 でした。200 に 169 をXOR演算すると……本来のパリティである 97 に戻ります！

計算されたエラー値を配列にXORすることで、ノイズだらけだった受信メッセージが、完璧な送信メッセージ [72, 65, 76, 97, 162, 112, 246] へとパズルが解けるように修復されました。そして、見事に 「HAL」 という文字が浮かび上がりました。

4. エラー訂正編まとめ

第8回のシンドローム計算から始まったリード・ソロモン符号のエラー訂正アルゴリズム。
一見するとブラックボックスのように思えるQRコードの強力な復元力は、以下の3つのアルゴリズムの見事なリレーによって支えられていました。

シンドローム計算: エラーの兆候を検知する。
バーレカンプ・マッシー（BM）法: 過去の失敗から学習し、エラーの場所を示す方程式（地図）を作る。
チェン探索＆フォルニー法: 方程式を総当たりで解いて居場所を突き止め、エラーの値を算出して修復する。

数学とプログラミングの力が結集したこの美しい仕組みを「車輪の再発明」として一から書き上げたことで、QRコードがなぜあれほどタフなのか、その本質を深く理解できたはずです。

復元の方法についてはここまでで完結となります。次回はおまけとして、わざと汚した自作QRコードを読み取るサンプルを紹介して、このシリーズの締めとしようと思います。

次回：QRデコーダ完成版
QRコードのデコードに挑む！特別編：汎用デコーダの完成と「汚れ」への挑戦【QRコードを解読する第12回(完)】