Two Families of Linear Codes Containing Non-GRS MDS Codes

这是一份关于论文《Two Families of Linear Codes Containing Non-GRS MDS Codes》（包含非 GRS MDS 码的两类线性码）的详细技术总结。

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

• 背景：最大距离可分（MDS）码在分布式存储、组合设计、有限几何及密码学等领域具有重要应用。广义 Reed-Solomon (GRS) 码是 MDS 码中最著名且研究最充分的一类。
• 核心问题：
  1. 非 GRS MDS 码的构造与分类：虽然已知许多 GRS 码，但寻找和构造非 GRS（即不与 GRS 码等价）的 MDS 码对于理论分类（有限射影空间中的弧）和实际应用（如抵抗 Sidelnikov-Shestakov 和 Wieschebrink 攻击）至关重要。
  2. 自正交与自对偶性：在经典编码和量子编码理论中，构造具有自正交（Self-orthogonal）或自对偶（Self-dual）性质的 MDS 码是一个重要课题。
  3. 现有方法的局限：现有的非 GRS MDS 码构造方法（如扭曲 Reed-Solomon 码、删除 GRS 生成矩阵的行等）虽然有效，但需要探索更多样化的构造家族，以丰富 MDS 码的分类并扩大其参数范围。

2. 方法论 (Methodology)

作者通过修改广义 Reed-Solomon (GRS) 码的生成矩阵来构造两类新的线性码家族。主要技术工具包括：

• 生成矩阵的构造：
  • 第一类码 ($C_{i,j}$)：从 $RS(n, k+2, \Lambda)$ 的生成矩阵中删除第 $i+1$ 行和第 $j+1$ 行（其中 $1 \le i < j \le k$），得到 $k \times n$ 的生成矩阵 $G_{i,j}(\Lambda)$。
  • 第二类码 ($C_{h,k}$)：构造一个特殊的生成矩阵 $G_{h,k}$，包含从 $0$到$k-2$的幂次行，以及一个高次幂$h$的行（其中$h = k-1+r$）。
• 校验矩阵的推导：利用初等对称函数 ($\sigma_t$) 和完全对称函数 ($S_t$) 的性质，结合 Cramer 法则和范德蒙德矩阵行列式的性质，显式推导了两类码的校验矩阵。
• MDS 性质的判定：
  • 利用 Lemma 2.2：码是 MDS 当且仅当其生成矩阵的所有 $k \times k$ 子矩阵非奇异。
  • 利用 Proposition 3.4 和 Theorem 4.2：将子矩阵行列式的非零条件转化为初等对称函数或完全对称函数的非零条件。
• 非 GRS 性质的判定：
  • 采用 Schur 积（Hadamard 积）方法（基于 Lemma 2.1）。
  • 原理：若一个 $[n, k]$ MDS 码是 GRS 码且 $k \le (n-1)/2$，则其 Schur 平方 $C \star C$ 的维数应为 $2k-1$。如果计算出的 $\dim(C \star C) \ge 2k$，则该码是非 GRS 的。
• 自正交/自对偶性分析：
  • 通过引入缩放向量 $v$，构造等价码 $C_{i,j,v}$ 和 $C_{h,v}$。
  • 利用 $G G^T = 0$ 的条件，将其转化为关于多项式 $f(x)$ 的方程组，结合对称函数 $S_t$ 的性质，给出了自正交和自对偶的充要条件。

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

A. 第一类码家族 ($C_{i,j}$)

• 构造：通过删除 GRS 生成矩阵中的两行得到。
• MDS 条件：给出了码 $C_{i,j}$ 为 MDS 的充要条件，涉及初等对称函数 $\sigma_t$ 的特定组合不为零（Theorem 3.5）。
• 非 GRS 性质：
  • 证明了在特定参数范围（如 $k=3, 4$ 或 $5 \le k \le (n-4)/2$）下，$C_{i,j}$ 是非 GRS MDS 码（Theorem 3.7, Proposition 3.6）。
  • 利用 Schur 平方维数分析，确认了这些码的 Schur 平方维数 $\ge 2k$。
