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

技术摘要：基于奇特征有限域上幂函数的具有大最小距离的循环码构造

问题陈述
维度超过半码长（$k > v/2$）且最小距离大于码长平方根（$d > \sqrt{v}$）的循环码在需要高传输效率和强纠错能力的应用中（如通信系统、后量子密码学和雷达）是非常理想的。虽然在二进制域（特征为 2）上构建此类码已取得了显著进展，但利用奇特征有限域上具有已知微分均匀性的幂函数来构造非二进制循环码的研究相对较少。本文旨在解决构造无限族 $q$-ary 循环码（其中 $q$ 是奇素数的幂）以实现优良参数的空白，特别是针对目标维度 $k > (q^m - 1)/2$ 和最小距离 $d > \sqrt{q^m - 1}$ 的构造。

方法论
作者采用迹序列法来构造循环码。该方法包括以下步骤：

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)$ 生成。码的维度由序列的线性跨度（$L_s$）决定，该跨度对应于迹展开中非零系数的数量。
3. 幂函数选择： 本文选择了在 $\mathbb{F}_{q^m}$（$q$ 为奇数）上具有已知微分均匀性的特定单项式 $F(x) = x^d$。选择标准取决于 $m$ 的奇偶性以及指数 $d$ 的特定结构。
4. 代数分析：
   • 线性跨度： 作者利用 $q$-进展开、卢卡斯定理（Lucas' Theorem）以及循环陪集的性质来展开迹函数并识别非零项。这使得能够精确计算线性跨度 $L_s$ 并构造生成多项式 $M_s(x)$。
   • 最小距离界限： 使用 BCH 界和 Hartmann-Tzeng 界来建立最小距离 $d$ 的下界。这涉及在生成集的定义集中识别连续整数或特定集合（即生成多项式的根）。
   • 精确距离： 对于特定情况，作者构造了具有特定权重的显式码字以确定精确的最小距离，通常将构造的码与已知的原始 BCH 码联系起来。

主要贡献与结果
本文提出了若干个长度为 $v = q^m - 1$、维度超过 $v/2$ 的 $q$-ary 循环码无限族。具体的构造与结果根据所使用的幂函数进行分类：

1. 基于 $x^{2 \cdot 3^{(m-1)/2} + 1}$ ($m$ 为奇数) 的三进制码：

   • 构造于 $\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$-ary 码：

   • 构造于 $\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] 提出的关于 $m$ 为奇数时 $t = (m+1)/2$ 的循环码的维度和生成多项式的开放问题 5.31。
   • 提供了 $d$ 的下界，其范围根据 $q$ 和 $t$ 的不同，从 2 到 $2^{t-2} + 2$ 不等。

4. 基于 $x^{(3^{(m+1)/2} + 1)/2}$ ($m$ 为奇数) 的三进制码：

   • 利用了一个取决于 $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$-ary 码：

   • 将之前的二进制结果推广到奇特征情形。
   • 利用 $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}$，有效地平衡了码率和纠错能力。
• 解决开放问题： 本研究部分解决了 Ding [35] 关于 $m$ 为奇数时由 $F(x) = x^{(3^{(m+1)/2}-1)/(3-1)}$ 定义的三进制循环码的开放问题 5.31。
• 最优性： 所构造的若干码（及其对偶码）在与已知最佳线性码数据库 [47] 对比时，被鉴定为最优或接近最优。
• 理论进展： 本文利用高级数论工具（循环陪集、$p$-进展开、卢卡斯定理）为无限族循环码提供了显式的线性跨度和生成多项式公式，从而处理了奇特征域的复杂性。

作者总结道，这些构造为满足严苛应用需求的码提供了丰富的来源，并建议进一步探索奇特征域上的幂函数可能会产生更优的码族。他们还指出，这些码具有通过 CSS 构造来构建量子纠错码的潜力。