🔢 mathematics

A Generic Construction of $q$ -ary Near-MDS Codes Supporting 2-Designs with Lengths Beyond $q+1$

本文提出了首个支持 2-设计且长度超过 $q+1$ 的 $q$ 元近 MDS 码的通用构造方法，通过建立椭圆曲线码、有限阿贝尔群、子集和与组合设计之间的新联系，构建了包含无限族及其重量分布的此类码。

原作者： Hengfeng Liu, Chunming Tang, Zhengchun Zhou, Dongchun Han, Hao Chen

发布于 2026-04-07

📖 1 分钟阅读🧠 深度阅读

原作者： Hengfeng Liu, Chunming Tang, Zhengchun Zhou, Dongchun Han, Hao Chen

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个关于**“如何制造更完美的数字密码锁”的故事，同时意外地发现了一种“极其精妙的排列组合游戏”**。

为了让你轻松理解，我们把这篇充满数学符号的论文拆解成几个生活化的场景：

1. 背景：什么是“密码锁”和“完美锁”？

想象一下，你正在设计一种数字密码锁（在数学上叫“线性码”）。

MDS 锁（最大距离可分码）： 这是最完美的锁。它的规则是：只要密码里错了一个数字，系统就能立刻发现并纠正。这种锁非常坚固，但有一个死板的限制：它的长度（数字位数）不能超过某个特定的数（ $q+1$ ）。就像你只能造出长度不超过 10 位的完美锁，再多一位就不行了。
NMDS 锁（近 MDS 码）： 这是一种“几乎完美”的锁。它稍微放宽了一点要求，允许在极端情况下稍微“不完美”一点点，但依然非常强壮。
- 关键点： 这种“近完美”的锁，理论上可以造得比 MDS 锁更长（超过 $q+1$ 位）。
- 难题： 虽然理论上可以造很长的 NMDS 锁，但过去几十年里，大家只能造出很短的（长度 $\le q+1$ ），或者只有一些零星的、特例的（比如只有 2 进制或 3 进制的特殊情况）。大家一直找不到一种通用的方法，能造出既长、又完美、还能支持某种特殊结构的 NMDS 锁。

2. 什么是"2-设计”？（那个特殊的排列游戏）

论文里提到的"2-设计”（2-design），听起来很抽象，其实可以想象成**“完美的扑克牌局”或“公平的抽奖系统”**。

场景： 假设你有一大堆扑克牌（点），你要把它们分成很多手牌（块）。
规则： 无论你怎么选 2 张牌，它们同时出现在同一手牌里的次数，必须是完全一样的（比如每次都恰好出现 $\lambda$ 次）。
意义： 这种结构在密码学、实验设计和通信中非常有用，因为它保证了绝对的公平性和随机性。

之前的困境： 以前大家发现，那些短的 NMDS 锁（长度 $\le q+1$ ）有时候能产生这种完美的扑克牌局，但那些能造得很长（超过 $q+1$ ）的 NMDS 锁，几乎没人知道它们能不能产生这种完美的扑克牌局。

3. 本文的突破：用“椭圆曲线”和“子集求和”搭桥

作者们（刘恒峰、唐春明等）想出了一个绝妙的办法，把三个看似不相关的领域连在了一起：

椭圆曲线（Elliptic Curves）： 想象这是一条画在有限网格上的特殊曲线，上面有很多个“点”。这些点可以像数字一样相加（比如点 A + 点 B = 点 C）。
子集求和（Subset Sums）： 想象你从这些点里挑出几个，把它们加起来，看能不能凑成某个特定的目标（比如凑成“零”）。
密码锁（NMDS 码）： 作者发现，如果你能巧妙地挑选这些点，使得它们“凑不出”某些特定的和，你就能造出一个完美的长密码锁。

核心比喻：
想象你在玩一个**“找零钱”**的游戏。

以前大家只能玩小面额的（短锁）。
作者们发现，如果利用椭圆曲线上点的特殊排列（就像把硬币按某种神秘规律摆放），并且利用子集求和的数学规律，就能造出超长面额的硬币（长锁）。
更神奇的是，这种特殊的排列方式，天然地就符合“完美扑克牌局”（2-设计）的规则。

4. 他们具体做了什么？

作者们提出了一种通用的“配方”（Generic Construction）：

