2025-11-10T03:13:59.288121

Quasi perfect codes in the cartesian product of some graphs

Mane, Shinde

An important question in the study of quasi-perfect codes is whether such codes can be constructed for all possible lengths $n$. In this paper, we address this question for specific values of $n$. First, we investigate the existence of quasi-perfect codes in the Cartesian product of a graph $G$ and a path (or cycle), assuming that $G$ admits a perfect code. Second, we explore quasi-perfect codes in the Cartesian products of two or three cycles, $C_m\square C_n$ and $C_m\square C_n\square C_l$, as well as in the Cartesian products of two or three paths, $P_m\square P_n$ and $P_m\square P_n\square P_l$.

academic

Quasi perfect codes in the cartesian product of some graphs

基本信息

论文ID: 2510.13613
标题: Quasi perfect codes in the cartesian product of some graphs
作者: S. A. Mane, N. V. Shinde
分类: math.CO (组合数学)
发表时间: 2025年10月15日
论文链接: https://arxiv.org/abs/2510.13613

摘要

准完美码研究中的一个重要问题是能否为所有可能的长度n构造此类码。本文针对特定的n值探讨了这一问题。首先，在图G承认完美码的前提下，研究了图G与路径（或环）的笛卡尔积中准完美码的存在性。其次，探索了两个或三个环的笛卡尔积 $C_m\square C_n$ 和 $C_m\square C_n\square C_l$ 中的准完美码，以及两个或三个路径的笛卡尔积 $P_m\square P_n$ 和 $P_m\square P_n\square P_l$ 中的准完美码。

研究背景与动机

要解决的问题: 本研究旨在解决准完美码构造的存在性问题，特别是在图的笛卡尔积中构造准完美码的系统性方法。
问题的重要性:
- 完美码在纠错码理论中扮演核心角色，但相对稀少
- Golomb-Welch猜想断言不存在长度n≥3且e>1的完美Lee e纠错码
- 准完美码作为完美码的近似替代，具有重要的理论和应用价值
现有方法的局限性:
- 准完美码的存在条件仍然相当严格
- 覆盖半径大于3的准完美码已知的很少
- 缺乏系统性的构造方法
研究动机: 基于图G中的完美码，开发在G与特定图的笛卡尔积中构造准完美码的技术。

核心贡献

提出了基于完美码构造准完美码的系统性方法: 如果图G承认完美e纠错码，则可以在G□Pn或G□Cn中构造准完美e纠错码
构造了多种具体的准完美码:
- 在Pm□Pn□P6k-2和Cm□Cn□C6k中的准完美2纠错码
- 在P4□P4□P4中基于P2□P2□P2中完美码的准完美码
扩展了已知结果: 在Cn□Cn□Cl (3≤n≤19)中构造准完美码，利用Cn□Cn中的已知准完美码
提供了完整的理论框架: 系统性地分析了路径和环的笛卡尔积中准完美码的构造方法

e=1时: 可在G□P3k和G□C3k中构造准完美1纠错码
e≥2时: 可在G□P3和G□C3中构造准完美e纠错码

构造方法:

D' = D ⊕ {1}

其中⊕表示集合的直积。

2. 三维扩展构造（定理3.2）

对于Pm□Pn中的完美2纠错码D1，构造Pm□Pn□P6k-2中的准完美2纠错码：

步骤:

定义D2 = (0,3) + D1（平移码）
构造D = (D1⊕{0}) ∪ (D2⊕{3})
扩展到更大维度：C = ⋃(i=0 to k-1)(D1⊕{6i} ∪ D2⊕{6i+3})

3. 环积构造

定理3.6: 在C3□C6□C4k中构造准完美1纠错码

D0 = {(0,0), (1,2), (2,4)}
D1 = {(2,1), (0,3), (1,5)}
C = ⋃(i=0 to k-1)(D0⊕{4i} ∪ D1⊕{4i+2})

技术创新点

分层构造策略: 将高维图分解为低维层，在每层中应用已知的完美码
平移技术: 通过适当的平移操作确保不同层间的码字保持最小距离
周期性扩展: 利用基本构造块的周期重复实现任意大小的构造

实验设置

验证方法

本文主要通过理论证明验证构造的正确性，辅以计算机搜索验证特定情况：

理论验证: 证明构造码的最小距离和覆盖半径
计算机验证: 对于复杂情况（如定理4.4中的某些参数），使用计算机搜索验证

评价指标

最小距离: 任意两个码字间的最小距离
覆盖半径: 任意顶点到最近码字的最大距离
准完美性: 验证覆盖半径 = 纠错能力 + 1

实验结果

主要结果

定理3.1的结果:
- e=1时，在G□P3k和G□C3k中成功构造准完美1纠错码
- e≥2时，在G□P3和G□C3中成功构造准完美e纠错码
三维构造结果:
- 在Pm□Pn□P6k-2中构造准完美2纠错码（定理3.2）
- 在Cm□Cn□C6k中构造准完美2纠错码（推论3.3）
具体实例:
- C6□C6□C2中的完美1纠错码（定理4.2）
- C3□C6□C4k中的准完美1纠错码（定理3.6）

构造汇总表

基础图	目标图（笛卡尔积）	码性质/描述
G（有完美e纠错码）	G□Pn, G□Cn	准完美e纠错码
Pm□Pn, Cm□Cn	Pm□Pn□P6k-2, Cm□Cn□C6k	准完美2纠错码
Cn□Cn	Cn□Cn□Cl	3≤n≤19的准完美码