Optimal Ternary Codes with Weight $w$ and Distance $2w-2$ in $\ell_{1}$-Metric

Codes in $\ell_{1}$-metric distance have attracted a lot attention in the last decade for their useful applications in rank-modulation scheme for flash memory [1, 2, 3, 4, 5, 6]. In the recent error correcting problem of data storage in live DNA, $\ell_{1}$-metric was also revealed to play an important role in attacking the tandem duplication errors [7]. To store information in live DNA, the reliability of data is crucial. A tandem duplication error, which means an error happens by inserting a copy of a segment of the DNA adjacent to its original position during replication, is one of the errors we must fight against during DNA coding. According to [8], tandem duplications constitute about 3% of our human genome and may cause serious phenomena and severe information loss. As a consequence, duplication correcting codes have been studied by many recent works, for example [7, 9, 10, 11, 12]. Specially, the work in [7] connects duplication correcting codes with constant-weight codes (CWCs) in $\ell_{1}$-metric over integers, and shows that the existence of optimal CWCs with certain weights and lengths will result in optimal tandem duplication correcting codes [7, Theorem 20].

Motivated by this connection, it is interesting to study CWCs in $\ell_{1}$-metric. The central problem regarding CWCs is to determine the exact value of maximum cardinality of a code with given length, weight, minimum distance, and the alphabet size. CWCs with Hamming distance have been well studied [13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24] due to its wide applications in coding for bandwidth-efficient channels [25], the design of oligonucleotide sequences for DNA computing [26, 27], and so on. If the code is binary, the Hamming distance is indeed the $\ell_{1}$-metric. However, when it is $q$-ary with $q\geq 3$, the metrics are different. The study of non-binary CWCs with $\ell_{1}$-metric is very rare. Based on our knowledge, only works in [28, 29, 30] are involved.

In this paper, we consider ternary CWCs with $\ell_{1}$-metric. A ternary code of constant $\ell_{1}$-weight $w$, minimum $\ell_{1}$-distance $d$ and length $n$ is denoted by an $(n,d,w)_{3}$ code. The maximum size among all $(n,d,w)_{3}$ codes is denoted by $A_{3}(n,d,w)$, and a code achieving this size is called optimal. Optimal $(n,d,w)_{3}$ codes were constructed in [30] when $w=3,4$ for all possible distances $d$ and length $n$ with only finite many cases undetermined. For general weight $w$ and distance $2w-2$, the authors in [30] provided an upper bound $A_{3}(n,2w-2,w)\leq\left\lfloor\frac{n(n-1-(w-1)(w-2))}{w(w-1)}\right\rfloor+n$, and showed that this bound can be achieved for $n$ is large enough and $n\equiv w,-2w+3,1$ or $-w+2\mod(w-1)w$. This is only a fraction of the numbers $n$ when $w$ is big.

Our main contribution in this paper is showing that, given the weight $w$, the upper bound of $A_{3}(n,2w-w,w)$ provided in [30] can be achieved for all sufficiently large $n$, which greatly improves the result in [30]. We state our main result as follows.

Further, we show that there exists an optimal $(n,2w-2,w)_{3}$ code that is balanced unless when $w$ is odd and $n\equiv 1\mod(w-1)$ with certain restrictions. Here, a code is balanced means that the collection of supports of all codewords, viewed as cliques, forms a decomposition of the complete graph $K_{n}$. Our methods rely on a famous result of Alon et al. [31] on graph decompositions, which reduces the whole problem to looking for a sparse code with desired properties.

This paper is organized as follows. In Section II, we first introduce some necessary definitions and notations, then connect codes with graph packings to reduce the problem of finding an optimal code $\mathcal{C}$ to finding a proper sub-code $\mathcal{S}\subset\mathcal{C}$. Section III gives the general idea of how to find the sub-code $\mathcal{S}$, and illustrates the idea by taking $n\equiv 0,1\mod(w-1)$ with certain restrictions. A complete solution to the cases of $n\equiv 0,1\mod(w-1)$ is given in Section IV, where a nonexistence result of an optimal balanced code with $n\equiv 1\mod(w-1)$ under additional conditions is deduced. In Section V, we deal with all other cases, $n\equiv t\mod(w-1)$ with $2\leq t\leq w-2$ by an algorithmic construction of the required sub-code $\mathcal{S}$. Finally we conclude our results in Section VI.

