技術要約：極化符号の重み構造に関するチュートリアル

問題提起

極化符号（Polar codes）およびリード・マラー（RM）符号の重み分布は、特に短〜中程度のブロック長において、その誤り訂正性能を決定する重要な要因である。近年の研究では、代数的な手法を用いて最小重み符号語および重みが $2w_{min}$ までの符号語の特性付けに成功しているが、関連文献は断片的な状態にある。既存のアプローチはしばしば高い計算複雑度に依存しており、その理論的基盤（具体的には、単項式構造、アフィン自己同型、および低重み符号語の列挙の関係性）は、必ずしも統一的かつアクセシブルな形で提示されていない。さらに、$2w_{min}$ を超える重みや、事前変換された極化符号（例：CRC-polar、PAC）に対する閉形式による列挙は、依然として未解決の課題である。

手法

本論文は、極化符号およびRM符号の代数的基礎を分析するために、単項式に基づく多項式形式を採用している。その手法は、以下の論理的ステップに従って進行する：

1. 多項式表現： 著者らは、バイナリ符号語を体 $\mathbb{F}_2[x_0, \dots, x_{m-1}] / \langle x_i^2 - x_i \rangle$ 上の多項式へと写像する。この枠組みにおいて、符号語はすべての点 $\mathbb{F}_2^m$ における多項式の評価によって生成される。
2. 減少単項式符号（Decreasing Monomial Codes）： 極化符号とRM符号の両方を、減少単項式符号というクラスの下で統一的に扱う。これらは、下三角アフィン（LTA）群の作用に対して不変な特定の偏序関係（$\preceq$、ユニバーサル偏序として知られる）を満たす、生成単項式の集合によって定義される。
3. 軌道に基づく分析： 手法の核となるのは、単項式に対する LTA($m, 2$) 群（アフィン自己同型群の部分群）の作用である。著者らは、**軌道（orbit）**を、LTA変換による単項式の像の集合として定義する。LTA変換はハミング重みを保存するため、軌道のサイズをカウントすることで重み分布を分析できる。
4. 低重み符号語の分類： 本論文では、重みが $2w_{min}$ 未満の符号語を、軌道の和に基づき以下の2つの異なるタイプに分類している：
   • Type-I： 2つの最小重み軌道の和（$LTA \cdot f + LTA \cdot g$）によって形成される符号語。その重みは、変換された多項式間の共通線形形式の数によって決定される。
   • Type-II： $\mu \geq 2$ 個の最小重み軌道の和によって形成される符号語。これらは、より複雑な相互作用や、多項式の加算における潜在的な衝突（collision）を伴う。
5. 再帰的および剰余類に基づく列挙： 重みが低重み領域を超えた場合、あるいは短縮符号の場合、極化変換構造に基づく再帰的手法を用いる。これには、符号を剰余類（coset）に分解し、重み生成関数（WEF）を部分剰余類のWEFの積として利用するプロセスが含まれる。

主な貢献

本論文は、新しい理論的定理を導出することを目的としているのではなく、むしろ最近の進展に関する統一的な解説を提供することに主眼を置いている。その主な貢献は以下の通りである：

• 統一された枠組み： 極化符号とRM符号を減少単項式符号として明確に結びつけ、それらの重み構造の体系的な特性付けを容易にする。
• 低重み符号語の体系的な列挙：
  • 最大次数の単項式に対するLTA軌道の濃度に基づき、最小重み符号語（$w_{min}$）の数を導出するための閉形式の公式を詳述している。
  • これを Type-I 符号語（重みが $[1.5w_{min}, 2w_{min})$ の範囲）へと拡張し、生成単項式の共通因子に基づいた具体的なサブケース（A1, A2, B1）の計数公式を提供する。
  • Type-II 符号語（複数の軌道の和）の構造と計数について概説し、次数2の多項式の加算における衝突現象に対処している。
• 短縮符号の取り扱い： 短縮された座標上で符号語がゼロとなることを保証するために、平行移動ベクトルおよび行列の要素に制約を課すことで、短縮極化符号に対する軌道ベースの列挙をどのように適応させるかを説明している。
• 再帰的な重み構造： 全重みスペクトルを計算するための再帰的アルゴリズムのハイレベルな概要を提供し、剰余類分解を用いた具体的な例を示している。
• アクセシビリティと再現性： チュートリアルには、例示的な例（例：(64, 32) 極化符号）、単項式順序のハッセ図、および読者が結果を再現し代数的対象への習熟を高めるためのオープンソースコードへの参照が含まれている。

結果

本論文は、以下の具体的な例を通じてこれらの手法の適用を実証している：

• 最小重みの列挙： (64, 32) 極化符号について、情報集合におけるすべての最大次数単項式の軌道のサイズを合計することで、総最小重み符号語数（$A_8 = 920$）を算出している。
• 低重みの列挙： 導出されたType-IおよびType-IIの計数公式を適用することで、重み $1.5w_{min}$ の符号語数（$A_{12} = 25,472$）および重み $1.75w_{min}$ の符号数（$A_{14} = 32,768$）を計算している。
• 対称性： 極化符号が全一ベクトル（単項式1）を含む場合、対称な重み分布（$A_w = A_{N-w}$）を持つことを確認している。
• 再帰的計算： (8, 6) 極化符号の例は、全重み生成関数を再帰的に計算し、分布 $1 + 12X^2 + 38X^4 + 12X^6 + X^8$ を得られることを示している。

重要性と主張

著者らは、本研究を、技術的な文献（具体的には [2], [20], [22], [23], [24] を引用）への深い関与に向けた準備を目的としたチュートリアルとして位置づけている。

• 限定的な範囲： 本論文は、新しい理論的結果を導入するものではないことを明示している。その価値は、「明確で統一され、アクセシブルな解説」を提供することにある。
• ギャップの解消： アフィン自己同型（特にLTA群）の役割と、重み列挙の最新の進展を理解するために不可欠でありながら、非常にテクニカルに提示されがちな軌道ベースの記述を解明することを目指している。
• 今後の方向性： $2w_{min}$ までの重みについては閉形式の公式が存在するものの、あらゆる符号レートにおいてより高い重みに対する式を導出することは、依然として未解決の問題であることを認めている。また、事前変換された極化符号（例：CRC-polar）の列挙は、現在の閉形式の手法では扱われていないことも指摘している。著者らは、信頼性を損なうことなく最小距離を最大化したり低重み符号語を減らしたりするための符号設計において、単項式の選択を最適化するために、これらの重み構造を理解することが極めて重要であると示唆している。