Cyclic and Negacyclic Sum-Rank Codes

The Hamming weight $wt_{H}({\bf a})$ of a vector ${\bf a}=(a_{1},\ldots,a_{n})\in{\bf F}_{q}^{n}$ is the cardinality of its support

$$supp({\bf a})=\{i:a_{i}\neq 0\}.$$

The Hamming distance $d_{H}({\bf a},{\bf b})$ between two vectors ${\bf a}$ and ${\bf b}$ is defined to be the Hamming weight of ${\bf a}-{\bf b}$. For a code ${\bf C}\subset{\bf F}_{q}^{n}$, its minimum Hamming distance is

$$d_{H}=\min_{{\bf a}\neq{\bf b}}\{d_{H}({\bf a},{\bf b}):{\bf a},{\bf b}\in{\bf C}\}.$$

It is well-known that the Hamming distance of a linear code ${\bf C}$ is the minimum Hamming weight of its non-zero codewords. For the theory of error-correcting codes in the Hamming metric, the reader is referred to [36, 30, 28]. A code ${\bf C}$ in ${\bf F}_{q}^{n}$ of minimum distance $d_{H}$ and cardinality $M$ is called an $(n,M,d_{H})_{q}$ code. The code rate is $R({\bf C})=\frac{\log_{q}M}{n},$ and the relative distance is $\delta({\bf C})=\frac{d_{H}}{n}.$ For an $[n,k,d_{H}]_{q}$ linear code, the Singleton bound asserts that $d_{H}\leq n-k+1$. When the equality holds, this code is called a maximal distance separable (MDS) code. Reed-Solomon codes are well-known MDS codes [28]. Some BCH codes and Goppa codes can be considered as subfield subcodes of generalized Reed-Solomon codes, and contain examples of optimal binary codes for many parameters ([36, 28, 24]).

The rank-metric distance on the space ${\bf F}_{q}^{(n,m)}$ of size $n\times m$ matrices over ${\bf F}_{q}$, where $n\leq m$, is defined by $d_{r}(A,B)=\mathrm{rank}(A-B)$. The minimum rank-distance of a code ${\bf C}\subset{\bf F}_{q}^{(n,m)}$ is

$$d_{r}({\bf C})=\min_{A\neq B}\{d_{r}(A,B):A,B\in{\bf C}\}.$$

For a code ${\bf C}$ in ${\bf F}_{q}^{(m,n)}$ with the minimum rank distance $d_{r}({\bf C})\geq d$, the Singleton-like bound asserts that the number of codewords in ${\bf C}$ is upper bounded by $q^{m(n-d+1)}$ [23]. A code satisfying the equality is called a maximal rank distance (MRD) code. The Gabidulin code in ${\bf F}_{q}^{(n,n)}$ consists of ${\bf F}_{q}$-linear mappings on ${\bf F}_{q}^{n}\cong{\bf F}_{q^{n}}$ defined by $q$-polynomials $a_{0}x+a_{1}x^{q}+\cdots+a_{i}x^{q^{i}}+\cdots+a_{t}x^{q^{t}}$, where $a_{t},\ldots,a_{0}$ are arbitrary elements in ${\bf F}_{q^{n}}$ [23]. Then the minimum rank-distance of the Gabidulin code is at least $n-t$ since each nonzero $q$-polynomial above has at most $q^{t}$ roots in ${\bf F}_{q^{n}}$. There are $q^{n(t+1)}$ such $q$-polynomials. Hence the size of the Gabidulin code is $q^{n(t+1)}$ and it is an MRD code.

Sum-rank codes were introduced in [49] for their applications in multishot network coding (see also [39, 45]). The sum-rank codes were used to construct space-time codes [53], and codes for distributed storage ([12, 40, 37]). There have been some papers on upper bounds, constructions and applications of sum-rank codes in recent years (see, e.g., [11, 10, 37, 38, 39, 42, 41, 47, 48, 44] and references therein). Fundamental properties and some bounds on sizes of sum-rank codes were given in [10]. For a nice survey of sum-rank codes and their applications, the reader is referred to [43].

We recall some basic concepts and results for sum-rank codes from [10]. Let ${\bf F}_{q}^{(n,m)}$ be the set of all $n\times m$ matrices over ${\mathbf{{F}}}_{q}$. This is a linear space over ${\bf F}_{q}$ of dimension $nm$. Let $n_{i}\leq m_{i}$ be $2t$ positive integers satisfying $m_{1}\geq m_{2}\geq\cdots\geq m_{t}$. Set $N=n_{1}+\cdots+n_{t}$. Let

