定秩集秩度量码的Singleton型上界

doi:10.12677/aam.2026.152075

期刊菜单

定秩集秩度量码的Singleton型上界
Singleton Upper Bound of Rank Metric Codes with Given Ranks

DOI: 10.12677/aam.2026.152075, PDF, HTML, XML, 科研立项经费支持
作者: 刘翊文, 陈炫燃, 宋谭夕：苏州科技大学数学科学学院，江苏苏州；朱博华：石家庄铁道大学数理系，河北石家庄
关键词: 常维码；定秩集秩度量码；子空间码；Constant Dimension Codes； Rank Metric Codes with Given Ranks； Subspace Codes

摘要: 为了推动网络编码实用化，2006年Médard等人提出随机网络编码概念，2008年Kschischang等人针对错误纠正与数据恢复需求，提出子空间码模型，而定秩集秩度量码是用来构造子空间码的一类辅助码。我们的研究围绕网络编码范畴展开，主要针对常维码与定秩集秩度量码这两类核心研究对象。在网络编码基本原理的基础上，本文系统地研究了定秩集秩度量码的代数性质，给出了定秩集秩度量码的Singleton界，证明了定秩集秩度量码的渐近最优性。

Abstract: To promote the practical application of network coding, Médard et al. proposed the concept of random network coding in 2006. In 2008, to address the requirements of error correction and data recovery, Kschischang et al. put forward the subspace code model, where rank metric codes with given ranks serve as a class of auxiliary codes for constructing subspace codes. Our research focuses on the field of network coding, with its primary focus on two core research objects: constant dimension codes and rank metric codes with given ranks. Based on the fundamental principles of network coding, this paper systematically investigates the algebraic properties of rank metric codes with given ranks, derives the Singleton upper bound for such codes, and proves their asymptotic optimality.

文章引用：刘翊文, 陈炫燃, 宋谭夕, 朱博华. 定秩集秩度量码的Singleton型上界[J]. 应用数学进展, 2026, 15(2): 345-351. https://doi.org/10.12677/aam.2026.152075

1. 引言

网络编码[1]是在网络中进行信息传播时在中间节点进行编码的技术。为了提高通信性能，中间节点应该转发它们接收到的数据包的随机线性组合。因此，当没有错误发生时，其数据包所张成的向量空间是全局不变的。因为线性组合下的线性空间是不变的，所以它们正好是解码所需的码字[2]。本文考虑所有子空间的维数都是一致的，也就是常维码(CDCs)。

设Grassmann空间 $G_{q} (n, k)$ 表示 $F_{q}^{n}$ 中所有维度为 $k$ 的子空间的集合。众所周知，Grassmann空间 $G_{q} (n, k)$ 的基数由 $q$ 元高斯系数给出：

$| G_{q} (n, k) | = {[\begin{matrix} n \\ k \end{matrix}]}_{q} ≜ \prod_{i = 0}^{k - 1} \frac{q^{n - i} - 1}{q^{k - i} - 1}$ 。

一个参数为 $(n, M, d, k)$ 的常维码 $C$ 是 $G_{q} (n, k)$ 的一个子集，满足对于任意两个子空间 $U, V \in C$ ，子空间距离为：

$d_{I} (U, V) = \max {\dim U, \dim V} - \dim (U \cap V) \geq d$ 。

其中 $U, V \in F_{q}^{k \times n}$ 是矩阵，满足 $U = rowspace (U)$ 且 $V = rowspace (V)$ 。

令 $A_{q} (n, d, k)$ 表示 $(n, M, d, k)$ 常维码 $C$ 的最大可能个数。由于 $A_{q} (n, d, k) = A_{q} (n, d, n - k)$ (见文献[3])，在不损失一般性的情况下，我们总是假设 $n \geq 2 k$ 。 $F_{q}^{n}$ 的一个 $k$ 维子空间 $U$ 可以由一个 $k \times n$ 的生成矩阵表示，该矩阵的行构成 $U$ 的一个基。如果 $U, V \in G_{q} (n, k)$ ，那 $G_{q} (n, k)$ 上的子空间距离也可以表示为：

$d_{s} (U, V) = 2 rank (\begin{matrix} U \\ V \end{matrix}) - 2 k$ 。