For integers $m\leq m^{\prime},$ we denote $[m,m^{\prime}]\triangleq\{m,m+1,\dots,m^{\prime}\}$ and $[m]\triangleq[1,m]$ for short. Let $q\geq 2$ be an integer. A $q$-ary code $\mathcal{C}$ of length $n$ is a set of vectors in $I_{q}^{n}$, in which $I_{q}:=\{0,1,\ldots,q-1\}$. An element in $\mathcal{C}$ is called a codeword. For two codewords $\bm{u}=(u_{i})_{1\leq i\leq n}$ and $\bm{v}=(v_{i})_{1\leq i\leq n}$, the $\ell_{1}$-distance between $\bm{u}$ and $\bm{v}$ is $d(\bm{u},\bm{v})=\sum_{i=1}^{n}|u_{i}-v_{i}|$. Here the sum and subtraction are on ${\mathbb{Z}}$. The $\ell_{1}$-weight of $\bm{v}$ is the $\ell_{1}$-distance between $\bm{v}$ and vector $\bm{0}$. If a code $\mathcal{C}$ satisfies that the $\ell_{1}$-weight of any codeword is $w$ for some integer $w$, then we call $\mathcal{C}$ a constant-weight code. If further the minimum $\ell_{1}$-distance between any two distinct codewords in $\mathcal{C}$ is at least $d$, we say that $\mathcal{C}$ is an $(n,d,w)_{q}$ code.

In this paper, we focus on ternary codes, that is $q=3.$ The maximum size among all $(n,d,w)_{3}$ codes is denoted by $A_{3}(n,d,w).$ We call an $(n,d,w)_{3}$ code $\mathcal{C}$ optimal if the size of $\mathcal{C}$ reaches $A_{3}(n,d,w).$ The following lemma from [30] gives us an upper bound for $A_{3}(n,2w-2,w).$

When weight $w$ is fixed, let $B(n)\triangleq\left\lfloor\frac{n(n-1-(w-1)(w-2))}{w(w-1)}\right\rfloor$ for convenience. Our main work is to show that the upper bound $B(n)+n$ can be achieved when $n$ is sufficiently large for any fixed $w$.

For any codeword $\bm{u}\in\mathcal{C}$, the support of $\bm{u}$ is defined as $supp(\bm{u})=\{x\in[n],u_{x}\neq 0\}.$ There is a canonical one-to-one correspondence between a vector $\bm{u}$ in $I_{3}^{n}$ to a subset of $[n]\times[2]$. We can express the vector $\bm{u}=(u_{1},u_{2},\ldots,u_{n})$ as a subset $\{(x,{u_{x}})\in[n]\times[2]\mid{x\in supp(\bm{u})}\}$, which we call the labeled support of $\bm{u}$. Specially for any $j\in[n]$, if $u_{j}=i\in I_{3}$, we say the position $j$ is labeled by the symbol $i$ in the codeword $\bm{u}$. For short, we usually write a member $(a,b)\in[n]\times[2]$ in the form $a_{b}$.

For ternary codes of constant weight $w$, the type of a codeword is denoted by $1^{a}2^{b}$ for some nonnegative integers $a$ and $b$ satisfying $a+2b=w$. Here, a codeword is of type $1^{a}2^{b}$ if there are in total $a$ different positions labeled by $1$ and $b$ different positions labeled by $2$ in it. We usually write $1^{w}$ instead of $1^{w}2^{0}$ for convenience. By a simple observation, there exists a necessary and sufficient condition of an $(n,2w-2,w)_{3}$ code.

On the one hand, conditions (a) and (b) can lead to an $(n,2w-2,w)_{3}$ code trivially. On the other hand, if any one of them are violated, there must be two different codewords in $\mathcal{C}$ such that the $\ell_{1}$-distance between them is less than $2w-2.$ We will use the language in graph packings to rewrite this fact in the next subsection.

In this section, we illustrate the idea of our main construction of $\mathcal{S}$ by simple cases such that the resulting code is optimal and balanced. To make our constructions simple, we assume that $\mathcal{S}$ only contains codewords of types $1^{w-2}2^{1}$ and $1^{w-4}2^{2}$. Let $x$, $y$ and $z$ denote the number of codewords of types $1^{w}$, $1^{w-2}2^{1}$ and $1^{w-4}2^{2}$, respectively.

Based on the above assumption, we first figure out the valid numbers $x$, $y$, and $z$ of codewords with different types by the balanced property. We start with $x=B(n)$, $y=n$, and $z=0$, which in total reaches the upper bound. Note that the current $S$ is the union of cliques of order $w-1$ from these $n$ codewords of type $1^{w-2}2^{1}$. Let $\ell$ be the number in the range $0\leq\ell<{w\choose 2}$ such that

that is

Let $G_{n}=K_{n}-S$, then the right hand side of Equation (1) is the number of edges in $G_{n}$. If $\ell\neq 0$, i.e., $e(K_{w})\nmid e(G_{n})$, then there does not exist a $K_{w}$-decomposition of $G_{n}$, that is the code can not be balanced. To make it balanced, we need to modify the initial numbers $x$, $y$ and $z$ so that all cliques consume $\ell$ extra edges. We do the following two operations without changing the sum $x+y+z$.