选材： 选一条特殊的椭圆曲线，确保它上面的点能组成一个特定的数学结构（比如 $Z_p \oplus Z_p$ ，就像两个互相垂直的网格）。
调味： 利用“子集求和”的数学定理，证明只要满足特定条件（比如 $p$ 整除 $k$ ），这些点就能完美地组成"2-设计”。
成品： 造出了一系列长度超过 $q+1$ 的 NMDS 密码锁。
- 以前大家以为超过 $q+1$ 的长锁很难同时满足“完美扑克牌局”的条件。
- 现在，作者们不仅造出来了，还给出了无限多种造法（只要 $q$ 和 $p$ 满足一定条件）。

5. 这个发现有什么用？

打破纪录： 这是人类第一次系统地造出长度超过 $q+1$ 且能支持2-设计的 NMDS 码。就像以前只能造出 10 层楼高的完美大厦，现在能造出 20 层、50 层甚至更高的了。
新工具： 他们发现这些长锁虽然不符合最经典的“阿夫穆斯 - 马特森定理”（一个老牌的判断标准），但符合一个**“广义版”**的新标准。这就像发现了一种新的建筑材料，虽然不符合旧的建筑规范，但在新规范下是坚固且合法的。
应用前景： 这些新的密码锁和排列组合结构，未来可能用于更安全的通信系统、更高效的实验设计，或者更复杂的加密算法。

总结

简单来说，这篇论文就像是一位**“乐高大师”**：

以前大家只能用有限的积木块（短长度）拼出完美的对称图案（2-设计）。
大师发现了一种新的拼接技巧（利用椭圆曲线和子集求和），不仅能用更多的积木块（长长度）拼出图案，而且拼出来的图案比以前的更复杂、更精妙。
最重要的是，他提供了一套通用的说明书，让任何人都可以按照这个步骤，造出无数种这样的“超长完美密码锁”。

这项研究填补了数学界的一个长期空白，证明了在“长距离”的领域里，依然存在着完美的秩序。

这是一份关于论文《A Generic Construction of q-ary Near-MDS Codes Supporting 2-Designs with Lengths Beyond q + 1》（支持长度超过 $q+1$ 的 $q$ 元近 MDS 码及其 2-设计的一般构造）的详细技术总结。

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

背景：
- MDS 码与 NMDS 码：最大距离可分（MDS）码的参数为 $[n, k, n-k+1]$ ，几乎最大距离可分（AMDS）码为 $[n, k, n-k]$ 。如果一个码及其对偶码都是 AMDS，则称为近 MDS（NMDS）码。
- 设计与码的关系：线性码与组合设计（ $t$ -designs）之间有密切联系。许多 $t$ -设计可以从线性码中导出。
- 现有局限：虽然已知存在长度超过 $q+1$ 的 NMDS 码，但同时支持 2-设计且长度超过 $q+1$ 的 $q$ 元 NMDS 码极其罕见。现有的已知例子仅限于少量的二元和三元特例（如扩展 Golay 码及其对偶码），且大多长度不超过 $q+1$ 。
核心问题：
- 如何构造通用的（generic） $q$ 元 NMDS 码，使其长度 $n > q+1$ ，并且能够支持 2-设计（2-designs）？
- 如何确定这些码的重量分布（weight distribution）？

2. 方法论 (Methodology)

本文提出了一种基于椭圆曲线码（Elliptic Curve Codes）、有限阿贝尔群和**子集和（Subset Sums）**理论的一般构造方法。

椭圆曲线码与 NMDS 性质的联系：
- 利用代数几何码（AG 码）中的椭圆曲线码。设 $E$ 为有限域 $\mathbb{F}_q$ 上的椭圆曲线， $P = \{P_1, \dots, P_n\}$ 为 $E(\mathbb{F}_q)$ 的子集。
- 通过有理除子 $D$ 定义码 $C(E, P, D)$ 。
- 关键判据（Proposition 4）：该码是 NMDS 码（即最小距离 $d = n-k$ ）当且仅当在群 $E(\mathbb{F}_q)$ 中，集合 $P$ 的 $k$ -子集和等于除子 $D$ 的“和点” $Q_D$ 的计数 $N(P, k, Q_D) > 0$ 。
子集和与设计的联系：
- 将码的最小重量码字的支撑集（support）与有限阿贝尔群 $E(\mathbb{F}_q)$ 中的子集和结构联系起来。
- 利用已知关于有限阿贝尔群中子集和构成 $t$ -设计的条件（Theorem 10, 11, 13）。
- 特别是，当 $E(\mathbb{F}_q) \cong \mathbb{Z}_p \oplus \mathbb{Z}_p$ （ $p$ 为奇素数）时，子集和结构可以生成 2-设计。
构造策略：
1. 选择满足特定条件的椭圆曲线 $E/\mathbb{F}_q$ ，使其有理点群结构为 $E(\mathbb{F}_q) \cong \mathbb{Z}_p \oplus \mathbb{Z}_p$ 。
2. 构造一个特殊的 $\mathbb{F}_q$ -有理除子 $D$ ，使得其对应的和点 $Q_D = \infty$ （零元）。这通过选取 $Q \in E(\mathbb{F}_{q^2}) \setminus E(\mathbb{F}_q)$ 使得 $Q \oplus \phi(Q) = \infty$ 来实现（Lemma 3）。
3. 利用广义 Assmus-Mattson 定理（Generalized Assmus-Mattson Theorem）证明构造出的码支持 2-设计。

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