这两个矩阵通常不是唯一的。实际上，人们可以注意到，对于任何 $A \in G L_{k} (F_{q})$ ， $U = rowspace (A U)$ 。然而，Grassmann流形元素存在唯一的矩阵表示，即行简化阶梯形。一个秩为 $k$ 的 $k \times n$ 矩阵是行简化阶梯形，如果：

1) 一行的前导系数在该行中位于前一行前导系数的右侧；

2) 所有前导系数都是1；

3) 每个前导系数都是其所在列中唯一的非零元素。

为了获得最优的常维码，Silva、Kschischang和Kötter在文献[4]中指出，最大秩距离码(MRDs)可以导致渐近最优的CDCs [2] [3]，并且在随机线性网络编码的背景下可以高效解码。许丽卿等学者[5]和刘双庆等学者[6]选择定秩集秩度量码这种新的辅助码，将其运用于子空间码的构造实践中。对于子空间码的更多构造和界的相关信息，感兴趣的读者可以参考文献[2] [3] [6]-[18]。

本文系统研究了文献[6]中引入的定秩集秩度量码，并给出了定秩集秩度量码的Singleton界，证明了定秩集秩度量码的渐近最优性。我们还建立了定秩集秩度量码和子空间码之间的联系。

2. 预备知识

令q是一个素数幂， $F_{q}$ 表示q阶有限域， $F_{q}^{m \times n}$ 表示 $F_{q}$ 上所有尺寸为 $m \times n$ 的矩阵的集合。对于矩阵 $A \in F_{q}^{m \times n}$ ，用 $rank (A)$ 表示 $A$ 的秩。

定义2.1：

$[m, n]$ ：表示大于等于 $m$ 并且小于等于 $n$ 的连续整数。

定义2.2：

对于矩阵 $A, B \in F_{q}^{m \times n}$ ，它们的秩距离定义如下：

$d_{R} (A, B) = rank (A - B)$ ，

并且秩分布已经确定。

定义2.3 [19]：

${[m \times n, k, δ]}_{q}$ －秩度量码 $C$ 是 $F_{q}^{m \times n}$ 上的 $k$ 维线性子空间，且满足最小秩距离 $\geq δ$ 。

对于 ${[m \times n, k, δ]}_{q}$ －秩度量码，它的Singlenton型上界为：

$k \leq m (n - δ + 1)$ ，

当等号成立时，称为最大秩度量(MRD)码，记为 $MRD {[m \times n, δ]}_{q}$ 码。Delsarte [20] (1978)和Gabidulin [21] (1985)分别证明了任何参数的最大秩度量码都是存在的。

定理2.4：(最大秩度量码的秩分布[20] [21])

对于任意的 $MRD {[m \times n, δ]}_{q}$ 码，其秩分布由以下式子给出： $A_{0} = 1$ ，当 $1 \leq i \leq δ - 1$ 时， $A_{i} = 0$ ，并且有

$A_{δ + i} = {[\begin{matrix} n \\ δ + i \end{matrix}]}_{q} \sum_{j = 0}^{i} {(- 1)}^{j - i} {[\begin{matrix} δ + i \\ i - j \end{matrix}]}_{q} q^{(\begin{matrix} i - j \\ 2 \end{matrix})} (q^{m (j + 1)} - 1)$ ，

其中 $0 \leq i \leq n - δ$ 。

进一步，对码字的秩进行限制，则得到了定秩集秩度量码。

定义2.5：

对于 $K \subseteq {0, 1, \dots, n - 1}$ ， $C \subseteq F_{q}^{m \times n}$ 是一个参数为 ${(m \times n, δ, K)}_{q}$ -定秩集秩度量码，如果 $C$ 满足

1) 对于任意的 $C \in C$ ， $rank (C) \in K$ ；

2) 对于任意的 $C_{1}, C_{2} \in C$ ，且 $C_{1} \neq C_{2}$ ，有 $d_{R} (C_{1}, C_{2}) \geq δ$ 。