$${\bf F}_{q}^{(n_{1},m_{1}),\ldots,(n_{t},m_{t})}={\bf F}_{q}^{(n_{1},m_{1})}\bigoplus\cdots\bigoplus{\bf F}_{q}^{(n_{t},m_{t})}$$

be the set of all ${\bf x}=({\bf x}_{1},\ldots,{\bf x}_{t})$, ${\bf x}_{i}\in{\bf F}_{q}^{(n_{i}\times m_{i})}$, $i=1,\ldots,t$. This is a linear space over ${\bf F}_{q}$ of dimension $\Sigma_{i=1}^{t}n_{i}m_{i}$. Set

$$wt_{sr}({\bf x})=\Sigma_{i=1}^{t}\mathrm{rank}({\bf x}_{i}),$$

where ${\bf x}=({\bf x}_{1},\ldots,{\bf x}_{t})\in{\bf F}_{q}^{(n_{1},m_{1}),\ldots,(n_{t},m_{t})}$. The sum-rank distance between two vectors ${\bf x}$ and ${\bf y}$ in ${\bf F}_{q}^{(n_{1},m_{1}),\ldots,(n_{t},m_{t})}$ is

$$d_{sr}({\bf x},{\bf y})=wt_{sr}({\bf x}-{\bf y})=\Sigma_{i=1}^{t}\mathrm{rank}({\bf x}_{i}-{\bf y}_{i}),$$

where ${\bf x}=({\bf x}_{1},\ldots,{\bf x}_{t})$ and ${\bf y}=({\bf y}_{1},\ldots,{\bf y}_{t})$ in ${\bf F}_{q}^{(n_{1},m_{1}),\ldots,(n_{t},m_{t})}$. This is indeed a metric on ${\bf F}_{q}^{(n_{1},m_{1}),\ldots,(n_{t},m_{t})}$.

A subset ${\mathbf{{C}}}$ of the finite space ${\bf F}_{q}^{(n_{1},m_{1}),\ldots,(n_{t},m_{t})}$ with the sum-rank metric is called a sum-rank code with block length $t$ and matrix sizes $n_{1}\times m_{1},\ldots,n_{t}\times m_{t}$. Its minimum sum-rank distance is defined by

$$d_{sr}({\bf C})=\min_{{\bf x}\neq{\bf y},{\bf x},{\bf y}\in{\bf C}}d_{sr}({\bf x},{\bf y}).$$

The code rate of ${\bf C}$ is $R_{sr}=\frac{\log_{q}|{\bf C}|}{\Sigma_{i=1}^{t}n_{i}m_{i}}$. The relative distance is $\delta_{sr}=\frac{d_{sr}}{N}$. When ${\bf C}\subset{\bf F}_{q}^{(n_{1},m_{1}),\ldots,(n_{t},m_{t})}$ is a linear subspace of the linear space ${\bf F}_{q}^{(n_{1},m_{1}),\ldots,(n_{t},m_{t})}$ over ${\bf F}_{q}$, ${\bf C}$ is called a linear sum-rank code. When $q=2$, this code is called a binary sum-rank code.

In general it is interesting to construct good sum-rank codes with large sizes and large minimum sum-rank distances, and develop their decoding algorithms. When $t=1$, this is the rank-metric code case [23]. When $m_{1}=\cdots=m_{t}=m$ and $n_{1}=\cdots=n_{t}=n$, this is the $t$-sum-rank code over ${\bf F}_{q^{m}}$ with length $nt$. When $m=n=1$, this is the Hamming metric code case. Hence the sum-rank coding is a generalization of the the Hamming metric coding and the rank-metric coding. When $q=2$ and $n_{1}=\cdots=n_{t}=m_{1}=\cdots=m_{t}=2$, sum-rank codes are in the space ${\bf F}_{2}^{(2,2),\ldots,(2,2)}={\bf F}_{2}^{(2,2)}\bigoplus\cdots\bigoplus{\bf F}_{2}^{(2,2)}$, this is the generalization of the binary Hamming metric codes to the sum-rank codes of the matrix size $2\times 2$. In the fundamental paper [41] by U. Martínez-Peñas, many linear binary sum-rank BCH codes of matrix size $2\times 2$ were constructed, and their decoding algorithms were given.

The Singleton-like bound on sum-rank codes was proposed in [40, 10]. The general form of the bound given in Theorem III.2 in [10] is as follows. The minimum sum-rank distance $d_{sr}$ can be written uniquely in the form $d_{sr}=\Sigma_{i=1}^{j-1}n_{i}+\delta+1$ where $0\leq\delta\leq n_{j}-1$, then

