On the Error Probability of RPA Decoding of Reed-Muller Codes over BMS Channels

技術要約：BMSチャネルにおけるリード・マラー符号のRPA復号のエラー確率について

問題提起
リード・マラー（RM）符号は、バイナリメモリレス対称（BMS）チャネルにおいて通信路容量を達成できることが知られている、バイナリ線形符号の基本的なファミリーである。理論的な容量達成特性は確立されているものの、実用的な復号には課題が残っている。YeとAbbeによって導入された再帰的投影・集約（RPA）復号器は、バイナリ対称チャネル（BSC）上のRM符号に対して、最尤（ML）性能に近い性能を示すことが実証されている。しかし、一般的なBMSチャネルにおけるRPA復号の厳密な解析的性能保証は、これまで欠落していた。RameshwarとLalitha（2025）による最近の研究では、BSCについてはそのような保証が提供されているが、これらの結果を任意のBMSチャネルへと拡張することは非自明である。なぜなら、彼らの証明戦略を直接一般化するには、チャネルに対する制限的な仮定（例：出力アルファベットのサイズおよび対数尤度比の有界性）が必要となるからである。本論文は、このような制限的な仮定を置くことなく、一般的なBMSチャネルにおけるRPA復号の明示的なエラー確率境界を導出することで、このギャップに対処する。

手法
著者らは、RPA復号と極性符号（Polar Code）構成との間の特定の構造的等価性を活用することで、BSCを用いたアプローチを一般化する証明戦略を展開している。

1. チャネルの等価性： コアとなる技術的洞察は、RPA復号における投影操作と、極性符号構成における「チャネル結合」フェーズとの間の等価性を特定することである。具体的には、RM符号を1次元部分空間に沿って投影することは、元のBMSチャネル $W$ の2回の独立した使用から得られるチャネルと同一である、新しいチャネル $W^-$ を誘導する。
2. バチャラヤ・パラメータの解析： この等価性を利用して、著者らはRPA復号器の再帰木を通じたバチャラヤ・パラメータ（$Z$）の進化を分析する。彼らは、各ステップにおける誘導チャネルのバチャラヤ・パラメータが $Z(W^-) \leq 1 - (1 - Z(W))^2$ を満たすことを確立する。これにより、再帰木の「リーフ（葉）」の部分（第1次RM符号が復号される箇所）におけるチャネル品質を、初期のチャネルパラメータに基づいて抑えることが可能となる。
3. 再帰的エラー境界の導出： 解析は、RPA復号器の1回の反復のみで収束する場合に焦点を当てる。著者らは、RPA再帰木の各ノードにおけるエラー確率に関する漸化式を導出する。
   • ベースケース： リーフノード（第1次RM符号）については、MLエラー確率に対する一般的な和の境界（union bound）を用いる。極めて重要な点として、この境界は任意のBMSチャネルに対して成立し、特定のチャネル制約を必要としない。
   • 再帰ステップ： 高次のノードについては、子ノードにおけるエラーの確率と、正しい子ノードの復号を条件とした集約ステップにおけるエラーの確率によって、エラー確率が抑えられる。
4. 再帰の展開： これらの漸化式を展開することにより、著者らは、ブロック長 $n = 2^m$ および符号次数 $r$ の関数として、全ブロックエラー確率 $P_{err}(RM(m, r))$ に対する閉形式の上限境界を導出する。

主な貢献と結果
主要な貢献は、一般的なBMSチャネルにおけるRPA復号器の消失エラー確率に関する解析的保証を提供する定理4である。

• 主要な結果： 本論文は、バチャラヤ・パラメータ $Z$ を持つBMSチャネルに対し、RM次数 $r$ が概ね以下のようにスケールする場合、RPA復号器はブロック長 $n \to \infty$（または $m \to \infty$）に伴い消失エラー確率を達成することを証明している：
  $$r < \log_2 m - \log_2 \lambda$$
  ここで $\lambda = -\ln(1-Z)$ である。
• 漸近的スケーリング： このスケーリングは、$r$ が $m$ に対して対数的に成長すること（すなわち $r \sim \log \log n$）を示唆している。この漸近的挙動は、[19]で確立されたBSCに関する結果と一致している。
• 汎用性： BSCの証明を一般化しようとするこれまでの試みとは異なり、この手法は、チャネルに対する追加の仮定（対数尤度比の有界性など）を必要としない。この証明は、バチャラヤ・パラメータの性質と、極性符号結合への構造的等価性にのみ依存している。

意義と主張
本論文は、その研究がRameshwarとLalitha（2025）による結果の重要な一般化であることを主張している。RPA復号器が「低レート」のRM符号（次数が $\log \log n$ としてスケールするもの）に対して、すべての BMSチャネル上で消失エラー確率を達成することを明示的に証明することで、著者らはRPA復号の理論的理解をBSCを超えて拡張している。

著者らは、BSCに対する彼らの導出された境界は、[19]の特定の境界よりもわずかに弱い（これは任意のBMSチャネルに対する汎用性を必要とするためである）ことを認めているが、符号次数 $r$ の漸近的成長率は同一である。また、彼らの解析は、復号器の1回の反復が十分である領域に限定していることを明記している。したがって、複数回の反復によって導入される相関を分析するためにこの制限を緩和することが、エラー確率のさらなる漸近的改善を得るための重要な方向性であると示唆しているが、これは本研究では達成されていない。

要約すると、本論文は、RPA復号器が広範なBMSチャネルクラスにおいてRM符号に対して有効であることを示す、最初の厳密かつ仮定のない解析的証明を提供しており、特定のチャネル制約がない場合でも、復号器の性能がブロック長とともに良好にスケールすることを裏付けている。