Low-Pathwidth GRAND: Exact Likelihood-Ordered Enumeration for BPSK Transmission over Correlated Gaussian Noise

あなたは、騒がしく混雑した部屋の中で秘密のメッセージを送ろうとしていると想像してください。あなたは一連の言葉を叫びますが、風や話し声、そしてエコーがあなたの声を歪ませます。聞き手は、あなたが実際に意図した言葉が何であったかを推測しなければなりません。デジタル通信の世界では、この「部屋」はチャネルであり、「言葉」はビットデータであり、「ノイズ」は信号をかき乱すランダムな干渉です。デコーダ（復号器）の目標は、この混沌とした状況の中で元のメッセージを特定することです。

数十年にわたり、エンジニアたちは「Guessing Random Additive Noise Decoding」（GRAND：加法的ランダムノイズ推測復号）と呼ばれる巧妙な戦略を使用してきました。GRANDはメッセージを直接推測する代わりに、逆方向に働きます。つまり、何が「ノイズ」であったのかを推測するのです。それは、最も可能性の高いノイズパターン（穏やかな微風のようなもの）から始め、より可能性の低いもの（ハリケーンのようなもの）へと進んでいきます。もし、受信した信号から推測したノイズパターンを差し引いた結果が有効なメッセージであれば、そこで停止し、勝利を宣言します。この仕組みが完璧に機能するためのコツは、デコーダがノイズパターンを、最も確率の高いものから最も低いものへと、正確な順序で推測することです。

しかし、ノイズが単なるランダムな静止音ではなく、「相関」を持っている場合、事態は非常に複雑になります。例えば、風がランダムに吹くのではなく、ある瞬間に突風が吹けば、その直後の瞬間にも再び吹く可能性が高いといった状況です。これはビット間に複雑なネットワークを生み出し、ノイズパターンの順位付けを極めて困難にします。従来のメソッドは、これらのつながりを無視したり、メッセージを独立した小さな塊に分割したりすることで問題を簡略化しようとしましたが、こうした近道はしばしば誤った推測を招きました。

本論文では、Low-Pathwidth GRAND (LP-GRAND) と呼ばれる、極めて精密な新しいデコーダを紹介します。これは、単にノイズを推測するだけでなく、ノイズの「相互作用グラフ」全体をマッピングして、可能性をチェックするための完璧な順序を見つけ出す熟練の探偵のようなものです。著者らは、ノイズを特定の数学的な形状（二次エネルギー地形）として扱い、巧妙な「トレリス」（段階的なマップ）を使用することで、相関が強い場合であっても、あらゆる可能なノイズパターンを確率の高い順にリストアップできることを示しました。彼らは、もしこのリストに従って一つも飛ばさずに進めば、最初に見つかった有効なメッセージが必ず最善の答えであることを数学的に証明しました。特定の符号を用いたシミュレーションにおいて、この新手法は、従来の「ブロックベース」の近道よりも高い頻度で、かつ高速に正しいメッセージを見つけ出し、複雑なつながりをマッピングするために時間をかけることが報われることを証明しました。

コアとなるアイデア：ノイズの迷路をマッピングする

LP-GRANDの仕組みを理解するために、ノイズを巨大な多次元の迷路だと想像してみましょう。単純な「メモリレス（記憶のない）」世界では、迷路の各経路は独立しています。つまり、前のステップでの選択に関係なく、任意の時点で左折か右折を選択できます。しかし、「相関のある」世界では、迷路はねじれています。ステップ5で左に曲がると、ステップ6では右に曲がらざるを得ない、といった具合です。この「ねじれ」こそが、数学的な難題を生みます。

著者らは、特定の種類のノイズ（既知の精度行列を持つガウスノイズ）に対しては、このねじれた迷路を、トレリスと呼ばれる構造化された層状のマップへと平坦化できることに気づきました。もしノイズの接続が「疎（sparse）」である場合（つまり、隣接するビット同士が会話するように、近くのビットとしか繋がっていない場合）、このマップは無限に巨大化することはありません。代わりに、限られた数の「段（rung）」を持つ梯子のような、扱いやすい規模に留まります。

LP-GRANDはこの梯子を利用して、「ベストファースト探索」を実行します。単に梯子を下るのではなく、あらゆる可能な経路の「エネルギーコスト」を計算します。エネルギーが低いほど、そのノイズパターンはより起こりやすいものです。**サフィックス・ダイナミックプログラミング（後方動的計画法）**を用いることで、デコーダは先読みを行い、次に探索すべき最も安価な経路がどれであるかを正確に把握できます。これは、出口までの距離だけでなく、最短ルートを確実に見つけるために、あらゆるルートを訪れるべき正確な順序を教えてくれるGPSを持っているようなものです。

