NEW OPTIMAL LINEAR CODES OVER $\ \boldsymbol {\mathbb {Z}_{4}}$

Abstract

We present novel approaches for constructing linear codes over $\mathbb {Z}_{4}$ from the known ones. We obtain new linear codes, many of which are optimal. In particular, we find all optimal codes of type $4^{k_{1}}2^{k_{2}}$ for $k_{1}=2,~k_{2}=0$ and many optimal codes for $k_{1}=3,~k_{2}=0.$

1 Introduction

In its early development, algebraic coding theory considered codes over finite fields. Codes over finite rings were introduced in the first half of the 1970s by Blake [7, 8]. He showed how to construct codes over $\mathbb {Z}_{m}$ from cyclic codes over ${\mathbb {F}}_{p},$ where p is a prime factor of m [7]. He then determined the structure of codes over $\mathbb {Z}_{p^{r}}$ [8]. Spiegel generalised Blake’s results to codes over $\mathbb {Z}_{m},$ where m is an arbitrary positive integer [24, 25]. Hammons et al. showed how several well-known families of nonlinear binary codes were intimately related to linear codes over $\mathbb {Z}_{4}$ [16]. Since the work by Hammons et al. [16], there has been great interest in codes over many other finite rings.

Pless and Qian considered cyclic and quadratic residue codes over $\mathbb {Z}_{4}$ [21]. Cyclic and negacyclic codes and the mass formula for the codes over $\mathbb {Z}_{4}$ have been explored by Abualrub and Oehmke [1], Blackford [5, 6] and others. In 1997, Bonnecaze and Duursma considered the translate of linear codes over $\mathbb {Z}_{4}$ and computed the complete weight enumerators of the translate codes [9]. The decoding algorithm for linear codes over $\mathbb {Z}_{4}$ was given by Byrne et al. [11].

Regarding the construction of optimal codes over $\mathbb {Z}_{4},$ so far, only self-dual codes are available (see [17, 22]). There are only a few publications on linear (but not self-dual) codes over $\mathbb {Z}_{4}$ , for example, Gulliver and Wong [15], Dougherty et al. [13] and Aydin and Asamov [2, 3]. New linear codes over $\mathbb {Z}_{4}$ were obtained indirectly, as a $\mathbb {Z}_{4}$ -image of certain Gray maps from finite rings to $\mathbb {Z}_{4}.$ In many cases, the resulting codes have not-so-good minimum distances (see [10, 12, 23] for recent developments).

The purpose of this paper is twofold. First, we reprove the Plotkin bound for the Lee distance of linear codes over $\mathbb {Z}_{4}$ by an elementary approach. Second, we develop new constructions of linear codes over $\mathbb {Z}_{4}.$ By using these methods, we obtain many new free linear codes over $\mathbb {Z}_{4}$ with the highest known minimum Lee distance as well as optimal linear codes over $\mathbb {Z}_{4}.$ Our results contribute significantly to the Aydin and Asamov database of $\mathbb {Z}_{4}$ codes [2, 3].

The organisation of the paper is as follows. In Section 2, we describe several basic facts regarding linear codes over $\mathbb {Z}_{4}.$ Section 3 contains the proof of the Plotkin bound for the Lee distance. Section 4 contains several construction methods for linear codes over $\mathbb {Z}_{4}$ and their applications to obtain new optimal codes over $\mathbb {Z}_{4}$ as well as the linear codes over $\mathbb {Z}_{4}$ with the highest known minimum Lee distance. We finish with concluding remarks. We follow [18] for undefined terms in coding theory.

2 Preliminaries

A code of length n over the ring $\mathbb {Z}_{4}$ is a nonempty subset of $\mathbb {Z}_{4}^{n}.$ If the code is also a submodule of $\mathbb {Z}_{4}^{n},$ then we say that the code is linear. The linear code is called free if it is a free submodule of $\mathbb {Z}_{4}^{n}.$

A matrix $G\in \mathbb {Z}_{4}^{k \times n}$ is called a generator matrix of a linear code C of length n over $\mathbb {Z}_{4}$ if the rows of G generate C and no proper subset of the rows of G generates C.

Two codes are said to be equivalent if one can be obtained from the other by permuting the coordinates and (if necessary) changing the signs of certain coordinates. Codes differing by only a permutation of coordinates are called permutation-equivalent. It is well known (see [16]) that any linear code over $\mathbb {Z}_{4}$ is permutation-equivalent to the linear code C with generator matrix G of the form

(2.1) $$ \begin{align} G= \begin{pmatrix} I_{k_{1}} & A & B_{1}+2 B_{2}\\[3pt] 0 & 2 I_{k_{2}} & 2 D \end{pmatrix}, \end{align} $$