A. 通用构造 (Theorem 14)

论文给出了第一个支持 2-设计且长度 $n > q+1$ 的 $q$ 元 NMDS 码的通用构造：

参数条件：设 $q$ 为素数幂， $p$ 为奇素数，满足 $\gcd(p^2-q-1, q)=1$ ， $-2\sqrt{q} \le p^2-q-1 \le 2\sqrt{q}$ ，且 $p \mid (q-1)$ 。
码参数：存在参数为 $[p^2, 2k, p^2-2k]$ 的 NMDS 码，其中 $p \mid k$ 且 $0 < k < p^2/2$ 。
设计性质：
- 该码的最小重量码字支撑集构成一个 2- $(p^2, p^2-2k, \lambda)$ 设计。
- 其对偶码（参数 $[p^2, p^2-2k, 2k]$ ）的最小重量码字也构成一个 2- $(p^2, 2k, \lambda^\perp)$ 设计。
- 长度突破：码长 $n = p^2$ 。由于 $p^2 \approx q + 2\sqrt{q} + 1$ （根据 Hasse-Weil 界），这些码的长度显著超过了经典的 $q+1$ 界限。
理论突破：这些码满足广义 Assmus-Mattson 定理，但不满足经典的 Assmus-Mattson 定理，扩展了设计构造的理论边界。

B. 重量分布 (Theorem 15)

论文推导了构造出的 NMDS 码及其对偶码的完整重量分布公式。
利用有限阿贝尔群上的子集和计数公式（Theorem 8），给出了最小重量码字数量 $A_{p^2-2k}$ 的显式表达式，并由此递推得到所有重量分布。
证明了对于构造中的码，所有重量 $w$ （从最小距离到 $n$ ）的码字数量均大于 0。

C. 具体实例与参数表

Example 1：给出了 $q=7, p=3$ 的具体构造，生成了 $[9, 6, 3]$ 码，其最小重量支撑集构成 Steiner 三元系 $S(2, 3, 9)$ 。
Table III & IV：列出了大量满足条件的 $(q, p)$ 参数对及对应的码参数。在 $p < 2000$ 范围内找到了 38 组参数，表明存在无限族（猜想）满足条件的码。

4. 意义与影响 (Significance)

突破长度限制：首次提供了长度超过 $q+1$ 且支持 2-设计的 $q$ 元 NMDS 码的通用构造。此前该领域仅有个别的二元/三元特例。
连接多个领域：成功建立了椭圆曲线码、有限阿贝尔群子集和与组合设计之间的深刻联系，展示了代数几何工具在构造组合设计中的强大能力。
丰富设计理论：构造出的 2-设计属于新的组合设计族，且这些设计无法通过经典的 Assmus-Mattson 定理获得，必须依赖广义版本，丰富了 $t$ -设计的构造理论。
应用潜力：NMDS 码在密码学、有限几何和组合设计中具有重要应用。该构造为设计具有特定参数（特别是长码长）的纠错码和保密方案提供了新的资源。
未来方向：论文指出，利用不同有理点群结构的椭圆曲线可能构造出支持更高阶 $t$ -设计（ $t > 2$ ）的码，这为后续研究指明了方向。

总结

该论文通过巧妙利用椭圆曲线的有理点群结构（特别是 $\mathbb{Z}_p \oplus \mathbb{Z}_p$ 结构）和子集和理论，解决了长期存在的“构造长长度 NMDS 码以支持 2-设计”的难题。其提出的通用构造方法不仅打破了 $q+1$ 的长度壁垒，还给出了精确的重量分布，为编码理论和组合设计领域做出了重要贡献。