Optimal binary codes from $\mathcal{C}_{D}$-codes over a non-chain ring

基本信息

• 论文ID: 2510.09057
• 标题: Optimal binary codes from $\mathcal{C}_{D}$-codes over a non-chain ring
• 作者: Ankit Yadav, Ritumoni Sarma, Anuj Kumar Bhagat (Indian Institute of Technology Delhi)
• 分类: cs.IT math.IT
• 发表时间: 2025年10月10日 (arXiv预印本)
• 论文链接: https://arxiv.org/abs/2510.09057v1

摘要

本文研究了在非链环 $\mathcal{R} := \mathbb{F}_2[x,y]/\langle x^2, y^2, xy-yx\rangle$ 上的 $\mathcal{C}_D$-码的子域码 $\mathcal{C}_{D}^{(2)}$，其中定义集合 $D$ 基于单纯复形构造。作者确定了各种 $D$ 对应的 $\mathcal{C}_D^{(2)}$ 的汉明重量分布和参数，识别出多个距离最优的无限码族，并提供了这些码为极小码和自正交码的充分条件。此外，还从构造的二重码中获得了两个强正则图族。

研究背景与动机

问题背景

1. 距离最优码的重要性: 对于固定的参数 $n$ 和 $k$，距离最优码实现了最大可能的错误检测和纠错能力，这是编码理论的主要目标之一。
2. 现有构造方法:
   • Gray映射：从有限环上的码构造有限域上的码
   • 单纯复形：Chang和Hyun首次引入用于构造最优线性码
3. 前期工作局限: Shi和Li在文献27中研究了环 $\mathcal{R}$ 上 $\mathcal{C}_D$-码的Lee重量分布及其Gray像，但未涉及子域码的研究。

研究动机

1. 参数改进: 证明二元子域码 $\mathcal{C}_D^{(2)}$ 相比文献27中的二元Gray像具有更好的参数
2. 理论完善: 为基于单纯复形的码族提供极小性和自正交性的理论条件
3. 应用拓展: 将二重码应用于强正则图的构造

核心贡献

1. 确定了子域码的汉明重量分布: 对于基于单纯复形构造的各种定义集合 $D$，完整刻画了 $\mathcal{C}_D^{(2)}$ 的重量分布
2. 构造了多个距离最优码族: 识别出若干无限的距离最优二元线性码族，部分达到Griesmer界
3. 建立了极小性和自正交性条件: 提供了 $\mathcal{C}_D^{(2)}$ 为极小码和自正交码的充分条件
4. 参数优势证明: 证明了子域码相比Gray像码具有更好的参数表现
5. 强正则图构造: 利用二重投影码构造了两个强正则图族

方法详解

任务定义

研究环 $\mathcal{R} = \mathbb{F}_2[x,y]/\langle x^2, y^2, xy-yx\rangle$ 上的线性码 $\mathcal{C}_D$，其中：

• 定义集合 $D$ 基于单纯复形构造
• 目标是分析其二元子域码 $\mathcal{C}_D^{(2)}$ 的性质

理论框架

1. 环结构与基

环 $\mathcal{R}$ 的每个元素可表示为 $a + bu + cv + duv$，其中 $a,b,c,d \in \mathbb{F}_2$，$u = x + \langle x^2, y^2\rangle$，$v = y + \langle x^2, y^2\rangle$。

选择 $\mathbb{F}_2$-基 $\mathcal{B} = \{b_1 = 1+u+v, b_2 = u+v, b_3 = u, b_4 = uv\}$。

2. 子域码构造

利用 $\mathbb{F}_2$-值迹映射 $\tau: \mathcal{R} \to \mathbb{F}_2$： $\tau(a + bu + cv + duv) = a + b + c + d$

定理 3.3: 若 $D = b_1D_1 + b_2D_2 + b_3D_3 + b_4D_4$，则 $\mathcal{C}_D^{(2)}$ 由矩阵生成： $G^{(2)} = \begin{pmatrix} G_1 + G_4 \\ G_3 \\ G_2 \\ G_1 \end{pmatrix}$

3. 重量计算公式

对于 $(x_1,x_2,x_3,x_4) \in (\mathbb{F}_2^m)^4$，有： $\text{wt}(c_D^{(2)}(x_1,x_2,x_3,x_4)) = \frac{|D|}{2} - \frac{1}{2}\sum_{d_1 \in D_1} (-1)^{(x_1+x_4)d_1} \sum_{d_2 \in D_2} (-1)^{x_3d_2} \sum_{d_3 \in D_3} (-1)^{x_2d_3} \sum_{d_4 \in D_4} (-1)^{x_1d_4}$

核心技术创新

1. 布尔函数技巧

定义布尔函数 $\psi(\cdot | Y): \mathbb{F}_2^m \to \mathbb{F}_2$： $\psi(x_1 | Y) = \prod_{i \in Y}(1-\alpha_i) = \begin{cases} 1, & \text{if } \text{Supp}(x_1) \cap Y = \emptyset \\ 0, & \text{if } \text{Supp}(x_1) \cap Y \neq \emptyset \end{cases}$

2. 单纯复形的应用

利用单纯复形 $\Delta_X$ 和其补集 $\Delta_X^c$ 的性质： $\sum_{t \in \Delta_Y} (-1)^{x_1 t} = 2^{|Y|}\psi(x_1 | Y)$$\sum_{t \in \Delta_Y^c} (-1)^{x_1 t} = 2^m\delta_{0,x_1} - 2^{|Y|}\psi(x_1 | Y)$