where $A,B_{1},B_{2}$ and D are $(0,1)$ -matrices. Moreover, the code C is a free linear code if and only if $k_{2}=0.$ The generator matrix of a linear code C over $\mathbb {Z}_{4}$ is said to be in standard form if it has the form given in (2.1).

The Lee weight of $ x \in \mathbb {Z}_{4},$ denoted by $w_{L}(x),$ is defined by $w_{L}(0)=0, w_{L}(1)\,{=}\,1, w_{L}(2)=2$ and $w_{L}(3)=1.$ The Lee weight of a vector $\mathbf {x}=(x_{1},x_{2},\ldots ,x_{n}) \in \mathbb {Z}_{4}^{n}$ is $ w_{L}(\mathbf {x})=\sum _{i=1}^{n} w_{L}(x_{i}). $ For $\mathbf {x},\mathbf {y} \in \mathbb {Z}_{4}^{n},$ the Lee distance between $\mathbf {x}$ and $\mathbf {y},$ denoted by $d(\mathbf {x},\mathbf {y}),$ is $d(\mathbf {x},\mathbf {y})=w_{L}(\mathbf {x}-\mathbf {y}).$ The minimum Lee distance of a linear code $C \subseteq \mathbb {Z}_{4}^{n}$ is

$$ \begin{align*}d_{L}=d_{L}(C):=\mathrm\min\{d_{L}(\mathbf{x},\mathbf{y}):\mathbf{x},\mathbf{y} \in C, \mathbf{x} \neq \mathbf{y}\}.\end{align*} $$

It is clear that for a linear code $C,$ the minimum Lee distance is exactly the same as the minimum Lee weight, namely $d_{L}(C)=\mathrm \min \{ w_{L}(\mathbf {x}):\mathbf {x} \in C, \mathbf {x} \neq \mathbf {0}\}.$ We write the parameters of a linear code C over $\mathbb {Z}_{4}$ as $[n, 4^{k_{1}}2^{k_{2}}, d_{L}],$ where n is the length of $C, |C| = 4^{k_{1}}2^{k_{2}}$ and $d_{L} = d_{L}(C).$ Following Hammons et al. [16] (see also [26]), we say that C is of type $4^{k_{1}}2^{k_{2}}.$

Determining or estimating the minimum distance of a given linear code is one of the fundamental problems in coding theory, because the minimum distance of the code determines its capability in detecting and correcting errors that appear during the transmission of information. In 2001, Dougherty and Shiromoto [14] proved an upper bound for the minimum Lee distance of codes over $\mathbb {Z}_{4}$ .

Theorem 2.1 (Singleton Lee distance bound; [14, Theorem 3.1])

If C is a linear code of length n over $\mathbb {Z}_{4}$ with parameters $[n,4^{k_{1}}2^{k_{2}},d_{L}]$ , then

(2.2) $$ \begin{align} d_{L}\leq 2n-2k_{1}-k_{2}+1. \end{align} $$

Remark 2.2. Dougherty and Shiromoto [14] called the codes meeting the bound (2.2) maximum Lee distance separable (MLDS) codes.

3 Plotkin Lee distance bound

For $\mathbf {x}=(x_{1},x_{2},\ldots ,x_{n}),~\mathbf {y}=(y_{1},y_{2},\ldots ,y_{n})\in \mathbb {Z}_{4}^{n},$ the Euclidean inner product of $\mathbf {x}$ and $\mathbf {y}$ is $\mathbf {x}\cdot \mathbf {y}=\sum _{i=1}^{n} x_{i} y_{i}\in \mathbb {Z}_{4}.$ For $\mathbf {x}\in \mathbb {Z}_{4}^{n},$ let $\mathbf {x}^{\prime }=(x_{1},\ldots ,x_{n-1}) \in \mathbb {Z}_{4}^{n-1},$ that is, the vector obtained from $\mathbf {x}$ by dropping its last entry. Let 0 denote the zero vector.

Let $G \in \mathbb {Z}_{4}^{(k_{1}+k_{2})\times n}$ be a generator matrix of a linear code C over $\mathbb {Z}_{4}.$ Following Kløve [19], for any $\mathbf {c}\in \mathbb {Z}_{4}^{k_{1}+k_{2}},$ the multiplicity of $\mathbf {c},$ denoted by $\mu (\mathbf {c}),$ is the number of occurrences of $\mathbf {c}$ as a column vector in $G.$ Observe that for any $\mathbf {x}\in \mathbb {Z}_{4}^{k}$ with $k:=k_{1}+k_{2}$ ,

