New Constructions of Binary Cyclic Codes with Both Relatively Large Minimum Distance and Dual Distance

这是一份关于论文《New Constructions of Binary Cyclic Codes with Both Relatively Large Minimum Distance and Dual Distance》（具有较大最小距离和对偶距离的二元循环码新构造）的详细技术总结。

1. 研究背景与问题 (Problem)

核心问题：
二元循环码在理论和应用中具有重要地位。构造一个具有大最小距离 ($d$) 和 大对偶距离 ($d^\perp$) 的无限族二元循环码是一个长期存在的难题。

• 现有困境： 现有的研究表明，通常当循环码的最小距离 $d$ 增加时，其对偶码的最小距离 $d^\perp$ 会相应减小。
• 目标参数： 研究聚焦于长度 $n = 2^m - 1$，维数 $k$ 接近 $n/2$（即 $k \approx (n \pm 1)/2$）的码。
• 现有界限： 许多已知构造的最小距离下界受限于“平方根界限”（Square-root bound, $d \approx \sqrt{n}$），或者虽然 $d$ 很大但 $d^\perp$ 很小。
• 具体挑战： 除了 punctured Reed-Muller 码（穿孔 Reed-Muller 码）外，目前鲜有其他构造能在 $d \cdot d^\perp$ 的乘积上达到 $2n$ 的渐近界限。

2. 方法论 (Methodology)

论文通过精心构造定义集 (Defining Set) $Z$ 来生成循环码。定义集是 $\mathbb{Z}_n$ 的子集，由 2-分圆陪集（2-cyclotomic cosets）组成。利用 BCH 界（BCH bound）来推导最小距离 $d$ 和 $d^\perp$ 的下界。

主要技术工具包括：

1. 分圆陪集分析： 利用 $C_{i}^{(2,n)}$ 的性质，特别是当 $m$ 为合数（如 $m=p_1p_2$）时，陪集大小的分类讨论。
2. 布尔函数与旋转对称性： 在 $m$ 为偶数时，借鉴旋转对称布尔函数的构造思想，将向量空间 $\mathbb{F}_2^m$ 划分为具有特定汉明重量（Hamming weight）和对称性质的子集（如 $B, T, G$ 等）。
3. 集合划分与补集构造： 通过选择特定的子集 $S_1, S_2$ 作为定义集，确保定义集包含连续的整数区间（以满足 BCH 界），同时控制定义集的大小以维持维数 $k \approx n/2$。
4. 对偶距离分析： 利用定义集 $Z$ 的补集 $-(\mathbb{Z}_n \setminus Z)$ 来构造对偶码的定义集，并分析其包含的连续整数区间。

3. 主要贡献与结果 (Key Contributions & Results)

论文根据 $m$ 的奇偶性及因子分解情况，提出了三种主要的构造方案：

情形一：$m$ 为偶数 ($m$ is even)

• 构造方法： 将 $\mathbb{F}_2^m$ 中的向量按前一半和后一半是否相等（或互补）进行分类，构造集合 $B, T, G$ 以及辅助集合 $P_1, P_2$。
• 结果：
  • 构造了两族码，参数分别为 $[2^m-1, 2^{m-1} \pm 1, d]$。
  • 最小距离： $d \ge 2^{m/2} - 1$。
  • 对偶距离： $d^\perp \ge 2^{m/2}$。
  • 对比： 相比文献 [26] 中的构造，本文的 $d$ 和 $d^\perp$ 均有显著提升，且 $d \cdot d^\perp \approx n$。

情形二：$m$ 为两个不同素数的乘积 ($m = p_1 p_2$)

• 构造方法： 利用 $m=p_1p_2$ 时分圆陪集大小仅为 $p_1, p_2$ 或 $p_1p_2$ 的特性。通过选取特定大小的陪集构建定义集。
• 结果：
  • 构造了维数为 $k = (n+1)/2$ 的码。
  • 最小距离： $d$ 的下界远大于 $\frac{n}{\log_2 n}$，甚至超过了 $\sqrt{n}$ 的平方根界限。
  • 具体公式： 当 $p_2 > p_1 \ge 3$ 时，$d$ 的下界由多个取整函数项组成，数值巨大。
  • 对偶距离： $d^\perp \ge 2^{\lfloor \log_2(p_1p_2) \rfloor + 1}$。
  • 意义： 这是目前已知在 $k \approx n/2$ 时，最小距离下界最大的构造之一。