实验设置

理论验证

本文主要是理论工作，通过数学证明验证结果。作者使用MAGMA计算机代数系统验证了具体例子。

验证实例

例 4.8: $m=4$, $X=Y=Z=\emptyset$, $W=\{1,2,3\}$

• 得到参数为 $[120, 7, 60]$ 的二重最优二元线性码
• 重量枚举式：$x^{120} + 15x^{56}y^{64} + 112x^{60}y^{60}$
• 该码既极小又自正交，可构造量子纠错码 $[[120, 106, 3]]$

实验结果

主要理论结果

定理 4.2 给出了6种不同定义集合对应的码参数：

1. 一重码: $D = b_1\Delta_X + b_2\Delta_Y + b_3\Delta_Z + b_4\Delta_W$
   • 参数: $[2^{|X|+|Y|+|Z|+|W|}, |X|+|Y|+|Z|+|W|, 2^{|X|+|Y|+|Z|+|W|-1}]$
   • 距离最优条件: $|X|+|Y|+|Z|+|W| \geq 2$
2. 二重码: $D = b_1\Delta_X^c + b_2\Delta_Y + b_3\Delta_Z + b_4\Delta_W$（$|X| < m$）
   • 参数: $[(2^m-2^{|X|})2^{|Y|+|Z|+|W|}, m+|Y|+|Z|+|W|, (2^m-2^{|X|})2^{|Y|+|Z|+|W|-1}]$
   • 达到Griesmer界，距离最优
3. 四重码: $D = b_1\Delta_X^c + b_2\Delta_Y^c + b_3\Delta_Z + b_4\Delta_W$
   • 参数: $[(2^m-2^{|X|})(2^m-2^{|Y|})2^{|Z|+|W|}, 2m+|Z|+|W|, (2^m-2^{|X|}-2^{|Y|})2^{m+|Z|+|W|-1}]$
   • 距离最优条件: $2^{|X|+|Y|+|Z|+|W|} \leq m+|Z|+|W|+\min\{|X|,|Y|\}$

极小性和自正交性条件

定理 4.7 提供了充分条件：

• 自正交性: 当每个码字重量为4的倍数时（利用定理2.2）
• 极小性: 当 $\frac{\text{wt}_{\min}}{\text{wt}_{\max}} > \frac{1}{2}$ 时（利用引理2.3）

强正则图构造

定理 4.12和4.13 构造了两个强正则图族：

• 第一族参数: $(2^{m+|Y|+|Z|+|W|}, (2^m-2^{|X|})2^{|Y|+|Z|+|W|}, (2^m-2^{|X|+1})2^{|Y|+|Z|+|W|}, (2^m-2^{|X|})2^{|Y|+|Z|+|W|})$
• 第二族参数: $(2^{m+|Y|+|Z|+|W|}, 2^{|X|+|Y|+|Z|+|W|}-1, 2^{|X|+|Y|+|Z|+|W|}-2, 0)$

相关工作

历史发展

1. Gray映射方法: Hammons等人首次应用Gray映射构造最优非线性码
2. 单纯复形方法: Chang和Hyun引入单纯复形构造最优线性码
3. 环上码理论: 在各种有限环上构造码的研究

本文贡献定位

• 扩展了Shi和Li的工作，从Gray像转向子域码
• 提供了更系统的理论框架
• 证明了参数优势和最优性

结论与讨论

主要结论

1. 成功构造了多个距离最优的二元线性码族
2. 建立了极小性和自正交性的理论判据
3. 证明了子域码相比Gray像码的参数优势
4. 实现了从编码理论到图论的应用

局限性

1. 仅考虑了具有单个极大元素的单纯复形
2. 扩展到两个极大元素的复形计算过于复杂
3. 某些距离最优性条件较为严格

未来方向

1. 研究不同字母表上的 $\mathcal{C}_D$-码的子域码
2. 探索具有两个极大元素的单纯复形
3. 寻找更一般的距离最优性条件

深度评价

优点

1. 理论贡献显著: 系统地分析了子域码的重量分布，填补了理论空白
2. 方法创新性强: 巧妙结合了单纯复形、布尔函数和迹映射
3. 结果完整性好: 提供了完整的重量分布表和参数公式
4. 应用价值高: 构造的码可用于量子纠错码和强正则图

不足

1. 计算复杂度高: 对于复杂单纯复形，计算变得非常繁琐
2. 实用性验证不足: 缺乏大规模数值实验和实际应用测试
3. 推广性有限: 方法主要适用于特定的环结构

影响力

1. 学术价值: 为代数编码理论提供了新的研究方向
2. 实用价值: 构造的最优码在通信系统中有潜在应用
3. 可复现性: 理论结果完整，但需要较强的数学背景理解

适用场景

1. 需要高效错误纠正的通信系统
2. 量子信息处理中的量子纠错码
3. 组合数学中的强正则图构造
4. 密码学中的秘密共享方案

参考文献

论文引用了35篇相关文献，主要包括：

• 27 Shi, M. and Li, X. 的前期工作（本文直接扩展）
• 9 Chang, S. and Hyun, J.Y. 关于单纯复形的开创性工作
• 13 Hammons等人关于Gray映射的经典工作
• 12 Griesmer关于码长界的基础理论