🔢 mathematics

Construction of MRD Codes Based on Circular-Shift Operations

本文提出了一种基于循环移位操作、完全在有限域 $\mathbb{F}_q$ 上构建的高效最大秩距离（MRD）码方案，通过 $q$ -线性化多项式刻画了其与传统 Gabidulin 码及扭曲 Gabidulin 码的异同与联系，并证明了在特定参数下该方案能显著降低编码复杂度。

原作者： Zhe Zhai, Sheng Jin, Qifu Tyler Sun, Zongpeng Li

发布于 2026-02-16

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Zhe Zhai, Sheng Jin, Qifu Tyler Sun, Zongpeng Li

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

这篇论文介绍了一种更聪明、更高效的“数据防丢”新方法。

为了让你轻松理解，我们可以把MRD 码（最大秩距离码）想象成一种超级坚固的“数据保险箱”。在分布式存储（比如云盘）或网络传输中，数据可能会因为硬件故障或网络干扰而“损坏”或“丢失”。MRD 码的作用就是给数据加上特殊的“锁”和“备用件”，即使坏了一部分，也能完美还原。

以前的老方法（比如 Gabidulin 码）虽然很厉害，但有一个大缺点：它们用的“数学语言”太复杂了。

1. 以前的痛点：在“外星语言”里算数

想象一下，以前的工程师在造保险箱时，必须在一个巨大的、复杂的“外星数学王国”（扩展域 $F_{q^N}$ ）里进行计算。

比喻：这就像你要造一把锁，却必须先去学习一门极其深奥的古代外语，用那种语言里的加减乘除来设计锁芯。
后果：随着数据量变大（ $N$ 变大），这个“外星王国”变得越来越大，计算变得极其缓慢且昂贵。就像为了造一把小锁，非要动用整个图书馆的算力，而且很难灵活调整锁的大小。

2. 这篇论文的突破：回到“母语”算数

这篇论文的作者提出了一种基于**“循环移位”（Circular-Shift）**的新方法。

比喻：他们不再去那个复杂的“外星王国”了，而是直接在我们的**“母语”（基础域 $F_q$ ，比如简单的 0 和 1）**里干活。
核心操作——循环移位：想象你有一排数字 [1, 2, 3, 4, 5]。
- 循环移位就是把它们像转盘子一样转一下：[5, 1, 2, 3, 4] 或者 [4, 5, 1, 2, 3]。
- 在计算机里，这只需要把数据块“挪个位置”，不需要做复杂的数学乘法，就像把积木块换个位置一样简单快速。

3. 新方法的三大优势

A. 速度更快（省了“翻译费”）

旧方法：每次计算都要在“外星语言”和“母语”之间反复翻译，还要做复杂的乘法。
新方法：全程只用“母语”，而且核心操作只是“挪位置”（移位）和“异或”（XOR，一种简单的二进制加法，0+0=0, 0+1=1, 1+1=0）。
结果：论文证明，在特定情况下，新方法生成一个数据块的计算量是 $O(nkL) $，而旧方法是$ $，而旧方法是$ O(nkL^2)$。
- 通俗理解：如果旧方法需要跑 100 公里，新方法只需要跑 10 公里。速度提升了一个数量级！

B. 更灵活（想造多大就造多大）

旧方法：因为依赖那个复杂的“外星王国”，参数选大了就卡死，很难灵活调整。
新方法：因为只用简单的“母语”和“挪位置”，参数可以选得很大，非常灵活，适合各种规模的存储系统。

C. 既熟悉又陌生（与旧方法的关系）

论文还花了很多篇幅研究新方法和旧方法（Gabidulin 码）的关系：

有时候它们是“双胞胎”：在特定条件下，新方法生成的保险箱和旧方法生成的完全一样。这意味着新方法提供了一种更简单的制造旧方法保险箱的途径（不用学外星语也能造出同样的锁）。
有时候它们是“表亲”：在更多情况下，新方法造出的保险箱是全新的，和旧方法不一样，甚至和一种叫“扭曲 Gabidulin 码”的变体也不同。这就像发现了一种全新的锁芯结构，可能带来新的安全特性。

