基于二次数域、部分差集与差集构造具有一维壳（Hull）的线性码
本文旨在为研究编码理论与代数的学者介绍Li Chengju与Zeng Peng于2019年在《IEEE Transactions on Information Theory》第65卷第3期上发表的一项研究，题目为“具有一维壳的线性码的构造”。
本项研究由来自华东师范大学可信计算上海市重点实验室的Chengju Li（同时隶属于北京的中国科学院密码科学技术国家重点实验室）和Peng Zeng共同完成。论文于2018年8月在线发表，并于2019年2月发布了最终版本。该研究发表在信息论领域的顶级期刊 IEEE Transactions on Information Theory 上，得到了包括国家自然科学基金、上海市启明星计划等多个中国国家级与省部级科研项目的资助。
该研究隶属于编码理论这一数学与计算机科学的交叉领域，核心关注点是线性码（Linear Codes），特别是其壳（Hull） 的性质与构造。
1. 核心概念与背景知识： * 线性码与对偶码： 一个参数为[n, k, d]的线性码C是有限域GF(q)上维度为k的子空间。其对偶码C⊥定义为与C中所有码字正交（在标准内积下）的向量集合。 * 码的壳（Hull）： 定义为线性码与其对偶码的交集，即 Hull© = C ∩ C⊥。壳本身也是一个线性子空间。根据壳的维度ℓ，可以定义几类重要的码： * 当ℓ = 0时，称为LCD码（线性互补对偶码）。这类码因其在密码学（如防范侧信道攻击）和编码理论中的优良性质而被广泛研究。 * 当ℓ = k时，码C是自正交的；若进一步有ℓ = n/2，则C是自对偶码。 * 研究动机： 壳的概念最初由Assmus和Key于1990年引入，用于分类有限投影平面。后续研究发现，壳的维度大小直接影响两个关键算法的计算复杂度：（1）判定两个线性码是否置换等价；（2）计算线性码的自同构群。一般而言，壳的维度越小，这些算法的效率越高。Sendrier的工作表明，随机线性码的期望壳维度在n和k趋于无穷时是一个常数。因此，从算法效率的角度，构造壳维度小的线性码具有实际意义。LCD码（壳维数为0）的构造已有大量研究，但壳维数为非零（特别是最小非零值）的码，即具有一维壳的线性码，其构造方法在文献中鲜有报道。
2. 研究目标： 本论文的核心目标是系统地研究并构造具有一维壳的线性码。具体而言，作者旨在： * 建立线性码和循环码具有一维壳的充分必要条件。 * 基于这些刻画，发展出多种构造一维壳线性码的具体方法。 * 探索并构造具有一维壳的循环码，并分析其存在性条件。 * 在已知的最佳线性码数据库中进行比对，验证所构造的部分码在特定参数下是最优的。
研究主要分为两大板块：一是针对一般线性码的刻画与构造；二是针对循环码这一特殊子类的刻画与构造。
（一） 一般线性码的一维壳构造
流程1：基于生成矩阵的刻画。 * 研究对象： 任何标准生成矩阵形式为G = [I_k, P]的[n, k]线性码C，其中I_k是k阶单位阵，P是k × (n-k)矩阵。 * 处理方法与分析： 作者首先推导出一个一般性命题（Proposition 1）：码C具有ℓ维壳，当且仅当矩阵(I_k + PP^T)的秩为k - ℓ。由此可直接得出，C具有一维壳当且仅当该矩阵的秩为k-1。基于此，作者提出了一个便于构造的充分条件（Theorem 1）：如果矩阵PP^T有一个代数重数为1的特征值-1，则码C具有一维壳。这为后续构造提供了理论基础。
流程2：从特征值与特征向量理论出发建立构造框架。 * 研究对象： 设G是一个v阶有限阿贝尔群，定义v×v矩阵P = (p_ij)，其中p_ij = ρ(x_j - x_i)，ρ是G到复数域C的某个函数。 * 处理方法与分析： 作者指出，对于G的任意加法特征φ，向量(φ(x_1), …, φ(xv))^T是P的特征向量，对应的特征值为∑{x∈G} ρ(x)φ(x)。所有v个特征（对应v个不同的特征向量）给出了P的全部特征值。这一理论工具是后续通过数论和组合结构构造矩阵P的关键。
流程3：利用二次数域与高斯和构造。 * 研究对象与方法： 作者选取一个二次域K = Q(√r)，设p是奇素数，满足-1是剩余类环O_K / p中的平方元（其中p是O_K中包含p的素理想）。设β是该环中-1的平方根的一个原像。 * 构造矩阵P： 取有限域GF(r^m)，定义函数ρ：当x非零时，ρ(x)为二次乘法特征η(x)；当x=0时，ρ(x)=β。利用此ρ函数和有限域加法群，按流程2的方法构造出一个r^m × r^m的矩阵P，其元素来自OK（由β和±1组成）。 * 特征值计算与约化： 利用高斯和理论，作者精确计算了矩阵P及其转置乘积P P^T的特征值谱（公式5）。这些特征值是β与高斯和的函数。随后，将矩阵P模素理想p得到有限域GF(q)（q = p或p^2，取决于p在K中的分裂情况）上的矩阵P̄。 * 获得线性码： 以G = [I{r^m}, P̄]为生成矩阵，构造线性码C。 * 判定一维壳： 核心在于分析矩阵P̄ P̄^T在有限域GF(q)中是否有且仅有一个特征值为-1。作者根据r模4的余数、m的奇偶性以及p的性质（如p ≡ 1 mod 4或p ≡ 3 mod 4且(r/p)=-1），分多种情况（Theorem 3, 4, 5）给出了确保这一条件成立的参数要求，从而证明所构造的码具有一维壳。例如，Theorem 3指出，当r ≡ 1 mod 4且p ∤ (r^m + 4)时，若p ≡ 1 mod 4，则C是p元码且有一维壳；若(r/p)=-1且p ≡ 3 mod 4，则C是p^2元码且有一维壳。 * 示例： 论文给出了多个具体参数的示例，如r=7, m=1, p=5时，得到一个最优的[14,7,6]线性码。
流程4：利用部分差集（Partial Difference Sets）构造。 * 研究对象： 设D是阿贝尔群G中的一个(v, k, λ, μ)部分差集，且λ ≠ μ。 * 构造矩阵P： 定义函数ρ，当x在D中时为1，否则为0。由此构造关联矩阵P。 * 特征值分析： 对于非平凡特征φ，矩阵P的特征值为φ(D) = ∑_{d∈D} φ(d)，其值为(λ-μ ± √Δ)/2，其中Δ = (λ-μ)^2 + 4(k-μ)。由于D = -D，P是对称阵，故P P^T = P^2的特征值为φ(D)^2。 * 判定一维壳： 应用Theorem 1，码C具有一维壳的条件是：k^2 ≡ -1 (mod p) 且对所有非平凡特征φ，有φ(D)^2 ≢ -1 (mod p)（Theorem 6）。作者特别以Paley型部分差集（D为有限域GF(r^m)中所有非零平方元集合，其中r^m ≡ 1 mod 4）为例，给出了具体的参数条件（Theorem 7）。
流程5：利用差集（Difference Sets）构造。 * 研究对象： 设D是阿贝尔群G中的一个(v, k, λ)差集。 * 构造与特征值： 同样构造关联矩阵P。利用差集产生2-设计的性质，得到P P^T = (k-λ)I_v + λJ，其中J是全1矩阵。 * 判定一维壳： 矩阵P P^T的特征值为：k+λ(v-1)（重数1）和k-λ（重数v-1）。因此，码C具有一维壳的充分必要条件是：k+λ(v-1) ≡ -1 (mod p) 且 k-λ ≢ -1 (mod p)（Theorem 8）。作者同样以Paley型差集（D为GF(r^m)中所有非零平方元，r^m ≡ 3 mod 4）为例进行了说明（Theorem 9）。
（二） 循环码的一维壳刻画与构造
流程6：基于定义集的刻画。 * 研究对象： 长度为n、与q互素的循环码C，其定义集S = {i ∈ Z_n : g(β^i)=0}，其中g(x)是生成多项式，β是n次单位原根。 * 处理方法与分析： 作者得到了一个核心定理（Theorem 10）：循环码C具有一维壳，当且仅当存在唯一的整数i（0 ≤ i ≤ e-1，其中e = gcd(n, q-1)），使得对称差集 S \ (-S) = {i n / e}。这里-S = {n - j : j ∈ S}。这个定理从组合角度清晰地刻画了一维壳循环码的定义集特征。 * 重要推论： 由该定理直接可得，当e ≤ 2时不存在一维壳循环码。特别地，不存在二元或三元的一维壳循环码（Corollary 1）。这解释了为何以往文献中少见此类构造。
流程7：基于生成多项式的刻画。 * 研究对象： 同上，循环码C及其生成多项式g(x)。 * 处理方法与分析： 与Theorem 10等价，作者给出了生成多项式层面的刻画（Theorem 11）：循环码C具有一维壳，当且仅当存在唯一的整数i（满足特定条件），使得g(x) * m{i n/e}(x) 或 g(x) * m{(e-i)n/e}(x) 是自互反多项式，其中m_a(x)是β^a的极小多项式。该定理为构造提供了代数工具。
流程8：一维壳循环码与LCD码的包含关系及BCH码构造。 * 结构关系： 作者证明（Theorem 12），任何一个一维壳循环码C，都包含在一个LCD循环码中，同时也包含另一个LCD循环码。这意味着可以通过研究结构更清晰的LCD循环码来推知一维壳循环码的参数界限。 * 具体构造示例（BCH码）： 作为应用，作者利用Theorem 10，构造了一类具有一维壳的BCH码（Theorem 13）。给定e≥3和整数i < e/2，BCH码 C(q, n, 2in/e + 1, n - in/e + 1) 具有一维壳。这提供了一类可具体参数化的、具有一维壳的循环码家族。
结论： 本研究成功地系统化并推进了具有一维壳的线性码的构造理论。论文建立了此类码的多种特征定理，并创新性地利用二次数域、部分差集、差集以及循环码的代数结构，发展出多条有效且丰富的构造途径。研究同时揭示了循环码中一维壳存在的苛刻条件，并构造了具有一维壳的BCH码。
价值： * 科学价值： 1. 理论融合创新： 将编码理论、代数数论、特征和与组合设计等多个数学分支的工具深度融合，为解决编码构造问题提供了新颖的跨学科范式。 2. 填补研究空白： 聚焦于介于LCD码（0维壳）与自正交码（高维壳）之间的“一维壳”这一相对未被充分探索的类别，系统性地填补了该领域构造理论的空白。 3. 深化结构理解： 对循环码一维壳条件的刻画，深化了人们对循环码对偶结构与其自同构群/等价性判定算法复杂度之间内在联系的理解。 * 应用价值： 1. 算法优化资源： 所构造的小壳维度（尤其是一维壳）线性码，可直接作为测试用例，或为设计更高效的码等价性判定及自同构群计算算法提供理想的输入资源。 2. 提供优质码字： 研究中产生的多个达到数据库记录的最优码，可直接应用于通信、存储等需要高性能纠错码的实际系统中。 3. 方法启发性强： 提出的基于数论和组合结构的构造框架，具有高度的可扩展性，可启发后续研究者利用其他代数域（如分圆域）或更复杂的组合结构来构造具有特定壳性质的码。
论文在最后部分（第五节）简要总结了所有主要贡献，并指出了未来可能的研究方向，例如利用分圆域来构造一维壳线性码，因为分圆域具有更丰富的代数结构。此外，作者也坦诚指出，确定所构造码的精确最小距离在一般情况下是非常困难的问题，这通常是编码理论中的核心挑战。尽管如此，对于通过BCH构造得到的那类循环码，其设计距离提供了最小距离的下界，而Reed-Solomon码作为特例则是MDS码（达到Singleton界）。文末的致谢部分提及了审稿人和编委的宝贵意见对提升论文质量起到了重要作用。