$$|{\bf C}|\leq q^{\Sigma_{i=j}^{t}n_{i}m_{i}-m_{j}\delta}.$$

A code attaining this bound is called a maximal sum-rank distance (MSRD) code. When $m_{1}=\cdots=m_{t}=m$, this bound is of the form

$$|{\bf C}|\leq q^{m(N-d_{sr}+1)}.$$

It is clear that when $t=1$, this is the Singleton-like bound for rank-metric codes, and when $n=m=1$, this is the Singleton bound for codes in the Hamming metric. For constructions of some MSRD codes, the reader is referred to [10, 42, 14]. Linearized Reed-Solomon codes, which are the sum-rank versions of the classical Reed-Solomon codes, were introduced and studied in [37]. Their Welch-Berlekamp decoding algorithm was presented in [39].

There have been several constructions of sum-rank codes with good parameters. The analogue sum-rank codes of Hamming codes and simplex codes were given in [38]. Sum-rank Hamming codes have the minimum sum-rank distance three and are perfect. The reader is referred to [37] and [41] for linearized Reed-Solomon codes. Twisted linearized Reed-Solomon codes were constructed in [47]. Cyclic-skew-cyclic (CSC) sum-rank codes of the matrix size $n_{1}=\cdots=n_{t}=n$, $m_{1}=\cdots=m_{t}=m$ were proposed and studied in [41] by a deep algebraic method. These sum-rank codes are linear over ${\bf F}_{q^{m}}$. The sum-rank BCH bound on CSC codes was proved and sum-rank BCH codes were introduced in [41]. Dimensions of sum-rank BCH codes were lower bounded in [41, Theorem 9]. Many sum-rank codes of the parameters $n=m=2$ and $q=2$ were constructed in Tables I, II, III, IV, V, VI and VII of [41]. The minimum sum-rank distances of CSC codes were improved in a recent paper [4]. Similar sum-rank Hartmann-Tzeng bound and sum-rank Roos bound for CSC codes were proved in their paper. A decoding algorithm for sum-rank BCH codes was presented in [41]. For several recent works on sum-rank codes, the reader is referred to [1, 7, 9, 16]. In our previous paper [14], we proposed a construction of linear sum-rank codes by combining several Hamming metric codes and $q$-polynomials.

Similar to the distance-optimal codes in the Hamming metric, see [18], distance-optimal sum-rank codes can be defined as follows. Let ${\mathbf{{C}}}\subset{\bf F}_{q}^{(n_{1},m_{1}),\ldots,(n_{t},m_{t})}$ be a sum-rank code with $M$ codewords and the minimum sum-rank distance $d_{sr}$, and there is no sum-rank code with $M$ codewords and the minimum sum-rank distance $d_{sr}+1$, we call ${\mathbf{{C}}}$ a distance-optimal sum-rank code. We will construct an infinite family of distance-optimal cyclic sum-rank codes with respect to the sphere packing bound. We refer to [10] for the sphere packing bound in the sum-rank metric. In general, it is more difficult to construct optimal sum-rank codes attaining some upper bounds in the sum-rank metric. Sum-rank Hamming codes constructed in [38] are perfect in the sum-rank metric, then distance-optimal. However the minimum sum-rank distance of sum-rank Hamming codes is three. In this paper, we show that cyclic sum-rank codes provide infinitely many distance-optimal sum-rank codes with minimum sum-rank distance four.

The main contributions of this paper are as follows.

1) Cyclic, negacyclic and constacyclic sum-rank codes over ${\bf F}_{q}$ of the matrix size $n\times m$ are introduced. Cyclic-skew-cyclic sum-rank codes are special cyclic sum-rank codes.

2) Cyclic, negacyclic and constacyclic sum-rank codes are constructed with cyclic, negacyclic and constacyclic codes in the Hamming metric through a one-way bridge.

3) With cyclic or negacyclic or constacyclic codes in the Hamming metric with known dimensions, specific families of cyclic or negacyclic or constacyclic sum-rank codes with known dimensions and controllable minimum sum-rank distances are presented.

4) In some cases, the minimum sum-rank distances of some cyclic, negacyclic and constacyclic sum-rank codes are determined explicitly. Notice that it is difficult to determine the minimum sum-rank distances and dimensions of cyclic-skew-cyclic sum-rank codes ([41, 4]).

5) Many distance-optimal binary sum-rank codes and an infinite family of distance-optimal binary cyclic sum-rank codes with minimum sum-rank distance four are constructed. To the best of the authors’ knowledge, this is the first infinite family of distance-optimal codes with minimum sum-rank distance four in the literature.