4. 总结：这到底意味着什么？

想象一下，以前我们要给数据加锁，必须雇佣一群精通高深数学的专家，在昂贵的超级计算机上慢慢算。

现在，这篇论文告诉我们：其实只要用简单的“挪位置”技巧（循环移位），在普通的计算机上就能造出同样坚固、甚至更坚固的锁！

对普通用户：意味着未来的云存储可能更便宜、速度更快，因为服务器处理数据的负担变轻了。
对工程师：提供了一套新的工具箱，不用再去啃那些复杂的扩展域数学，直接用最基础的逻辑门（XOR 和移位）就能搞定最高级的纠错码。

一句话总结：
作者把原本需要“高深数学魔法”才能完成的防丢数据技术，变成了“简单的积木挪位游戏”，既保留了强大的保护能力，又让计算变得飞快且廉价。

这篇论文提出了一种基于循环移位（Circular-Shift）操作构造最大秩距离（MRD）码的新方法。该方法旨在解决传统 MRD 码（如 Gabidulin 码）在参数选择灵活性和实际实现复杂度方面的局限性，特别是避免了在扩展域 $F_{q^N}$ 上的复杂算术运算。

以下是对该论文的详细技术总结：

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

现有方法的局限性：目前大多数 $(N \times n, q^{Nk}, d)$ $(N \times n, q^{N k}, d)$ MRD 码（如 Gabidulin 码及其变体）的构造依赖于扩展域 $F_{q^N}$ $F_{q^{N}}$ 的算术运算。
- 实现复杂：随着 $N$ 的增大，扩展域 $F_{q^N}$ 的运算复杂度急剧增加，导致硬件或软件实现困难。
- 参数选择僵化：为了高效实现，通常需要将 $N$ 限制在较小范围，这限制了 MRD 码在密码学、分布式存储和子空间码等应用中的参数灵活性。
- 基的选择难题：将 $F_{q^N}$ 上的向量转换为 $F_q$ 上的矩阵需要选择特定的基，而如何高效选择基以优化转换过程尚未得到充分研究。
核心问题：能否在仅使用基域 $F_q$ 算术运算（避免扩展域算术）的情况下，构造出具有高效编码且参数灵活的 MRD 码？

2. 方法论 (Methodology)

作者提出了一种基于**循环移位线性网络编码（LNC）**思想的构造方法，完全在基域 $F_q$ 上操作。

基本设定：
- 设 $q$ 为素数， $L$ 为满足 $\gcd(q, L)=1$ 的正整数。
- $m_L$ 为 $q$ 模 $L$ 的乘法阶（即 $q^{m_L} \equiv 1 \pmod L$ ）。
- $J$ 为 $L$ 的欧拉函数值（即 $1 $到$ L-1 $中与$ L$ 互质的整数个数）。
- 构造 $(J \times n, q^{Jk}, d)$ 的 MRD 码，其中 $n \le m_L \le J$ 。
构造核心：
- 定义一个 $k \times n$ 的分块矩阵 $\Psi_{k \times n}$ ，其每个块是 $L \times L$ 的循环置换矩阵 $C_L$ 的幂次。
- 引入两个矩阵 $P \in F_q^{J \times L}$ 和 $Q \in F_q^{L \times J}$ 。
- 码字生成公式为： $C = \{ \Delta(m(I_k \otimes P) \Psi_{k \times n} (I_n \otimes Q)) : m \in F_q^{Jk} \}$ 。
- 其中 $\Delta$ 是将行向量映射为 $J \times n$ 矩阵的变换， $\otimes$ 为克罗内克积。
- 通过特定的 $P$ 和 $Q$ 设计（基于范德蒙德矩阵和特定的多项式 $\tau(x)$ ），确保生成的码满足 MRD 性质。
两种构造变体：
1. $C_1$ ：使用 $P=G_L, Q=H_L$ 。
2. $C_2$ ：使用 $P=G_L, Q=\tau(C_L)G_L^T$ 。在特定条件下（如 $L$ 为素数）， $C_2$ 的编码复杂度更低。