$$ \begin{align*} w_{L}(\mathbf{x} G)=\sum_{\mathbf{c}\in\mathbb{Z}_{4}^{k}} \mu(\mathbf{c}) w_{L}(\mathbf{x}\cdot\mathbf{c}). \end{align*} $$

It is also clear that

$$ \begin{align*} \sum_{\mathbf{c}\in\mathbb{Z}_{4}^{k}} \mu(\mathbf{c})=n. \end{align*} $$

The next lemma shows that for any given nonzero codeword $\mathbf {c}\in \mathbb {Z}_{4}^{k}$ , the sum $\sum _{\mathbf {x}\in \mathbb {Z}_{4}^{k}}w_{L}(\mathbf {x}\cdot \mathbf {c})$ depends only on $k.$ This result is very important in what follows.

Lemma 3.1. Let k be a positive integer. If $\mathbf {c}=(c_{1},c_{2},\ldots ,c_{k})\in \mathbb {Z}_{4}^{k}$ is a nonzero vector, then

$$ \begin{align*} \sum_{\mathbf{x}\in\mathbb{Z}_{4}^{k}}w_{L}(\mathbf{x}\cdot \mathbf{c})=4^{k}. \end{align*} $$

Proof. It is clear for the case $k=1$ . Since $\mathbf {c}$ is a nonzero vector, there exists i such that $c_{i}\neq 0$ . Without loss of generality, let $i=k$ . If $\mathbf {c}^{\prime } = \mathbf {0},$ then

$$ \begin{align*} \sum_{\mathbf{x}\in\mathbb{Z}_{4}^{k}}w_{L}(\mathbf{x}\cdot \mathbf{c})&=\sum_{\mathbf{x}\in\mathbb{Z}_{4}^{k}}w_{L}(x_{k}c_{k})=4^{k}. \end{align*} $$

If $\mathbf {c}^{\prime } \neq \mathbf {0},$ define $ H_{i}:=\{\mathbf {y}\in \mathbb {Z}_{4}^{k-1}:\mathbf {y}\cdot \mathbf {c}^{\prime }=i\} \text { for }i\in \mathbb {Z}_{4}$ . Since $c_{k}\neq 0$ ,

$$ \begin{align*} \sum_{\mathbf{x}\in\mathbb{Z}_{4}^{k}}w_{L}(\mathbf{x}\cdot \mathbf{c})&=\sum_{i=0}^{3}\sum_{\mathbf{x}^{\prime}\in H_{i}}\sum_{x_{k}=0}^{3} w_{L}(\mathbf{x}^{\prime}\cdot \mathbf{c}^{\prime}+x_{k}c_{k})\\[3pt] &=4|H_{0}|+4|H_{1}|+4|H_{2}|+4|H_{3}|=4^{k}.\\[-3pc] \end{align*} $$

The next lemma follows by applying Lemma 3.1.

Lemma 3.2. Let n and k be positive integers. If a matrix $G\in \mathbb {Z}_{4}^{k\times n}$ has no zero column, then

$$ \begin{align*} \sum_{\mathbf{x}\in\mathbb{Z}_{4}^{k}}w_{L}(\mathbf{x} G)=4^{k} n. \end{align*} $$

Lemma 3.3 (Constant sum of Lee weights)

Let C be a linear code over $\mathbb {Z}_{4}$ with parameters $[n,4^{k_{1}}2^{k_{2}},d_{L}].$ If $\mu (\mathbf {0})=0$ , then

$$ \begin{align*} \sum_{\mathbf{c}\in C} w_{L}(\mathbf{c})=|C|n. \end{align*} $$

Proof. Let G be a generator matrix of C in standard form. Since G does not have any zero column, then, by Lemma 3.2, $\sum _{\mathbf {x}\in \mathbb {Z}_{4}^{k}}w_{L}(\mathbf {x} G)=4^{k} n$ for $k:=k_{1}+k_{2}$ . If $k_{2}=0,$ then

$$ \begin{align*} \sum_{\mathbf{c}\in C} w_{L}(\mathbf{c})=\sum_{\mathbf{x}\in\mathbb{Z}_{4}^{k_{1}}}w_{L}(\mathbf{x} G)=4^{k_{1}} n=|C|n. \end{align*} $$

If $k_{2}>0,$ let $\mathbf {g^{(1)}},\ldots ,\mathbf {g^{(k_{2})}}$ be all distinct $k_{2}$ row vectors of G which have entries $0$ or $2$ only. We have

