Lifted Codes with Construction of Echelon-Ferrers for Constant Dimension Codes

Abstract

Finding the highest possible cardinality, $A_q(n,d;k)$, of the set of k-dimensional subspaces in ${\mathbb{F}}_q^n$, also known as codewords, is a fundamental problem in constant dimension codes (CDCs). CDCs find applications in a number of domains, including distributed storage, cryptography, and random linear network coding. The goal of recent research papers has been to establish $A_q(n,d;k).$ We further improved the echelon-Ferrers construction with an algorithm, and enhanced the inserting construction by swapping specified columns of the generator matrix to obtain new lower bounds.

1. Introduction

Assume that ${\mathbb{F}}_q$ is a finite field with q elements. The set of all k-dimensional subspaces of a ${\mathbb{F}}_q$-vector space V is denoted by ${\mathcal{G}}_q(k,n)$. In vector space ${\mathbb{F}}_q^n$, the projective space over the finite field ${\mathbb{F}}_q$ of order n, represented as ${\mathcal{P}}_q\left(n\right)$, often includes all of the subspaces. These subspaces constitute a metric space when combined. Together, and the defining metric is the subspace distance. It is described as

$$\begin{array}{cc}\hfill d_S(U,W)& =\dim (U+W)-\dim (U\cap W)\hfill \\ & =2·\dim (U+W)-\dim \left(U\right)-\dim \left(W\right).\hfill \end{array}$$

CDCs are a special class of subspace codes with important applications in network coding, especially in random network coding. In recent years, network coding has garnered significant attention as an innovative method for transmitting data over networks. It is extensively used in distributed storage systems, peer-to-peer networks, social networks, wireless communication networks, and other types of networks. In random network coding, conventional error-correcting code techniques may not be adequate due to the unpredictability of network topologies. The ability of CDCs to preserve vector space properties makes them an effective tool for addressing this issue.

Since Köetter and Kschischang [1] first introduced subspace codes, there has been extensive research on them [2,3,4,5,6,7,8]. Heinlein et al. [9] provide more details regarding their theoretical foundation. Additionally, the most recent bounds on constant dimension codes and subspace codes can be found there.

To create CDCs, rank metric codes (RMCs), specifically maximum rank distance (MRD) codes, are employed. One technique for creating CDCs using rank metric codes is the lifting construction [1], which forms a subspace by concatenating an identity matrix with a matrix of RMCs. In the context of random linear network coding, lifted MRD codes can produce asymptotically optimal CDCs and can be decoded effectively. Etzion and Silberstein [10] introduced a new family of Ferrers diagram RMCs to generalize the lifted MRD code architecture, which they called the multilevel construction.

Today, there are primarily two approaches used to build CDCs in conjunction with parallel linkage construction. The first technique is called parallel multilevel construction [11]. Another approach is the block inserting construction, initially introduced in [12]. CDCs built using matrix blocks are inserted into the parallel linkage construction through the block inserting construction.

In [13], MinYao Niu proposed a new method for constructing constant dimension codes. The parallel linkage construction can incorporate the constant dimension codes derived from this method.

In [14], Xianmang He presented a construction for subspace codes of constant dimension that involves the insertion of a composite structure made up of an MRD code and its sub-codes, providing some improved lower bounds over previous results.

Building CDCs is a useful application of lifting Ferrers diagram codes. Furthermore, the discovery of linkage construction enables the creation of a large number of CDCs. In [15], Fagang Li derived some new CDC lower bounds for small parameters by combining the two construction techniques.

In [16], Troha introduced a construction called the linkage construction from Corollary 39 in [17]. This construction involves joining two CDCs of shorter length and results in the establishment of a lower bound for the following CDCs.

$$\begin{array}{cc}\hfill A_q(n,d,k)& \ge A_q(m,d,k)q^{\max \{n-m,k\}(\min \{n-m,k\}-\frac{1}{2}d+1)}\hfill \\ \hfill & +A_q(n-m+k-\frac{d}{2},d,k),\hfill \end{array}$$

(1)

where $k\le m\le n-\frac{d}{2}.$

In this paper, we are inspired by [13,18]. The linkage construction and insertion construction have been effectively improved. The paper is structured as follows: In Section 1, we review some fundamental concepts of CDC. In Section 2, we introduce effective methods for constructing CDCs, including parallel linkage construction, Ferrers diagram construction, and sub-code construction. The main part of this article is in Section 3, where we first propose an improved algorithm based on the greedy algorithm that yields a better set of identification vectors. We then describe an insertion construction method by swapping specific columns of the generator matrix. Using our approach, we derive several new lower bounds.

2. Preliminaries

2.1. Rank-Metric Codes

Over the field ${\mathbb{F}}_q$, let ${\mathbb{F}}_q^{m\times \ell }$ be a $m\times \ell$ matrices space. The rank-metric is defined as follows for any two distinct matrices  $A,B\in {\mathbb{F}}_q^{m\times \ell }$:

$$d_R(A,B):=\mathrm{rank}(A-B).$$

A rank-metric code is a subset of ${\mathbb{F}}_q^{m\times \ell }$ with the rank-metric. We can refer to a rank-metric code as linear rank-metric code if it is a linear subspace of ${\mathbb{F}}_q^{m\times \ell }$. Clearly, the rank-distance of a rank-metric code $\mathcal{C}$ is defined as

$$d_R\left(\mathcal{C}\right):=\min \{d_R(A,B):A,B\in \mathcal{C},A\ne B\}.$$

