Construction of cyclic codes with large minimum distance from power functions over odd characteristic finite fields

技術要約：奇数特性の有限体上のべき関数を用いた、大きな最小距離を持つ巡回符号の構成

問題提起
符号の次元が符号長の半分を超える（$k > v/2$）かつ、最小距離が符号長の平方根より大きい（$d > \sqrt{v}$）巡回符号は、通信システム、ポスト量子暗号、レーダーなどの高い伝送効率と強力な誤り訂正を必要とするアプリケーションにおいて非常に望ましい。バイナリ体（特性2）におけるこのような符号の構成については大きな進展が見られる一方で、奇数特性の有限体における既知の微分均一性を持つべき関数を用いた非バイナリ巡回符号の構成については、比較的注目されてこなかった。本論文は、有利なパラメータ、具体的には次元 $k > (q^m - 1)/2$ および最小距離 $d > \sqrt{q^m - 1}$ をターゲットとした、$q$ 進巡回符号（$q$ は奇素数の冪）の無限族を構成するというギャップに対処するものである。

手法
著者らは、巡回符号を構成するためにトレース列アプローチを採用している。その手法は以下のステップを含む：

1. 列の定義： 与えられた有限体 $\mathbb{F}_{q^m}$ と原始元 $\alpha$ に対して、トレース関数を用いて数列 $s_\infty = (s_t)_{t \ge 0}$ を定義する：$s_t = \text{Tr}_{q^m}^q(F(\alpha^t + 1))$。ここで、$F(x)$ は $\mathbb{F}_{q^m}$ 上の選択されたべき関数である。
2. 生成多項式の決定： 巡回符号 $C_F$ は、数列 $s_\infty$ の最小多項式 $M_s(x)$ によって生成される。符号の次元は、数列の線形スパン（linear span $L_s$）によって決定され、これはトレース展開における非ゼロ係数の数に対応する。
3. べき関数の選択： 本論文では、奇数特性の有限体 $\mathbb{F}_{q^m}$ 上で既知の微分均一性を持つ単項式 $F(x) = x^d$ を選択する。選択基準は、$m$ のパリティおよび指数 $d$ の特定の構造に依存する。
4. 代数的解析：
   • 線形スパン： 著者らは、$q$ 進展開、リュカの定理、および巡回コセットの性質を利用して、トレース関数を展開し、非ゼロ項を特定する。これにより、線形スパン $L_s$ の正確な計算と生成多項式 $M_s(x)$ の構成が可能となる。
   • 最小距離の下界： 最小距離 $d$ の下界は、BCH限界およびHartmann-Tzeng限界を用いて確立される。これには、定義集合（生成多項式の根の集合）内における連続する整数または特定の集合の特定が含まれる。
   • 正確な距離： 特定のケースでは、既知の原始BCH符号に関連付けられた特定の重みを持つ明示的な符号語を構成することで、正確な最小距離を決定する。

主な貢献と結果
本論文は、次元が $v/2$ を超える長さ $v = q^m - 1$ の $q$ 進巡回符号のいくつかの無限族を提示している。構成された符号および結果は、使用されるべき関数によって以下のように分類される：

1. $x^{2 \cdot 3^{(m-1)/2} + 1}$ ($m$ が奇数) からの3進符号：

   • $\mathbb{F}_{3^m}$ 上で構成。
   • 線形スパンは $3m + N_3(m)$ であり、次元は $3^m - 1 - 3m - N_3(m)$ となる。
   • 最小距離 $d$ は $3 \le d \le 8$ を満たす。
   • 例：$m=5$ の場合、ほぼ最適である $[242, 226, 5]$ 符号が得られる。

2. $x^{p^{m/2} + 2}$ ($m$ が偶数、$p$ は奇数) からの $p$ 進符号：

   • $\mathbb{F}_{p^m}$ 上で構成。
   • 線形スパンは $p$ と $m$ に依存する（例：$p=3$ の場合は $N_p(m) + 5m/2$）。
   • 最小距離の下界が確立されている：$d \ge 3$ ($p=3$ の場合)、$d \ge 5$ ($p \ge 5, p \nmid m$ の場合)、および $d \ge 4$ ($p \ge 5, p \mid m$ の場合)。
   • 特定のケース（例：$p=5, p \nmid m$ の場合の $d=5$）について正確な距離が決定されている。