The rest of this paper is organized as follows. In Section 2, cyclic-skew-cyclic sum-rank codes and their bounds are recalled. In Section 3, cyclic and negacyclic sum-rank codes are defined, and a general construction of cyclic and negacyclic sum-rank codes is introduced. In addition, the BCH bound and Hartmann-Tzeng bound for a type of cyclic sum-rank codes are developed. In Section 4, specific families of cyclic sum-rank codes are presented. In Section 5, constructions of negacyclic sum-rank codes are proposed. In Section 6, $\lambda$-constacyclic sum-rank codes are introduced and studied. In Section 7, distance-optimal binary sum-rank codes with minimum sum-rank distance four are constructed. In Section 8, the decoding of cyclic and negacyclic sum-rank codes is discussed. Section 9 concludes this paper.

We first recall the definition of cyclic-skew-cyclic (CSC) sum-rank codes introduced and studied in [41, 4]. By Definition 4 in [41], a sum-rank code ${\bf C}$ over ${\bf F}_{q}$ with block length $t$ and matrix size $n\times m$ is called cyclic-skew-cyclic (CSC) if the following hold:

(1) If ${\bf x}=({\bf x}_{1},\ldots,{\bf x}_{t})\in{\bf C}$ , where ${\bf x}_{i}\in{\bf F}_{q}^{(n,m)}$, $i=1,\ldots,t$, then $({\bf x}_{t},{\bf x}_{1},...,{\bf x}_{t-1})\in{\bf C}$.

(2) If ${\bf x}=({\bf x}_{1},\ldots,{\bf x}_{t})\in{\bf C}$ with ${\bf x}_{i}=(x_{i,1},x_{i,2},...,x_{i,m})\in{\bf F}_{q}^{(n,m)}$, $i=1,\ldots,t$, then $({\bf x}^{\prime}_{1},{\bf x}^{\prime}_{2},...,{\bf x}^{\prime}_{t})\in{\bf C}$, where ${\bf x}^{\prime}_{i}=(\sigma(x_{i,m}),\sigma(x_{i,1}),...,\sigma(x_{i,m-1}))\in{\bf F}_{q}^{(n,m)}$, $i=1,\ldots,t$, and $\sigma:{\bf F}_{q^{ns}}\rightarrow{\bf F}_{q^{ns}}$ is defined as $a\longmapsto a^{q^{s}}$ with $s=\mathrm{ord}_{t}(q)$.

In [41] and [4], sum-rank BCH lower bound, sum-rank Hartmann-Tzeng lower bound and sum-rank Roos lower bound on minimum sum-rank distances of CSC codes were given. We recall these bounds for references later.

We consider sum-rank codes over ${\mathbf{{F}}}_{q}$ with block length $t$ and matrix size $n\times m$. Assume that $\gcd(t,q)=1$. Let

$$x^{t}-1=m_{1}(x)\cdots m_{h}(x)$$

be the canonical factorisation of $x^{t}-1$ over ${\mathbf{{F}}}_{q}$, where each $m_{i}(x)$ is an irreducible polynomial in ${\bf F}_{q}[x]$. Let $s=\mathrm{ord}_{t}(q)$. Let $a\in{\bf F}_{q^{s}}$ be a primitive $t$-th root of unity and $\beta$ be a normal element of the extension ${\bf F}_{q^{s}}\subseteq{\bf F}_{q^{ns}}$. Given a cyclic-skew-cyclic code ${\bf C}\subseteq{\bf F}_{q}^{(n,m),...,(n,m)}$ with minimal generator skew polynomial $g(x,z)$, the defining set of ${\bf C}$ is ${\bf T_{C}}=\{(a,\beta)\in{\bf F}_{q^{s}}\times{\bf F}_{q^{ns}}^{*}|a^{t}=1,$ total evaluation map Ev${}_{a,\beta}(g(x,z))=0\}.$

The sum-rank HT bound and sum-rank Roos bound were proposed and proved in [4]. Lower bounds on dimensions of cyclic-skew-cyclic sum-rank codes can be obtained from these two bounds as follows.

When $n=m=1$, above lower bounds are the classical BCH bound, the classical Hartmann-Tzeng bound and the classical Roos bound for cyclic codes in the Hamming metric.

In this section, we first introduce cyclic and negacyclic sum-rank codes in ${\bf F}_{q}^{(n,m),\ldots,(n,m)}$. Cyclic-skew-cyclic(CSC) codes introduced in [41] are special cases of cyclic sum-rank codes. Then we present a general construction of cyclic sum-rank codes directly from cyclic codes in the Hamming metric. Afterwards, we propose and prove the BCH bound and Hartmann-Tzeng bound for a type of cyclic sum-rank codes.