We know that the upper bound of its cardinality is $q^{\max \{m,\ell \}·\left(\min \right\{m,\ell \}-d+1)}$. A rank-metric code attaining this bound is called an MRD code (see [19,20]). A linear MRD code with distanced d is denoted by $\mathcal{Q}(q,m,n,d)$, and its cardinality is denoted by $a(q,m,n,d)$. Additionally, if the rank of each codewords is at most r, we use the notation $\mathcal{Q}(q,m,n,d;r)$ to represent it, and we refer to it as a rank-restricted RMC (RRMC). Its cardinality is usually denoted by $a(q,m,n,d;r)$.

Lemma 1 

([19]). Let $Q(q,m,n,d)$$(m\ge n)$ is a linear MRD code with rank distance $\le n$. Its rank distribution is given by

$${\mathcal{A}}_r\left(Q(q,m,n,d)\right)=\left(\genfrac{}{}{0pt}{}{n}{r}\right)\sum _{i=0}^{r-d}{(-1)}^i{q}^{\left(\genfrac{}{}{0pt}{}{i}{2}\right)}{\left(\genfrac{}{}{0pt}{}{r}{i}\right)}_q\left(\frac{q^{m(n-d+1)}}{q^{m(n+i-r)}}-1\right),$$

(2)

where $d\le r\le n,{\mathcal{A}}_r\left(Q(q,m,n,d)\right)$ representing the cardinality of codewords in $Q(q,m,n,d)$ with rank r.

2.2. Ferrers Diagram Maximum Rank Distance Codes

Let X be a k-dimensional subspace within a space ${\mathbb{F}}_q^n$. Its structure can be described by a generating matrix whose rows span the bases of X. This generator matrix can be transformed into a unique row-reduced echelon matrix $E\left(X\right)$ using Gaussian elimination. Moreover, we define an identifying vector $v\left(X\right)$, which is labeled with 1 at each pivot position in $E\left(X\right)$, and is located in the space ${\mathbb{F}}_2^n$. The space ${\mathcal{G}}_q(k,n)$ can be classified into $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ distinct classes based on these identifying vectors, with each class having the same identifying vector.

To transform the subspace X into the Ferrers diagram form $\mathcal{F}\left(X\right)$, a series of operations is applied to $E\left(X\right)$. First, any leading zeros in the rows to the left of the pivots are removed. Second, the pivot column is removed, and the remaining entries are shifted to the right. The Ferrers diagram of X, denoted ${\mathcal{F}}_X$, is the resulting processed matrix. ${\mathcal{F}}_X$ and $\mathcal{F}\left(X\right)$ are closely related, and ${\mathcal{F}}_X$ can be obtained by replacing the entries of $\mathcal{F}\left(X\right)$ with dots.

For example, if the generator matrix of a 4-dimensional subspace X in the space ${\mathbb{F}}_2^9$ is reduced to a row-reduced echelon form, the corresponding Ferrers diagram of X can be easily constructed by applying the aforementioned procedures.

$$E\left(X\right)=\left(\begin{array}{ccccccccc}1& 1& 0& 0& 1& 0& 0& 0& 1\\ 0& 0& 1& 1& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 1\end{array}\right).$$

Subsequently, the identifying vector representing X is designated as $v\left(X\right)$ = $101001010.$ Furthermore, ${\mathcal{F}}_X$ is recorded as the Ferrers table form of X, which is

$$\begin{array}{ccccc}1& 0& 1& 0& 0\\ & 1& 0& 0& 0\\ & & & 1& 0\\ & & & & 1\end{array}.$$

And $\mathcal{F}\left(X\right)$ is recorded as the Ferrers diagrams form of X, which is

$$\begin{array}{ccccc}•& •& •& •& •\\ & •& •& •& •\\ & & & •& •\\ & & & & •\end{array}.$$

Definition 1 

([21]). Assume that $v_1$ and $v_2$ are two vectors of length n, $v_i\left[j\right]$ represents the j-th component in the vector $v_i$, $(i=1,2,j=1,2,\cdots ,n)$, The Hamming distance

$$d_H(v_1,v_2)=\sum _{i=1}^{n}N(v_1\left[j\right]\ne v_2\left[j\right])$$

for $v_1,v_2\in {\mathbb{F}}_q^n$, when $v_1\left[j\right]\ne v_2\left[j\right],N(v_1\left[j\right]\ne v_2\left[j\right])=1.$

Lemma 2 

([10]). Let $X,Y\in {\mathcal{P}}_q\left(n\right)$, $v\left(X\right),v\left(Y\right)$ is identifying vector of $X,Y$, then

$$\begin{array}{c}\hfill d_S(X,Y)\ge d_H(v\left(X\right),v\left(Y\right)),\end{array}$$

Definition 2 

([10]). Let $\mathcal{F}$ be a Ferrers diagram, where the rightmost column contains m points and the topmost row contains ℓ points. A linear rank-metric code associated with a Ferrers diagram $\mathcal{F}$ is called a Ferrers diagram rank metric code (FDRM) if it satisfies the following condition: For any code word M in ${\mathcal{C}}_{\mathcal{F}}$, if M is not in some term of $\mathcal{F}$, then the value of that term must be zero. Moreover, for any nonzero code word A, if its rank is no less than δ, the dimension of ${\mathcal{C}}_{\mathcal{F}}$ is $dim.$ Based on these conditions, we represent the FDRM code ${\mathcal{C}}_{\mathcal{F}}$ as the $[\mathcal{F},dim,\delta ]$ FDRM code.