$$ \begin{align*} \mathbf{x} G=\mathbf{x} G+\sum_{i=1}^{k_{2}}x_{i} \mathbf{g^{(i)}}=(\mathbf{x}+[0,\ldots,0,x_{1},\ldots,x_{k_{2}}])G \end{align*} $$

for $x_{1},\ldots ,x_{k_{2}}\in \{0,2\}.$ There are $2^{k_{2}}$ possible different values for $x_{1},\ldots ,x_{k_{2}}.$ Hence, in the summation $\sum _{\mathbf {x}\in \mathbb {Z}_{4}^{k}}w_{L}(\mathbf {x} G),$ every codeword in C appears exactly $2^{k_{2}}$ times. Thus,

$$ \begin{align*} 4^{k} n=\sum_{\mathbf{x}\in\mathbb{Z}_{4}^{k}}w_{L}(\mathbf{x} G)=2^{k_{2}}\sum_{\mathbf{c}\in C} w_{L}(\mathbf{c}). \end{align*} $$

Therefore,

$$ \begin{align*} \sum_{\mathbf{c}\in C} w_{L}(\mathbf{c})=\frac{4^{k} n}{2^{k_{2}}}=4^{k_{1}}2^{k_{2}}n=|C|n.\\[-40pt] \end{align*} $$

Next, we prove the Plotkin bound for the minimum Lee distance.

Theorem 3.4 (Plotkin Lee distance bound)

Let C be a linear code over $\mathbb {Z}_{4}$ with parameters $[n,4^{k_{1}}2^{k_{2}},d_{L}].$ Then

(3.1) $$ \begin{align} d_{L}\leq \frac{|C|}{|C|-1}n. \end{align} $$

Proof. Let $\mu (\mathbf {0}) = m$ . From Lemma 3.3, $|C|(n-m)=\sum _{\mathbf {c}\in C} w_{L}(\mathbf {c})\geq (|C|-1)d_{L}.$ Therefore,

$$ \begin{align*} d_{L}\leq \frac{|C|}{|C|-1}(n-m)\leq\frac{|C|}{|C|-1}n.\\[-40pt] \end{align*} $$

The linear codes C whose minimum Lee distance $d_{L}(C)$ is the integer nearest to the upper bound of the Plotkin Lee distance bound (3.1) as given in Theorem 3.4 are called Plotkin-optimal. In other words, a linear code C is Plotkin-optimal if

$$ \begin{align*}\displaystyle d_{L}(C)=\bigg \lfloor \frac{|C|}{|C|-1}n \bigg \rfloor.\end{align*} $$

Remark 3.5. The bound similar to Theorem 3.4 for (not necessarily linear) codes over $\mathbb {Z}_{m}$ is presented in [4, Theorem 13.49]. It was originally proved by Wyner and Graham [27]. Our proof above is very simple (compared with the proof in [4, 27]), although limited to linear codes over $\mathbb {Z}_{4}.$

4 Optimal codes

The nonexistence of MLDS codes over $\mathbb {Z}_{4}$ , except for the trivial ones, was proved by Dougherty and Shiromoto [14].

Theorem 4.1 [14]

There are no MLDS codes over $\mathbb {Z}_{4}$ except the trivial ones, namely the linear codes with parameters $[n,4^{0}2^{1},2n], [n,4^{n}2^{0},1]$ or $[n,4^{n-1}2^{1},2].$

Since there are no linear codes over $\mathbb {Z}_{4}$ whose minimum Lee distance attains the Singleton Lee distance bound (2.2) except the trivial ones, we consider the optimality of the codes with respect to the Plotkin Lee distance bound (3.1).

4.1 Optimal linear codes

In this section, we discuss several methods to construct optimal codes. For any nonnegative integers $k_{1},k_{2}$ with $k_{1}+k_{2}>0$ , let $G^{(k_{1},k_{2})}$ denote the generator matrix of a linear code $C^{(k_{1},k_{2})}$ whose columns consist of all possible nonzero vectors in $\mathbb {Z}_{4}^{k_{1}}\times (2\mathbb {Z}_{4})^{k_{2}}.$ We can define $G^{(k_{1},k_{2})}$ recursively as follows:

$$ \begin{align*}\displaystyle G^{(0,1)} := [2], \quad G^{(1,0)} := [1 \quad 2 \quad 3],\end{align*} $$

$$ \begin{align*} G^{(k_{1}+1,0)}:= \left[\begin{array}{@{}c|c|c|c| c c c@{}} G^{(k_{1},0)} & G^{(k_{1},0)} & G^{(k_{1},0)} & G^{(k_{1},0)} &\textbf{0} & \textbf{0} & \textbf{0} \\[3pt] \hline 0\;0\ldots 0 &1\;1\ldots 1 &2\;2\ldots 2 &3\;3\ldots 3 &1 &2 &3 \end{array}\;\right], \end{align*} $$

