Construction of MRD Codes Based on Circular-Shift Operations

論文概要

タイトル: Construction of MRD Codes Based on Circular-Shift Operations
著者: Zhe Zhai, Sheng Jin, Qifu Tyler Sun, Zongpeng Li
分野: 符号理論、ランク距離符号（Rank Metric Codes）、ネットワーク符号化

1. 背景と課題 (Problem)

最大ランク距離（MRD）符号は、暗号学、分散ストレージ、部分空間符号など、幅広い分野で応用されています。現在、最もよく知られている MRD 符号の構成法（Gabidulin 符号や Twisted Gabidulin 符号など）は、拡大有限体 $\mathbb{F}_{q^N}$ 上の演算に依存しています。

しかし、この従来のアプローチには以下の重大な課題があります：

• 実装の複雑さ: パラメータ $N$（符号長や次元に関連）が大きくなると、必要となる拡大有限体 $\mathbb{F}_{q^N}$ の演算が極めて複雑になり、実用的な実装が困難になります。
• 基底選択の問題: $\mathbb{F}_{q^N}$ から $\mathbb{F}_q$ 上の行列へ変換する際に、効率的な基底の選択方法が十分に研究されておらず、パラメータの柔軟な選択が制限されています。
• 計算コスト: 従来の構成法では、有限体上の乗算（特に多項式乗算）が必要となり、計算量が増大します。

2. 提案手法 (Methodology)

この論文では、円形シフト（Circular-Shift）演算に基づいた新しい MRD 符号の構成法を提案しています。この手法の最大の特徴は、拡大有限体 $\mathbb{F}_{q^J}$ の演算を一切使用せず、すべて基本有限体 $\mathbb{F}_q$ 上の演算（加算とシフト）のみで符号生成を行う点です。

主要な構成要素:

• パラメータ設定:
  • $q$: 素数（または素数の冪）。
  • $L$: $q$ と互いに素な正整数 ($\gcd(q, L)=1$)。
  • $m_L$: $q$ の $L$ に関する乗法次数（$q^{m_L} \equiv 1 \pmod L$）。
  • $J$: $L$ に関するオイラー関数 $\phi(L)$（$1$から$L-1$までの$L$ と互いに素な整数の個数）。
  • 符号パラメータ: $(J \times n, q^{Jk}, d)$ MRD 符号。ここで $n \le m_L \le J$。
• 符号の定義:
  情報ベクトル $m \in \mathbb{F}_q^{Jk}$ に対して、符号語 $C$ は以下の行列演算で定義されます。
  $$C = \{ \Delta(m(I_k \otimes P) \Psi_{k \times n} (I_n \otimes Q)) : m \in \mathbb{F}_q^{Jk} \}$$
  • $\Psi_{k \times n}$: 各ブロックが $L \times L$ の巡回シフト行列（Circulant Matrix）であるブロック行列。
  • $P, Q$: $\mathbb{F}_q$ 上で構成された特定の行列（$P=GL, Q=HL$ など）。
  • $\Delta$: ベクトルを行列に変換する写像。
• 実装の利点: 符号語の生成において、有限体 $\mathbb{F}_q$ 上の要素ごとの加算（XOR 演算）と列ごとの円形シフトのみを使用します。

3. 主要な貢献と結果 (Key Contributions & Results)

A. 効率的な符号生成

提案された符号は、拡大有限体の演算を不要にするため、実装が大幅に簡素化されます。特に $q=2$ の場合、符号語の生成に必要な演算は XOR 演算のみとなります。

B. Gabidulin 符号との関係性の解明

提案された符号と既存の Gabidulin 符号（および Twisted Gabidulin 符号）との本質的な違いと関連性を、$\mathbb{F}_q^N$ 上の $q$-線形化多項式を用いて明確にしました。

• $J \neq m_L$ の場合: 特定の条件下（パラメータ $l_j$ の選択など）において、提案符号は任意の Gabidulin 符号や Twisted Gabidulin 符号と異なる（同値でない）ことを証明しました。これは、既存の MRD 符号とは異なる新しい符号族の存在を示しています。
• $J = m_L$ の場合: 提案された符号は、ある基底に対する Gabidulin 符号と一致することが証明されました。
  • 意義: 一致するとしても、提案構成法は $\mathbb{F}_{q^J}$ の演算を回避し、$\mathbb{F}_q$ のみで Gabidulin 符号を構成する新しいアプローチを提供します。これは、従来の基底選択の困難さを解決する実用的な代替手段となります。

C. Gabidulin 符号の一般化との等価性

特定の行列 $P, Q$ の選択において、提案された MRD 符号は、いくつかの $(m_L \times n, q^{m_L k}, d)$ Gabidulin 符号を和と連結（concatenation）して得られる「Gabidulin 符号の一般化」と同値であることを示しました。これは文献で初めて探索された構成です。

D. 計算量解析 (Computational Complexity)

$q=2$、$L$ が素数、$n \le m_L$ の場合の符号生成コストを比較しました。

• 提案符号 (Circular-shift based): $O(nkL)$ の XOR 演算で済みます。
• 従来の Gabidulin 符号: 拡大有限体 $\mathbb{F}_{2^{L-1}}$ 上の演算を必要とするため、$O(nkL^2)$ の XOR 演算（多項式乗算の近似）が必要です。
• 結果: 提案手法は、パラメータ $L$ が大きいほど計算量が劇的に減少し、効率的な実装が可能になります。

4. 意義と結論 (Significance & Conclusion)

この論文は、MRD 符号の構築において「拡大有限体の演算」というボトルネックを「円形シフト演算」という単純な操作で代替する画期的な手法を提示しました。

• 実用性の向上: 複雑な有限体演算ライブラリが不要になるため、ハードウェア実装（FPGA や ASIC）やソフトウェア実装が容易になり、大規模なパラメータ設定が可能になります。
• 理論的洞察: 既存の Gabidulin 符号や Twisted Gabidulin 符号との関係を多項式評価の観点から整理し、新しい符号族の位置づけを明確にしました。
• 将来の展望: 符号の復号アルゴリズムの設計や、部分空間符号（Subspace Codes）への応用など、今後の研究課題が示唆されています。

総じて、この研究は MRD 符号の理論的枠組みを維持しつつ、その実用的な適用可能性を飛躍的に高める重要な貢献と言えます。