Lemma 3 

([10]). Let $\mathcal{F}$ be a Ferrers diagram, it has ℓ points in the first row, and m points in the last column, and ${\mathcal{C}}_{\mathcal{F}}\subseteq {\mathbb{F}}_q^{m\times \ell }$ is an FDRM code, and it meets the following conditions: $\forall A\in$${\mathcal{C}}_{\mathcal{F}}\setminus \left\{0\right\},$ rank$\left(A\right)\ge \delta$. Then $|{\mathcal{C}}_{\mathcal{F}}|\le q^{{\min }_i\left\{w_i\right\}}$, where $w_i$ represents the number of points in the $\mathcal{F}$ that are neither in the first i row nor in the rightmost $\delta -1-i$ column, where i ranges from 0 to $\delta -1.$

Lemma 4 

([10]). Let ${\mathcal{C}}_{\mathcal{F}}\subseteq {\mathbb{F}}_q^{k\times (n-k)}$ be an $[\mathcal{F},dim,\delta ]$ FDRM code, then the lifted FDRM code ${\mathbb{C}}_{\mathcal{F}}$ is an ${(n,q^{dim},2\delta ,k)}_q$CDC.

In order to construct an ${(n,M,2\delta ,k)}_q$ CDC on ${\mathcal{G}}_q(k,n),$ we first screen out a subset $\mathbb{C}\subseteq {\mathbb{F}}_2^n,$ which has two key properties. Firstly, the weight is equal to k for any vector; secondly is that these vectors have a minimum Hamming distance of $2\delta .$ Then we treat these vectors in $\mathbb{C}$ as identifying vectors, and for each identifying vector, we construct a corresponding $[\mathcal{F},dim,\delta ]$ FDRM code. According to Lemmas 2 and 3, these lifted FDRM codes are combined to form an ${(n,M,2\delta ,k)}_q$ CDC. The structural design on which this construction method is based, which is commonly called multilevel construction (see [10,17]).

2.3. Linkage Construction

Given some matrices $M\in {\mathbb{F}}_q^{k\times m}$, the row space of M over ${\mathbb{F}}_q$ are expressed as the rs$\left(M\right).$

Definition 3 

([16]). Let $\mathcal{M}\subseteq {\mathbb{F}}_q^{k\times m}$ be a set of matrices, if rank$\left(M_j\right)=k$, $M_j\in \mathcal{M}$ and $rs\left(M_{j_1}\right)\ne rs\left(M_{j_2}\right)$ for any two different matrices $M_{j_1},M_{j_2}\in \mathcal{M},$ we denoted it as an SC-representing set. Then the set $\left\{rs\right(M):M\in \mathcal{M}\}$ is CDC, and we denoted it by $\mathcal{C}\left(\mathcal{M}\right).$

Lemma 5 

([22]). Let $n_1\ge k$ and $n_2\ge k,$${\mathcal{Q}}_1$ is an ${(k,n-k,\frac{d}{2})}_q$ MRD code, ${\mathcal{Q}}_2$ is a ${(k,n-k,\frac{d}{2};k-\frac{d}{2})}_q$ RRMC code. Then ${\mathcal{C}}_1\cup {\mathcal{C}}_2$ is an ${(n,N,d,k)}_q$ CDC, where

$$\begin{array}{cc}\hfill {\mathcal{C}}_1& :=\left\{\mathrm{rs}\left(I_k\right|Q_1)\right|Q_1\in {\mathcal{Q}}_1\},\hfill \\ \hfill {\mathcal{C}}_2& :=\left\{\mathrm{rs}\left(Q_2\right|I_k)\right|Q_2\in {\mathcal{Q}}_2\}.\hfill \end{array}$$

Lemma 6 

([15]). Let $n_1\ge k,n_2\ge k,n_1+n_2=n,$$\mathcal{U}$ be an SC-representation set of ${(n_1,N_1,d,k)}_q$ CDC with cardinality $N_1$, and $\mathcal{R}$ be a $(q,k,n_2,\frac{d}{2})$ linear rank metric code with cardinality $N_R$. Assume that the identifying vectors $v_j\in V_S$ with length n and weight k satisfy the following conditions.

(a) For each $v_j$, the number of $ones$ in the last $n_2$ positions is more than or equal to $\frac{d}{2}.$

(b) The Hamming distance of two different identifying vectors is more than or equal to d.

Let ${\mathcal{C}}_{{\mathcal{F}}_j}\subseteq {\mathbb{F}}_q^{k\times (n-k)}$ be an $[{\mathcal{F}}_j,{\rho }_j,\delta =\frac{d}{2}]$ FDRM code, with the corresponding identifying vector $v_j$, ${\mathbb{C}}_{{\mathcal{F}}_j}$ are lifted FDRM code of $C_{{\mathcal{F}}_j}$. Define $\mathcal{C}:=\mathcal{A}\cup \mathcal{B}$ as the subspace code of length n, where

$$\begin{array}{cc}\hfill \mathcal{A}& :=\left\{\mathrm{rs}\right(U\left|R\right)|U\in \mathcal{U},R\in \mathcal{R}\},\hfill \\ \hfill \mathcal{B}& :={\cup }_j{\mathbb{C}}_{{\mathcal{F}}_j}.\hfill \end{array}$$

Then $\mathcal{C}:=\mathcal{A}\cup \mathcal{B}$ is an ${(n,N,d,k)}_q$ CDC with $N=N_1{N}_R+{\sum }_j|{\mathbb{C}}_{{\mathcal{F}}_j}|$.