なぜ古い近道は失敗したのか

この論文以前、エンジニアはメッセージを小さなブロックに分割し、あるブロックのノイズが次のブロックに影響を与えないと仮定することで、問題を簡略化しようとすることがよくありました。これは、ジグソーパズルのピース同士が絵として繋がっていることを無視して、パズルを解こうとするようなものです。

本論文は、これらの「ブロックベースの近似」に対して明確に反対しています。著者らは、ノイズが相関している場合、これらの近道は「クロス座標相互作用（一つの部分のノイズが他の部分にどのように影響するかという微妙な関係）」を見逃してしまうことを示しています。テストの結果、これらの近道は、相関のあるノイズにおいて誤ったノイズパターンを最初に推測してしまうことがあり、デコーディングエラーを引き起こしました。論文では、これらの近道は計算こそ速いものの、「最大尤度（Maximum Likelihood: ML）」最適ではない、つまり絶対的な最善の答えを見つける保証がないことを示しています。対照的に、LP-GRANDは決して妥協せず、相関のあるノザの完全なエネルギーを計算するため、最初に見つけた有効なメッセージが数学的に最も可能性の高いものであることを保証します。

結果：完璧な一致

著者らは単に理論を提示しただけでなく、このデコーダを厳格にテストしました。彼らは、小さな [20, 12] 符号と、より大きな [64, 52] 符号という2種類の異なる符号を用いてシミュレーションを行いました。

小さな符号のテストでは、LP-GRANDを「全探索（exhaustive search）」と比較しました。全探索とは、最善のメッセージを見つけるために、あらゆる可能なメッセージを一つずつチェックする手法です。この全探索はゴールドスタンダード（最高基準）ですが、通常は実用には遅すぎます。10,000フレームのデータを通じて、LP-GRANDは全探索と100%一致しました。LP-GRANDは、毎回全く同じ「最善の」メッセージを見つけ出し、そのノイズパターンの順序付けが数学的に完璧であることを証明しました。

より大きな [64, 52] 符号については、LP-GRANDを一般的なブロックベースの近道（ORBGRAND-AIやExactBlockProductなど）と比較しました。信号品質が 2 dB のとき、LP-GRANDは他のすべての手法よりも低い「ブロック誤り率（BLER）」を達成しました。簡単に言えば、より少ないミスを出したということです。例えば、特定のランダム符号を用いたテストにおいて、LP-GRANDの誤り率は約 0.022 であったのに対し、最高のブロックベース近似の誤り率は 0.040 でした。これは、LP-GRANDがこれらのテストにおいて、他の手法よりも約2倍信頼性が高かったことを意味します。

「パス幅」の魔法

このデコーダの秘訣は、**パス幅（pathwidth）**という概念です。ノイズの接続を、点（ビット）が線で結ばれたグラフだと想像してください。もしグラフが長い直線であれば、パス幅は小さくなります。もしグラフが絡まった毛糸玉であれば、パス幅は非常に大きくなります。著者らは、ノザの行列が「ハーフバンド幅（half-bandwidth）」（つまり、近くのビット同士しか接続していないこと）を持つ場合、パス幅が十分に小さくなり、管理可能なトレリスを構築できることを示しました。

彼らは、パス、ラダー（梯子）、バイナリツリーなど、さまざまな形状のグラフでこれをテストしました。「パス」や「ラダー」のような形状は、多くの現実世界のチャネルで見られる種類のノイズを表しており、これらに対してデコーダは完璧に機能しました。さらに、ノイズの接続がシャッフル（置換）され、整然とした順序になっていないシナリオでもテストを行いました。逆カチール・マッキー（Reverse Cuthill–McKee: RCM）と呼ばれる巧妙な並べ替えトリックを使用することで、依然として低いパス幅を見つけ出し、デコーダを効率的に実行することができました。シャッフルされた64ビット符号を用いたテストでは、LP-GRANDはテストされた50フレームすべてで正しいメッセージを見つけましたが、ブロックベースの手法は17から25フレームでエラーを出しました。

結論

本論文は、特定の重要なクラスのノイズの多いチャネルに対して、正確かつ効率的なデコーダを提示しています。適切な数学的マップを使用すれば、速度と精度のどちらか一方を選ぶ必要はないことを証明しています。ノイズを構造化されたエネルギー地形として扱い、「低パス幅」のアプローチを用いてそれをナビゲートすることで、LP-GRANDは最初に見つけた有効なメッセージが最善のものであることを保証します。従来の近道よりも複雑なセットアップを必要としますが、シミュレーションによれば、相関のあるノイズに対してはこの追加の努力が大幅なエラーの減少につながり、将来の高信頼性通信システムにとって強力なツールとなることが示されています。