$$ \begin{align*}G^{(k_{1},k_{2}+1)}:= \left[\begin{array}{@{}c|c|c @{}} G^{(k_{1},k_{2})} & G^{(k_{1},k_{2})} & \textbf{0}\\[3pt] \hline 0\;0\ldots 0 &2\;2\ldots 2 &2 \end{array}\;\right]. \end{align*} $$

The theorem below shows the existence of a linear code over $\mathbb {Z}_{4}$ of length n satisfying the bound (3.1), for any given $k_{1}$ and $k_{2}.$ Moreover, the code has a constant Lee weight.

Theorem 4.2 (Existence of optimal codes)

The linear code $C^{(k_{1},k_{2})}$ with parameters $[n,4^{k_{1}}2^{k_{2}},d_{L}],$ where $n=4^{k_{1}}2^{k_{2}}-1$ and $d_{L}=4^{k_{1}}2^{k_{2}}$ , is optimal. Moreover, all nonzero codewords in $C^{(k_{1},k_{2})}$ have the Lee weight $d_{L}.$

Proof. First, consider the case $k_{2}=0.$ Observe that for any nonzero vector $\mathbf {y}\in C^{(k_{1},0)}$ , there exists a unique $\mathbf {x}\in \mathbb {Z}_{4}^{k_{1}}$ such that $\mathbf {y}=\mathbf {x} G^{(k_{1},0)}$ . By Lemma 3.1, $w_{L}(\mathbf {y})$ is equal to

$$ \begin{align*} w_{L}(\mathbf{x} G^{(k_{1},0)})=\sum_{\mathbf{c}\in\mathbb{Z}_{4}^{k_{1}}} \mu(\mathbf{c}) w_{L}(\mathbf{x}\cdot\mathbf{c})=\sum_{\mathbf{c}\in\mathbb{Z}_{4}^{k_{1}}} w_{L}(\mathbf{c}\cdot\mathbf{x})=4^{k_{1}}. \end{align*} $$

For the case when $k_{2}>0,$ we do an induction on $k_{2}$ . For any nonzero $\mathbf {y}\in C^{(k_{1},k_{2})}$ , there exists a unique $\mathbf {x}\in \mathbb {Z}_{4}^{k_{1}}\times (2\mathbb {Z}_{4})^{k_{2}}$ such that $\mathbf {y}=\mathbf {x} G^{(k_{1},k_{2})}$ . Define $k:=k_{1}+k_{2}$ . Then

$$ \begin{align*} w_{L}(\mathbf{y}) &=\sum_{\mathbf{c}\in\mathbb{Z}_{4}^{k}} \mu(\mathbf{c}) w_{L}(\mathbf{x}\cdot\mathbf{c})=\sum_{\mathbf{c}^{\prime}\in\mathbb{Z}_{4}^{k_{1}}\times (2\mathbb{Z}_{4})^{k_{2}-1}} w_{L}(\mathbf{c}^{\prime}\cdot\mathbf{x}^{\prime})+w_{L}(\mathbf{c}^{\prime}\cdot\mathbf{x}^{\prime}+2x_{k}), \end{align*} $$

and the last sum is equal to $4^{k_{1}}2^{k_{2}}$ .

The construction in the next lemma is easy to verify.

Lemma 4.3 (Construction A)

If $C_{1}$ and $C_{2}$ are linear codes of type $4^{k_{1}}2^{k_{2}}$ with $n(C_{1})+n(C_{2})< 4^{k_{1}}2^{k_{2}}-1,$ having generator matrices (in standard form) $G_{1}$ and $G_{2},$ respectively, then the linear code $C^{\prime } $ generated by the matrix $G^{\prime }:=[G_{1}~|~G_{2}]$ is of length $n(C_{1})+n(C_{2})$ with $d_{L}(C^{\prime })\geq d_{L}(C_{1})+d_{L}(C_{2})$ .

The following construction is a special case of Lemma 4.3.

Corollary 4.4 (Construction 1 for optimal codes)

If C is a Plotkin-optimal linear code with parameters $[n,4^{k_{1}}2^{k_{2}},d_{L}]$ with generator matrix (in standard form) $G,$ then the linear code $C^{\prime } $ generated by the matrix $G^{\prime }:=[G~|~G^{(k_{1},k_{2})}]$ is also optimal of length $n+4^{k_{1}}2^{k_{2}}-1.$

