# Asymmetric Lee Distance Codes for DNA-Based Storage

Ryan Gabrys14, Han Mao Kiah3, and Olgica Milenkovic4
This work was supported in part by the NSF STC Class 2010 CCF 0939370 grant
and the Strategic Research Initiative (SRI) Grant conferred by the University
of Illinois, Urbana-Champaign. Parts of the results were presented at the
Information Theory Workshop (ITW) in Jerusalem, 2015, and the International
Symposium on Information Theory (ISIT), 2015.  4 Coordinated Science
Laboratory, University of Illinois, Urbana-Champaign, USA
1Spawar Systems Center San Diego, Code 532, USA
3 School of Physical and Mathematical Sciences, Nanyang Technological
University, Singapore
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We introduce a new family of codes, termed asymmetric Lee distance (ALD)
codes, designed to correct errors arising in DNA-based storage systems and
systems with parallel string transmission protocols. ALD codes are defined
over a quaternary alphabet and analyzed in this particular setting, but the
derived results hold for other alphabet sizes as well. Our technical
contributions are two-fold: First, we derive upper bounds on the size of the
codes under the ALD metric based on linear programming techniques. Second, we
propose a number of code constructions which imply lower bounds.

Keywords. Coding for DNA-based storage, Delsarte linear programming bounds,
Lee distance.

##  I Introduction

Codes for classical symmetric channels with single-sequence inputs and single-
sequence outputs have been extensively studied in the past and a number of
diverse solutions such as algebraic codes [18], codes on graphs – e.g., LDPC
codes [17] – and polar codes [19] have been proposed to address the underlying
communication problem. Similar advances have been reported for parallel
channels [9], under the rather common assumption that the individual channels
introduce uncorrelated errors, as well as for channels with asymmetric error
properties [12]. In both scenarios, the alphabet size of the codes is
restricted by the system design, and often, input sequences are de-interleaved
or represented as arrays over smaller alphabets in order to enable more
efficient transmission. Far less is known about channels that operate on
several sequences at the same time and introduce correlated and asymmetric
symbol errors. The goal of this work is to introduce and analyze one such
scenario, motivated by an abstraction of emerging read channels used for DNA-
based storage systems [11, 22].

DNA-based storage systems have recently been implemented using biochemical
methods for synthesizing (writing) the desired digital content in DNA [3, 8,
22], and reading the content via DNA sequencing systems. DNA synthesis may be
performed with small error rates, the dominant error events being simple
substitutions [23]. The read process introduces errors that cannot be modeled
using standard information-theoretic channels. For example, the high
throughput Illumina sequencing platform may be viewed as a channel that has a
single sequence as its input and a multiset of the input sequence substrings
as its output [11]. On the other hand, fast evolving, miniaturized nanopore
sequencers such as MinION [15] introduce context-dependent, bursty deletion
errors.

The goal of this work is to propose designs for error-correcting codes capable
of handling “asymmetric” errors arising in new solid state nanopore sequencing
systems. In these systems, the DNA strings are read one symbol (nucleotide) at
the time, and the identity of the symbol is determined by the drop of an
otherwise fixed current caused by the nucleotide passing through the
sequencing pore [7, 16]. Since nucleotides have different atomic structures,
they lead to different current drop responses. A stylized depiction of one
such system response to the four nucleotides A,T,G,C is shown in Figure 1.

Figure 1: Nanopore sequencers: detection system output distribution ($y$-axis)
versus current drop in nA ($x$-axis), along with a mapping of binary words of
length two to the DNA alphabet, as adopted in our analysis.

As may be seen from Figure 1, the impulse response distributions corresponding
to T and C exhibit significant overlap, making the symbols highly confusable.
In contrast, the impulse responses corresponding to A and G are widely
separated and are very unlikely to be confused. The pairs of nucleotides G and
T and A and C are only slightly confusable. Using a sequencer with the given
symbol response would lead to _asymmetric errors_ , in so far that one would
have high incidence rates of T-C substitution errors, a significantly smaller
incidence rate of G-T and A-C substitution errors, and a very low incidence
rate of A-G substitution errors.

To abstract this error model, we introduce an asymmetric confusion graph shown
in Figure 2.

---
$\textstyle{{\tt G}\
(0;0)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1+\lambda}$$\scriptstyle{2(1+\lambda)}$$\textstyle{{\tt
T}\
(1;0)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1+\lambda}$$\scriptstyle{\lambda}$$\textstyle{(0;1)\
{\tt
C}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1+\lambda}$$\textstyle{{\tt
A}\
(1;1)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1+\lambda}$

Figure 2: A weighted confusion graph for the code alphabet $\\{{{\tt
A,T,G,C}\\}}$, involving $n=1$ symbols. The symbols are encoded as pairs of
bits.

There, we used the following binary encoding of the DNA alphabet: G
$\to(0;0)$, A $\to(1;1)$, C $\to(0;1)$ and T $\to(1;0)$. The labels of the
edges of the confusion graph depend on a positive integer parameter $\lambda$
and are chosen to have a simple form that inversely correlates with the
probability of the corresponding substitution error111Note that one can choose
different functions of $\lambda$ for the edge labels, as long as the resulting
distance $d$ satisfies $d((0;0),(1;1))<d((0;0),(1;0))<d((0;0),(1;1))$. The
proposed functions $\lambda,\lambda+1,2(\lambda+1)$ were chosen for simplicity
of analysis and based on the fact that for $\lambda=1$, they produce weights
that are powers of two, namely $1,2,4$.. As an example, the pairs of bits
$(0;0)$ and $(1;0)$ are twice more likely to be confused than the pairs of
bits $(0;0)$ and $(1;1)$. Hence, the distance “induced” by the former pair is
half the distance “induced” by the latter pair. Clearly, one could adopt a
significantly more general model for the labels of the confusion graph which
more precisely captures the actual errors in the sequencing devise; but such a
model would introduce unnecessary notational inconvenience and lead to tedious
calculations that obscure the actual ideas behind the analysis.

The confusion graph in Figure 2 has another interpretation in terms of a
parallel channel model, interesting in its own right. To motivate this
interpretation, consider Figure 3 which depicts a transmission model where two
binary input sequences are simultaneously passed through _two channels_ that
introduce substitution errors. Simultaneous errors in both strings are less
likely than individual string errors. In addition to the substitution errors,
the outputs of the channels may be _switched_ – in other words, the label of
the channel from which the output symbol originated may be in error. The
confusion graph for this type of channel is also captured by the model of
Figure 2, where the vertices are indexed by pairs of bits denoting the inputs
into the two channels. Such switching errors may arise due to loss of
synchronization in de-interleaving or due to the lack of channel side
information.

The central problems of the presented work are to evaluate the ultimate coding
limits under the distance induced by the symbol metric of Figure 2 and to
describe combinatorial constructions for _pairs_ of binary sequences
(codewords) that are at a sufficiently large “asymmetric Lee distance” (ALD)
from each other. As discussed in the sections to follow, the ALD equals a
scaled version of the Lee distance with an additional modification that two
symbols are deemed to be of higher importance than the other two symbols. The
two distinguished symbols capture the uncertainty about the actual ordering of
the readouts in the parallel channel or the fact that two nucleotide impulse
responses tend to show a high degree of overlap. The ALD was not previously
studied in the literature, although its relationship with the Lee metric
allows one to adapt certain proof methods [2] used for the latter distance to
the case of the ALD. Nevertheless, the asymmetry of the ALD also calls for
developing new, specialized coding techniques that enable deriving tight
bounds on the code size and constructing codes that approach these bounds.

The contributions of this paper are three-fold. First, we introduce a new
channel model and the corresponding distance measure that has applications in
macromolecular storage. Second, we derive upper bounds on the size of
codebooks under the newly introduced distance using recently proposed linear
programming (LP) approaches on hypergraphs [13] and LP methods based on
alphabet extensions and Delsarte-like techniques [5]. Third, we describe a
number of linear and nonlinear code constructions and accompanying decoding
procedures.

The paper is organized as follows. Section II contains a formal definition of
the ALD. Section III describes how to use linear LP methods on hypergraphs in
order to derive non-asymptotic upper bounds on codes in the ALD. Section IV
introduces a new LP framework that uses specialized alphabet embeddings.
Sections V and VI present new code constructions for the ALD.

Figure 3: A pair of channels with individual substitution errors, and outputs
which may be switched. In the given example, the outputs of the channels at
position three are switched.

##  II Preliminaries and Problem Formulation

For $a,b\in\mathbb{F}_{2}$, the indicator function $\mathbbm{1}(a,b)$ takes
the value $\mathbbm{1}(a,b)=1$ if $a=b,$ and zero otherwise. Similarly, an
$n$-variate indicator function for a collection of $n$ symbols
$a_{1},\ldots,a_{n}$ over $\mathbb{F}_{2}$ takes the value
$\mathbbm{1}(a_{1},\ldots,a_{n})=1$ if $a_{1}=a_{2}=\ldots=a_{n},$ and zero
otherwise. As an illustration, $\mathbbm{1}(0,0,0)=1,$ while
$\mathbbm{1}(0,1,1)=0$.

Consider next four sequences
${\boldsymbol{a}}=(a_{1},\ldots,a_{n}),{\boldsymbol{b}}=(b_{1},\ldots,b_{n}),{\boldsymbol{c}}=(c_{1},\ldots,c_{n}),{\boldsymbol{d}}=(d_{1},\ldots,d_{n})\in\mathbb{F}_{2}^{n}$,
paired as $({\boldsymbol{a}};{\boldsymbol{b}})$ and
$({\boldsymbol{c}};{\boldsymbol{d}})$. The pairing of two binary sequences of
length $n$ results in one sequence over a quaternary alphabet as illustrated
by the following example $((0,1,0);(1,1,1))=((0;1),(1;1),(0;1))$ where
$((0;1),(1;1),(0;1))\in(\mathbb{F}_{2}^{2})^{3}$.

For a positive integer $\lambda$, the ALD
$d_{\lambda}(({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}}))$
between two pairs of binary sequences
$({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}})$ is
defined as

$\displaystyle
d_{\lambda}(({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}}))=$
$\displaystyle\sum_{i=1}^{n}\Big{(}(1+\lambda)\left(\mathbbm{1}(a_{i},b_{i})+\mathbbm{1}(c_{i},d_{i})\right)+$
(1)
$\displaystyle\lambda\mathbbm{1}(a_{i},\bar{b}_{i},\bar{c}_{i},d_{i})-2(1+\lambda)\mathbbm{1}(a_{i},b_{i},c_{i},d_{i})\Big{)},$

where $\bar{a}$ denotes the complement of the bit $a$.

The confusion graph for a code of length $n=1$ under the ALD matches the one
depicted in Figure 2: For example, it is easy to see that
$d_{\lambda}((0;0),(1;1))$ equals

$\displaystyle(1$
$\displaystyle+\lambda)\left(\mathbbm{1}(0,0)+\mathbbm{1}(1,1)\right)+\lambda\mathbbm{1}(0,1,0,1)-2(1+\lambda)\mathbbm{1}(0,0,1,1)$
$\displaystyle=(1+\lambda)(1+1)+\lambda\;0-2(1+\lambda)\;0=2(1+\lambda).$

It can be verified that
$d_{\lambda}(({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}}))$
is a metric with respect to the pairs of binary sequences in the argument:
$d_{\lambda}$ is non-negative and symmetric, and it satisfies the triangle
inequality. From (1) and the confusion graph, we also observe that the ALD is
asymmetric in terms of the costs of different transitions, and in particular,
complementary pairs are treated differently than non-complementary pairs.
Furthermore, when pairs are complementary, the distance depends on the binary
weight of the pairs. The choice of the parameter $\lambda$ governs the degree
of asymmetry.

In order to highlight the relationship between
$d_{\lambda}(({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}}))$
and the Lee distance, let us first recall that the Lee distance between two
symbols $a,b$ over $\mathbb{Z}_{4}$ is defined as
$d_{L}(a,b)=\min(|a-b|,4-|a-b|)$. Next, let us introduce a mapping
$\mathcal{Z}:\mathbb{F}_{2}^{2}\to\mathbb{Z}_{4}$ such that $(0;0)\to 1$,
$(1;0)\to 0$, $(0;1)\to 2$ and $(1;1)\to 3$. By changing the weight between
$(1;0)$ and $(0;1)$ from $\lambda$ to $2(1+\lambda)$, we arrive at a scaled
version of the Lee distance $d_{L}(a,b)$ between two symbols
$a,b\in\mathbb{Z}_{4}$, i.e.,

$\displaystyle(1+\lambda)\,\cdot\,\min\\{{4-|a-b|,|a-b|\\}}=(1+\lambda)\,\cdot\,d_{L}(a,b).$
(2)

More precisely, for two sequences
${\boldsymbol{z}}_{1}=({\boldsymbol{a}};{\boldsymbol{b}}),{\boldsymbol{z}}_{2}=({\boldsymbol{c}};{\boldsymbol{d}})$
viewed over $\mathbb{Z}_{4}^{n}$, we have

$\displaystyle
d_{\lambda}({\boldsymbol{z}}_{1},{\boldsymbol{z}}_{2})=(1+\lambda)\cdot
d_{L}({\boldsymbol{z}}_{1},{\boldsymbol{z}}_{2})-$ (3)
$\displaystyle(2+\lambda)\sum_{i:\,\\{{z_{1,i},z_{2,i}\\}}=\\{{0,2\\}}}\,(1-\mathbbm{1}(z_{1,i},z_{2,i}))\leqslant(1+\lambda)\cdot
d_{L}({\boldsymbol{z}}_{1},{\boldsymbol{z}}_{2}).$