情形三：$m$ 为奇数 ($m$ is odd)

论文提出了两族新的构造，旨在打破 $d$ 增大则 $d^\perp$ 减小的传统权衡。

• 第一族 (Theorem 15)：

  • 参数： $[2^m-1, 2^{m-1}, d]$。
  • 距离： $d \ge 2^{(m+1)/2} - 1$，$d^\perp \ge 2^{(m+1)/2}$。
  • 对比： 性能优于或等于 punctured Reed-Muller 码，且 $d \cdot d^\perp \approx 2n$。

• 第二族 (Theorem 22)：

  • 参数： $[2^m-1, 2^{m-1}, d]$。
  • 距离： $d \ge 4 \cdot (2^{(m-1)/2} - 4) + 1$，$d^\perp \ge 2^{(m-1)/2}$。
  • 对比： 相比文献 [28] 的构造，在保持相同对偶距离 $d^\perp$ 的同时，显著提高了最小距离 $d$。
  • 乘积界限： 这两族码均实现了 $d \cdot d^\perp \approx 2n$ 的渐近界限。

4. 结果汇总与对比 (Summary of Results)

情形	$m$ 的性质	码长 $n$	维数 $k$	最小距离 $d$	对偶距离 $d^\perp$	$d \cdot d^\perp$ 渐近值
偶数	$m$ 为偶数	$2^m-1$	$2^{m-1} \pm 1$	$\ge 2^{m/2}-1$	$\ge 2^{m/2}$	$\approx n$
合数	$m=p_1p_2$	$2^m-1$	$(n+1)/2$	$> n/\log_2 n$	$\ge 2^{\lfloor \log_2 m \rfloor + 1}$	$\approx n$
奇数	$m$ 为奇数	$2^m-1$	$2^{m-1}$	$\ge 2^{(m+1)/2}-1$	$\ge 2^{(m+1)/2}$	$\approx 2n$
奇数	$m$ 为奇数	$2^m-1$	$2^{m-1}$	$\ge 4(2^{(m-1)/2}-4)+1$	$\ge 2^{(m-1)/2}$	$\approx 2n$

注：Punctured Reed-Muller 码的 $d \cdot d^\perp \approx 2n$，本文在 $m$ 为奇数时的构造达到了这一界限，且在某些情况下 $d$ 更大。

5. 意义与展望 (Significance & Future Work)

学术意义：

1. 突破权衡关系： 本文成功构造了多族二元循环码，在保持 $d$ 和 $d^\perp$ 都较大的同时，打破了以往“增大 $d$ 必减小 $d^\perp$"的直观印象。
2. 提升下界： 在 $m=p_1p_2$ 的情况下，最小距离下界远超平方根界限和 $n/\log_2 n$ 界限。
3. 逼近理论极限： 对于 $k \approx n/2$ 的码，本文构造的 $d \cdot d^\perp \approx 2n$ 是目前已知最好的结果之一（除 punctured Reed-Muller 码外）。

开放问题 (Open Problem)：
论文最后提出了一个重要的开放问题：
定义 $\Delta = \limsup_{n \to \infty} \frac{d \cdot d^\perp}{n}$。

• 已知 punctured Reed-Muller 码和本文构造表明 $\Delta \ge 2$。
• 问题： 是否存在无限族二元循环码使得 $\Delta > 2$？即能否构造出 $d \cdot d^\perp$ 的渐近下界超过 $2n$ 的码？
• 确定 $\Delta$ 的确切值。

总结：
该论文通过创新的定义集构造方法，在二元循环码的参数优化上取得了重要进展，特别是在平衡最小距离与对偶距离方面，为编码理论提供了新的构造思路和更优的参数实例。