Proof. It is clear that $n(C^{\prime })=n(C)+n(C^{(k_{1},k_{2})})=n+4^{k_{1}}2^{k_{2}}-1$ and $|C|=|C^{\prime }|$ . Moreover, since the Lee weight of any nonzero codeword in $C^{(k_{1},k_{2})}$ is $4^{k_{1}}2^{k_{2}}$ (Theorem 4.2), then $d_{L}(C^{\prime })\geq d_{L}(C)+d_{L}(C^{(k_{1},k_{2})})=\lfloor {|C|}n(C^{\prime })/{(|C|-1)}\rfloor $ . Therefore, $C^{\prime }$ is optimal by Theorem 3.4.

Corollary 4.5 (Construction 2 for optimal codes)

If $C_{1}$ and $C_{2}$ are Plotkin-optimal linear codes of type $4^{k_{1}}2^{k_{2}}$ with $n(C_{1})+n(C_{2})< 4^{k_{1}}2^{k_{2}}-1$ , having generator matrices (in standard form) $G_{1}$ and $G_{2},$ respectively, then the linear code $C^{\prime }$ generated by the matrix $G^{\prime }:=[G_{1}~|~G_{2}]$ is also optimal of length $n(C_{1})+n(C_{2}).$

Proof. Straightforward from Lemma 4.3 and Theorem 3.4.

By using a similar idea as in proving Theorem 4.2, we obtain the following result.

Theorem 4.6 (Construction B)

If C is a linear code with parameters $[n,4^{k_{1}}2^{k_{2}},d_{L}]$ with generator matrix (in standard form) $G,$ then the code $C^{\prime }_{1}$ generated by the matrix

(4.1) $$ \begin{align} G^{\prime}_{1}:= \left[\begin{array}{@{}c|c|c|c@{}} G & G & G & G \\\hline 0\;0\ldots 0 &1\;1\ldots 1 &2\;2\ldots 2 &3\;3\ldots 3 \end{array}\;\right] \end{align} $$

is linear with parameters $[4n,4^{k_{1}+1}2^{k_{2}},d_{L}(C^{\prime }_{1})]$ , and the code $C^{\prime }_{2}$ generated by

(4.2) $$ \begin{align} G^{\prime}_{2}:=\left[\begin{array}{@{}c|c@{}} G & G \\ \hline 0\;0\ldots 0 &2\;2\ldots 2 \end{array}\;\right] \end{align} $$

is linear with parameters $[2n,4^{k_{1}}2^{k_{2}+1},d_{L}(C^{\prime }_{2})]$ . Moreover, $d_{L}(C^{\prime }_{1})\geq \min \{4n,4d_{L}\}$ and $d_{L}(C^{\prime }_{2})\geq \min \{2n,2d_{L}\}.$

Corollary 4.7 (Construction 3 for optimal codes)

If C is a Plotkin-optimal linear code with parameters $[n,4^{k_{1}}2^{k_{2}},d_{L}]$ and $n(C)< 4^{k_{1}}2^{k_{2}}-1$ , having generator matrix (in standard form) $G,$ then the linear code $C^{\prime }_{1}$ generated by the matrix $G^{\prime }_{1}$ in (4.1) is optimal with parameters $[4n,4^{k_{1}+1}2^{k_{2}},4n]$ and the linear code $C^{\prime }_{2}$ generated by the matrix $G^{\prime }_{2}$ in (4.2) is also optimal with parameters $[2n,4^{k_{1}}2^{k_{2}+1},2n].$

Proof. Straightforward from Theorems 3.4 and 4.6.

It is easy to see that the linear codes with parameters $[1,4^{1} 2^{0}, 1]$ and $[4,4^{2} 2^{0},4]$ are both Plotkin-optimal. By applying Construction 3 as given in Corollary 4.7 repeatedly, we obtain a class of optimal codes.

Corollary 4.8. Let $k_{1},k_{2}$ be nonnegative integers with $k_{1}+k_{2}>0$ . Then there exists an optimal linear code with parameters $[4^{k_{1}}2^{k_{2}}, 4^{k_{1}+1}2^{k_{2}},4^{k_{1}}2^{k_{2}}]$ .

Remark 4.9. Zinoviev and Zinoviev [28] have also constructed codes over $\mathbb {Z}_{4}$ with parameters $(n,4n,n)$ . Their construction uses Hadamard matrices of order $n.$ Our construction is simpler and produces linear codes.

Next, we derive another method to construct optimal codes.

Theorem 4.10. The linear code C having a generator matrix G given by