如果 $| C | = M$ ，则一个参数为 ${(m \times n, δ, K)}_{q}$ -定秩集秩度量码可以表示为 ${(m \times n, M, δ, K)}_{q}$ -定秩集秩度量码。给定 $m, n, K$ 和 $δ$ ，其中 $m \geq n$ ，记号 $A_{q}^{R} (m \times n, δ, K)$ 表示所有参数为 ${(m \times n, δ, K)}_{q}$ -定秩集秩度量码中码字个数的最大值。最近，季利均等人给出了定秩集秩度量码的球填充上界。

3. 定秩集秩度量码(GRMCs)的Singleton界

本章主要研究定秩集秩度量码的Singleton型上界，并且证明出当参数满足 $m \geq n \geq \dots \geq r \geq d_{R} > 1$ 时， ${(m \times n, M, d, [r, \dots, n])}_{q}$ 定秩集秩度量码的渐进性是最优的。进一步，对一类特殊的定秩集秩度量码进行研究，即 ${(n \times n, M, n - 2, {n - 1, n})}_{q}$ -定秩集秩度量码，并展示了其上、下界的比。已有文献中定秩集秩度量码的球填充界需依赖于对集合 ${B \in F_{q}^{m \times n} : rank (B) = i 且 rank (B - E_{j}) \leq l}$ 的估计，目前学界尚未形成对该集合的有效估计方法，导致球填充界难以给出显式表达，而本文提出的Singleton界是显式的表达式，且对于部分类别的定秩集秩度量码而言，该界能够达到渐近最优。

引理3.1 (定理8 [12])：

当 $m \geq n \geq r \geq d_{R} > 1$ 时，

$A_{R} (m \times n, d_{R}, r) \leq {[\begin{matrix} n \\ r \end{matrix}]}_{q} \cdot α (m, r - d_{R} + 1)$ 。

其中 $α (m, i) = \prod_{j = 0}^{i - 1} (q^{m} - q^{j})$ 。

定理3.2 (定秩集秩度量码的Singleton界)：

当 $m \geq n \geq r \geq d_{R} > 1$ 时，

$A_{q}^{R} (m \times n, d_{R}, [r, n]) \leq \sum_{i = r - d_{R} + 1}^{n - d_{R} + 1} {[\begin{matrix} n - d_{R} + 1 \\ i \end{matrix}]}_{q} α (m, i)$ 。

证明设 $C$ 是任意一个 ${(m \times n, M, d_{R}, [r, n])}_{q}$ -定秩集秩度量码。考虑通过对 $C$ 中的所有码字任意删除 $d_{R} - 1$ 列得到的码 $C^{'}$ 。此时 $C^{'}$ 是一个 ${(m \times (n - d_{R} + 1), M, 1, [r - d_{R} + 1, n - d_{R} + 1])}_{q}$ -定秩集秩度量码。