2.4. Sub-Codes Construction

Lemma 7 

([23]). The sub-codes construction can be described as follows: Let $n_1$, $n_2$, $a_1$, $a_2$, $b_1$, $b_2$ be positive integers such that $n_1+n_2=n,a_1+a_2=k$, and $b_1+$ $b_2\ge \frac{d}{2}$. For $i=1,2$, assume ${\mathcal{M}}_i^r$ is a $\left(q,a_i,n_i,\frac{d}{2}\right)$ MRD code, where $r=1,2,\dots ,s$, $s=min\left\{\frac{a(q,a_1,n_1-a_1,b_1)}{a(q,a_1,n_1-a_1,\frac{d}{2})},\frac{a(q,a_2,n_2-a_2,b_2)}{a\left(q,a_2,n_2-a_2,\frac{d}{2}\right)}\right\}$. For any $M\in {\mathcal{M}}_i^{r_1}$ and $M^{\prime }\in {\mathcal{M}}_i^{r_2}$ (where $1\le r_1,r_2\le s$, and $M\ne$$M^{\prime })$, we know that when $r_1=r_2$, rank$(M-M^{\prime })\ge \frac{d}{2}$, and when $r_1\ne r_2$, rank$(M-M^{\prime })\ge b_i.$ Then $D={\bigcup }_{r=1}^s{D}_r$ is an ${(n,|D|,d,k)}_q$ CDC, where $D_r$ consists of subspaces of the form:

$$\left(\begin{array}{cc}{I}_{a_1}|M_1& O_1\\ O_2& I_{a_2}|M_2\end{array}\right),$$

${\mathcal{M}}_1\in {\mathcal{M}}_1^r$, ${\mathcal{M}}_2\in {\mathcal{M}}_2^r$. $I_{a_i}$ is the identity matrix of size $a_i\times a_i$, and $O_1$, $O_2$ are zero matrices of size $a_1\times n_2$ and $a_2\times n_1$.

Lemma 8 

([14]). Suppose $n_1,n_2,a_1,a_2$ are positive integers such that $n_1+n_2=n,a_1+a_2=k$ and $n_i\ge k,\frac{d}{2}\le a_i\le n_i-\frac{d}{2}$, for $i=1,2,$${\mathcal{M}}_1^r$ and ${\mathcal{M}}_2^r$ be as defined above. Let ${\mathcal{M}}_3$ be an ${(a_1,n_2-a_2,\frac{d}{2})}_q$ MRD code. Then ${\mathcal{C}}_3={\bigcup }_{r=1}^s{\mathcal{C}}^r$ is an ${(n,d,k)}_q$ CDC with

$${\mathcal{C}}^r=\left\{rs\left(\begin{array}{ccccccc}{I}_{a_1}& & M_1& & O_1& & M_3\\ O_2& & O_3& & I_{a_2}& & M_2\end{array}\right)\right\},$$

where $M_1\in {\mathcal{M}}_1^r,M_2\in {\mathcal{M}}_2^r$ for $1\le r\le s,$ and $M_3\in {\mathcal{M}}_3,O_1,O_2,O_3$ are zero matrices with $O_1=O_{a_1\times a_2},O_2=O_{a_2\times a_1},O_3=O_{a_2\times (m_1-a_1)}.$

3. Main Results

In this section, we first propose Algorithm 1, which incorporates the construction method from Lemma 6. With the help of this algorithm, we obtain improved new lower bounds for linkage construction and echelon-Ferrers constructions. Then, inspired by [13], we refine the insertion construction by swapping specific columns of the generator matrix, and as a result, we derive several new lower bounds.  

Algorithm 1: Modified greedy algorithm

3.1. Algorithm

Regarding recent improvements in the echelon-Ferrers construction, we refer to [18]. As for improvements in linkage construction, determining the optimal parameters for a new set of identifying vectors is a challenging problem. In this part, we use an improved algorithm based on a greedy approach to obtain a better set of identifying vectors, denoted by $V_S$.

We made a minor enhancement to the greedy algorithm, focusing on selecting the identifying vectors with the maximum and second maximum dimensions as the best candidates. That is, we randomly added the identifying vectors from $max$ and $max-1$ to the set $V_S$ until the set $V_n$ was empty. Finally, after repeated experiments, we selected the final result.

Corollary 1.

$A_2(14,4;4)\ge 1259181405$ and $A_q(14,4;4)\ge q^{30}+q^{26}+q^{25}+3q^{24}+2q^{23}+3q^{22}+q^{21}+q^{20}+2q^{18}+2q^{16}+3q^{15}+5q^{14}+6q^{12}+7q^{11}+9q^{10}+7q^9+8q^8+5q^7+3q^6+q^4+q^3+q^2+1$ for $q\ge 2.$

Proof. 

Let $n_1=8,n_2=6$, and  ${\mathbb{C}}_{{\mathcal{F}}_j}$ be lifted FDRM code corresponding to the identifying vector in

Table A1. Construction for $A_q(14,4,4)$.

	Identifying Vector	Dimension		Identifying Vector	Dimension