$$ \begin{align*} G:= \left[\begin{array}{@{}c|c|c| c c c@{}} G^{(k_{1},0)} & G^{(k_{1},0)} & G^{(k_{1},0)} &\mathbf{0} &\mathbf{0} &\mathbf{0} \\ \hline 1\;1\ldots 1 &2\;2\ldots 2 &3\;3\ldots 3 &1 &2 &3 \end{array}\;\right] \end{align*} $$

is optimal with parameters $[3.4^{k_{1}},4^{k_{1}+1}2^{0},3.4^{k_{1}}]$ .

Proof. Since the code $C^{(k_{1}+1,0)}$ has a generator matrix

$$ \begin{align*} G^{(k_{1}+1,0)}:= \left[\begin{array}{@{}c|c|c|c| c c c@{}} G^{(k_{1},0)} & G^{(k_{1},0)} & G^{(k_{1},0)} & G^{(k_{1},0)} &\mathbf{0} &\mathbf{0} &\mathbf{0} \\ \hline 0\;0\ldots 0 &1\;1\ldots 1 &2\;2\ldots 2 &3\;3\ldots 3 &1 &2 &3 \end{array}\;\right],\end{align*} $$

for any $\mathbf {c}\in C,$ we have $w_{L}(\mathbf {c})=w_{L}(\mathbf {c_{1}})-w_{L}(\mathbf {c_{2}})$ for some $\mathbf {c_{1}}\in C^{(k_{1}+1,0)}$ and $\mathbf {c_{2}}\in C^{(k_{1},0)}.$ Since the Lee weight of all nonzero codewords in $C^{(k_{1}+1,0)}$ is $4^{k_{1}+1}$ and the Lee weight of all nonzero codewords in $C^{(k_{1},0)}$ is $4^{k_{1}}$ (Theorem 4.2), the Lee weight of any codeword in C is either $0, 3.4^{k_{1}}$ or $4^{k_{1}+1}.$ Therefore, $d_{L}(C)=3.4^{k_{1}}.$

Remark 4.11. Theorem 4.10 gives us a way to obtain free optimal two-weight codes (codes with exactly two nonzero weights).

By applying Corollary 4.7 to the code in Theorem 4.10, or by attaching three codes with parameters $[4^{k_{1}}2^{k_{2}},4^{k_{1}+1}2^{k_{2}},4^{k_{1}}2^{k_{2}}]$ (see Corollary 4.8) using Corollary 4.5, we obtain another class of optimal codes.

Corollary 4.12. Let $k_{1},k_{2}$ be nonnegative integers with $k_{1}+k_{2}>0$ . Then there exist an optimal linear code with parameters $[3.4^{k_{1}}2^{k_{2}}, 4^{k_{1}+1}2^{k_{2}},3.4^{k_{1}}2^{k_{2}}].$

We end this subsection by deriving a construction for free optimal linear codes.

Corollary 4.13 (Construction 4 for optimal codes)

If C is a Plotkin-optimal linear code of type $4^{k_{1}} 2^{0}$ and length $n<4^{k_{1}}-1$ with generator matrix (in standard form) $G,$ then the linear code $C^{\prime }$ with generator matrix

$$ \begin{align*} G^{\prime}:= \left[ \begin{array}{@{}c|c|c|c| c c c@{}} G & G^{(k_{1},0)} & G^{(k_{1},0)} & G^{(k_{1},0)} &\mathbf{0} & \mathbf{0} & \mathbf{0} \\ \hline 0\;0\ldots 0 &1\;1\ldots 1 &2\;2\ldots 2 &3\;3\ldots 3 &1 &2 &3 \end{array}\; \right] \end{align*} $$

is optimal with parameters $[3.4^{k_{1}}+n,4^{k_{1}+1}2^{0},3.4^{k_{1}}+n].$

Proof. Every nonzero codeword $\mathbf {c^{\prime }}\in C^{\prime }$ satisfies $w_{L}(\mathbf {c^{\prime }})=w_{L}(\mathbf {c})+w_{L}(\mathbf {c^{*}})$ for some $\mathbf {c} \in C,$ where $\mathbf {c}^{*}$ is a codeword of Lee weight $3.4^{k_{1}}$ or $4^{k_{1}+1}$ (Theorem 4.10). Here, if $w_{L}(\mathbf {c})=0$ , then $w_{L}(\mathbf {c}^{*})=4^{k_{1}+1},$ which implies $w_{L}(\mathbf {c}^{\prime })=w_{L}(\mathbf {c})+w_{L}(\mathbf {c}^{*})=4^{k_{1}+1}$ . Moreover, if $w_{L}(\mathbf {c})>0,$ then $w_{L}(\mathbf {c}^{\prime })=w_{L}(\mathbf {c})+w_{L}(\mathbf {c}^{*})\geq n+3.4^{k_{1}}.$ Hence, $d_{L}\geq 3.4^{k_{1}}+n.$ By Theorem 3.4, $C^{\prime }$ is optimal.