3. 主要贡献 (Key Contributions)

新型 MRD 码构造：提出了基于循环移位的 MRD 码，完全在 $F_q$ 上进行运算，避免了 $F_{q^J}$ 的算术运算。
多项式刻画与关系分析：
- 利用定义在行向量空间 $F_q^N$ 上的 $q$ -线性化多项式集合，统一刻画了 Gabidulin 码、扭曲 Gabidulin 码和本文提出的循环移位码。
- 当 $J \neq m_L$ 时：证明了在特定参数设置下，提出的 MRD 码与任何 Gabidulin 码或扭曲 Gabidulin 码都不等价（即属于新的码族）。
- 当 $J = m_L$ 时：证明了提出的 MRD 码与 Gabidulin 码等价。但这仍然是一个重要贡献，因为它提供了一种仅基于 $F_q$ 算术构造 Gabidulin 码的新途径，避免了传统方法中 $F_{q^J}$ 的复杂运算。
广义 Gabidulin 码的等价性：证明了在特定参数选择下，提出的 MRD 码等价于一种新的广义 Gabidulin 码，该码由多个 $(m_L \times n, q^{m_L k}, d)$ Gabidulin 码求和并拼接而成。
复杂度分析：
- 在 $q=2, L$ 为素数且 $n \le m_L$ 的情况下，生成一个码字所需的异或（XOR）运算复杂度为 $O(nkL)$。
- 相比之下，传统 Gabidulin 码（基于 $F_{2^{L-1}}$ 构造）的编码复杂度为 $O(nkL^2)$ 。

4. 关键结果 (Results)

MRD 性质证明：通过数学推导证明了在满足特定秩条件（如式 33 和 48）时，构造的码具有最大秩距离 $d = n - k + 1$ 。
等价性区分：
- 通过引理 11 和定理 12，严格证明了当 $J \neq m_L$ 且参数满足特定线性无关条件时，新码与 Gabidulin 码本质不同。
- 当 $J = m_L$ 时，新码与 Gabidulin 码重合，但构造方法更优（基于 $F_q$ ）。
计算复杂度优势：
- 循环移位码：仅需 $O(nkL)$ 次 XOR 操作（对于 $q=2$ ），无需乘法运算。
- 传统 Gabidulin 码：需要 $O(nkL^2)$ 次 XOR 操作（因为涉及 $F_{2^L}$ 中的乘法，通常视为 $O(L^2)$ 复杂度）。
- 这意味着在 $L$ 较大时，新方法的编码效率显著高于传统方法。

5. 意义与影响 (Significance)

降低实现门槛：通过消除对扩展域算术的依赖，使得 MRD 码可以在资源受限的设备或大规模系统中更高效地实现。
参数灵活性：允许 $J$ 和 $k$ 选择更大的值，扩展了 MRD 码在分布式存储和子空间码中的应用场景。
理论突破：揭示了循环移位操作与 MRD 码之间的深刻联系，并建立了循环移位码与 Gabidulin 码家族之间的理论桥梁（等价性与差异性）。
工程价值：对于 $q=2$ 的二进制系统，该方法将编码复杂度从二次方降低到线性方（相对于 $L$ ），具有显著的工程实用价值。

总结：该论文提出了一种高效、基于基域运算的 MRD 码构造方法。它不仅解决了传统 Gabidulin 码实现复杂的问题，还通过理论分析厘清了新码与经典码族的关系，为未来在分布式存储和网络安全中的应用提供了新的理论基础和高效算法。