1	11000000110000	18	31	00000110011000	11
2	00110000110000	16	32	00010100100001	10
3	10100000101000	16	33	00001001100100	10
4	00001100110000	14	34	00101000001001	9
5	01100000011000	15	35	10000010100001	9
6	01100000100100	15	36	00100010001010	8
7	01010000101000	15	37	00011000000110	9
8	10010000100100	14	38	10001000000101	8
9	10100000010100	14	39	01000100010001	9
10	10010000011000	14	40	00110000000011	8
11	11000000001100	14	41	10000100001001	8
12	00110000001100	12	42	01010000000101	9
13	10001000100010	12	43	00010001100010	9
14	00000011110000	12	44	00010100001010	9
15	01010000010010	12	45	00100010010001	8
16	00001010101000	12	46	00000011001100	8
17	01001000010100	12	47	00100001100001	8
18	00010100010100	11	48	01000100000110	8
19	00100100100010	11	49	10000010000110	7
20	00011000010001	10	50	01000010001001	7
21	01001000100001	11	51	00010001001001	6
22	00000101101000	11	52	00100001000110	6
23	01000010100010	10	53	00001100000011	6
24	00001100001100	10	54	00100100000101	7
25	00001001011000	10	55	10000001010001	7
26	00101000010010	11	56	10000001001010	7
27	00000110100100	11	57	00000000111001	3
28	01001000001010	10	58	00000011000011	4
29	11000000000011	10	59	00000000110110	2
30	10000100010010	10	60	00000000001111	0

, by Lemma 6, so we have $A_q(14,4;4)\ge A_q(8,4;4)q^{18}+q^{18}+2q^{16}+3q^{15}+5q^{14}+6q^{12}+7q^{11}+9q^{10}+7q^9+8q^8+5q^7+3q^6+q^4+q^3+q^2+1$, it is known that $A_2(8,4;4)\ge 4801$and$A_q(8,4;4)\ge q^{12}+q^2{(q^2+1)}^2(q^2+q+1)+1$for$q\ge 2$. The result is obviously valid.    □

The best known lower bound is given in [24], i.e., $A_2(14,4;4)\ge 1259181253$ for $q=2.$ Our result is above it.

Corollary 2.

$A_2(18,4;4)\ge 5158164361445$ and $A_q(18,4;4)\ge A_q(12,4;4)q^{18}+q^{22}+2q^{20}+3q^{19}+5q^{18}+6q^{16}+7q^{15}+10q^{14}+6q^{13}+12q^{12}+9q^{11}+8q^{10}+q^9+5q^8+2q^7+3q^6+2q^4+q^2+1$ for $q\ge 2.$

Proof. 

Let $n_1=12,n_2=6$, and  ${\mathbb{C}}_{{\mathcal{F}}_j}$ be lifted FDRM code corresponding to identifying vector in

Table A2. Construction for $A_q(18,4,4)$.

	Identifying Vector	Dimension		Identifying Vector	Dimension
1	110000000000110000	22	43	010000010000100001	12
2	101000000000101000	20	44	010000100000001010	12
3	001100000000110000	20	45	010100000000000101	13
4	010100000000101000	19	46	001001000000010001	13
5	100100000000100100	18	47	000000110000001100	12
6	110000000000001100	18	48	001010000000001001	13
7	100100000000011000	18	49	000100100000010001	12
8	101000000000010100	18	50	001001000000001010	13
9	011000000000011000	19	51	000000001010101000	12
10	011000000000100100	19	52	000000000011110000	12
11	000011000000110000	18	53	100000010000000110	10
12	100010000000100010	16	54	001000000100100010	11
13	000110000000010100	16	55	000011000000000011	10
14	001100000000001100	16	56	000000000110011000	11
15	000010100000101000	16	57	001000100000000110	11
16	010100000000010010	16	58	100000001000001010	10
17	000000110000110000	16	59	100000010000010001	11
18	000110000000100001	15	60	000000101000010010	11
19	000001100000011000	15	61	000000000101101000	11
20	100001000000010010	14	62	000000001001011000	10
21	110000000000000011	14	63	000000001100001100	10
22	000110000000001010	14	64	000100010000001001	10
23	010001000000010100	15	65	100000100000001001	11
24	010001000000100010	15	66	000000100100010100	11
25	100001000000100001	14	67	000000010100010010	10
26	000001010000101000	15	68	000000000110100100	11
27	010010000000010001	14	69	000000001001100100	10
28	000010010000011000	14	70	001000010000000101	9
29	000100100000100010	14	71	000000001010010001	8
30	000011000000001100	14	72	000001001000000101	8
31	001010000000010010	15	73	000000010010001010	8
32	000010010000100100	14	74	000000110000000011	8
33	000001100000100100	15	75	000000000011001100	8
34	000000001100110000	14	76	000000001010000110	7
35	000101000000000110	12	77	000000001100000011	6
36	001000100000100001	13	78	000000100010000101	6
37	000000011000100010	12	79	000000000101010001	7
38	010001000000001001	12	80	000000000101000110	6
39	100010000000000101	12	81	000000000000111100	4
40	001100000000000011	12	82	000000000011000011	4
41	010010000000000110	13	83	000000000000110011	2
42	000000011000010100	12	84	000000000000001111	0

, by Lemma 6 and $A_2(12,4;4)\ge 19676797$. The result is obviously valid.    □

The best known lower bound is given in [24], i.e., $A_2(18,4;4)\ge 5158164354661$ for $q=2.$ Our result is above it.

3.2. Construction

Niu et al. presented an improved inserting construction by exchanging some specified columns of the generator matrix of the CDC in [13]. Based on this, we have enhanced the column-swapping procedure.

Proposition 1.