• 显式构造：利用有限域上的多项式根构造了长度可达 $(q/p)^{1/4}$ 的非 GRS MDS 码（Theorem 3.8）。
• 自正交/自对偶：
  • 给出了 $C_{i,j,v}$ 为自正交的充要条件：存在多项式 $f(x)$ 使得 $v_m^2 = u_m f(\alpha_m)$，并满足特定的对称函数约束（Theorem 3.10, 3.11）。
  • 证明了当 $n=2k$ 时，特定子家族可以构造出自对偶码（Corollary 3.13），并给出了具体实例。

B. 第二类码家族 ($C_{h,k}$)

• 构造：生成矩阵包含低次幂行和一个高次幂行 $h$。
• MDS 条件：码 $C_{h,k}$ 为 MDS 的充要条件是对于 $\Lambda$ 的任意 $k$ 元子集，其完全对称函数 $S_{h-k+1}$ 不为零（Theorem 4.2）。
• 非 GRS 性质：
  • 证明了在多种参数设置下（$h=k$, $h=k+r$ 等），$C_{h,k}$ 均为非 GRS MDS 码（Theorem 4.4, 4.5）。
  • 指出这类码的 Schur 平方维数可能达到 $2k+1$ 或更高，表明它们与之前文献（如 [25, 23]）中的非 GRS 码不等价。
• 显式构造：构造了长度可达 $(q/p)^{1/2}$ 的非 GRS MDS 码（Theorem 4.6），以及长度为 $q+2$（当 $q$ 为偶数时）的码。
• 自正交/自对偶：
  • 推导了 $C_{h,v}$ 为自正交的充要条件，涉及多项式系数与对称函数 $S_t$ 的线性关系（Theorem 4.7, 4.8）。
  • 给出了自对偶码存在的条件：当 $q$ 为偶数且 $r=1, S_1=0$ 时，存在自对偶码（Corollary 4.10, 4.11）。

C. 具体实例

论文提供了多个具体的数值例子（Example 1-9），在有限域 $\mathbb{F}_{17}, \mathbb{F}_{23}, \mathbb{F}_{25}, \mathbb{F}_{37}$ 等上展示了非 GRS MDS 码、自正交码和自对偶码的生成矩阵构造。

4. 意义与影响 (Significance)

1. 理论分类的丰富：该研究扩展了有限射影空间中弧（Arcs）的分类，提供了新的非 GRS MDS 码家族，证明了这些码在结构上不同于已知的扭曲 Reed-Solomon (TRS) 码或广义扭曲码。
2. 密码学安全性：由于非 GRS MDS 码对基于 GRS 码结构的攻击（如 Sidelnikov-Shestakov 攻击）具有抵抗力，新构造的码家族为设计更安全的密码系统（如基于编码的公钥密码体制）提供了新的候选方案。
3. 量子编码应用：通过构造自正交和自对偶的 MDS/NMDS 码，为构建量子纠错码（如 CSS 码）提供了新的资源。
4. 构造方法的创新：通过系统性地删除 GRS 生成矩阵的行并引入高次幂行，结合对称函数理论，提供了一套通用的构造框架，能够生成具有不同长度和维数的非 GRS MDS 码。
5. 未来方向：论文指出，将此类构造推广到删除任意数量行（即更一般的 $C_I$ 码）是一个极具挑战性但重要的研究方向，尽管其 MDS 条件的显式化非常困难。

总结

这篇文章通过修改 GRS 码的生成矩阵，成功构造了两类新的线性码家族。作者不仅给出了这些码成为 MDS 码的精确充要条件，还利用 Schur 积方法严格证明了其非 GRS 性质。此外，文章深入探讨了这些码的自正交和自对偶性质，并给出了具体的构造实例。这项工作显著丰富了非 GRS MDS 码的理论库，并在密码学和量子编码领域具有潜在的应用价值。