•   (O1)

  Replace one codeword of type $1^{w-2}2^{1}$ by a codeword of type $1^{w}$ to consume $(w-1)$ more edges, i.e., $x\rightarrow x+1$, $y\rightarrow y-1$;

• (O2)

  Replace two codewords of type $1^{w-2}2^{1}$ by a codeword of type $1^{w}$ and one of type $1^{w-4}2^{2}$ to consume one more edge, i.e., $y\rightarrow y-2$, $x\rightarrow x+1$ and $z\rightarrow z+1$.

By these two operations, we are able to figure out some values of $x$, $y$ and $z$, such that the total number of codewords $x+y+z=B(n)+n$ still holds, and $\ell$ extra edges are all consumed, that is, they are valid for a balanced code. Suppose that we do $a$ times of (O1) and $b$ times of (O2), then $(a,b)$ is just any nonnegative integral solution to

Then $x=B(n)+a+b$, $y=n-a-2b$, $z=b$. We always choose $b$ as the smallest nonnegative integer such that Equation (3) has a nonnegative integral solution.

Next, we try to construct $y$ codewords of type $1^{w-2}2^{1}$ and $z$ codewords of type $1^{w-4}2^{2}$ to form a new subgraph $S$. It is clear now that the new $G_{n}=K_{n}-S$ will satisfy $e(K_{w})\mid e(G_{n})$. To apply Theorem II.1 or Remark II.1, we need that $G_{n}$ is $(w-1)$-divisible, or equivalently, for all $v\in V(K_{n})$, $n-1-d_{S}(v)\equiv 0\mod{(w-1)}$. For any $v\in V(K_{n}),$ we define $y_{v}$ and $z_{v}$ the number of cliques of type $1^{w-2}2^{1}$ and $1^{w-4}2^{2}$, respectively, containing $v$ in $\mathcal{S}$. Thus $d_{S}(v)=y_{v}(w-2)+z_{v}(w-3)$ and

Denote $R(v)\triangleq y_{v}+2z_{v}$. For simplicity, we assume $R(v)$ can only be the least two non-negative integers satisfying this equation. Assume that $n\equiv t\mod(w-1)$ with $0\leq t\leq w-2$. Let

Then $R(v)\in\{R_{m},R_{m}+w-1\}$.

When constructing $\mathcal{S}$, we follow an additional rule that each vertex can be in at most one clique of type $1^{w-4}2^{2},$ i.e., $z_{v}=0$ or $1$ for all $v.$ Since there are in total $z=b$ cliques of type $1^{w-4}2^{2}$, $|\{v\in V(K_{n}):z_{v}=1\}|=b(w-2).$ Note that $d_{S}(v)=(w-2)R(v)-(w-1)z_{v}$, then $\sum_{v}d_{S}(v)=\sum_{v}(w-2)R(v)-\sum_{\{v:z_{v}=1\}}(w-1)=\sum_{v}(w-2)R(v)-b(w-1)(w-2).$ Let $c$ be the number of vertices having $R(v)=R_{m}$ in $S$. By the handshaking lemma, $\sum_{v}d_{S}(v)=2e(S)$, and we have

That is

So far, we have two equations (3) and (5), and three undetermined parameters $a,b,c$. It is possible for us to find a common nonnegative integral solution $(a,b,c)$ to both equations. Note that the value $c$ reflects the distribution of vertices in codewords of type $1^{w-2}2^{1}$ and $1^{w-4}2^{2}$ in some way. In Example II.3, an $(n,w-1)$ modular Golomb ruler produces $n$ codewords of type $1^{w-2}2^{1}$ such that each vertex occurs in exactly $(w-1)$ such codewords, which contributes $(w-1)$ to $y_{v}$ or $R(v)$ for each $v\in{\mathbb{Z}}_{n}$.

Based on the above valid choices of $a,b,c$, we have the following result.

By Lemma III.1, to show that an optimal balanced $(n,2w-2,w)_{3}$ code exists with $A_{3}(n,2w-2,w)=B(n)+n$, we only need to find an $(n,2w-2,w)_{3}$ code $\mathcal{S}$ satisfying Lemma III.1. Next, we take $n\equiv 0,1\mod(w-1)$ to show the way of computing the valid triple $(a,b,c)$, and then the numbers $x,y$ and $z$. By computing the right hand side of Equation (2), we know that $(w-1)\mid 2\ell$. Assume that $(w-1)\mid\ell$ in the following constructions, since in this case we only need to do operation (O1). We will give constructions for code $\mathcal{S}$ satisfying Lemma III.1.