3. $x^{(q^{(m+1)/2} - 1)/(q-1)}$ ($m$ が奇数) からの符号：

   • この構成は、指数が幾何級数の和である特定のケースに対処している。
   • 著者らは、$N_p(k)$ 項の和を含む線形スパンの一般的な公式を導出している。
   • 意義： この構成は、Ding [35] によって提起された、指数 $t = (m+1)/2$（$m$ が奇数）における巡回符号の次元と生成多項式に関する オープン・プロブレム 5.31 を部分的に解決している。
   • $d$ の下界は、$q$ と $t$ に応じて 2 から $2^{t-2} + 2$ の範囲で提供される。

4. $x^{(3^{(m+1)/2} + 1)/2}$ ($m$ が奇数) からの3進符号：

   • $m$ に応じて完全非線形（PN）関数または4-均一関数となる単項式を利用している。
   • 線形スパンは $N_3(m) + (N_3(t+1) + \sum N_3(k)2^{t-k})m$ として計算される。
   • 最小距離の下界は、特定の可除条件の下で $d \ge 8$ と確立される。

5. $x^{p^h - 1}$ ($1 \le h \le \lceil m/2 \rceil$) からの $p$ 進符号：

   • 従来のバイナリの結果を奇数特性へと一般化している。
   • 線形スパンは、$p$ 進展開と特定の集合 $\hat{\Gamma}(t)$ を用いて導出される。
   • 最小距離の下界は、多くのケースにおいて符号長の平方根よりも大幅に優れていることが示されている（例：$d \ge p^h + 2$）。
   • $h \mid m$ の場合、この符号が設計距離 $p^h + 1$ を持つナローセンス原始BCH符号と等価であることを示すことで、正確な距離が決定されている。

6. $x^{2 \cdot p^{m/2} - 1}$ および $x^{p^{2h} - p^h + 1}$ からの符号：

   • これらのセクションは、特定の指数を用いて、$m$ が偶数の場合と奇数の場合を扱っている。
   • 著者らは、線形スパンと最小多項式の複雑な式を導出している。
   • 定理11および定理13は、これらの一族における最小距離の下界が、多くの場合、平方根の境界（$\sqrt{v}$）よりも著しく優れていることを示している。

意義および主張
本論文は、DingおよびZhou [14] によるバイナリの枠組みを非バイナリの設定へと拡張することを主張している。主な意義は以下の通りである：

• パラメータの改善： 構成された符号は、次元 $k > (q^m - 1)/2$ および最小距離 $d > \sqrt{q^m - 1}$ を達成し、符号率と誤り訂正能力を効果的にバランスさせている。
• オープン・プロブレムの解決： 本研究は、$m$ が奇数のときの $F(x) = x^{(3^{(m+1)/2}-1)/(3-1)}$ によって定義される3進巡回符号に関する、Ding [35] のオープン・プロブレム 5.31 を部分的に解決している。
• 最適性： 構成された符号（およびその双対）のいくつかは、最良既知線形符号のデータベース [47] と比較して、最適またはほぼ最適であると特定されている。
• 理論的進展： 本論文は、奇数特性の場の複雑さを扱うために、巡回コセット、$p$ 進展開、リュカの定理といった高度な数論的ツールを利用して、無限族の符号に対する線形スパンと生成多項式の明示的な公式を提供している。

著者らは、これらの構成が要求の厳しいアプリケーションに適した符号の豊かなソースを提供すると結論付けており、奇数特性の場におけるべき関数のさらなる探索が、より最適な一族を生み出す可能性があることを示唆している。また、これらの符号がCSS構成を通じて量子誤り訂正符号を構成するために使用できる可能性についても言及している。