Polar Complexity: A New Descriptive Complexity with Applications to Source and Joint Source-Channel Coding

技術的概要：極性複雑性と適応型二重極性符号化

問題定義
個々の有限長二値系列を効率的に記述することは、情報理論における根本的な課題のままです。シャノンの枠組みは既知の統計を持つ確率的源に対する平均記述長を最適化しますが、確率モデルを持たない個々の系列には直接適用できません。一方、コルモゴロフ複雑性は、系列を生成する最短プログラムの長さによって系列の複雑性を定義しますが、理論的には普遍的であるものの計算不可能です。既存の計算可能なアプローチ、例えばレンペル・ジブ（LZ）複雑性や線形複雑性は、反復パターンや線形漸化式などの特定の構造的仮定に依存しており、任意の系列の完全な規則性を捉えきれていない可能性があります。さらに、従来の固定長極性源符号化は確率的源に対してエントロピーを達成しますが、特定の個々の系列の正確な復元に必要な最小圧縮長を決定するメカニズムを本質的に備えていません。

手法
本論文は、逐次打ち消し復号（SCD）を用いて特定の二値系列の正確な復元を保証するために必要な最小極性圧縮長（PCL）として定義される、新たな記述的複雑性指標「極性複雑性（Polar Complexity）」を導入します。この手法は、任意のブロック長に対して極性変換を一般化する二値平衡木（BBT）極性符号化フレームワークに基づいています。

1. 極性複雑性の定義と計算:

   • 著者らは、系列 $\mathbf{s}$ の極性複雑性 $L^\star(\mathbf{s})$ を、標準的な設定（凍結ノード選択に極性重み法を使用し、決定論的 SCD パラメータ $\tau=0$ を用いる）の下で、極性圧縮表現から系列を完全に復元できる最小の PCL $L$ として定義します。
   • 正確な計算: 復元可能性の単調性（ある長さ $L$ で系列が復元可能であれば、任意の $L' > L$ でも復元可能である）を利用し、本論文は $L^\star(\mathbf{s})$ を効率的に計算するための二分探索アルゴリズムを提案します。これにより、SCD 試行回数が系列長に対して線形から対数に削減されます。
   • 低複雑性推定: 反復的な復号試行を回避するため、予測極性複雑性が導入されます。この手法は、局所的に曖昧または誤りを受けやすい葉ノードの「臨界セット」を特定するために、神様支援型 SCD（GA-SCD）を利用します。予測複雑性は、この臨界セット内の最高優先度ノードの選択優先度によって決定され、真の極性複雑性に対する保守的な上限を提供します。

2. 極性ベースの二段階源符号化:

   • 各源系列を、極性複雑性の二進表現を含む固定長ヘッダーと、可変長の極性圧縮系列のペアとして符号化する新しい源符号化方式が提案されます。
   • この方式は厳密に非損失かつプレフィックスフリーです。
   • 理論的解析により、ブロック長が 2 のべき乗である二値無記憶源（BMS）において、凍結ノード選択と SCD パラメータが源分布に対して最適化されている場合、この方式の正規化平均圧縮長は漸近的に源エントロピーに収束することが証明されます。

3. 適応型二重極性結合源・チャネル符号化（JSCC）:

   • 著者らは、提案された源符号化を極性チャネル符号化と統合し、適応型 JSCC 方式を構築します。
   • メカニズム: 符号器と復号器は、事前に定義された候補 PCL の有限集合を共有します。与えられた源系列に対して、符号器は、その系列の予測極性複雑性以上である最小の候補 PCL を選択します。この選択された PCL がチャネル符号器におけるアクティブノードと凍結ノードの割り当てを決定します。
   • 復号: 復号器は候補 PCL 集合に対して仮説検定を行います。各仮説に対して候補源系列を再構成し、CRC チェックを使用して無効な候補をフィルタリングしながら、事後最大確率（MAP）基準に基づいて最終的な推定値を選択します。
   • 最適化: 候補 PCL 集合の設計は、フレーム誤り率（FER）を最小化する最適化問題として定式化されます。これは、性能（より細かい粒度）と複雑性（候補集合のサイズ）のトレードオフを調整するために、動的計画法を用いて効率的に解かれます。

主な貢献

• 極性複雑性: 正確な SCD 復元に必要な最小 PCL に基づく、新たな計算可能な記述的複雑性指標の導入。
• 効率的アルゴリズム: 正確な計算のための二分探索アルゴリズムと、極性複雑性の推定のための低複雑性 GA-SCD ベースの予測手法の開発。
• 二段階源符号化: 動作に源統計の事前知識を必要としない（ただし、エントロピー達成の証明にはパラメータ調整のために統計の知識を仮定する）厳密に非損失かつプレフィックスフリーの符号化方式。
• 適応型 JSCC: 個々の源実現の圧縮性にチャネル符号率を適応させる統合された二重極性 JSCC フレームワーク。性能と複雑性のトレードオフを最適化するための候補 PCL 集合を動的計画法に基づいて最適化する手法を含む。

結果

• 源符号化性能: シミュレーションにより、提案された二段階方式が短いブロック長（$K=64$）において列挙符号化と同等の圧縮性能を達成しつつ、計算複雑性が大幅に低い（$O(K \log K)$ 対 $O(K^2)$）ことが示されました。この方式は様々な源分布に対して堅牢であり、事前統計知識を必要としません。
• 複雑性推定: 二分探索法は、逐次探索と比較して極性複雑性を決定する計算コストを大幅に削減します。予測極性複雑性は、真の複雑性をわずかなギャップで常に上回って抑えることが確認され、JSCC 設計における有用性が検証されました。
• JSCC 性能: 適応型二重極性 JSCC のシミュレーション（ブロック長 $N=128$ および $N=1024$）において、提案方式は既存の極性符号ベースの JSCC ベースライン（二重 CRC 極性および結合 SCLD 方式を含む）を上回りました。フレーム誤り率（FER）は、候補 PCL 集合の基数が増加するにつれて単調に減少し、復号器が真の PCL を知っている場合の理論的下限に近づきます。

意義
本論文は、確率的源の性質から、極性符号化下での個々の系列の復元挙動へと焦点を移すことで、記述的複雑性の実用的かつ計算可能な尺度を提供すると主張しています。この「極性複雑性」は、厳密に非損失かつ適応的な新しいクラスの符号化方式を可能にします。提案された適応型二重極性 JSCC 方式は、柔軟な性能と複雑性のトレードオフを提供し、個々の源実現の特定の圧縮性にチャネル保護をマッチングさせることが、静的または非適応的な結合符号化アプローチと比較して優れた誤り率性能をもたらすことを示しています。この研究は、アルゴリズム的複雑性の概念と、実用的な容量近似符号化技術の間のギャップを埋めています。