Let $v_i\in V_d$ be a vector with length $n_1-a_1+a_2$ and weight $a_2$, where $n_1-a_1=a_2=d-1$, and the number of ones in the last $a_2$ positions of $v_i$ is at least $\frac{d}{2}$, the Hamming distance between distinct vectors in $V_d$ is at least d. Then, the set $V_d$ contains at least $d-1$ distinct vectors.

Next, we explain Proposition 1 using Algorithm 2.    

Algorithm 2: $get{V}_d$

Input: d   Output: target vector set $V_d$   1 Construct an alternative element set: V contains all vectors with length $n=2(d-1)$ and weight $d-1$, and the number of $ones$ in the last $d-1$ positions is at least $\frac{d}{2}$   2 Select a vector, and if its Hamming distance from other vectors in $V_d$ is at least d, add it to $V_d$   3 Repeat step 2 until V is empty.

We present a portion of the results here. When $d=4,6$ and 8, as shown in

Table 1. Identifying vector set $V_d$.

d		${\mathit{V}}_{\mathit{d}}$
4	${\mathit{v}}_1=100011$		${\mathit{v}}_2=001110$
	${\mathit{v}}_3=010101$
6	${\mathit{v}}_1=0101011001$		${\mathit{v}}_2=0001110110$
	${\mathit{v}}_3=1010010011$		${\mathit{v}}_4=0110001110$
	${\mathit{v}}_5=1000101101$
8	${\mathit{v}}_1=01101001001011$		${\mathit{v}}_2=10100100101101$
	${\mathit{v}}_3=01000111011100$		${\mathit{v}}_4=00110011100110$
	${\mathit{v}}_5=11010000010111$		${\mathit{v}}_6=10001010111010$
	${\mathit{v}}_7=00011101110001$

.

Theorem 1.

Using the notation from Lemma 6, $n_1=n_2=k,$$k\ge d$, ${\mathcal{M}}_3$ is an ${(a_1,n_2-a_2,\frac{d}{2};a_1-d+1)}_q$ RRMC code. Let ${\mathcal{C}}_i^r$ be obtained by swapping columns $\left(\genfrac{}{}{0pt}{}{M_1}{O_3}\right)$ and $\left(\genfrac{}{}{0pt}{}{O_1}{I_{a_2}}\right)$ of ${\mathcal{C}}^r$, and $v\left({\mathcal{C}}_i^r\right)=\left(\stackrel{a_1}{\overbrace{1\cdots 1}}\stackrel{n_1-a_1+a_2}{\overbrace{v_i}}\stackrel{n_2-a_2}{\overbrace{0\cdots 0}}\right),$$v_i\in V_d$. Then ${\mathcal{C}}_3:={\bigcup }_{i=1}^{d-1}{\bigcup }_{r=1}^s{\mathcal{C}}_i^r$ is an $(n,|{\mathcal{C}}_3{|,d,k)}_q$ CDC with $|{\mathcal{C}}_3|={\bigcup }_{i=1}^{d-1}{\bigcup }_{r=1}^s\left|{\mathcal{C}}_i^r\right|$.

Proof. 

From $a_1+a_2=k$, it is easy to see that the codewords of ${\mathcal{C}}_3$ form a k-dimensional subspace of ${\mathbb{F}}_q^n.$ The minimum subspace distance of ${\mathcal{C}}_3$ is at least d, as proven from two aspects:

Let the sets $W_3$ and $W_3^{\prime }$ be the distinct codewords of and $C_{i_1}^r$ and $C_{i_2}^r$.

$W_3=rs\left(G_3\right),G_3=\left(\begin{array}{cccc}{I}_{a_1}& P& S& M_3\\ 0_2& Q& T& M_2\end{array}\right),$

$W_3^{\prime }=rs\left(G_3^{\prime }\right),G_3^{\prime }=\left(\begin{array}{cccc}{I}_{a_1}& P^{\prime }& S^{\prime }& {M_3}^{\prime }\\ 0_2& Q^{\prime }& T^{\prime }& {M_2}^{\prime }\end{array}\right),$

• where $M_1,M_1^{\prime }\in {\mathcal{M}}_1^r,M_2,M_2^{\prime }\in {\mathcal{M}}_2^r,M_3,M_3^{\prime }\in {\mathcal{M}}_3.$

I. If $i_1=i_2$, that is, the positions of the swapped columns are the same, this is equivalent to proving that ${\mathcal{C}}_i^r$ are CDCs for $1\le i\le d-1.$

$\begin{array}{cc}\hfill d_S\left(W_3,W_3^{\prime }\right)& =2\mathrm{rank}\left(\begin{array}{cccc}{I}_{a_1}& P& S& M_3\\ O_2& Q& T& M_2\\ I_{a_1}& P^{\prime }& S^{\prime }& M_3^{\prime }\\ O_2& Q^{\prime }& T^{\prime }& M_2^{\prime }\end{array}\right)-2k,\hfill \\ & =2\mathrm{rank}\left(\begin{array}{cccc}{I}_{a_1}& M_1& O_1& M_3\\ O_2& O_3& I_{a_2}& M_2\\ I_{a_1}& M_1^{\prime }& O_1& M_3^{\prime }\\ O_2& O_3& I_{a_2}& M_2^{\prime }\end{array}\right)-2k,\hfill \\ & =2\mathrm{rank}\left(\begin{array}{cccc}{I}_{a_1}& M_1& O_1& M_3\\ O_{a_1}& M_1^{\prime }-M_1& O_1& M_3^{\prime }-M_3\\ O_2& O_3& I_{a_2}& M_2\\ O_2& O_3& O_{a_2}& M_2^{\prime }-M_2\end{array}\right)-2k.\hfill \end{array}$