将 $C^{'}$ 分解为不同秩的码字集合 $C^{'} = \sum_{i = r - d_{R} + 1}^{n - d_{R} + 1} {C^{'}}_{i}$ ， ${C^{'}}_{i}$ 表示 $C^{'}$ 中秩为i的所有码字。由上述引理，

$| C_{i} | \leq {[\begin{matrix} n - d_{R} + 1 \\ i \end{matrix}]}_{q} α (m, i)$ 。

因此，

$| C | = | C^{'} | \leq \sum_{i = r - d_{R} + 1}^{n - d_{R} + 1} {[\begin{matrix} n - d_{R} + 1 \\ i \end{matrix}]}_{q} α (m, i)$ 。

证毕。

推论3.3：

当 $m \geq n \geq r \geq d_{R} > 1$ 时，存在 ${(m \times n, M, d_{R}, [r, n])}_{q}$ -定秩集秩度量码，使

$\lim_{q \to \infty} \frac{M}{\sum_{i = r - d_{R} + 1}^{n - d_{R} + 1} {[\begin{matrix} n - d_{R} + 1 \\ i \end{matrix}]}_{q} \cdot α (m, i)} = 1$ 。

证明设 $C = \cup_{i = r}^{n} C_{i}$ ， $C_{i}$ 表示一个 $MRD {[m \times n, d_{R}]}_{q}$ 码中秩为 $i$ 的所有码字。根据定理2.3，有 $| C | = \sum_{i = 1}^{n} A_{i}$ 。考虑 $A_{n} = \sum_{j = 0}^{n - d_{R}} {(- 1)}^{i - n + d_{R}} {[\begin{matrix} n \\ n - d_{R} - j \end{matrix}]}_{q} q (\begin{matrix} n - d_{R} - j \\ 2 \end{matrix}) (q^{m (j + 1)} - 1)$ 。

设 $f_{j} (q) = {[\begin{matrix} n \\ n - d_{R} - j \end{matrix}]}_{q} q (\begin{matrix} n - d_{R} - j \\ 2 \end{matrix}) (q^{m (j + 1)} - 1)$ ，则

$\begin{matrix} \deg (f_{j} (q)) = (n - d_{R} - j) (d_{R} + j) + \frac{(n - d_{R} - j) (n - d_{R} - j - 1)}{2} + m (j + 1) \\ = - \frac{1}{2} j^{2} + (m - d_{R} + \frac{1}{2}) j + \frac{(n - d_{R}) (n + d_{R} - 1) + 2 m}{2} \end{matrix}$

对于 $0 \leq j \leq m - d_{R} + \frac{1}{2}$ ， $\deg (f_{j} (q))$ 是 $j$ 的增函数，并且

$\deg (f_{n - d_{R} - 1} (q)) = m (n - d_{R} + 1)$ 。

令 $| C | = q^{m (n - d_{R} + 1)} - h_{1} (q)$ ，其中 $\deg (h_{1} (q)) < m (n - d_{R} + 1)$ 且 $h_{1} (q) > 0$ 。根据定理3.2，有

$A_{q}^{R} (m \times n, d_{R}, [r, n]) \leq \sum_{i = r - d_{R} + 1}^{n - d_{R} + 1} {[\begin{matrix} n - d_{R} + 1 \\ i \end{matrix}]}_{q} \cdot α (m, i)$ 。

设 $g_{i} (q) = {[\begin{matrix} n - d_{R} + 1 \\ j \end{matrix}]}_{q} α (m, j)$ ，则

$\deg (g_{j} (q)) = (n - d_{R} + 1 - j) \cdot j + m j = - j^{2} + (m + n - d_{R} + 1) j$ 。

由于当 $j$ 为主元时， $\deg (f_{j} (q))$ 在 $j \leq \frac{m + n - d_{R} + 1}{2}$ 时是增函数，所以对于 $r - d_{R} + 1 \leq j \leq n - d_{R} + 1$ ，

$\deg (g_{n - d_{R} + 1} (q)) = m (n - d_{R} + 1)$ 。

可得

$\sum_{i = r - d_{R} + 1}^{n - d_{R} + j} {[\begin{matrix} n - d_{R} + 1 \\ j \end{matrix}]}_{q} α (m, j) = q^{m (n - d_{R} + 1)} - h_{2} (q)$ ，

其中 $\deg (h_{2} (q)) < m (n - d_{R} + 1)$ 且 $h_{2} (q) > 0$ 。

因此，

$\lim_{q \to \infty} \frac{M}{\sum_{i = r - d_{R} + 1}^{n - d_{R} + 1} {[\begin{matrix} n - d_{R} + 1 \\ i \end{matrix}]}_{q} \cdot α (m, i)} = \lim_{q \to \infty} \frac{q^{m (n - d_{R} + 1)} - h_{1} (q)}{q^{m (n - d_{R} + 1)} - h_{2} (q)} = 1$ 。

证毕。

推论3.4：

对于任意 ${(n \times n, A_{n - 1} + A_{n}, n - 2, {n - 1, n})}_{q}$ -定秩集秩度量码，其中 $A_{i}$ 表示在 $MRD {[n \times n, n - 2]}_{q}$ 码中秩为i的码字个数，有

$\frac{| C |}{\sum_{i = 2}^{3} {[\begin{array}{l} 3 \\ i \end{array}]}_{q} \cdot α (n, i)} > 0.83$ 。

证明根据定理2.3，可知

$A_{n} = \frac{(q^{n} - 1) (q^{n - 1} - 1)}{(q^{2} - 1) (q - 1)} \cdot q \cdot (q^{n} - 1) - \frac{q^{n} - 1}{q - 1} (q^{2 n} - 1) + q^{3 n} - 1$ ，

$A_{n - 1} = \frac{q^{n} - 1}{q - 1} \cdot (- \frac{(q^{n - 1} - 1) (q^{n} - 1)}{q - 1} + q^{2 n} - 1)$ 。

根据定理3.2中GRMCs中的Singleton界，有

$\sum_{i = 2}^{3} {[\begin{array}{l} 3 \\ i \end{array}]}_{q} \cdot 2 \cdot (n, i) = q^{3 n} - q^{n + 2} - q^{n + 1} - q^{n} + q^{2} + q$ 。

由于 $| C | = A_{n - 1} + A_{n}$ ，所以

$\begin{matrix} \frac{| C |}{\sum_{i = 2}^{3} {[\begin{array}{l} 3 \\ i \end{array}]}_{q} \cdot α (n, i)} = \frac{A_{n - 1} + A_{n}}{\sum_{i = 2}^{3} {[\begin{array}{l} 3 \\ i \end{array}]}_{q} \cdot α (n, i)} \\ = \frac{q^{3 n + 3} - q^{3 n + 2} - q^{3 n + 1} + q^{3 n} - q^{3 n - 1} - q_{1}^{n} + 2 q_{1}^{2 n - 1} - q^{n - 1} + q^{3} + q^{2} + q}{q^{3 n + 3} - q^{3 n + 2} - q^{3 n + 1} + q^{3 n} - q^{n + 5} + q^{n + 3} + q^{n + 2} - q^{n} + q^{5} - 2 q^{3} + q} \\ = 1 - \frac{q^{3 n - 1} - q^{2 n} - 2 q^{2 n - 1} - q^{n + 5} + q^{n + 3} + q^{n + 2} + q^{n} + q^{n - 1} + q^{5} - q^{3} - q}{q^{3 n + 3} - q^{3 n + 2} - q^{3 n + 1} + q^{3 n - q_{1}^{n + 5}} + q^{n + 3} + q^{n + 2} - q^{n} + q^{5} - 2 q^{3} + q} \\ \geq 1 - \frac{q^{3 n - 1}}{q^{3 n + 3} - q^{3 n + 2} - q^{3 n + 1} + q^{3 n}} = 1 - \frac{1}{q^{4} - q^{3} - q^{2} + q} \end{matrix}$

设函数 $f (q) = 1 - \frac{1}{q^{4} - q^{3} - q^{2} + q}$ ，根据链式法则，对 $f (q)$ 求导，得到

$f^{'} (q) = \frac{4 q^{3} - 3 q^{2} - 2 q + 1}{{(q^{4} - q^{3} - q^{2} + q)}^{2}}$ 。

令

$D (q) = 4 q^{3} - 3 q^{2} - 2 q + 1, D {(q)}^{'} = 12 q^{2} - 6 q - 2$ ，

对于 $q \in [2, + \infty)$ ， $D {(q)}^{'} \geq 0$ ，则 $D (q)$ 单调递增，即 $D (q) \geq D (2) = 17$ 。可知 $f^{'} (q) > 0$ ，即 $f (c)$ 在 $[2, + \infty)$ 上单调递增。

所以当 $q = 2$ 时，可知

$1 - \frac{1}{q^{4} - q^{3} - q^{2} + q} > 0.83$ 。

因此，

$\frac{| C |}{\sum_{i = 2}^{3} {[\begin{array}{l} 3 \\ i \end{array}]}_{q} \cdot α (n, i)} > 0.83$ 。

证毕。

4. 结语

尽管定秩集秩度量码在常维码的构造中扮演着不可或缺的角色，但其渐近最优性问题还未完全解决。在现有的研究成果中，仅经典MRD码与部分特殊常秩码的最优性得到了验证，其余定秩集秩度量码的最优性则仍有待进一步探究。

基金项目

江苏省大学生创新创业项目(202410332137Y)。

参考文献

[1]	Ahlswede, R., Cai, N., Li, S.-R. and Yeung, R.W. (2000) Network Information Flow. IEEE Transactions on Information Theory, 46, 1204-1216. [Google Scholar] [CrossRef]
[2]	Koetter, R. and Kschischang, F.R. (2008) Coding for Errors and Erasures in Random Network Coding. IEEE Transactions on Information Theory, 54, 3579-3591. [Google Scholar] [CrossRef]
[3]	Etzion, T. and Vardy, A. (2011) Error-Correcting Codes in Projective Space. IEEE Transactions on Information Theory, 57, 1165-1173. [Google Scholar] [CrossRef]
[4]	Silva, D., Kschischang, F.R. and Koetter, R. (2008) A Rank-Metric Approach to Error Control in Random Network Coding. IEEE Transactions on Information Theory, 54, 3951-3967. [Google Scholar] [CrossRef]
[5]	Xu, L. and Chen, H. (2018) New Constant-Dimension Subspace Codes from Maximum Rank Distance Codes. IEEE Transactions on Information Theory, 64, 6315-6319. [Google Scholar] [CrossRef]
[6]	Liu, S., Chang, Y. and Feng, T. (2020) Parallel Multilevel Constructions for Constant Dimension Codes. IEEE Transactions on Information Theory, 66, 6884-6897. [Google Scholar] [CrossRef]
[7]	Ahlswede, R. and Aydinian, H. (2009) On Error Control Codes for Random Network Coding. 2009 Workshop on Network Coding, Theory, and Applications, Lausanne, 15-16 June 2009, 68-73. [Google Scholar] [CrossRef]
[8]	Delsarte, P. (1973) An Algebraic Approach to the Association Schemes of Coding Theory. Ph.D. Thesis, Philips Research Laboratories.
[9]	Etzion, T. and Silberstein, N. (2009) Error-Correcting Codes in Projective Spaces via Rank-Metric Codes and Ferrers Diagrams. IEEE Transactions on Information Theory, 55, 2909-2919. [Google Scholar] [CrossRef]
[10]	Etzion, T. and Silberstein, N. (2013) Codes and Designs Related to Lifted MRD Codes. IEEE Transactions on Information Theory, 59, 1004-1017. [Google Scholar] [CrossRef]
[11]	Frankl, P. and Wilson, R.M. (1986) The Erdös-Ko-Rado Theorem for Vector Spaces. Journal of Combinatorial Theory, Series A, 43, 228-236. [Google Scholar] [CrossRef]
[12]	Gadouleau, M. and Yan, Z. (2010) Constant-Rank Codes and Their Connection to Constant-Dimension Codes. IEEE Transactions on Information Theory, 56, 3207-3216. [Google Scholar] [CrossRef]
[13]	Heinlein, D., Kiermaier, M., Kurz, S. and Wassermann, A. (2016) Tables of Subspace Codes. arXiv: 1601.02864v2.
[14]	Liu, S. and Ji, L. (2023) Double Multilevel Constructions for Constant Dimension Codes. IEEE Transactions on Information Theory, 69, 157-168. [Google Scholar] [CrossRef]
[15]	Silberstein, N. and Etzion, T. (2011) Enumerative Coding for Grassmannian Space. IEEE Transactions on Information Theory, 57, 365-374. [Google Scholar] [CrossRef]
[16]	Trautmann, A.-L. and Rosenthal, J. (2010) New Improvements on the Echelon-Ferrers Construction. Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems, Budapest, 5-9 July 2010, 405-408.
[17]	Xia, S. and Fu, F. (2008) Johnson Type Bounds on Constant Dimension Codes. Designs, Codes and Cryptography, 50, 163-172. [Google Scholar] [CrossRef]
[18]	Yu, S., Ji, L. and Liu, S. (2022) Bilateral Multilevel Construction of Constant Dimension Codes. Advances in Mathematics of Communications, 16, 1165-1183. [Google Scholar] [CrossRef]
[19]	刘双庆. 子空间码的组合和代数结构方法[D]: [博士学位论文]. 北京: 北京交通大学, 2020.
[20]	Delsarte, P. (1978) Bilinear Forms over a Finite Field, with Applications to Coding Theory. Journal of Combinatorial Theory, Series A, 25, 226-241. [Google Scholar] [CrossRef]
[21]	Gabidulin, E.M. (1985) Theory of Codes with Maximum Rank Distance. Problems of Information Transmission, 21, 3-16.

为你推荐

友情链接