An Ordered-Reliability-Bits Chase Decoding Algorithm for BCH Codes

技術要約：BCH符号のための順序信頼度ビット・チェイス復号アルゴリズム

問題提起
短ブロック長におけるチャネル符号化は、超高信頼低遅延通信（URLLC）や光伝送ネットワーク（OTN）などのアプリケーションにおいて極めて重要である。Bose-Chaudhuri-Hocquenghem（BCH）符号は、その強力な代数的構造と大きな最小距離により、これらのシナリオで広く利用されている。Berlekamp-Massey（BM）法のような硬判定復号アルゴリズムは効率的であるが、符号固有の誤り訂正能力に制限があり、符号のポテンシャルを最大限に引き出すことはできない。軟判定復号（SDD）は性能向上をもたらすが、多くの場合、高い計算複雑性を伴う。ChaseアルゴリズムやGuessing Random Additive Noise Decoding（GRAND）といった既存のSDD手法は、トレードオフに直面している。すなわち、近似的な最大尤度（ML）性能を実現しようとすると、指数関数的な復号複雑性の増加（例：Chase復号における$2^p$個のテストパターンの走査）が必要となる。本論文は、高い復号性能を維持しつつ、この複雑性を低減するという課題に取り組んでいる。

手法
著者らは、低複雑度な**Ordered-Reliability-Bits Chase（ORB-Chase）**復号アルゴリズムを提案している。この手法は、主に以下の2つの方法で従来のChaseアルゴリズムを改良したものである。

1. 論理重みに基づくテスト誤りパターン（TEP）生成：
   最も信頼度の低いビット（LRB）や固定された組み合わせのみに基づいてテストパターンを生成するのではなく、本アルゴリズムは**論理重み（logical weight）**を指標としてTEPを順序付けする。

   • ビットは信頼度（LLR絶対値の昇順）に従ってソートされる。
   • テストパターンの論理重み $w_L(e_n)$ は、このソートされたシーケンスにおける反転ビットのインデックスの総和として定義される（$w_L(e_n) = \sum i \cdot e_i$）。
   • TEPは、論理重みの昇順で生成される。同一の論理重みを持つパターンに対しては、整数分割生成器を用いてハミング重数の昇順でソートされる。この順序付けにより、ノイズシーケンスの尤度を近似し、最も確率の高い誤りパターンを優先する。

2. 整数ベースの早期終了基準：
   生成された候補符号語がML符号語であるかどうかを判断する基準を導入することで、全候補リストを生成することなく復号プロセスを終了させる。

   • 本手法は、先行研究の「最適性基準（Optimality Criterion）」を適応させたものであり、符号語の相関不一致を、最も信頼度の高いビットから導出された下限と比較する。
   • 計算オーバーヘッドを削減するため、著者らは浮動小数点による信頼度値を整数表現の信頼度に置き換えた。これは、ソートされた信頼度値に区分線形曲線（piecewise linear curve）を適合させ、その傾きを1に量子化することで実現される。
   • 終了条件は、反転したビットの整数信頼度の総和が、指標を改善するために反転し得る可能性のある最も信頼度の高いビットの整数信頼度の総和以下であるかどうかをチェックする。これが満たされた場合、現在の符号語がMLとして受理され、復号は停止する。

主な貢献

• アルゴリズム設計： 論理重み順序付けによるTEP生成と、整数ベースの早期終了メカニズムを統合したORB-Chaseアルゴリズムの提案。
• 複雑性の低減： テストパターンの最大数（$\ell_{max}$）に対する柔軟な制限と、従来のChaseアルゴリズムと比較してBerlekamp-Massey（BM）呼び出し回数を大幅に削減する早期終了条件の導入。
• 近似の妥当性検証： 整数ベースの基準が、浮動小数点による最適性基準と比較して、性能損失をほとんど伴わずにML識別プロセスを正確に近似できることを実証した。

結果
AWGNチャネルおよびBPSK変調下において、(127, 113, 5) BCH符号および(256, 239, 6) 拡張BCH（eBCH）符号を用いたシミュレーションを実施した。

• Performance vs. ORBGRAND： (127, 113, 5) 符号において、$\ell_{max}=16$ のORB-Chaseアルゴリズムは、ブロック誤り率（BLER）$10^{-3}$ において、$\ell_{max}=16$ のORBGRANDアルゴリズムを約1.5 dB上回った。また、ORB-Chaseアルゴリズムは $\ell_{max}=200$ でML下限に接近したが、同等の性能を得るためにORBGRANDは $\ell_{max}=10^5$ という大幅に多いクエリを必要とした。
• Chaseとの複雑性比較：
  • 平均BM復号呼び出し回数を主要な複雑性指標として用いた。
  • (127, 113, 5) 符号において、$E_b/N_0 = 6$ dBのとき、ORB-Chaseアルゴリズムは、同等のBLR性能を達成するChaseアルゴリズムと比較して、平均BM呼び出し回数を92.3%（$\ell_{max}=16$ の場合）および98.0%（$\ell_{max}=200$ の場合）削減した。
  • (256, 239, 6) eBCH符号でも同様の傾向が見られ、高SNRにおいて最大**98.1%**の複雑性削減を達成した。
• 終了の有効性： 整数ベースの早期終了基準は、ほとんどすべてのシミュレーションケースにおいて、浮動小数点による最適性基準と同じ終了決定を下すことが示され、その正確性が検証された。

意義と主張
本論文は、ORB-Chaseアルゴリズムが誤り訂正性能と計算複雑性の優れたトレードオフを提供すると主張している。より少ないテストパターンとBM呼び出し回数でMLに近い性能を実現することにより、本アルゴリズムは、短ブロック長BCH符号の効率的な軟判定復号を必要とする実用的なアプリケーションの有望な候補として提示されている。著者らは、本アルゴリズムの効率は $E_b/N_0$ が高くなるにつれて向上し、平均復号試行回数が急速に減少することに注目している。今後の課題としては、テスト誤りパターンの生成順序のさらなる最適化が挙げられるが、現在の貢献は、論理重み順序付けと整数ベースの終了基準の有効性に焦点を当てている。