There are the following three cases.

(1) if $M_3\ne M_3^{\prime }$ then rank$\left(\genfrac{}{}{0pt}{}{G_5}{G_5^{\prime }}\right)\ge a_1+a_2+\mathrm{rank}\left(M_3^{\prime }-M_3\right)\ge k+\frac{d}{2}$.

(2) if $M_3=M_3^{\prime },r=r^{\prime },M_1,M_1^{\prime }\in {\mathcal{M}}_1^r,M_2,M_2^{\prime }\in {\mathcal{M}}_2^r$, that is $M_1\ne M_1^{\prime }$ or $M_2\ne M_2^{\prime }$, then $\mathrm{rank}\left(\begin{array}{c}{G}_5\\ G_5^{\prime }\end{array}\right)=a_1+a_2+\mathrm{rank}\left(M_1^{\prime }-M_1\right)+\mathrm{rank}\left(M_2^{\prime }-M_2\right)\ge k+\frac{d}{2}$.

(3) if $M_3=M_3^{\prime },r\ne r^{\prime }$, $M_1\in M_1^r,M_1^{\prime }\in M_1^{r^{\prime }},M_2\in M_2^r,M_2^{\prime }\in M_2^{r^{\prime }},M_1\ne M_1^{\prime },M_2\ne M_2^{\prime }$. then $\mathrm{rank}\left(\begin{array}{c}{G}_5\\ G_5^{\prime }\end{array}\right)=a_1+a_2+\mathrm{rank}\left(M_1^{\prime }-M_1\right)+\mathrm{rank}\left(M_2^{\prime }-M_2\right)=a_1+a_2+b_1+b_2\ge k+\frac{d}{2}.$

II. If $i_1\ne i_2$, that is the positions of the swapped columns are different, this is equivalent to proving that the subspace distance between $C_{i_1}^r$ and $C_{i_2}^r$ is at least d for $i_1\ne i_2.$

It easy to see that $d_H\left(G_3,G_3^{\prime }\right)=d_H\left(v_{i_1},v_{i_2}\right)\ge d.$ By Lemma 2, $d_S(v\left({\mathcal{C}}_{i_1}^r\right),v\left({\mathcal{C}}_{i_2}^r\right))\ge d.$

Hence, ${\mathcal{C}}_3$ is an $(n,|{\mathcal{C}}_3{|,d,k)}_q$ CDC with $|{\mathcal{C}}_3|=$ ${\bigcup }_{i=1}^{d-1}{\bigcup }_{r=1}^s\left|{\mathcal{C}}_i^r\right|.$ □

Example 1.

Let $n_1=n_2=k=12$, $d=6$, $a_1=7$, $a_2=5$, $b_1=1$, $b_2=2$. By Theorem 1, we take $M_1\in {\mathcal{M}}_1^r$ and $M_2\in {\mathcal{M}}_2^r$, where $M_1^r$ is an $(q,7,5,3)$ MRD code, ${\mathcal{M}}_2^r$ is an $(q,5,7,3)$ MRD code, $1\le r\le s$, $s=min$$\left\{\frac{a(q,a_1,n_1-a_1,b_1)}{a\left(q,a_1,n_1-a_1,\frac{d}{2}\right)},\frac{a(q,a_2,n_2-a_2,b_2)}{a\left(q,a_2,n_2-a_2,\frac{d}{2}\right)}\right\}$, and $M_3$ is a $\left(q,7,7,3;2\right)$ RRMC code. The following are the generator matrices of ${\mathcal{C}}_i^r$ for $1\le i\le 5$. Then ${\mathcal{C}}_4={\bigcup }_{r=1}^5{\bigcup }_{i=1}^s{\mathcal{C}}_i^r$ is an $(n,|{\mathcal{C}}_4{|,d,k)}_q$ CDC.

Theorem 2.

With the same notations as Theorem 1. Let ${\mathcal{C}}_1$ and ${\mathcal{C}}_2$ be as in Lemma 5, and ${\mathcal{C}}_3$ as in Theorem 1. Then $\mathcal{C}:={\mathcal{C}}_1\cup {\mathcal{C}}_2\cup {\mathcal{C}}_3$ is an ${(n,|\mathcal{C}|,d,k)}_q$ CDC with $\left|\mathcal{C}\right|=|{\mathcal{C}}_1|+|{\mathcal{C}}_2|+|{\mathcal{C}}_3|$.

Proof. 

Let $W_1\in {\mathcal{C}}_1,W_2\in {\mathcal{C}}_2,W_3\in {\mathcal{C}}_3$, and $W_1=rs\left(G_1\right),G_1=rs\left(I_k\right|Q_1),$

$W_2=rs\left(G_2\right),G_2=rs\left(Q_2\right|I_k),$

$W_3=rs\left(G_3\right),G_3=rs\left(\begin{array}{cccc}{I}_{a_1}& P& S& M_3\\ O_2& Q& T& M_2\end{array}\right),$

• where $Q_1\in {\mathcal{Q}}_1,Q_2\in {\mathcal{Q}}_2,M_1\in {\mathcal{M}}_1^r,M_2\in {\mathcal{M}}_2^r,$ and $M_3\in {\mathcal{M}}_3.$

The proof is composed of two parts:

I. The subspace distance between CDCs ${\mathcal{C}}_1$ and ${\mathcal{C}}_3$ is at least d.

It is easy to see that the identifying vector corresponding to $W_1$ is $v\left(G_1\right)=(\stackrel{k}{\overbrace{1\cdots 1}}\stackrel{n-k}{\overbrace{0\cdots 0}}).$ by $V_d$ and $n_1=n_2=k$, it follows that $v\left(G_3\right)$ has at least $\frac{d}{2}$ ones in the last k position, and at most $k-\frac{d}{2}$ ones in the first k position. Then $d_H(v\left(G_1\right),v\left(G_3\right))\ge k-(k-\frac{d}{2})+\frac{d}{2}=d.$ Therefore, by Lemma 2, we have $d_S({\mathcal{C}}_1,{\mathcal{C}}_3)\ge d_H(v\left(G_1\right),v\left(G_3\right))\ge d$.

II. The subspace distance between CDCs ${\mathcal{C}}_2$ and ${\mathcal{C}}_3$ is at least d.

$$\dim (W_2+W_3)=\mathrm{rank}\left(\begin{array}{ccc}B& & I_k\\ I_{a_1}& P& S& M_3\\ O_2& Q& T& M_2\end{array}\right)=\mathrm{rank}\left(\begin{array}{ccc}{I}_k& & B\\ S& M_3& I_{a_1}& P\\ T& M_2& 0_2& Q\end{array}\right).$$

$$\begin{array}{cc}\hfill \mathrm{rank}\left(\begin{array}{cc}S& M_3\\ T& M_2\end{array}\right)& \le \mathrm{rank}\left(S\right|M_3)+\mathrm{rank}\left(T\right|M_2)\hfill \\ & \le \mathrm{rank}\left(S\right)+\mathrm{rank}\left(M_3\right)+a_2\hfill \\ & \le \frac{d}{2}-1+\mathrm{rank}\left(M_3\right)+a_2\hfill \\ & \le \frac{d}{2}-1+a_1-d+1+a_2=k-\frac{d}{2},\hfill \end{array}$$

where rank$\left(S\right)\le \frac{d}{2}-1$ because there is at most $\frac{d}{2}-1$ non-zero columns in S. Then, $\dim (W_2^{\prime }\cap W_3^{\prime })\le k-\frac{d}{2}$. Let $W_2^{\prime }=rs\left(I_k\right|B),W_3^{\prime }=rs\left(\begin{array}{cccc}S& M_3& I_{a_1}& P\\ T& M_2& O_2& T\end{array}\right)$, we have

$\begin{array}{cc}\hfill d_S(W_2,W_3)& =2\dim (W_2+W_3)-2k\hfill \\ & =2\dim (W_2^{\prime }+W_3^{\prime })-2k\hfill \\ & =2k-2\dim (W_2^{\prime }\cap W_3^{\prime }).\hfill \end{array}$

Hence, we can obtain $d_S(W_2,W_3)=2k-2\dim (W_2^{\prime }\cap W_3^{\prime })\ge d.$

Combining all the aforementioned discussions, we arrive at the conclusion that $\mathcal{C}:={\mathcal{C}}_1\cup {\mathcal{C}}_2\cup {\mathcal{C}}_3$ is an $(n,|\mathcal{C}|,d,k)q$ CDC with $\left|\mathcal{C}\right|=|{\mathcal{C}}_1|+|{\mathcal{C}}_2|+|{\mathcal{C}}_3|$. □

Corollary 3.

By Theorem 2, we have

$A_q(n,d,k)\ge |{\mathcal{C}}_1|+|{\mathcal{C}}_2|+|{\mathcal{C}}_3|=a(q,k,n-k,\frac{d}{2})+a(q,k,n-k,\frac{d}{2};k-\frac{d}{2})+(d-1)·s·a(q,a_1,n_2-a_2,\frac{d}{2})·a(q,a_2,n_2-a_2,\frac{d}{2})·a(q,a_2,n_2-a_2,\frac{d}{2};a_1-d+1).$

Corollary 4.

For $d=6$ and $d_1=1$, $d_2=2$, we have

$A_q(14,6,7)\ge q^{35}+(1+{\sum }_{r=3}^4{\mathcal{A}}_r\left(Q(q,7,7,3)\right)+5q^{12}).$

$A_q(16,6,8)\ge q^{48}+(1+{\sum }_{r=3}^5{\mathcal{A}}_r\left(Q(q,8,8,3)\right)+5q^{15}).$

$A_q(18,6,9)\ge q^{63}+(1+{\sum }_{r=3}^6{\mathcal{A}}_r\left(Q(q,9,9,3)\right)+5q^{25}).$

Example 2.

By Corollary 4, we have

$A_2(14,6,7)\ge 34532258504$,

$A_5(16,6,8)\ge 3552716061446350546877864809763610$,

$A_9(18,6,9)\ge 1310020512493866349004817889700802603385869505242199741941650$,

• which improve the lower bounds in [13].

4. Conclusions

This paper presents two improved construction methods for CDCs. First, we propose an enhanced algorithm that combines linkage structures and echelon-Ferrers designs, improving the lower bounds of $A_2(14,4;4)$ and $A_2(18,4;4)$. Secondly, we enhance the inserting construction through column transformations of the generator matrix and obtain new lower bounds for $A_2(14,6;7)$, $A_5(16,6;8)$, and $A_9(18,6;9)$. We hope that these construction methods and the algorithms for computing identifying vectors will provide inspiration for the construction of other CDCs.