---
$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1+\lambda}$$\scriptstyle{2(1+\lambda)}$$\textstyle{0\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1+\lambda}$$\scriptstyle{2(1+\lambda)}$$\textstyle{2\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1+\lambda}$$\textstyle{3\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{1+\lambda}$

Figure 4: A weighted confusion graph for the Lee distance scaled by
$1+\lambda$.

Simple inspection of the transition diagram for the ALD also reveals that

$d_{\lambda}(z_{1},z_{2})\geqslant\frac{\lambda}{2}d_{L}(z_{1},z_{2}).$

Furthermore, the Lee distance over $\mathbb{Z}_{4}$ equals the Hamming
distance over $\mathbb{Z}_{2}^{2}$ under Gray mappings from
$\mathbb{F}_{2}^{2}$ and $\mathbb{Z}_{4}$. Hence, since $\mathcal{Z}$ is a
Gray map, we have

$d_{\lambda}(z_{1},z_{2})\geqslant\frac{\lambda}{2}d_{H}(z_{1},z_{2}).$

Note that the distance between pairs of symbols
$(a;b),(c;d)\in\mathbb{F}^{2}_{2}$ under the ALD depends on the exact values
of the bits in $(a;b)$ and $(c;d)$ and not on their sum. For example, if
$\lambda=1$, $(a;b)=(0;0)$ and $(c;d)=(1;1)$ then
$d_{\lambda}((a;b),(c;d))=4$; on the other hand, for the same choice of the
parameter $\lambda$ and for $(a;b)=(1;0)$ and $(c;d)=(0;1)$, we have
$d_{\lambda}((a;b),(c;d))=1$, despite the fact that in both cases we have
$(a;b)+(c;d)=(a+c;b+d)=(1;1)$. At the same time, for both choices of paired
vectors, the underlying Lee distance equals two, as the Lee distance for the
given mapping $\mathcal{Z}$ only depends on the Hamming weight of
$(a;b)+(c;d)$. The connection between the ALD, Lee metric, and asymmetric
error-correcting codes will be used in some of our subsequent derivations.

In what follows, we refer to an error that causes a transition between $(1;0)$
and $(0;1)$ as a Class 1 error; similarly, we refer to an error that causes a
single substitution in one of the input strings as a Class 2 error. An error
that causes a transition between $(0;0)$ and $(1;1)$ is referred to as a Class
3 error. Note that based on Figure 2, an edge in the confusion graph
corresponding to a Class 1 error has weight $\lambda$, an edge corresponding
to a Class 2 error has weight $1+\lambda$, while an edge corresponding to a
Class 3 error has weight $2(1+\lambda)$.

Let $d$ be a positive integer. We say that two pairs of sequences
$({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}})\in\mathbb{F}^{n}_{2}\times\mathbb{F}^{n}_{2}$
are (d,$\lambda$)-distinguishable if their ALD $d_{\lambda}$ is at least $d$;
conversely, we say that two pairs of sequences are (d,
$\lambda$)-indistinguishable if their ALD is less than $d$. Furthermore, for
an ordered pair of sequences
$({{\boldsymbol{a}}};{{\boldsymbol{b}}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$,
we let

$\displaystyle{\cal
B}_{(r,\lambda)}({\boldsymbol{a}};{\boldsymbol{b}}):=\\{({\boldsymbol{c}};{\boldsymbol{d}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}:d_{\lambda}(({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}}))\leqslant
r\\}$ (4)

denote the set of pairs of sequences that are
$(r+1,\lambda)$-indistinguishable from $({\boldsymbol{a}};{\boldsymbol{b}})$.
We also use $A_{\lambda}(n,d)$ to denote the largest number of
$(d,\lambda)$-distinguishable sequences of length $n$.

###### Example 1

. Let
$\left((0,1,1)\,;\,(1,1,1)\right)\in\mathbb{F}_{2}^{3}\times\mathbb{F}_{2}^{3}.$
Then, the following eight vector pairings

$\displaystyle\left((0,1,1)\,;\,(1,1,1)\right),\left((1,1,1)\,;\,(1,1,1)\right),\left((0,1,1)\,;\,(0,1,1)\right),$
$\displaystyle\left((1,1,1)\,;\,(0,1,1)\right),\left((0,0,1)\,;\,(1,1,1)\right),\left((0,1,1)\,;\,(1,0,1)\right),$
$\displaystyle\left((0,1,0)\,;\,(1,1,1)\right),\left((0,1,1)\,;\,(1,1,0)\right)$

are $(3,1)$-indistinguishable from $\left((0,1,1)\,;\,(1,1,1)\right)$. For
example, the ALD between $\left((1,1,1)\,;\,(1,1,1)\right)$, the second pair
in the above list, and $\left((0,1,1)\,;\,(1,1,1)\right)$, the chosen pair,
equals $1+\lambda=2$, and this distance arises from the pair of symbols in the
first positions, $(1;1)$ and $(0;1)$.

On the other hand, there are seven pairs of sequences
$(3,1)$-indistinguishable from $\left((0,0,0)\,;\,(0,0,0)\right)$, namely

$\displaystyle\left((0,0,0)\,;\,(0,0,0)\right),\left((1,0,0)\,;\,(0,0,0)\right),\left((0,0,0)\,;\,(1,0,0)\right),$
$\displaystyle\left((0,1,0)\,;\,(0,0,0)\right),\left((0,0,0)\,;\,(0,1,0)\right),\left((0,0,1)\,;\,(0,0,0)\right),$
$\displaystyle\left((0,0,0)\,;\,(0,0,1)\right).$

Note that the sum of the two vectors in the first example equals
${\boldsymbol{a}}+{\boldsymbol{b}}=(0,1,1)+(1,1,1)=(1,0,0)$, and hence has
Hamming weight one. On the other hand, the sum of the two vectors in the
second example equals
${\boldsymbol{a}}+{\boldsymbol{b}}=(0,0,0)+(0,0,0)=(0,0,0)$ and has Hamming
weight zero.

Although the ALD depends on the exact values of its arguments
${{\boldsymbol{a}}},{{\boldsymbol{b}}}$, we show next that $|{\cal
B}_{(r,\lambda)}({\boldsymbol{a}};{\boldsymbol{b}})|$ only depends on the
Hamming weight of ${{\boldsymbol{a}}}+{{\boldsymbol{b}}}$, where the sum is
taken modulo $2$. This claim parallels a result for the $Z$-channel, which
asserts that the size of the error sphere is a function of the Hamming weights
of the transmitted sequences [12]. To draw upon this parallel, we subsequently
denote the Hamming weight of ${{\boldsymbol{a}}}+{{\boldsymbol{b}}}$ by
$w({\boldsymbol{a}};{\boldsymbol{b}})$. Clearly,
$w({\boldsymbol{a}};{\boldsymbol{b}})=d_{H}({\boldsymbol{a}},{\boldsymbol{b}})$,
where $d_{H}({\boldsymbol{a}},{\boldsymbol{b}})$ denotes the Hamming distance
between ${\boldsymbol{a}}$ and ${\boldsymbol{b}}$.

###### Lemma 1

. Let
$({\boldsymbol{a}};{\boldsymbol{b}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
be a pair of sequences with weight $w({\boldsymbol{a}};{\boldsymbol{b}})$.
Then, $|{\cal B}_{(r,\lambda)}({\boldsymbol{a}};{\boldsymbol{b}})|$ depends on
$({\boldsymbol{a}};{\boldsymbol{b}})$ only through
$w({\boldsymbol{a}};{\boldsymbol{b}})$.

###### Proof:

From (1) and (4), one can see that $|{\cal
B}_{(r,\lambda)}({\boldsymbol{a}};{\boldsymbol{b}})|$ equals the number of
paired sequences
$({\boldsymbol{c}};{\boldsymbol{d}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
that satisfy

$\displaystyle\sum_{i=1}^{n}\Big{(}(1+\lambda)\left(\mathbbm{1}(a_{i},b_{i})+\mathbbm{1}(c_{i},d_{i})\right)+$
$\displaystyle\lambda\mathbbm{1}(a_{i},\bar{b}_{i},\bar{c}_{i},d_{i})-2(1+\lambda)\mathbbm{1}(a_{i},b_{i},c_{i},d_{i})\Big{)}\leqslant
r.$

First, assume that ${\boldsymbol{a}}$ and ${\boldsymbol{b}}$ are fixed and let
$E=\\{i:a_{i}=b_{i}\\}$ and $D=\\{i:a_{i}\neq b_{i}\\}$. We are interested in
the number of paired sequences
$({\boldsymbol{c}};{\boldsymbol{d}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
that satisfy

$\displaystyle\sum_{i\in
E}(1+\lambda)(1+\mathbbm{1}(c_{i},d_{i}))-2(1+\lambda)\mathbbm{1}(a_{i},c_{i},d_{i})+$
$\displaystyle\sum_{i\in
D}(1+\lambda)\,\mathbbm{1}(c_{i},d_{i})+\lambda\mathbbm{1}(a_{i},\bar{c}_{i},d_{i})\leqslant
r.$

The above inequality may be rewritten as

$\displaystyle(1+\lambda)\,\sum_{i=1}^{n}\mathbbm{1}(c_{i},d_{i})-2(1+\lambda)\sum_{i\in
E}\,\mathbbm{1}(a_{i},c_{i},d_{i})+$ $\displaystyle\lambda\sum_{i\in
D}\mathbbm{1}(a_{i},\bar{c}_{i},d_{i})\leqslant r-(1+\lambda)\,|E|.$

The first term in the above sum does not depend on the choice of
${\boldsymbol{a}}$. For $i\in E$, independent on the choice of $a_{i}$, the
second sum provides a non-zero contribution if and only if
$a_{i}=c_{i}=d_{i}$. For $i\in D$, independent on the choice of $a_{i}$, the
third sum provides a non-zero contribution if and only if
$a_{i}=\bar{c}_{i}=d_{i}$. Hence, it follows that the number of choices for
${\boldsymbol{c}}$ and ${\boldsymbol{d}}$ satisfying the inequality depends
only on $|E|$ and $|D|$, and consequently on
$w({\boldsymbol{a}};{\boldsymbol{b}})$ only, as
$w({\boldsymbol{a}};{\boldsymbol{b}})=|D|$ and $|E|+|D|=n$. ∎

Next, we turn our attention to deriving an expression for
$\mathcal{V}_{\lambda}(n,w,r):=|{\cal
B}_{(r,\lambda)}({\boldsymbol{a}};{\boldsymbol{b}})|$, with
$w({\boldsymbol{a}};{\boldsymbol{b}})=w$. Recall that ${\cal
B}_{(r,\lambda)}({\boldsymbol{a}};{\boldsymbol{b}})$ was defined in (4) and
let

$\mathbf{S}_{\lambda}(n,w,r):=\\{({{\boldsymbol{c}}};{{\boldsymbol{d}}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}:d_{\lambda}(({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}}))=r\\},$

with $S_{\lambda}(n,w,r)=|\mathbf{S}_{\lambda}(n,w,r)|$. Clearly,
$\mathcal{V}_{\lambda}(n,w,r)=\sum_{j=0}^{r}S_{\lambda}(n,w,j).$ The next
lemma establishes a formula for $S_{\lambda}(n,w,r)$ which may be subsequently
used to determine $\mathcal{V}_{\lambda}(n,w,r)$. For simplicity of notation,
we use $k\ast\ell\ast m\ast\lambda=r$ to denote $(2k+\ell)(1+\lambda)+\lambda
m=r$, and similarly, $k\ast\ell\ast m\ast\lambda\leqslant r$ to denote
$(2k+\ell)(1+\lambda)+\lambda m\leqslant r$.

###### Lemma 2

. For positive integers $n,w$ and $r$ such that $w\leqslant n$,

$S_{\lambda}(n,w,r)=\sum_{k,\ell,m:\,k\ast\ell\ast
m\ast\lambda=r}\left(\begin{array}[]{c}w\\\
m\end{array}\right)\left(\begin{array}[]{c}n-w\\\
k\end{array}\right)\left(\begin{array}[]{c}n-k-m\\\
\ell\end{array}\right)2^{\ell}.$

###### Proof:

We count the number of sequences
$({\boldsymbol{c}};{\boldsymbol{d}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
such that
$d_{\lambda}(({\boldsymbol{a}};{\boldsymbol{b}});({\boldsymbol{c}};{\boldsymbol{d}}))=r,$
where $w({\boldsymbol{a}};{\boldsymbol{b}})=w$. Suppose that
$({\boldsymbol{c}};{\boldsymbol{d}})$ is the result of $m$ Class 1 errors, $k$
Class 3 errors, and $\ell$ Class 2 errors occurring in
$({\boldsymbol{a}};{\boldsymbol{b}})$. We first arbitrarily choose the
locations of any of the Class 1 errors from among the $w$ locations in
$({\boldsymbol{a}};{\boldsymbol{b}})$ for which $a_{1}\neq b_{1}$. There are
$\left(\begin{array}[]{c}w\\\ m\end{array}\right)$ choices for the locations.
Similarly, we can choose the locations of the Class 3 errors amongst the $n-w$
locations where $a_{1}=b_{1}$. There are $\left(\begin{array}[]{c}n-w\\\
k\end{array}\right)$ choices for these locations. The locations of the Class 2
errors are chosen among the remaining $n-k-m$ locations in
$({\boldsymbol{a}};{\boldsymbol{b}})$, and this choice of locations is coupled
with the choice of which of the $2$ available bits is changed (recall that a
Class 2 error causes a substitution error in one of the two input strings at
any given location). There are $\left(\begin{array}[]{c}n-k-m\\\
\ell\end{array}\right)2^{\ell}$ choices for the Class 2 errors, which proves
the statement in the lemma. ∎

###### Corollary 3

. For positive integers $n,w$ and $r$ such that $w\leqslant n$,

$\mathcal{V}_{\lambda}(n,w,r)=\sum_{k,\ell,m:\,k\ast\ell\ast
m\ast\lambda\leqslant r}\left(\begin{array}[]{c}w\\\
m\end{array}\right)\left(\begin{array}[]{c}n-w\\\
k\end{array}\right)\left(\begin{array}[]{c}n-k-m\\\
\ell\end{array}\right)2^{\ell}.$

The next corollary will be useful for the derivations in the sections to
follow.

###### Corollary 4

. For positive integers $n,w$ and $r$ such that $w\leqslant n$, it holds that
$\mathcal{V}_{\lambda}(n,w,r)\geqslant\mathcal{V}_{\lambda}(n,w-1,r)$.

###### Proof:

To prove the claimed result, consider the ratio

$\displaystyle\frac{\left(\begin{array}[]{c}w\\\
m\end{array}\right)\left(\begin{array}[]{c}n-w\\\
k\end{array}\right)\left(\begin{array}[]{c}n-k-m\\\
\ell\end{array}\right)2^{\ell}}{\left(\begin{array}[]{c}w-1\\\
m\end{array}\right)\left(\begin{array}[]{c}n-w-1\\\
k\end{array}\right)\left(\begin{array}[]{c}n-k-m\\\
\ell\end{array}\right)2^{\ell}}=\frac{w(n-w)}{(w-m)(n-w-k)}.$

Since $w\geqslant w-m$ and $n-w\geqslant n-w-k$ for all possible parameter
choices, one has $\frac{w(n-w)}{(w-m)(n-w-k)}\geqslant 1$. Given that

$\mathcal{V}_{\lambda}(n,w,r)=\sum_{k\ast\ell\ast m\ast\lambda\leqslant
r}\left(\begin{array}[]{c}w\\\
m\end{array}\right)\left(\begin{array}[]{c}n-w\\\
k\end{array}\right)\left(\begin{array}[]{c}n-k-m\\\
\ell\end{array}\right)2^{\ell}$

it clearly follows that
$\frac{\mathcal{V}_{\lambda}(n,w,r)}{\mathcal{V}_{\lambda}(n,w-1,r)}\geqslant
1$. Thus,
$\mathcal{V}_{\lambda}(n,w,r)\geqslant\mathcal{V}_{\lambda}(n,w-1,r),$ as
desired. ∎

##  III Upper Bounds from Hypergraphs

In what follows, we focus our attention on non-asymptotic upper bounds derived
based on a recent optimization on hypergraphs framework. We start our
exposition by introducing the relevant notation borrowed from [13].

###  III-A Hypergraph Preliminaries

A hypergraph ${\cal H}$ is an ordered pair of sets $(V,E)$, where $V$ denotes
the set of vertices and where $E$ denotes the set of hyperedges, i.e.,
selected subsets of $V$. A _matching_ in ${\cal H}$ is a set of disjoint
hyperedges, and we use $\nu({\cal H})$ to denote the size of the largest
matching, i.e., the maximum number of disjoint hyperedges in ${\cal H}$. The
number $\nu({\cal H})$ is also known as the matching number of the hypergraph
${\cal H}$. A _fractional matching_ of a hypergraph is a function $f$ with
domain $E$ and range $[0,1]$ that assigns a value $f(e)$ to each hyperedge $e$
so that $\sum_{e\in E(v)}\,f(e)\leqslant 1$ for each vertex $v$ and its set of
incident hyperedges $E(v)$. If we restrict the range of $f$ to $\\{{0,1\\}}$,
the fractional matching reduces to the indicator function of a matching. The
_fractional matching number_ of a hypergraph ${\cal H}$, denoted by
$\nu^{*}({\cal H})$, equals

$\nu^{*}({\cal H})=\sup_{f:f\;\text{a fractional matching}}\;\sum_{e\in
E}\,f(e),$

or equivalently

$\nu^{*}({\cal
H})=\sup\left\\{\sum_{i=1}^{|E|}\,\textbf{z}_{i}\,:\textbf{M}\cdot\textbf{z}\leqslant
1,\textbf{z}\in\mathbb{R}_{+}^{|E|}\right\\},$

where M denotes the vertex-hyperedge incidence matrix of the hypergraph.

A subset of the vertex set that has a nonempty intersection with every edge is
called a _transversal_ of the hypergraph ${\cal H}$, and the smallest size of
a transversal is called the transversal number of the hypergraph, denoted by
$\tau({\cal H})$. Similarly as for the case of matchings, one may define a
_fractional transversal_ as a function $g$ with domain $V$ and range $[0,1]$
that assigns a value $g(v)$ to each vertex $v$ so that $\sum_{v\in
V(e)}\,g(v)\geqslant 1$ for each edge $e$ and its set of incident vertices
$V(e)$. If we restrict the range of $g$ to $\\{{0,1\\}}$, the fractional
transversal reduces to the indicator function of a transversal. The
_fractional transversal number_ of a hypergraph ${\cal H}$, denoted by
$\tau^{*}({\cal H})$, equals

$\tau^{*}({\cal H})=\inf_{g:g\;\text{a fractional transversal}}\;\sum_{v\in
V}\,g(v),$

or equivalently

$\tau^{*}({\cal
H})=\inf\left\\{\sum_{i=1}^{|V|}\,\textbf{z}_{i}\,:\textbf{M}^{T}\cdot\textbf{z}\geqslant
1,\textbf{z}\in\mathbb{R}_{+}^{|V|}\right\\}.$

Using duality arguments, it can be shown that $\nu^{*}({\cal
H})=\tau^{*}({\cal H})$.

Next, fix two positive integers $r$ and $\lambda$ and recall the definition of
${\cal B}_{(r,\lambda)}$ from (4). We introduce the following hypergraph

${\cal H}_{(r,\lambda),n}=(\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n},\\{{\cal
B}_{(r,\lambda)}({\boldsymbol{a}};{\boldsymbol{b}}):({\boldsymbol{a}};{\boldsymbol{b}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\\}),$

with vertex set $\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$ and edges that
represent subsets of vertices within ALD balls of radius $r$ around some
vertex. Then, the following result follows directly from [13].

###### Lemma 5

. Given the hypergraph ${\cal H}_{(r,\lambda),n}$, one has

$A_{\lambda}(n,2r+1)=\nu({\cal H}_{(r,\lambda),n})\leqslant\tau^{*}({\cal
H}_{(r,\lambda),n}).$

Intuitively, the lemma asserts the fact that a matching in the hypergraph
corresponds to a packing of balls in the ALD metric, as no two hyperedges
(balls) are allowed to intersect. Thus, the matching number is the largest
number of disjoint balls that may be packed in the corresponding space, and
hence it is equal to the largest size of an ALD code.

We find the following reformulation of the aforementioned bound useful [13].
Let ${\mathbf{A}}_{(r,\lambda)}$ be a square matrix with $4^{n}$ rows and
columns, indexed by the elements of
$\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$. We set
${\mathbf{A}}_{(r,\lambda)}(i,j)=1$ if
$({\boldsymbol{x}}_{i,1};{\boldsymbol{x}}_{i,2})\in{\cal
B}_{(r,\lambda)}({\boldsymbol{x}}_{j,1};{\boldsymbol{x}}_{j,2}),$ and zero
otherwise, for any two pairs
$({\boldsymbol{x}}_{i,1};{\boldsymbol{x}}_{i,2}),({\boldsymbol{x}}_{j,1};{\boldsymbol{x}}_{j,2})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$.
Observe that ${\mathbf{A}}_{(r,\lambda)}$ is the adjacency matrix of the ALD
$r$-confusion graph.

Let $\mathbb{R}_{+}$ denote the set of non-negative reals. Then,

$\displaystyle\tau^{*}({\cal
H}_{(r,\lambda),n})=\min\Bigg{\\{}\sum_{i=1}^{4^{n}}w_{i}:{{\boldsymbol{w}}}\in\mathbb{R}_{+}^{4^{n}},\,{\mathbf{A}}^{T}_{(r,\lambda)}\cdot{{\boldsymbol{w}}}\geqslant{\bf
1}\Bigg{\\}}.$ (5)

For simplicity, we subsequently write
$\tau^{*}\left({\mathbf{A}}_{(r,\lambda)}\right)$ to refer to $\tau^{*}({\cal
H}_{(r,\lambda),n})$, as $\tau^{*}({\cal H}_{(r,\lambda),n})$ is a function of
${\mathbf{A}}_{(r,\lambda)}$ only. Note that (5) is an LP involving $4^{n}$
constraints, which may be prohibitively large to solve even for moderate
values of $n$. We show next how to significantly reduce this number of
constraints by using _hypergraph symmetries_ [6].

Following the approach of [6], define a directed graph ${\cal
G}_{(r,\lambda)}$ on the vertex set
$\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$, with an arc from
$({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2})$ to
$({\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2})$ iff
$({\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2})\in{\cal
B}_{(r,\lambda)}({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2})$. An automorphism
$\pi$ of ${\cal G}_{(r,\lambda)}$ is a permutation in $\mathbb{S}_{4^{n}}$
(the symmetric group of order $(4^{n})!$) that operates on the vertex set and
preserves adjacencies. The set of all automorphisms of ${\cal
G}_{(r,\lambda)}$ is denoted by ${\rm Aut}({\cal G}_{(r,\lambda)})$ and
represents a subgroup of $\mathbb{S}_{4^{n}}$. The group ${\rm Aut}({\cal
G}_{(r,\lambda)})$ induces a relation $R$ on the vertices of ${\cal
G}_{(r,\lambda)}$ in the following manner: $(x,y)\in R$ iff there exists a
$\pi\in{\rm Aut}({\cal G})$ such that $\pi(x)=y.$ Clearly, $R$ is an
equivalence relation. Hence, given a subgroup $H$ of ${\rm Aut}({\cal
G}_{(r,\lambda)})$ of order $n_{H}$, we may use $H$ to partition the vertex
set into $n_{H}$ equivalence classes $\\{V_{H,1},\ldots,V_{H,n_{H}}\\}$.

With a change in the indices of the corresponding expression in [6], let
${\mathbf{A}}_{H,(r,\lambda)}$ be an $n_{H}\times n_{H}$ matrix indexed by the
elements of the subgroup $H$, with entries ${\mathbf{A}}_{H,(r,\lambda)}(i,j)$
defined according to

$\frac{\Big{|}\Big{\\{}\big{(}({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2}),({\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2})\big{)}:({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2})\in
V_{H,j},\ ({\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2})\in V_{H,i}\cap{\cal
B}_{(r,\lambda)}({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2})\Big{\\}}\Big{|}}{|V_{H,j}|},\,1\leqslant
i,j\leqslant n_{H}.$

We interpret the matrix ${\mathbf{A}}_{H,(r,\lambda)}$ as follows: One is
given $n_{H}$ equivalence classes, representing the indices of the rows and
columns of the matrix. The entry in row $i$ and column $j$ is the normalized
number of pairs
$({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2}),({\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2})$
such that $({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2})$ is in the equivalence
class $j$, and $({\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2})$ is in a subset of
the equivalence class $i$ that comprises points in an $r$-ball around
$({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2})$. Normalization is performed with
respect to the size of the $j$-th equivalence class, $|V_{H,j}|$.

Using the ALD hypergraph symmetries, we can simplify the statement in Lemma 5
and arrive at the following theorem which follows from the methods introduced
in [6, 13].

###### Theorem 6

. Let $H$ be a subgroup of ${\rm Aut}({\cal G}_{(r,\lambda)})$ and let
${\mathbf{A}}_{H,(r,\lambda)}$ be as defined before. Then,

$\tau^{*}({\mathbf{A}}_{(r,\lambda)})=\min\Bigg{\\{}\sum_{i=1}^{n_{H}}|V_{H,i}|\cdot
w_{i}:{\boldsymbol{w}}\in\mathbb{R}_{+}^{n_{H}},{\mathbf{A}}_{H,(r,\lambda)}^{T}\cdot{{\boldsymbol{w}}}\geqslant
1\Bigg{\\}},$

and $A_{\lambda}(n,2r+1)\leqslant\tau^{*}({\mathbf{A}}_{(r,\lambda)}).$

We next identify a set of automorphisms of $\mathcal{G}_{(r,\lambda)}$ that
allow us to apply Theorem 6 to the case of ALD codes. For every permutation
$\sigma=(\sigma(1),\ldots,\sigma(n))\in\mathbb{S}_{n}$ and for every
${\boldsymbol{z}}\in\mathbb{F}_{2}^{n}$, let

$\displaystyle\pi_{\sigma,{{\boldsymbol{z}}}}:\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\to\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
(6)

be a mapping such that for all
$({\boldsymbol{a}};{\boldsymbol{b}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$,
$(\pi_{\sigma,{{\boldsymbol{z}}}}({{\boldsymbol{a}}};{{\boldsymbol{b}}}))_{i}=(a_{\sigma(i)};b_{\sigma(i)})$
if $z_{i}=0$ and
$(\pi_{\sigma,{\boldsymbol{z}}}({{\boldsymbol{a}}};{{\boldsymbol{b}}}))_{i}=(\bar{a}_{\sigma(i)};\bar{b}_{\sigma(i)})$
otherwise. It is straightforward to see that
$H=\\{\pi_{\sigma,{\boldsymbol{z}}}:\sigma\in\mathbb{S}_{n},{\boldsymbol{z}}\in\mathbb{F}_{2}^{n}\\}$
is a subgroup of ${\rm Aut}({\cal G}_{(r,\lambda)})$: Coordinate permutations
do not change the code, and complementation preserves the ALD symmetries of
the pairings.

The subgroup $H$ partitions the space
$\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$ into $n+1$ equivalence classes,
with
$({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}})\in\mathbb{F}_{2}^{n}$
belonging to the same equivalence class if and only if
$w({\boldsymbol{a}};{\boldsymbol{b}})=w({\boldsymbol{c}};{\boldsymbol{d}})$.
The equivalence class containing a pair of vectors ${\boldsymbol{a}}$ and
${\boldsymbol{b}}$ of weight $w({\boldsymbol{a}};{\boldsymbol{b}})=i$ has
$2^{n}\,\binom{n}{i}$ elements. Consequently,

$\displaystyle\tau^{*}({\mathbf{A}}_{(r,\lambda)})$
$\displaystyle=\min\Bigg{\\{}2^{n}\cdot\sum_{\ell=0}^{n}\left(\begin{array}[]{c}n\\\
\ell\end{array}\right)\cdot w_{\ell}:$ (9) $\displaystyle\hskip
56.9055pt{{\boldsymbol{w}}}\in\mathbb{R}_{+}^{n+1},{\mathbf{A}}_{H,(r,\lambda)}^{T}\cdot{\boldsymbol{w}}\geqslant
1\Bigg{\\}}.$

$n\backslash d_{\lambda=1}$ 3 5 7 9 11 13 1 3 1 1 1 1 1 2 9 2 2 1 1 1 3 30 7 5
2 2 1 4 99 21 13 5 4 2 5 336 67 35 12 9 4 6 1161 219 101 32 21 9 7 4080 731
296 90 51 20 8 14535 2483 895 258 130 50 9 52377 8563 2783 771 348 127 10
190557 29901 8890 2361 966 340

TABLE I: Bounds on ALD code sizes based on the LP in (9)

By using the automorphism group, the dimension of the weight vector
${\boldsymbol{w}}$ reduces from $4^{n}$, as given in (5), to $n+1$, as given
in (9). Solutions of the LP of (9), for $n\leqslant 9$ and odd
$d_{\lambda=1}\leqslant 13$ are listed in Table I.

To complete our analysis, we exhibit two feasible weight vectors for the
optimization problem in (9) which lead to appropriate upper bounds on the size
of ALD codes.

###### Theorem 7

. Let $\mathcal{V}_{\lambda}(n,w,r)=\mathcal{V}_{\lambda}(n,0,r)$ for $w<0$.
Suppose that $n,r,\lambda$ are positive integers, and set
$\mu=\lfloor\frac{r}{1+\lambda}\rfloor$. Let the elements of
${{\boldsymbol{w}}}=(w_{0},w_{1},\ldots,w_{n})\in\mathbb{R}_{+}^{n+1}$ be
given as

$w_{i}=\frac{1}{\mathcal{V}_{\lambda}(n,i-\mu,r)}.$

Then, Theorem 6 leads to

$A_{\lambda}(n,2r+1)\leqslant
2^{n}\cdot\sum_{i=0}^{n}\left(\begin{array}[]{c}n\\\
i\end{array}\right)\cdot\frac{1}{\mathcal{V}_{\lambda}(n,i-\mu,r)}.$

###### Proof:

The result follows directly from Theorem 6 and (9), provided that we can show
that ${\mathbf{A}}_{H,(r,\lambda)}^{T}\cdot{\boldsymbol{w}}\geqslant 1$. For
the given weight assignment, and for an arbitrary choice of an equivalence
class $V_{H,j}$ and $({\boldsymbol{a}};{\boldsymbol{b}})\in V_{H,j}$, we have

$\displaystyle\sum_{\\{(({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}})):({\boldsymbol{a}};{\boldsymbol{b}})\in
V_{H,j},({\boldsymbol{c}};{\boldsymbol{d}})\in V_{H,i}\cap{\cal
B}_{(r,\lambda)}({\boldsymbol{a}};{\boldsymbol{b}})\\}}\frac{w_{w({\boldsymbol{c}};{\boldsymbol{d}})}}{|V_{H,j}|}$
$\displaystyle=\sum_{({\boldsymbol{c}};{\boldsymbol{d}})\in{\cal
B}_{\begin{subarray}{c}(r,\lambda)\end{subarray}}({\boldsymbol{a}};{\boldsymbol{b}})}{\boldsymbol{w}}_{w({\boldsymbol{c}};{\boldsymbol{d}})}$
$\displaystyle=\sum_{({\boldsymbol{c}};{\boldsymbol{d}})\in{\cal
B}_{(r,\lambda)}({{\boldsymbol{a}}};{{\boldsymbol{b}}})}\frac{1}{\mathcal{V}_{\lambda}(n,w({{\boldsymbol{c}}};{{\boldsymbol{d}}})-\mu,r)}$
$\displaystyle\geqslant\sum_{({\boldsymbol{c}};{\boldsymbol{d}})\in{\cal
B}_{(r,\lambda)}({{\boldsymbol{a}}};{{\boldsymbol{b}}})}\frac{1}{\mathcal{V}_{\lambda}(n,w({{\boldsymbol{a}}};{{\boldsymbol{b}}}),r)}$
$\displaystyle=\frac{\mathcal{V}_{\lambda}(n,w({{\boldsymbol{a}}};{{\boldsymbol{b}}}),r)}{\mathcal{V}_{\lambda}(n,w({{\boldsymbol{a}}};{{\boldsymbol{b}}}),r)}=1,$

where the inequality follows from Corollary 4 and the observation that the
weight of any element in ${\cal
B}_{(r,\lambda)}({\boldsymbol{a}};{\boldsymbol{b}})$ is at most
$w({\boldsymbol{a}};{\boldsymbol{b}})+\mu$. ∎

Note that the choice of weights ${\boldsymbol{w}}$ from the previous theorem
produces the best possible upper bound on $A_{\lambda=r}(n,2r+1)$ achievable
via Theorem 6. This can be seen by noting that for $r=\lambda$, one may write

$\displaystyle\tau^{*}({\mathbf{A}}_{(\lambda,\lambda)})=$
$\displaystyle\min\Bigg{\\{}2^{n}\cdot\sum_{\ell=0}^{n}\left(\begin{array}[]{c}n\\\
\ell\end{array}\right)\cdot w_{\ell}:$ $\displaystyle\ \ \ \
w_{\ell}\cdot(\ell+1)\geqslant 1,0\leqslant\ell\leqslant n,w_{\ell}\geqslant
0\Bigg{\\}}.$

The bounds to follow are concerned with special choices of the problem
parameters and do not involve solving LPs.

###### Proposition 8

Suppose that $r=\lambda$. Then

$\tau^{*}({\mathbf{A}}_{(r,\lambda)})=2^{n}\cdot\sum_{\ell=0}^{n}\frac{\binom{n}{\ell}}{\ell+1}=\frac{2^{n}(2^{n+1}-1)}{n+1}.$

Hence, $A_{\lambda}(n,2\lambda+1)\leqslant{2^{n}(2^{n+1}-1)}/{(n+1)}$.

###### Proof:

Note that when $r=\lambda$, $A_{H,(r,\lambda)}$ is a diagonal matrix with
entries $a_{\ell,\ell}=\ell+1$ for $\ell\in\\{0,1,\ldots,n\\}$. Let
${\boldsymbol{w}}$ be a vector with entries
${\boldsymbol{w}}_{\ell}=(\frac{1}{\ell+1})$, $\ell=0,\ldots,n$. Then,
${\mathbf{A}}_{H,(r,\lambda)}^{T}\cdot{\boldsymbol{w}}={\mathbf{1}}$ and
${\boldsymbol{w}}$ is a feasible solution of the underlying LP. On the other
hand, since ${\mathbf{A}}_{H,(r,\lambda)}$ is symmetric,
${\mathbf{A}}_{H,(r,\lambda)}\cdot{\boldsymbol{w}}={\mathbf{1}}$ and
${\boldsymbol{w}}$ is a feasible solution of the dual LP. This proves the
claimed result. ∎

The following proposition may be proved along the same lines as Proposition 8.
It relies on using sphere-packing arguments and a subgraph of the ALD
confusion graph.

###### Proposition 9

For positive integers $r,\lambda$,

$A_{\lambda}(n,2r+1)\leqslant
2^{n}\cdot\sum_{\ell=0}^{n}\frac{\binom{n}{\ell}}{\sum_{j=0}^{\lfloor
r/\lambda\rfloor}\left(\begin{array}[]{c}\ell\\\ j\end{array}\right)}.$

###### Proof:

The proof follows from the simple observation that the vector
${\boldsymbol{w}}$ with entries

${\boldsymbol{w}}_{\ell}=\Bigg{(}\frac{1}{\sum_{j=0}^{\lfloor
r/\lambda\rfloor}\left(\begin{array}[]{c}\ell\\\
j\end{array}\right)}\Bigg{)},\,\ell=0,\ldots,n,$

satisfies
${\mathbf{A}}_{H,(r,\lambda)}^{T}\cdot{\boldsymbol{w}}\geqslant{\mathbf{1}}$,
and is hence a feasible solution of the linear program. ∎

Consider next the special case when $\lambda=1$, and $r\geqslant 2$. To ease
the notation, we introduce a function $K(n,r,i,j)$, such that

$\displaystyle K(n,r,i,j)=$
$\displaystyle\sum_{\ell=0}^{\lfloor\frac{r}{2}\rfloor}\left(\begin{array}[]{c}i\\\
\ell\end{array}\right)\cdot 2^{\ell}\cdot\left(\begin{array}[]{c}n-i\\\
j-i+\ell\end{array}\right)\cdot 2^{j-i+\ell}\cdot$ $\displaystyle\ \ \
\sum_{4k+m\leqslant r-2(j-i+2\ell)}\left(\begin{array}[]{c}n-j-\ell\\\
k\end{array}\right)\left(\begin{array}[]{c}i-\ell\\\ m\end{array}\right),$

for $j\geqslant i$, and

$\displaystyle K(n,r,i,j)=$
$\displaystyle\sum_{\ell=0}^{\lfloor\frac{r}{2}\rfloor}\left(\begin{array}[]{c}n-i\\\
\ell\end{array}\right)\cdot 2^{\ell}\cdot\left(\begin{array}[]{c}i\\\
i-j+\ell\end{array}\right)\cdot 2^{i-j+\ell}\cdot$ $\displaystyle\ \ \ \
\sum_{4k+m\leqslant r-2(i-j+2\ell)}\left(\begin{array}[]{c}j-\ell\\\
m\end{array}\right)\left(\begin{array}[]{c}n-i-\ell\\\ k\end{array}\right),$

for $j<i$. We also assume that $K(n,r,i,j)$ $=0$ whenever $r-2|i-j|<0$. Given
this setup, we may write
${\mathbf{A}}^{T}_{H,(r,1)}=\left(a_{i,j}\right)_{i=1,j=1}^{n+1}$, where
$a_{i,j}=K(n,r,i-1,j-1)$. The above claim follows from the observation that

$K(n,r,i,j)=\Big{|}\Big{\\{}({\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2}):w({\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2})=j,({\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2})\in{\cal
B}_{(r,1)}({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2})\Big{\\}}\Big{|},$

where $w({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2})=i$. To arrive at the
expression for the above set-cardinality for the case $j\geqslant i$, one has
to observe that one may choose $\ell$ locations for Class 2 errors from among
the $i$ locations where ${\boldsymbol{x}}_{1}$ and ${\boldsymbol{x}}_{2}$
differ in value; one may then choose the locations of the remaining
$j-(i-\ell)$ Class 2 errors from among the $n-i$ locations where
${\boldsymbol{x}}_{1}$ and ${\boldsymbol{x}}_{2}$ are equal in value. From the
remaining locations, we may choose the locations of $k$ Class 3 errors from
among positions in which the vectors agree in value, and $m$ Class 1 errors
from among positions in which the vectors disagree in value. Similar
reasonings apply for the case that $j<i$.

Next, we produce a weight assignment for (9) by considering another matrix
$\hat{{\mathbf{A}}}(n,r)$ related to ${\mathbf{A}}^{T}_{H,(r,1)}$ that takes
advantage of the structure of ${\mathbf{A}}^{T}_{H,(r,1)}$. The basic idea is
to change some values of ${\mathbf{A}}^{T}_{H,(r,1)}$ so as to ensure that the
diagonal elements of $\hat{{\mathbf{A}}}(n,r)$ are sufficiently large in order
to invoke certain results regarding positive solutions of linear equations.
The weights are then given as
${\boldsymbol{w}}=\hat{{\mathbf{A}}}(n,r)^{-1}\cdot{\mathbf{1}}$, and Theorem
11 establishes that ${\boldsymbol{w}}=\hat{{\mathbf{A}}}(n,r)^{-1}\cdot{\bf
1}$ is a feasible weight assignment for (9).

The matrix $\hat{{\mathbf{A}}}(n,r)$ is constructed as follows: let
$\hat{{\mathbf{A}}}(n,r)=\left(\hat{a}_{i,j}\right)_{i=1,j=1}^{n+1}$. Then,

$\hat{a}_{i,j}=\min\Big{(}K(n,r,i-1,j-1),\frac{1}{r}(K(n,r,i-1,i-1)-1)\Big{)}$

for $j\neq i$, and $\hat{a}_{i,i}=K(n,r,i-1,i-1)$. We find the following lemma
useful for the proof of Theorem 11.

###### Lemma 10

. (c.f. [10]) Suppose that the matrix
${\mathbf{M}}=(m_{ij})\in\mathbb{R}_{+}^{n\times n}$ contains no zero elements
on the diagonal, and let ${{\boldsymbol{b}}}>0$ be chosen arbitrarily. If for
all $i\in\\{1,\ldots,n\\}$,

$b_{i}>\sum_{j=1,j\neq i}^{n}m_{ij}\frac{b_{j}}{m_{jj}}$

then ${\mathbf{M}}$ is invertible and
${\mathbf{M}}^{-1}{\boldsymbol{b}}\geqslant 0$.

###### Theorem 11

. For any two positive integers $n,r$, we have

$A_{\lambda=1}(n,2r+1)\leqslant
2^{n}\cdot\sum_{\ell=0}^{n}\left(\begin{array}[]{c}n\\\
\ell\end{array}\right)\cdot w_{i},$

where
${\boldsymbol{w}}=(w_{0},\ldots,w_{n})=\hat{{\mathbf{A}}}(n,r)^{-1}\cdot(1,1,\ldots,1)$.

###### Proof:

First, note that by the definition of the matrix $\hat{{\mathbf{A}}}(n,r)$,
for all $i\in\\{1,\ldots,n+1\\}$, one has

$\displaystyle\sum_{j=1,j\neq
i}^{n+1}\frac{\hat{a}_{i,j}}{\hat{a}_{j,j}}\leqslant\sum_{j=i-\lfloor\frac{r}{2}\rfloor,j\neq
i}^{i+\lfloor\frac{r}{2}\rfloor}\frac{K(n,r,i-1,i-1)-1}{rK(n,r,i-1,i-1)}<1.$

Based on Lemma 10, there exists a ${\boldsymbol{w}}$ with non-negative entries
such that $\hat{{\mathbf{A}}}(n,r)\cdot{\boldsymbol{w}}=1$. By definition, we
also have ${\mathbf{A}}_{H,(r,1)}^{T}\geqslant\hat{{\mathbf{A}}}(n,r)$ and
since $\hat{{\boldsymbol{w}}}\geqslant 0$, it follows that

${\mathbf{A}}_{H,(r,1)}^{T}\cdot{\boldsymbol{w}}\geqslant\hat{{\mathbf{A}}}(n,r)\cdot{\boldsymbol{w}}=1,$

as desired. Thus, since
${\mathbf{A}}_{H,(r,1)}^{T}\cdot{\boldsymbol{w}}\geqslant 1$ and
${\boldsymbol{w}}\geqslant 0$, ${\boldsymbol{w}}$ is a feasible solution for
the program in (9). ∎

The results of our bounds on $A_{\lambda=1}(n,5)$, when $n\leqslant 15$, are
listed in Table III-A. In general, the bound from Proposition 9 provides the
weakest upper bound on the code size while the bound from Theorem 11 best
approximates the optimal weights solving the LP (9). Notice that the bound
from Theorem 7 is weaker than the bound from Theorem 11 for all code lengths
considered.

Length Bound from (9) Theorem 7 Proposition 9 Theorem 11 5 67 427 254 112 6
219 1079 793 354 7 731 2750 2508 1170 8 2483 7181 8048 3793 9 8563 19485 26190
12008 10 29901 55529 86393 40400 11 105490 166902 288649 139753 12 375448
527725 975954 486642 13 1346201 1742275 3336118 1665472 14 4858171 5949948
11518362 5679816 15 17631726 20833123 40130869 19999983

Comparison of Upper Bounds for $A_{\lambda=1}(n,5)$

In the next section, we consider another approach for deriving upper bounds on
$A_{\lambda}(n,d).$ The method we use is a combination of novel symbol mapping
techniques and the classical Delsarte-like LP approach. As will be shown by
computer simulation, Delsarte-like bounds tend to outperform hypergraph
methods for ALD codes for a number of parameter settings.

##  IV Upper Bounds from Delsarte-Like Inequalities

We focus next on classical LP techniques for bounding the number of
$(d,\lambda)$-distinguishable sequences $A_{\lambda}(n,d)$. The gist of our
approach is to map the symbols from $\mathbb{F}_{2}\times\mathbb{F}_{2}$ into
symbols from some sufficiently large alphabet for which the distance
constraints may be captured in a unique manner. We then proceed by introducing
the complete distance enumerator for ALD codes, and use these enumerators to
define an appropriate LP.

In order to explain why we need to map the symbols of
$\mathbb{F}_{2}\times\mathbb{F}_{2}$ into symbols from a larger alphabet,
consider the following natural mapping onto $\mathbb{Z}_{4}$:

$\displaystyle(0;0)$ $\displaystyle\mapsto 0,$ $\displaystyle(0;1)$
$\displaystyle\mapsto 1,$ $\displaystyle(1;0)$ $\displaystyle\mapsto 2,$
$\displaystyle(1;1)$ $\displaystyle\mapsto 3.$

Since $2-1\equiv 0-3\bmod 4$, one cannot distinguish between the binary pairs
$(1;0),(0;1)$ and $(0;0),(1;1)$ based on the difference of their images. To
insure distinguishability of the differences of the images, one may consider
using a mapping from $\mathbb{F}_{2}\times\mathbb{F}_{2}$ into
$\mathbb{F}_{2}\times\mathbb{F}_{2}\times\mathbb{F}_{2}$. Unfortunately, this
mapping results in poor bounds, due to the fact that many of the LP
constraints derived from this mapping are redundant.

Consider another mapping
$\phi^{(10)}:\mathbb{F}_{2}\times\mathbb{F}_{2}\to\mathbb{Z}_{10}$ given by

$\displaystyle(0;0)$ $\displaystyle\mapsto 0,$ $\displaystyle(0;1)$
$\displaystyle\mapsto 1,$ $\displaystyle(1;0)$ $\displaystyle\mapsto 9,$
$\displaystyle(1;1)$ $\displaystyle\mapsto 5.$

This mapping and the pairwise differences of the images are depicted in Figure
5. For any positive integer $n>1$, we extend the definition of the mapping
$\phi^{(10)}:\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\to\mathbb{Z}_{10}^{n}$
in a natural manner as
$\phi^{(10)}({\boldsymbol{a}};{\boldsymbol{b}})=(\phi^{(10)}(a_{i};b_{i}))_{i=1}^{n}$.

---
$\textstyle{0\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pm
1}$$\scriptstyle{5}$$\textstyle{9\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pm
1}$$\scriptstyle{\pm
2}$$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pm
4}$$\textstyle{5\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\pm
4}$

Figure 5: The map $\phi^{(10)}$. The labels of the edges equal the difference
of their defining vertices, taken modulo ten and reflected to lie in the
interval $[-5,4]$.

Let ${\boldsymbol{x}}\in\mathbb{Z}^{n}_{10}$. Define the profile of
${\boldsymbol{x}}$, denoted by $P({\boldsymbol{x}})$, as
$(m_{x})_{x\in\mathbb{Z}_{10}}$, where $m_{x}=\left|\\{i:x_{i}=x\\}\right|$.
For example, the profile of ${\boldsymbol{x}}=(5,1,4,1)\in\mathbb{Z}_{10}^{4}$
equals $P({\boldsymbol{x}})=(0,2,0,0,1,1,0,0,0,0)$. With each
$x\in\mathbb{Z}_{10}$, associate an indeterminate $z_{x}$. Given a collection
of words ${\cal C}\subseteq\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$, define
the complete distance enumerator of ${\cal C}$ as

$\displaystyle W_{{\cal C}}($ $\displaystyle z_{0},z_{1},\ldots,z_{9})=$
$\displaystyle\sum_{m_{0},\ldots,m_{9}}w[m_{0},m_{1},\ldots,m_{9}]z_{0}^{m_{0}}z_{1}^{m_{1}}\cdots
z_{9}^{m_{9}},$

where

$\displaystyle w[m_{0},m_{1},\ldots,m_{9}]=\,\frac{1}{|{\cal
C}|}\big{|}\\{({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}})\in{\cal
C}:$ $\displaystyle
P(\phi^{(10)}({\boldsymbol{a}};{\boldsymbol{b}})-\phi^{(10)}({\boldsymbol{c}};{\boldsymbol{d}}))=(m_{0},m_{1},\ldots,m_{9})\\}\big{|},$

and where the differences are applied componentwise and evaluated modulo ten.

###### Claim 1

Let ${\cal C}\subseteq\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$ with
$d_{\lambda}({\cal C})\geqslant d$ have a complete distance enumerator
$\sum_{m_{0},\ldots,m_{9}}w[m_{0},$ $\ldots,m_{9}]z_{0}^{m_{0}}$ $\cdots
z_{9}^{m_{9}}$. Then, the following claims are true:

  1. (i)

$|{\cal C}|=\sum_{m_{0},\ldots,m_{9}}w[m_{0},\ldots,m_{9}]$, which states that
the number of codewords may be retrieved by setting all variables in the
complete weight enumerator to one;

  2. (ii)

$w[n,0,\ldots,0]=1$, which follows from the definition of the complete weight
enumerator;

  3. (iii)

$w[m_{0},\ldots,m_{9}]=0$ whenever $m_{3}>0$ or $m_{7}>0$, which ensures that
the edge labels $\pm 3$ are not allowed;

  4. (iv)

$w[m_{0},\ldots,m_{9}]=0$ if
$(1+\lambda)(m_{1}+m_{4}+m_{6}+m_{9})+\lambda(m_{2}+m_{8})+2(1+\lambda)m_{5}<d$,
which captures the minimum distance constraint.

Let

$\chi({{\boldsymbol{x}}},{{\boldsymbol{y}}})=\exp(-2\pi\iota\,({\boldsymbol{x}}^{T}\cdot{\boldsymbol{y}})/10),$

where $\iota$ denotes the imaginary unit,
${\boldsymbol{x}},{\boldsymbol{y}}\in\mathbb{Z}_{10}^{n}$, and
${\boldsymbol{x}}^{T}\cdot{\boldsymbol{y}}=\sum_{i=1}^{n}x_{i}y_{i}$. Clearly,
$\chi({\boldsymbol{x}},{\boldsymbol{y}})=\prod_{i=1}^{n}\chi(x_{i},y_{i})$.
For ${\boldsymbol{x}}\in\mathbb{Z}_{10}^{n}$, suppose that
$P({\boldsymbol{x}})=(m_{0},\ldots,m_{9})$ and define
${\boldsymbol{z}}({\boldsymbol{x}})=\prod_{i}z_{i}^{m_{i}}$.

###### Lemma 12

. Fix ${\boldsymbol{x}}\in\mathbb{Z}_{10}^{n}$ and suppose that
$P({{\boldsymbol{x}}})=(m_{0},\ldots,m_{9})$. Then

$\sum_{{\boldsymbol{y}}\in\mathbb{Z}^{n}_{10}}{\boldsymbol{z}}({\boldsymbol{y}})\chi({\boldsymbol{x}},{\boldsymbol{y}})=F_{\textbf{z}}(m_{0},m_{1},\ldots,m_{9}),$

where

$F_{\textbf{z}}(m_{0},m_{1},\ldots,m_{9})=\prod_{j=0}^{9}\left(\sum_{i=0}^{9}z_{i}\chi(i,j)\right)^{m_{j}}.$
(10)

###### Proof:

The claim follows by induction. The base case $n=1$ can be easily verified,
while for $n\geqslant 2$, it suffices to observe that

$\displaystyle\sum_{(y_{1},y_{2})}{\boldsymbol{z}}(y_{1},y_{2})$
$\displaystyle\chi\Big{(}(x_{1},x_{2}),(y_{1},y_{2})\Big{)}=$
$\displaystyle\Big{(}\sum_{y_{1}}{\boldsymbol{z}}(y_{1})\chi(x_{1},y_{1})\Big{)}\cdot\Big{(}\sum_{y_{2}}{\boldsymbol{z}}(y_{2})\chi(x_{2},y_{2})\Big{)}.$

∎

###### Theorem 13

. Let ${\cal C}\subseteq\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$ and as
before write

$\sum_{m_{0},\ldots,m_{9}}w[m_{0},\,\ldots,m_{9}]z_{0}^{m_{0}}\cdots
z_{9}^{m_{9}}$

for the complete distance enumerator of ${\cal C}$. Define
$b[m_{0},\ldots,m_{9}]$ via

$\displaystyle\sum_{m_{0},\ldots,m_{9}}$ $\displaystyle
w[m_{0},\ldots,m_{9}]F_{\textbf{z}}(m_{0},\ldots,m_{9})=$
$\displaystyle\sum_{m_{0},\ldots,m_{9}}b[m_{0},\ldots,m_{9}]z_{0}^{m_{0}}\cdots
z_{9}^{m_{9}}.$

Then $b[m_{0},\ldots,m_{9}]\geqslant 0$, for all $m_{0},\ldots,m_{9}$.

###### Proof:

For ease of notation, let ${\boldsymbol{x}},{\boldsymbol{y}}\in{\cal C}$
denote two codewords $({\boldsymbol{x}}_{1};{\boldsymbol{x}}_{2})$ and
$({\boldsymbol{y}}_{1};{\boldsymbol{y}}_{2})$, respectively. Consider the
following expression:

$\sum_{{\boldsymbol{x}},{\boldsymbol{y}}\in{\cal
C}}\sum_{{\boldsymbol{u}}\in\mathbb{Z}_{10}^{n}}{\boldsymbol{z}}({\boldsymbol{u}})\chi({\boldsymbol{u}},\phi^{(10)}({\boldsymbol{x}})-\phi^{(10)}({\boldsymbol{y}})).$

On the one hand, using Lemma 12, we may rewrite the given expression as

$|{\cal
C}|\sum_{m_{0},\ldots,m_{9}}w[m_{0},\ldots,m_{9}]F_{\textbf{z}}(m_{0},\ldots,m_{9}).$

On the other hand, by switching the order of summation, one arrives at

$\displaystyle\sum_{{\boldsymbol{u}}\in\mathbb{Z}^{n}_{10}}{\boldsymbol{z}}({\boldsymbol{u}})\sum_{{\boldsymbol{x}},{\boldsymbol{y}}\in{\cal
C}}\chi({\boldsymbol{u}},\phi^{(10)}({\boldsymbol{x}})-\phi^{(10)}({\boldsymbol{y}}))$
$\displaystyle=\sum_{{\boldsymbol{u}}\in\mathbb{Z}^{n}_{10}}{\boldsymbol{z}}({\boldsymbol{u}})\sum_{{\boldsymbol{x}},{\boldsymbol{y}}\in{\cal
C}}\chi({\boldsymbol{u}},\phi^{(10)}({\boldsymbol{x}}))\chi({\boldsymbol{u}},-\phi^{(10)}({\boldsymbol{y}}))$
$\displaystyle=\sum_{{\boldsymbol{u}}\in\mathbb{Z}^{n}_{10}}{\boldsymbol{z}}({\boldsymbol{u}})\left(\sum_{{\boldsymbol{x}}\in{\cal
C}}\chi({\boldsymbol{u}},\phi^{(10)}({\boldsymbol{x}}))\right)\left(\sum_{{\boldsymbol{y}}\in{\cal
C}}\chi({\boldsymbol{u}},-\phi^{(10)}({\boldsymbol{y}}))\right)$
$\displaystyle=\sum_{{\boldsymbol{u}}\in\mathbb{Z}^{n}_{10}}{\boldsymbol{z}}({\boldsymbol{u}})\Big{|}\sum_{{\boldsymbol{x}}\in{\cal
C}}\chi({\boldsymbol{u}},\phi^{(10)}({\boldsymbol{x}}))\Big{|}^{2}.$

The proof follows since $\Big{|}\sum_{{\boldsymbol{x}}\in{\cal
C}}\chi({\boldsymbol{u}},\phi^{(10)}({\boldsymbol{x}}))\Big{|}^{2}\,\geqslant
0$. ∎

As a consequence of the above results, an upper bound for $|{\cal C}|$, with
$d_{\lambda}({\cal C})$ given, may be obtained from the following LP:

maximize
$\displaystyle\sum_{m_{0},\ldots,m_{9}}w[m_{0},\ldots,m_{9}],\text{subject to\
}$ $\displaystyle w[n,0,\ldots,0]=1,$ $\displaystyle
w[m_{0},\ldots,m_{9}]=0,\text{ if }m_{3}>0\text{ or }m_{7}>0,$ $\displaystyle
w[m_{0},\ldots,m_{9}]=0,\text{ if }(1+\lambda)(m_{1}+m_{4}$
$\displaystyle\hskip 90.41638pt+m_{6}+m_{9})+\lambda(m_{2}+m_{8})$
$\displaystyle\hskip 90.41638pt+2(1+\lambda)m_{5}<d,$
$\displaystyle\sum_{m_{0},\ldots,m_{9}}w[m_{0},\ldots,m_{9}]F_{\textbf{z}}(m_{0},\ldots,m_{9})\geqslant
0.$

The multivariate polynomial inequality is to be interpreted as a nonnegativity
constraint on the coefficients of the polynomials.

$n\backslash d_{\lambda=1}$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 – – 2 2 2 – – – – 2 2 2 2 3 – – – – – – 4 4 2 2 2 2 4 – – – – – – – – 4 4 3
3 2 2 2 2 5 – – – – – – – – – – 6 6 3 3 2 2 2 2 2 2

TABLE II: Results of the Delsarte LP approach for $\lambda=1$

$n\backslash d_{\lambda=1}$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 – – 3 3 2 – – – – 2 2 2 2 3 – – – – – – 5 5 2 2 2 2 4 – – – – – – – – 5 5 4
4 2 2 2 2 5 – – – – – – – – – – 9 9 4 4 4 4 2 2 2 2

TABLE III: Results of (9) for $\lambda=1$

As can be seen from Tables III and III, for a number of cases where
$d\geqslant 2n+1$, the bounds obtained from Delsarte’s method are tighter than
the bounds obtained via the LP techniques of Section III. For the case
$d<2n+1$, the output of the LP from Theorem 13 was unbounded.

##  V Lower Bounds from Linear Code Constructions

Throughout the remainder of the paper we present _constructive_ lower bounds
on the sizes of codes under the ALD. As a starting point, we focus mainly on
the case where $\lambda=1$ although many of the constructions can be extended
to other parameter settings. Also, for simplicity, we first address the case
where the minimum ALD is equal to three.

For a positive integer $v$, let
$H_{\bf{0,1}}\in\mathbb{F}_{2}^{v\times(2^{v}-2)}$ be a matrix which has as
its columns all non-zero vectors from $\mathbb{F}_{2}^{v},$ except for the
all-ones vector. Write
$H_{\bf{0,1}}=({{\boldsymbol{h}}}_{1},{{\boldsymbol{h}}}_{2},\ldots,{{\boldsymbol{h}}}_{2^{v}-2}),$
where for $i\in\\{1,\ldots,2^{v}-2\\}$, ${{\boldsymbol{h}}}_{i}$ represents
the $i$-th column of $H_{\bf{0,1}}$. Furthermore, let ${\bf
1}_{v}\in\mathbb{F}_{2}^{v\times 1}$ be the all-ones vector.

In this setting, define ${\cal
C}_{l}(2^{v}-2)\subseteq\mathbb{F}_{2}^{2^{v}-2}\times\mathbb{F}_{2}^{2^{v}-2}$
as

$\displaystyle{\cal C}_{l}(2^{v}-2):=$
$\displaystyle\Big{\\{}({{\boldsymbol{a}}};{{\boldsymbol{b}}})\in\mathbb{F}_{2}^{2^{v}-2}\times\mathbb{F}_{2}^{2^{v}-2}:$
$\displaystyle\sum_{i=1}^{2^{v}-2}a_{i}\cdot{{\boldsymbol{h}}}_{i}+\sum_{i=1}^{2^{v}-2}b_{i}\cdot{\bf
1}_{v}=\bf 0\\},$

where
$({{\boldsymbol{a}}};{{\boldsymbol{b}}})=((a_{1},\ldots,a_{2^{v}-2});(b_{1},\ldots,b_{2^{v}-2}))$.

The subscript “$l$” in the definition of the code ${\cal C}_{l}(2^{v}-2)$
serves to indicate that the code is a linear code. From the introductory
discussion, observe that a code with $\lambda=1$ and minimum ALD distance
three can either:

  1. 1.

Correct a single Class 1 error, or

  2. 2.

Detect a single Class 2 error.

In the following lemma, we show that the above defined code ${\cal
C}_{l}(2^{v}-2)$ can perform either 1) or 2).

###### Lemma 14

. For any positive integer $n$, $d_{\lambda=1}({\cal C}_{l}(2^{v}-2))\geqslant
3$.

###### Proof:

Let $n=2^{v}-2$. Suppose that $({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal
C}_{l}(2^{v}-2)$ was transmitted and that the pair of words
$({\boldsymbol{c}};{\boldsymbol{d}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
was received, where $({\boldsymbol{c}};{\boldsymbol{d}})$ is the result of at
most one Class 2 error occurring in $({\boldsymbol{a}};{\boldsymbol{b}})$. For
the remainder of this proof, let
${\boldsymbol{s}}=\sum_{i=1}^{n}c_{i}\cdot{{\boldsymbol{h}}}_{i}+\sum_{i=1}^{n}d_{i}\cdot{\mathbf{1}}_{v}$
denote the decoding “syndrome”. If a single Class 2 error occurred in position
$j\in\\{1,\ldots,n\\}$ of ${\boldsymbol{a}}$, then
${\boldsymbol{s}}={{\boldsymbol{h}}}_{j}\neq\bf 0$. Otherwise, if a Class 2
error occurred in position $j$ of ${\boldsymbol{b}}$, then
${\boldsymbol{s}}={\mathbf{1}}_{v}\neq\bf 0$. Clearly, if no Class 2 errors
occurred, then ${\boldsymbol{s}}={\bf 0}$. Thus, ${\cal C}_{l}(2^{v}-2)$ can
detect whether a single Class 2 error has occurred by checking if
${\boldsymbol{s}}$ is non-zero.

Suppose that $({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal C}_{l}(2^{v}-2)$ was
transmitted and that the vector
$({\boldsymbol{c}};{\boldsymbol{d}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
was received, where
$({\boldsymbol{c}};{\boldsymbol{d}})=((c_{1};d_{1}),(c_{2};d_{2}),\ldots,(c_{n};d_{n}))$
is the result of at most one Class 1 error in
$({\boldsymbol{a}};{\boldsymbol{b}})$. We describe next how to recover
$({\boldsymbol{a}};{\boldsymbol{b}})$ from
$({\boldsymbol{c}};{\boldsymbol{d}})$. Let
$\tilde{{\boldsymbol{s}}}={\boldsymbol{s}}+{\bf 1}_{v}$, where
${\boldsymbol{s}}$ denotes the previously defined syndrome. Note that if
$({\boldsymbol{c}};{\boldsymbol{d}})$ is the result of a single Class 1 error
in position $j$ of $({\boldsymbol{a}};{\boldsymbol{b}})$, then

$\tilde{{\boldsymbol{s}}}=\left(\sum_{i=1}^{n}c_{i}\cdot{{\boldsymbol{h}}}_{i}+\sum_{i=1}^{n}d_{i}\cdot{\mathbf{1}}_{v}\right)+{\bf
1}_{v}={{\boldsymbol{h}}}_{j}+{\bf 1}_{v}+{\bf 1}_{v}={{\boldsymbol{h}}}_{j}.$

Otherwise, if no error occurred,
$\tilde{{\boldsymbol{s}}}={\boldsymbol{s}}+{\bf 1}_{v}={\bf 1}_{v}$. From the
above discussion, and by recalling that ${{\boldsymbol{h}}}_{j}\neq{\bf
1}_{v}$ by construction, it is clear that a decoder for ${\cal
C}_{l}(2^{v}-2)$ can recover $({\boldsymbol{a}};{\boldsymbol{b}})$ from
$({\boldsymbol{c}};{\boldsymbol{d}})$, and
$({\boldsymbol{c}};{\boldsymbol{d}})$ from $\tilde{{\boldsymbol{s}}}$ as
follows. If $\tilde{{\boldsymbol{s}}}={\bf 1}_{v}$, then the decoder concludes
that no errors have occurred. Otherwise, if
$\tilde{{\boldsymbol{s}}}={{\boldsymbol{h}}}_{j}$ for some
$j\in\\{1,\ldots,n\\}$, then the decoder corrects a Class 1 error at position
$j$. ∎

For a ${\boldsymbol{u}}\in\mathbb{F}_{2}^{v}$, let ${\cal
C}_{l,{\boldsymbol{u}}}(2^{v}-2)\subseteq\mathbb{F}_{2}^{2^{v}-2}\times\mathbb{F}_{2}^{2^{v}-2}$
be a linear coset of ${\cal C}_{l}(2^{v}-2)$ so that

$\displaystyle{\cal C}_{l,{\boldsymbol{u}}}(2^{v}-2):=$
$\displaystyle\Big{\\{}({{\boldsymbol{a}}};{{\boldsymbol{b}}})\in\mathbb{F}_{2}^{2^{v}-2}\times\mathbb{F}_{2}^{2^{v}-2}:$
$\displaystyle\sum_{i=1}^{2^{v}-2}a_{i}\cdot{{\boldsymbol{h}}}_{i}+\sum_{i=1}^{2^{v}-2}b_{i}\cdot{\bf
1}_{v}={\boldsymbol{u}}\\}.$ (11)

The next result follows directly from Lemma 14. It will be used in the
following section.

###### Corollary 15

. For any positive integer $n$ and ${\boldsymbol{u}}\in\mathbb{F}_{2}^{v}$,
$d_{\lambda=1}({\cal C}_{l,{\boldsymbol{u}}}(2^{v}-2))\geqslant 3$.

As a consequence of Lemma 14 and Proposition 8, we have

$\small{\frac{4^{n}}{n+2}\leqslant
A_{\lambda=1}(n,3)\leqslant\frac{2^{n}(2^{n+1}-1)}{n+1}.}$

We now turn our attention to the problem of constructing codes with
$\lambda=1$ and minimum ALD equal to $d$, where $d>3$ is arbitrary. We first
describe the code construction, and then proceed to provide a proof for its
correctness.

Let $H_{d}\in\mathbb{F}_{2}^{s\times 2n}$ be a parity check matrix for a code
${\cal C}$ with Hamming distance $d$. Write
$H_{d}=({{\boldsymbol{h}}}_{1}^{\prime},\ldots,{{\boldsymbol{h}}}_{2n}^{\prime})$,
where ${{\boldsymbol{h}}}_{i}^{\prime}$ denotes the $i$-th column of $H_{d}$,
and define ${\cal
C}_{L}(n)\subseteq\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$ according to

$\displaystyle{\cal C}_{L}(n):=$
$\displaystyle\Big{\\{}({{\boldsymbol{a}}};{{\boldsymbol{b}}})=((a_{1};b_{1}),\ldots,(a_{n};b_{n}))\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}:$
$\displaystyle\sum_{i=1}^{n}a_{i}\cdot{{\boldsymbol{h}}}_{i}^{\prime}+\sum_{i=1}^{n}b_{i}\cdot({{\boldsymbol{h}}}_{i}^{\prime}+{{\boldsymbol{h}}}_{n+i}^{\prime})=\bf
0\Big{\\}}.$

Similar to before, the subscript “$L$” on ${\cal C}_{L}(n)$ refers to the fact
that this is a linear code, and in order to distinguish it from the distance-
three code ${\cal C}_{l}$, we used the capital letter $L$.

We have the following result.

###### Lemma 16

. For positive integers $n$ and $d\geqslant 4$, $d_{\lambda=1}({\cal
C}_{L}(n))\geqslant d$.

###### Proof:

Let $({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal C}_{L}(n)$ for $d\geqslant
4$. Since $({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal C}_{L}(n)$,
$\sum_{i=1}^{n}a_{i}\cdot{{\boldsymbol{h}}}_{i}^{\prime}+\sum_{i=1}^{n}b_{i}\cdot({{\boldsymbol{h}}}_{i}^{\prime}+{{\boldsymbol{h}}}_{n+i}^{\prime})=\bf
0$. Therefore, if $({\boldsymbol{c}};{\boldsymbol{d}})\in{\cal C}_{L}(n)$,
then
$\sum_{i=1}^{n}c_{i}\cdot{{\boldsymbol{h}}}_{i}^{\prime}+\sum_{i=1}^{n}d_{i}\cdot({{\boldsymbol{h}}}_{i}^{\prime}+{{\boldsymbol{h}}}_{n+i}^{\prime})=\bf
0$ as well. By combining these two equations, we deduce that given
$({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal C}_{L}(n)$,
$({\boldsymbol{c}};{\boldsymbol{d}})\in{\cal C}_{L}(n)$ if and only if

$\displaystyle\sum_{i=1}^{n}(a_{i}+c_{i})\cdot{{\boldsymbol{h}}}_{i}^{\prime}+\sum_{i=1}^{n}(b_{i}+d_{i})\cdot({{\boldsymbol{h}}}_{i}^{\prime}+{{\boldsymbol{h}}}_{n+i}^{\prime})=\bf
0.$ (12)

It remains to show that for any
$({\boldsymbol{c}};{\boldsymbol{d}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
where
$d_{\lambda=1}(({{\boldsymbol{a}}};{{\boldsymbol{b}}});({{\boldsymbol{c}}};{{\boldsymbol{d}}}))<d$,
equation (12) does not hold. Suppose, in particular, that
$({\boldsymbol{c}};{\boldsymbol{d}})$ is the result of $\epsilon_{1}$ Class 1
errors, $\epsilon_{2}$ Class 2 errors, and $\epsilon_{3}$ Class 3 errors
occurring in $({\boldsymbol{a}};{\boldsymbol{b}})$, where
$\epsilon_{1}+2\epsilon_{2}+4\epsilon_{3}<d$. Then,

$\sum_{i=1}^{n}(a_{i}+c_{i})\cdot{{\boldsymbol{h}}}_{i}^{\prime}+\sum_{i=1}^{n}(b_{i}+d_{i})\cdot({{\boldsymbol{h}}}_{i}^{\prime}+{{\boldsymbol{h}}}_{n+i}^{\prime})$

can be written as a sum of at most $\epsilon_{1}+2\epsilon_{2}+\epsilon_{3}$
columns of $H_{d}$. Since $\epsilon_{1}+2\epsilon_{2}+4\epsilon_{3}<d$, and
consequently $\epsilon_{1}+2\epsilon_{2}+\epsilon_{3}<d$, and since $H_{d}$ is
a parity-check matrix of a code with Hamming distance $d$, we conclude that
(12) does not hold. Therefore,
$\sum_{i=1}^{n}c_{i}\cdot{{\boldsymbol{h}}}_{i}^{\prime}+\sum_{i=1}^{n}d_{i}\cdot({{\boldsymbol{h}}}_{i}^{\prime}+{{\boldsymbol{h}}}_{n+i}^{\prime})\neq\bf
0$ and so $({\boldsymbol{c}};{\boldsymbol{d}})\not\in{\cal C}_{L}(n)$. ∎

We now comment on the size of the code ${\cal C}_{L}(n)$ for the case when
$d_{\lambda=1}=5$. More precisely, we compare the ALD codes ${\cal C}_{L}(n)$
with distance five to codes constructed for the Hamming distance. In
particular, we focus on (a) binary codes of length $2n$; and (b) the binary
image of quaternary codes of length $n$.

For (a), since a code with minimum ALD equal to five must be able to correct
four errors (resulting from two Class 1 errors), we require a binary code
${\cal C}$ that has minimum Hamming distance at least nine, so that one has

$|{\cal C}|\leqslant\frac{2^{2n}}{\sum_{j=0}^{4}\left(\begin{array}[]{c}2n\\\
j\end{array}\right)},$

which follows from the sphere packing bound. For $2n=2^{v}-2$, where
$v\geqslant 2$ is a positive integer,

$|{\cal C}_{L}(n)|\geqslant\frac{4^{n}}{(2n+2)^{2}},$

provided that one-bit shortened primitive binary BCH codes of minimum Hamming
distance $5$ are used as defining codes $H_{d}$. In this case, $|{\cal
C}|\leqslant|{\cal C}_{L}(n)|$. Proposition 9 for the case $\lambda=1$ and
distance five, and the lower bound on $|{\cal C}_{L}(n)|$ imply that for
$2n=2^{v}-2$, with $v>2$ an integer, it also holds that

$\frac{4^{n}}{(2n+2)^{2}}\leqslant A_{\lambda=1}(n,5)\leqslant\frac{3\cdot
2^{n}}{(n+1)(n+2)}\left(2^{n+2}-n-3\right).$

Next, consider the second case, (b). A quaternary code ${\cal C}$ with minimum
ALD distance five has to have Hamming distance at least five. Writing out the
sphere packing bound for quaternary codes with Hamming distance five, we
arrive at

$|{\cal C}|\leqslant\frac{4^{n}}{\sum_{j=0}^{2}\binom{n}{j}3^{j}}.$

For large enough $n$, this value is strictly smaller than
$\frac{4^{n}}{(2n+2)^{2}}$, which is a lower bound on $|{\cal C}_{L}(n)|$ for
$d_{\lambda=1}=5$. More precisely,

$\small{|{\cal
C}|\leqslant\frac{4^{n}}{\sum_{j=0}^{2}\left(\begin{array}[]{c}n\\\
j\end{array}\right)3^{j}}<\frac{4^{n}}{(2n+2)^{2}}\leqslant|{\cal
C}_{L}(n)|,}$

whenever $v\geqslant 5$. Hence, the previously proposed constructions also
outperform the “direct approach” with a quaternary alphabet.

##  VI Lower Bounds from Non-Linear Code Constructions

In what follows, we present constructions of non-linear codes under the ALD.
In many instances, the new code constructions result in codebooks larger than
their linear counterparts. We first consider the simplest case when $d=2$ and
$\lambda=1,$ and codes that can _detect_ one single Class 1 error. Then, we
extend our ideas to the case where the minimum ALD of the code is equal to
three and $\lambda=1$. For this parameter case, we improve upon the
construction in Lemma 16 whenever the block length is $n=2^{v}-2$, for any
positive integer $v\geqslant 5$. General code constructions are given at the
end of the section.

Recall that the weight of a vector pairing
$({\boldsymbol{a}};{\boldsymbol{b}})=((a_{1},\ldots,a_{n});(b_{1},\ldots,b_{n}))\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
is defined as $w({\boldsymbol{a}};{\boldsymbol{b}})=|\\{i:a_{i}\neq
b_{i}\\}|$. Let
$\mathcal{S}({\boldsymbol{a}};{\boldsymbol{b}})=(a_{j_{1}},\ldots,a_{j_{w({{\boldsymbol{a}}},{{\boldsymbol{b}}})}})$
be a subsequence of ${\boldsymbol{a}}$ obtained by deleting all the entries of
${\boldsymbol{a}}$ on which ${\boldsymbol{a}}$ and ${\boldsymbol{b}}$ agree.
In other words, if
$\mathcal{S}({\boldsymbol{a}};{\boldsymbol{b}})=(a_{j_{1}},\ldots,a_{j_{w({{\boldsymbol{a}}},{{\boldsymbol{b}}})}})$,
then ${j_{1}}<{j_{2}}<\cdots<j_{w({{\boldsymbol{a}}},{{\boldsymbol{b}}})}$ is
the largest set of indices for which $a_{j_{1}}\neq b_{j_{1}},a_{j_{2}}\neq
b_{j_{2}},\ldots,a_{j_{w({{\boldsymbol{a}}},{{\boldsymbol{b}}})}}\neq
b_{j_{w({{\boldsymbol{a}}},{{\boldsymbol{b}}})}}$. Furthermore, we denote the
set of indices supported in $\mathcal{S}({\boldsymbol{a}};{\boldsymbol{b}})$,
i.e., the set of indices for which ${\boldsymbol{a}}$ and ${\boldsymbol{b}}$
differ by ${\rm
Supp}({\boldsymbol{a}};{\boldsymbol{b}})=\\{{j_{1}},{j_{2}},\ldots,j_{w({{\boldsymbol{a}}},{{\boldsymbol{b}}})}\\}$.
Furthermore, for a set ${\cal
U}=\\{u_{1},u_{2},\ldots,u_{m}\\}\subseteq\\{{1,\ldots,n\\}}$, we let
$({\boldsymbol{a}};{\boldsymbol{b}})_{{\cal
U}}=((a_{u_{1}},a_{u_{2}},\ldots,a_{u_{m}});(b_{u_{1}},b_{u_{2}},\ldots,b_{u_{m}}))\in\mathbb{F}_{2}^{m}\times\mathbb{F}_{2}^{m},$
where $u_{1}<u_{2}<\cdots<u_{m}$.

Define ${\cal C}_{p}(n)\subseteq\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
according to a parity and a weight constraint

$\displaystyle{\cal C}_{p}(n):=$
$\displaystyle\\{({\boldsymbol{a}};{\boldsymbol{b}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}:w({\boldsymbol{a}};{\boldsymbol{b}})\geqslant
1,\sum_{i=1}^{n}a_{i}\equiv 0\bmod 2\\}$
$\displaystyle\cup\,\\{({\boldsymbol{a}};{\boldsymbol{b}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}:w({\boldsymbol{a}};{\boldsymbol{b}})=0\\}.$

The subscript “p” in ${\cal C}_{p}(n)$ serves to indicate that the underlying
code enforces a simple parity-check constraint. As before, let
$d_{H}({\boldsymbol{x}},{\boldsymbol{y}})$ stand for the Hamming distance
between two binary vectors
${\boldsymbol{x}},{\boldsymbol{y}}\in\mathbb{F}_{2}^{n}$. Equipped with this
notation, we may state the following result.

###### Proposition 17

. Let the code ${\cal C}_{p}(n)$ be defined as above, with $n\geqslant 1$. The
code has $d_{\lambda=1}=2$, and

$|{\cal C}_{p}(n)|=2^{2n-1}+2^{n-1}.$

The code ${\cal C}_{p}(n)$ has optimal code size for the given minimum ALD and
code length.

###### Proof:

Consider an arbitrary code ${\cal C}$ of length $n$ and with
$d_{\lambda=1}=2$. We partition the codewords in ${\cal C}$ into subsets of
the form

$\displaystyle{\cal
C}_{T,{\boldsymbol{v}}}:=\\{({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal
C}:{\rm Supp}({\boldsymbol{a}};{\boldsymbol{b}})=T,$
$\displaystyle({\boldsymbol{a}};{\boldsymbol{b}})_{[n]\setminus
T}=({\boldsymbol{v}};{\boldsymbol{v}}),\\}$

where $T$ ranges over all subsets of $\\{{1,\ldots,n\\}}$ and where
${\boldsymbol{v}}\in\mathbb{F}_{2}^{n-|T|}$ is arbitrary. We observe that a
word $({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal C}_{T,{\boldsymbol{v}}}$ is
completely determined by ${\boldsymbol{a}}$. In particular, $b_{j}=a_{j}+1$,
if $j\in T$, and $b_{j}=a_{j}$ otherwise.

If $T$ is empty, then $|{\cal C}_{T,{\boldsymbol{v}}}|\leqslant 2^{n}$ for all
${\boldsymbol{v}}$.

We show next that for any non-empty $T$ and any
${\boldsymbol{v}}\in\mathbb{F}_{2}^{n-|T|}$, $|{\cal
C}_{T,{\boldsymbol{v}}}|\leqslant 2^{|T|-1}$.

Let $k\in T$ be an arbitrarily chosen element. We proceed by considering the
following set:

${\cal
C}_{T,{\boldsymbol{v}}}^{\prime}:=\\{({\boldsymbol{a}};{\boldsymbol{b}})_{T\setminus
k}:({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal C}_{T,{\boldsymbol{v}}}\\}.$

We claim that $|{\cal C}_{T,{\boldsymbol{v}}}^{\prime}|=|{\cal
C}_{T,{\boldsymbol{v}}}|$. Suppose that on the contrary, $|{\cal
C}_{T,{\boldsymbol{v}}}^{\prime}|<|{\cal C}_{T,{\boldsymbol{v}}}|$. Then,
there exist two codewords
$({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}})\in{\cal
C}_{T,{\boldsymbol{v}}}$ such that
$({\boldsymbol{a}};{\boldsymbol{b}})_{\\{{1,\ldots,n\\}}\setminus
k}=({\boldsymbol{c}};{\boldsymbol{d}})_{\\{{1,\ldots,n\\}}\setminus k}$. In
other words, $({\boldsymbol{a}};{\boldsymbol{b}})$ and
$({\boldsymbol{c}};{\boldsymbol{d}})$ only differ in one single position $k$.
Furthermore, given that $k\in T$, it follows that
$d_{\lambda=1}(({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}}))=1$,
which contradicts the original assumptions as
$({\boldsymbol{a}};{\boldsymbol{b}}),({\boldsymbol{c}};{\boldsymbol{d}})$
cannot both belong to ${\cal C}$. Hence, if $T$ is non-empty, $|{\cal
C}_{T,{\boldsymbol{v}}}|=|{\cal C}_{T,{\boldsymbol{v}}}^{\prime}|\leqslant
2^{|T|-1},$ so that

$|{\cal C}|\leqslant\sum_{i=1}^{n}\left(\begin{array}[]{c}n\\\
i\end{array}\right)\cdot 2^{n-i}\cdot 2^{i-1}+2^{n}=2^{2n-1}+2^{n-1}.$

Note that ${\cal C}_{p}(n)$ can detect a single Class 1 error, since a single
Class 1 error changes the parity of ${\boldsymbol{a}}$ for any codeword in the
first subset of ${\cal C}_{p}(n)$. Hence, $d_{\lambda=1}({\cal
C}_{p}(n))\geqslant 2$ and given that simple counting arguments show that
$|{\cal C}_{p}(n)|=2^{2n-1}+2^{n-1}$, the result follows. ∎

The basic idea behind Proposition 17 was to use two sets,
$\\{({\boldsymbol{a}};{\boldsymbol{b}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}:w({\boldsymbol{a}};{\boldsymbol{b}})\geqslant
1\\}$ and
$\\{({\boldsymbol{a}};{\boldsymbol{b}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}:w({\boldsymbol{a}};{\boldsymbol{b}})=0\\}$,
the first of which imposes a parity constraint that increases the ALD. The
second set was used to enlarge the resulting codebook. We next pursue a
similar idea which relies on partitioning
$\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$ into subsets that satisfy
different constraints that boost either the ALD distance or the code size.

Our next immediate goal is to construct a family of codes ${\cal C}(n)$ with
$n=2^{v}-2$, where $v\geqslant 5$, that have minimum ALD at least three, and
size

$|{\cal C}(n)|\geqslant\frac{4^{n}}{n+2}+2^{n}.$

Recall that a code with minimum ALD equal to three, for $\lambda=1$, can
either (a) correct a single Class 1 error or (b) detect a single Class 2
error. We consider the following two sets of paired words ${\cal P}_{1}$ and
${\cal P}_{2},$ where every $({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal
P}_{1}$ has the property that $w({\boldsymbol{a}};{\boldsymbol{b}})\leqslant
7$ and $w({\boldsymbol{a}};{\boldsymbol{b}})\equiv 1\bmod 2$; and every
$({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal P}_{2}$ has the property that
$w({\boldsymbol{a}};{\boldsymbol{b}})\geqslant 9$.

Let ${\cal C}_{H}(i)\subseteq\mathbb{F}_{2}^{i}$ denote a binary code of
length $i$ with minimum Hamming distance three. Recall the definition of the
set $\mathcal{S}({\boldsymbol{a}};{\boldsymbol{b}})$ from the introduction of
this section and let

$\displaystyle{\cal C}_{1}(n):=$
$\displaystyle\Big{\\{}({{\boldsymbol{a}}};{{\boldsymbol{b}}})\in{\cal
P}_{1}\text{ s.t. }\mathcal{S}({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal
C}_{H}(w({{\boldsymbol{a}}};{{\boldsymbol{b}}}))\Big{\\}},\text{ and}$
$\displaystyle{\cal
C}_{2}(n):=\Big{\\{}({{\boldsymbol{a}}};{{\boldsymbol{b}}})\in{\cal
P}_{2}\cap{\cal C}_{l,{\boldsymbol{u}}}(n)\Big{\\}},$

for ${\cal C}_{l,{\boldsymbol{u}}}$ as defined in (V), and for some
${\boldsymbol{u}}\in\mathbb{F}_{2}^{v}$.

Furthermore, define ${\cal
C}(n)\subseteq\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$ as

$\displaystyle{\cal C}(n):={\cal C}_{1}(n)\cup{\cal C}_{2}(n).$

###### Lemma 18

. For any positive integer $v$, $d_{\lambda=1}({\cal C}(2^{v}-2))\geqslant 3$.

###### Proof:

Let $n=2^{v}-2$. We show that ${\cal C}(n)$ has minimum ALD three by
demonstrating that ${\cal C}(n)$ can either correct a single Class 1 error or
detect a single Class 2 error.

We start by establishing that ${\cal C}(n)$ can correct a single Class 1
error. Suppose that $({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal C}(n)$ was
transmitted and that
$({\boldsymbol{c}};{\boldsymbol{d}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$
was received, where $({\boldsymbol{c}};{\boldsymbol{d}})$ is the result of at
most one Class 1 error occurring in $({\boldsymbol{a}};{\boldsymbol{b}})$ at
some position $j\in{\rm Supp}({{\boldsymbol{a}}};{{\boldsymbol{b}}})$. Note
that
$d_{H}(\mathcal{S}({\boldsymbol{a}};{\boldsymbol{b}}),\mathcal{S}({\boldsymbol{c}};{\boldsymbol{d}}))\leqslant
1$. As a result, if $w({\boldsymbol{c}};{\boldsymbol{d}})=i\leqslant 7$, one
can use the decoder for ${\cal
C}_{H}(w({{\boldsymbol{c}}};{{\boldsymbol{d}}}))$ to correct the Class 1
error. Otherwise, if $i\geqslant 9$, one can use the decoder for ${\cal
C}_{l,{\boldsymbol{u}}}(n)$ to correct the Class 1 error.

Suppose that $({\boldsymbol{a}};{\boldsymbol{b}})\in{\cal C}(n)$ was
transmitted and that $({\boldsymbol{c}};{\boldsymbol{d}})$ was received, where
$({\boldsymbol{c}};{\boldsymbol{d}})$ is the result of at most one single
Class 2 error occurring in $({\boldsymbol{a}};{\boldsymbol{b}})$. Assume first
that $w({\boldsymbol{a}};{\boldsymbol{b}})=i\leqslant 7$. Since
$w({\boldsymbol{a}};{\boldsymbol{b}})\equiv 1\bmod 2$, we have
$w({\boldsymbol{c}};{\boldsymbol{d}})\equiv 0\bmod 2$ if a Class 2 error
occurred, and $w({\boldsymbol{c}};{\boldsymbol{d}})\equiv 1\bmod 2$ otherwise.
Thus, we can detect a Class 2 error whenever
$w({\boldsymbol{a}};{\boldsymbol{b}})=i\leqslant 7$. If
$w({\boldsymbol{a}};{\boldsymbol{b}})\geqslant 9$, the result follows from the
arguments presented in Lemma 14. ∎

The next lemma provides a bound on the cardinality of ${\cal C}(n)$.

###### Lemma 19

. For $v\geqslant 5$, $|{\cal C}(2^{v}-2)|\geqslant\frac{4^{n}}{n+2}+2^{n}$.

###### Proof:

Using an averaging argument, one can prove that

$\displaystyle|{\cal C}_{1}(n)|\geqslant
2^{n}\cdot\sum_{k\in\\{1,3,5,7\\}}\frac{\left(\begin{array}[]{c}n\\\
k\end{array}\right)}{8}.$ (15)

More precisely, the claim follows by observing that a Hamming code of length
$i$ and its coset codes partition the space $\mathbb{F}_{2}^{i}$; each of the
$i+1$ coset codes has minimum distance three. Therefore, there exists binary
codes ${\cal C}^{(1)}_{b},{\cal C}^{(3)}_{b},{\cal C}^{(5)}_{b},{\cal
C}^{(7)}_{b}$, of lengths $1,3,5,7$, respectively, each with minimum Hamming
distance three, so that

$|{\cal C}^{(i)}|\geqslant\frac{\left(\begin{array}[]{c}n\\\
i\end{array}\right)}{i+1},\,\text{ for }i\in\\{1,3,5,7\\}.$

From ${\cal C}^{(i)}_{b}$, $i\in\\{1,3,5,7\\}$, it is straightforward to
derive a code ${\cal C}_{1}(n)\subseteq{\cal P}_{1}$ whose cardinality
satisfies (15).

Using a similar reasoning, there exists a
${\boldsymbol{u}}\in\mathbb{F}_{2}^{v}$ in the definition of ${\cal C}_{2}(n)$
for which

$|{\cal C}_{2}(n)|\geqslant
2^{n}\cdot\sum_{k=9}^{n}\frac{\left(\begin{array}[]{c}n\\\
k\end{array}\right)}{n+2},\;\;\text{so that}$ $\displaystyle|{\cal C}(n)|$
$\displaystyle\geqslant
2^{n}\cdot\left(\sum_{k\in\\{1,3,5,7\\}}\frac{\binom{n}{k}}{8}+\sum_{k=9}^{n}\frac{\binom{n}{k}}{n+2}\right)$
$\displaystyle=\frac{2^{n}}{n+2}\cdot\left(\sum_{k=0}^{n}\binom{n}{k}+\sum_{k\in\\{1,3,5,7\\}}\frac{(n+2)\binom{n}{k}}{8}\right)$
$\displaystyle-\frac{2^{n}}{n+2}\cdot\left(\sum_{k=0}^{8}\binom{n}{k}\right)$
$\displaystyle=\frac{4^{n}}{n+2}+\frac{2^{n}}{n+2}\,B(n),$

where

$B(n)=\sum_{k\in\\{1,3,5,7\\}}\frac{(n+2)\binom{n}{k}}{8}-\sum_{k=0}^{8}\binom{n}{k}.$

Since $B(n)-(n+2)>0$ for $n\geqslant 30$, the result follows.

∎

We consider next the case $d>3$, with $\lambda=1$. The basic idea behind the
construction is to map the symbols from $\mathbb{F}_{2}\times\mathbb{F}_{2}$
to $\\{0,1,2,3\\}$ and then use codes in the Lee metric with proper
modifications. The map of interest
$\phi^{(4)}:\mathbb{F}_{2}\times\mathbb{F}_{2}\to\\{0,1,2,3\\}$ is defined as
follows:

$\phi^{(4)}(0;0)\to 0,\;\phi^{(4)}(0;1)\to 1,\;\phi^{(4)}(1;0)\to
2,\;\phi^{(4)}(1;1)\to 3.$

As before, for a word
$({\boldsymbol{a}};{\boldsymbol{b}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}$,
the map is extended in the natural manner according to
$\phi^{(4)}({\boldsymbol{a}};{\boldsymbol{b}})$ $=(\phi^{(4)}(a_{1};b_{1}),$
$\ldots,\phi^{(4)}(a_{n};b_{n}))$; the image of a set under the extended map
$\phi^{(4)}$ is the set of images of elements of the set under the map
$\phi^{(4)}$.

Let $q$ be an odd prime and suppose that $\ell$ and $d\geqslant 2$ are
positive integers. Let $u\in\mathbb{Z}_{d}$ and
${\boldsymbol{z}}\in\mathbb{F}_{q^{\ell}}^{\lfloor\frac{d}{2}\rfloor}$.
Furthermore, suppose that $\alpha$ is a primitive element of
$\mathbb{F}_{q^{\ell}}$. Then, for $n=q^{\ell}-1$, define ${\cal
C}_{N}(n,u,{{\boldsymbol{z}}})$ as follows:

$\displaystyle{\cal C}_{N}(n,u,{\boldsymbol{z}}):=\Big{\\{}$
$\displaystyle({{\boldsymbol{a}}};{{\boldsymbol{b}}})\in\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}:$
(16) $\displaystyle\sum_{i=1}^{n}\phi^{(4)}(a_{i};b_{i})\equiv u\mod d$
$\displaystyle\sum_{i=1}^{n}\phi^{(4)}(a_{i};b_{i})\cdot\alpha^{i}=z_{1}$
$\displaystyle\vdots$
$\displaystyle\sum_{i=1}^{n}\phi^{(4)}(a_{i};b_{i})\cdot\alpha^{i\cdot{\lfloor
d/2\rfloor}}=z_{\lfloor d/2\rfloor}\\},$

with all operations performed over $\mathbb{F}_{q^{\ell}}$.

###### Lemma 20

. Let $q$ be an odd prime where $q\geqslant d+1$. For $n=q^{\ell}-1$, $d$ an
odd positive integer, $u\in\mathbb{Z}_{d}$ and
${\boldsymbol{z}}\in\mathbb{F}_{q^{\ell}}^{\lfloor\frac{d}{2}\rfloor}$,
$d_{\lambda=1}({\cal C}_{N}(n,u,{{\boldsymbol{z}}}))\geqslant d$.

###### Proof:

Suppose that
$({{\boldsymbol{a}}};{{\boldsymbol{b}}}),({{\boldsymbol{c}}};{{\boldsymbol{d}}})\in{\cal
C}_{N}(n,u,{{\boldsymbol{z}}})$. For simplicity, let $\overline{{\rm
Supp}}({\boldsymbol{a}};{\boldsymbol{b}})$ stand for $[n]\setminus{\rm
Supp}({\boldsymbol{a}};{\boldsymbol{b}})$. Furthermore, let

$\displaystyle I$ $\displaystyle=|\\{m\in{\rm
Supp}({\boldsymbol{a}};{\boldsymbol{b}})\cap{\rm
Supp}({\boldsymbol{c}};{\boldsymbol{d}}):a_{m}\neq c_{m}\\}|,$ $\displaystyle
J$ $\displaystyle=|\\{m\in\overline{{\rm
Supp}}({\boldsymbol{a}};{\boldsymbol{b}})\cap\overline{{\rm
Supp}}({\boldsymbol{c}};{\boldsymbol{d}}):a_{m}\neq c_{m}\\}|,\text{ and}$
$\displaystyle K$
$\displaystyle=|\\{m\in[n]:(a_{m},b_{m})\neq(c_{m},d_{m})\\}|-(I+J).$

In order to show that
$d_{\lambda=1}(({{\boldsymbol{a}}};{{\boldsymbol{b}}}),({{\boldsymbol{c}}};{{\boldsymbol{d}}}))\geqslant
d$, we need to prove that $I+2K+4J\geqslant d$. Clearly, if over
$\mathbb{F}_{q}$ the Lee distance of $\phi^{(4)}({\cal
C}_{N}(n,u,{{\boldsymbol{z}}}))$ is at least $d$, then

$I+2K+4J\geqslant I+2K+3J\geqslant d$

and the result holds.

To see that the Lee distance of ${\cal C}_{N}(n,u,{{\boldsymbol{z}}})$ is at
least $d$, notice that we can recover any error vector of weight at most
$\lfloor\frac{d}{2}\rfloor$ from the power sums listed in (16). More
precisely, if the Lee weight of
$\phi^{(4)}({{\boldsymbol{e}}};{{\boldsymbol{f}}})$ is at most
$\lfloor\frac{d}{2}\rfloor$, where $({{\boldsymbol{e}}};{{\boldsymbol{f}}})$
denotes the error vector, it is known from [18] that given
$\sum_{i=1}^{n}\phi^{(4)}(e_{i};f_{i})\cdot\alpha^{i\cdot k}$ for
$k=\\{0,1,\ldots,\lfloor\frac{d}{2}\rfloor\\}$, one can uniquely determine the
vector $\phi^{(4)}({\boldsymbol{e}};{\boldsymbol{f}})$. Clearly, from (16), we
have the values of $\sum_{i=1}^{n}\phi^{(4)}(e_{i};f_{i})\cdot\alpha^{i\cdot
k}$ for $k\in\\{1,\ldots,\lfloor\frac{d}{2}\rfloor\\}$. For $k=0$, we can
uniquely determine $\sum_{i=1}^{n}\phi^{(4)}(e_{i};f_{i})$ as by assumption,
the Lee weight of $\phi^{(4)}({\boldsymbol{e}};{\boldsymbol{f}})$ is at most
$\lfloor\frac{d}{2}\rfloor$. ∎

Using an averaging argument that exploits the fact that the code from (16)
partitions the space into $d(n+1)^{\lfloor d/2\rfloor}$ sets of codewords, we
arrive at

$\displaystyle|{\cal
C}_{N}(n,u,{{\boldsymbol{z}}})|\geqslant\frac{4^{n}}{d(n+1)^{\lfloor
d/2\rfloor}},$ (17)

which for $d\geqslant 7$ improves the lower bounds from the previous section.
Recall from Section V that one alternative to using codes in the ALD is to
construct codes in the Hamming distance over $\mathbb{F}_{4}$. For instance
when $d=3$, a code with minimum Hamming distance $3$ can correct any error
with Hamming weight one and so it has codewords which are at distance at least
$3$ under the ALD. Since the largest code of distance $d=2r+1$ in the Hamming
metric over $\mathbb{F}_{4}$ has cardinality
$\frac{4^{n}}{\sum_{j=0}^{r}3^{j}\cdot\left(\begin{array}[]{c}n\\\
j\end{array}\right)}$ we see that for $d\geqslant 9$, and $n$ large enough the
quantity in (17) is larger than the largest possible code with Hamming
distance $d$ over $\mathbb{F}_{4}$. From Proposition 9, we also conclude that

$\frac{4^{n}}{d(n+1)^{r}}\leqslant A_{\lambda}(n,2r+1)\leqslant
2^{n}\cdot\sum_{\ell=0}^{n}\frac{\binom{n}{\ell}}{\sum_{j=0}^{r}\left(\begin{array}[]{c}\ell\\\
j\end{array}\right)},$

where $d=2r+1$. Note that the gap between the upper and lower bounds is a
function of $r$ as well as $n$. Table V compares the lower bounds of (16) with
the LP bound of (9).

The last construction we present may be used to generate codes under the ALD
for a large range of parameters. In particular, although our focus is on codes
with integer $\lambda$ values, we observe that the construction in question
may also be used to generate ALD codes with $0<\lambda<1$.

$n\backslash d_{\lambda=1}$ 3 5 7 1 1–3 2 2–9 1–2 1–2 3 6–30 1–7 1–5 4 18–99
3–21 1–13 5 57–336 6–67 1–35 6 196–1161 17–219 2–101 7 683–4080 52–731 5–296 8
2428–14535 162–2483 13–895 9 8739–52377 525–8563 38–2783 10 31776–190557
1734–29901 113–8890

TABLE IV: Comparison of the upper bound based on the LP in (9) (value on the
right of the dash line) with (17) (value on the left of the dash line). The
relative gap increases with increasing ALD.

Let ${\cal C}_{M}(n,d)$ be a code over $\mathbb{F}_{3}$ of length $n$ with
minimum Manhattan ($\ell_{1}$) distance $d$. Similarly, let ${\cal
C}_{H}(n,d)$ denote a binary code of length $n$ and minimum Hamming distance
$d$. Define

$\displaystyle{\cal C}_{\lambda}(n,d):=$
$\displaystyle\\{({{\boldsymbol{a}}};{{\boldsymbol{b}}})\in\\{0,1\\}^{n}\times\\{0,1\\}^{n}:$
$\displaystyle(a_{1}+b_{1},a_{2}+b_{2},\ldots,a_{n}+b_{n})\in{\cal
C}_{M}(n,\lceil\frac{d}{1+\lambda}\rceil),$
$\displaystyle\mathcal{S}({{\boldsymbol{a}}};{{\boldsymbol{b}}})\in{\cal
C}_{H}({w({{\boldsymbol{a}}};{{\boldsymbol{b}}})},\lceil\frac{d}{\lambda}\rceil)\\},$
(18)

where addition is performed over the reals. We have the following lemma.

###### Lemma 21

. Given integers $n$ and $d$, one has $d_{\lambda}({\cal
C}_{\lambda}(n,d))\geqslant d$.

###### Proof:

Suppose that
$({{\boldsymbol{a}}};{{\boldsymbol{b}}}),({{\boldsymbol{c}}};{{\boldsymbol{d}}})\in{\cal
C}_{\lambda}(n,d)$, and let

$\displaystyle I$ $\displaystyle=|\\{m\in{\rm
Supp}({\boldsymbol{a}};{\boldsymbol{b}})\cap{\rm
Supp}({\boldsymbol{c}};{\boldsymbol{d}}):a_{m}\neq c_{m}\\}|,$ $\displaystyle
J$ $\displaystyle=|\\{m\in\overline{{\rm
Supp}}({\boldsymbol{a}};{\boldsymbol{b}})\cap\overline{{\rm
Supp}}({\boldsymbol{c}};{\boldsymbol{d}}):a_{m}\neq c_{m}\\}|,\text{ and}$
$\displaystyle K$
$\displaystyle=|\\{m\in[n]:(a_{m},b_{m})\neq(c_{m},d_{m})\\}|-(I+J).$

Recall that if
$d_{\lambda}(({{\boldsymbol{a}}};{{\boldsymbol{b}}}),({{\boldsymbol{c}}};{{\boldsymbol{d}}}))\geqslant
d$, we need to show that

$\lambda\cdot I+(1+\lambda)\cdot K+2(1+\lambda)\cdot J\geqslant d.$

If $(a_{1}+b_{1},\ldots,a_{m}+b_{m})\neq(c_{1}+d_{1},\ldots,c_{m}+d_{m})$,
then $K+2J\geqslant\lceil\frac{d}{1+\lambda}\rceil$ from (18). Thus,

${d\leqslant}(1+\lambda)\cdot(K+2J){=}(1+\lambda)\cdot K+2(1+\lambda)\cdot J,$

which proves the claimed result. Otherwise, if
$(a_{1}+b_{1},\ldots,a_{m}+b_{m})=(c_{1}+d_{1},\ldots,c_{m}+d_{m})$, the
result is an immediate consequence of (18). ∎

##  VII Conclusion

We introduced a novel distance measure suitable for modeling the confusion
graph of a DNA-based data storage readout channel. The distance, termed the
asymmetric Lee distance (ALD) is related to the Lee distance, but refines the
Lee distance in terms of allowing symbol weightings and asymmetries in the
symbol distances. We derived upper bounds on the largest size of ALD codes
using LP-based techniques, and provided linear and non-linear code
constructions for some choices of symbol weighting parameters.

## References

  * [1] T. Alderson and S. Huntemann. “On maximum Lee distance codes,” _J. of Discrete Mathematics_ , 2013.
  * [2] J. Astola, “The Theory of Lee-codes,” Lappeenranta University of Technology, Department of Physics and Mathematics, Research Report, Jan. 1982.
  * [3] G. M. Church, Y. Gao, and S. Kosuri, “Next-Generation Digital Information Storage in DNA,” Science, vol. 337, no. 6102, pp. 1628-1628, Sep. 2012.
  * [4] D. Cullina and N. Kiyavash, “Generalized sphere-packing and sphere-covering bounds on the size of codes for combinatorial channels,” available at http://arxiv.org/abs/1405.1464, 2015.
  * [5] P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Doctoral dissertation, Universite Catholique de Louvain, 1973.
  * [6] A. Fazeli, A. Vardy, E. Yaakobi, “Generalized Sphere Packing Bound,” available at http://arxiv.org/abs/1401.6496, 2014.
  * [7] Feng, J., Liu, K., Bulushev, R. D., Khlybov, S., Dumcenco, D., Kis, A., and Radenovic, A., “Identification of Single Nucleotides in MoS2 Nanopores,” 2015, arXiv preprint arXiv:1505.01608.
  * [8] N. Goldman et al., “Towards practical, high-capacity, low-maintenance information storage in synthesized DNA,” Nature, Jan. 2013.
  * [9] E. Hof et al., “Capacity-achieving polar codes for arbitrarily permuted parallel channels,” IEEE Trans. on Info. Theory, vol. 59, no. 3, pp. 1505-1516, March 2013.
  * [10] M. Kaykobad, “Positive solutions of positive linear systems,” Lin. Alg. and its App., vol. 64, pp. 133-140, Jan. 1985.
  * [11] H. M. Kiah, G. Puleo, and O. Milenkovic, “Codes for DNA sequence profiles,” arXiv preprint arXiv:1502.00517, 2015.
  * [12] T. Kløve, _Error correcting codes for the asymmetric channel_ , Department of Pure Mathematics, University of Bergen, 1981.
  * [13] A.A. Kulkarni, and N. Kiyavash, “Nonasymptotic upper bounds for deletion correcting codes,” IEEE Trans. on Info. Theory, vol. 59, no. 8, pp. 5115-5130, April 2013.
  * [14] A. Mazumdar, A. Barg, and N. Kashyap, “Coding for high-density recording on a 1-D granular magnetic medium,” IEEE Trans. on Info. Theory, vol. 57, no. 11, pp. 7403-7417, June 2011.
  * [15] J. Miten, I. T. Fiddes, K. H. Miga, H. E. Olsen, B. Paten, and M. Akeson, “Improved data analysis for the MinION nanopore sequencer,” _Nature Methods_ , online, 2015.
  * [16] K. Nakamura, et al., “Sequence-specific error profile of Illumina sequencers,” Nucleic acids research, voll. 39, no. 13, 2011.
  * [17] T. Richardson and R. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding,” IEEE Trans. on Info. Theory, vol. 47, no. 2, pp. 599-618, August 2002.
  * [18] Roth, R., Introduction to coding theory, Cambridge University Press, 2006.
  * [19] Tal, I., Vardy, A., “How to construct polar codes,” IEEE Trans. on Info. Theory, vol. 59, no. 10, pp. 6562 - 6582, September 2013.
  * [20] L. Tolhuizen, “The generalized Gilbert-Varshamov bound is implied by Turan’s theorem,” _IEEE Transactions on Information Theory_ , 43, 5, pp. 1605-1606, 1997.
  * [21] P. Turan, “On an extremal problem in graph theory”, Matematikai es Fizikai Lapok, vol. 48, pp.436 452, 1941.
  * [22] S. M. Yazdi, Y. Yuan, J. Ma, H. Zhao, and O. Milenkovic, “A Rewritable, Random-Access DNA-Based Storage System,” arXiv preprint arXiv:1505.02199, 2015 (also to be presented at DNA21, Boston, USA, 2015).
  * [23] S. M. Yazdi, H. M. Kiah, E. Ruiz Garcia, J. Ma, H. Zhao, and O. Milenkovic. ”DNA-Based Storage: Trends and Methods.” arXiv preprint arXiv:1507.01611, 2015.