4.2 Optimal codes for $k_{1}=2, ~k_{2}=0$

In this subsection, we determine all optimal codes with $k_{1}=2, k_{2}=0.$ In Table 2, we compare the codes constructed by our methods with the codes having the highest minimum Lee distance in the database [3]. All computations were done using the Magma Calculator [20]. By applying Lemma 4.3 to the codes in Table 2, we obtain all optimal codes with $k_{1}=2, k_{2}=0$ , as presented in Table 1. We conclude that the difference between the bound (3.1) and the minimum Lee distance of optimal codes we derived is at most $1.$

Table 1 All optimal linear codes for $k_{1}=2, k_{2}=0$ .

PLDB, Plotkin Lee distance bound (3.1); bold text, Plotkin-optimal.

Table 2 New Plotkin-optimal and good linear codes for $k_{1}=2, k_{2}=0, 2\leq n\leq 61$ .

DB, The highest minimum Lee distance among all existing linear codes of length n in the database [3]; C, Corollary; T, Theorem; L, Lemma; PLDB, Plotkin Lee distance bound (3.1); LDB, Singleton Lee distance bound (2.2); bold-italic text, Plotkin-optimal; bold text, New good linear code;

#, Constructed by adding or removing column(s) from the generator matrix of the nearest optimal code.

Remark 4.14. In Table 1, we obtained the OPTIMAL codes after proving the nonexistence of Plotkin-optimal codes. To prove the nonexistence of Plotkin-optimal linear codes C of length $n\equiv 1,3,5\; (\mathrm {mod}\;15)$ , we consider the refined Plotkin bound for binary codes [18] and apply it for $\Phi (C)$ , where $\Phi $ is the Gray map defined in [16]. It is not hard to prove the nonexistence of Plotkin-optimal linear codes of length $n\equiv 2,7,9,11\; (\mathrm {mod}\;15)$ .

4.3 Optimal codes for $k_{1}=3, ~k_{2}=0$

In this subsection, we use our methods to construct many new optimal and nearly optimal free linear codes presented in Table 3 which are not in the database of $\mathbb {Z}_{4}$ codes [3]. As before, all computations were done using the Magma Calculator [20]. In many cases, the minimum Lee distance improved significantly. From Table 3 and Lemma 4.3, we conclude that the difference between the bound (3.1) and the minimum Lee distance of optimal codes is at most 2.

Table 3 New Plotkin-optimal and good linear codes for $k_{1}=3, k_{2}=0, 3\leq n\leq 66$ .

DB, The highest minimum Lee distance among all existing linear codes of length n in the database [3]; C, Corollary; T, Theorem; L, Lemma; PLDB, Plotkin Lee distance bound (3.1); LDB, Singleton Lee distance bound (2.2); bold-italic text, Plotkin-optimal; bold text, New good linear code;

#, Constructed by adding or removing column(s) from the generator matrix of the nearest optimal code.

5 Concluding remarks

We can apply the Gray map defined in [16] to our new Plotkin-optimal linear codes in Tables 2 and 3 to obtain many binary codes that are also Plotkin-optimal and $\mathbb {Z}_{4}$ -linear. This will be of interest for further investigation.

Regarding the existence of linear codes with good minimum Lee distance, we propose the following conjecture.

Conjecture 5.1. There exist free linear codes C over $\mathbb {Z}_{4}$ with parameters $[n,4^{k}2^{0},d_{L}]$ and minimum distance satisfying

$$ \begin{align*}\displaystyle d_{L}\geq \bigg \lfloor\frac{4^{k}}{4^{k}-1}n \bigg\rfloor-(ak+b)\end{align*} $$

for some constants $a, b$ .

For $a=1,b=0$ , we notice that the conjecture holds for all n when $k=2,3$ . For $k>3$ , it holds for $n\equiv m \pmod {(4^{k}-1)},$ with $0\leq m\leq k+1$ and $3\cdot 4^{k-1}\leq m< 4^{k}-1$ .

We are now working on a generalisation of our observation here to the linear codes over the ring $\mathbb {Z}_{2^{r}}.$ So far, we have succeeded in proving that several properties given here also hold for codes over the ring $\mathbb {Z}_{2^{r}},$ with $r \in \mathbb {Z}^{+}.$ As an example, we can obtain a similar bound to that in Theorem 3.4 for linear codes over $\mathbb {Z}_{2^{r}}$ . The results will be published in a separate paper.