# Parameters of Codes for the Binary Asymmetric Channel

Giuseppe Cotardo∗ School of Mathematics and Statistics
University College Dublin, Ireland  Alberto Ravagnani∗∗ Department of
Mathematics and Computer Science
Eindhoven University of Technology, the Netherlands

###### Abstract.

We introduce two notions of discrepancy between binary vectors, which are not
metric functions in general but nonetheless capture the mathematical structure
of the binary asymmetric channel. In turn, these lead to two new fundamental
parameters of binary error-correcting codes, both of which measure the
probability that the maximum likelihood decoder fails. We then derive various
bounds for the cardinality and weight distribution of a binary code in terms
of these new parameters, giving examples of codes meeting the bounds with
equality.

###### Key words and phrases:

Binary asymmetric channel, discrepancy, combinatorial neural code,
unsuccessful decoding, bound.

∗ The author is supported by the Irish Research Council through grant n.
GOIPG/2018/2534

∗∗ The author is supported by the Dutch Research Council through grants n.
OCEANW.KLEIN.539 and n. VI.Vidi.203.045.

## Introduction

In [3], the authors initiate the study of coding theory in connection with
neuroscience. They take a new look at neural coding from a mathematical
perspective, discretizing receptive fields and modeling them as binary codes
$C\subseteq\\{0,1\\}^{n}$. Under this approach, each of the $n$ coordinates of
a vector represents a neuron, which is “on” if the corresponding coordinate is
a $1$, and “off” otherwise.

In the context of discretized receptive field codes, it is natural to assume
that the failure of a neuron to be “on” is more probable than a neuron being
“on” when it should not (we refer to [3] for an explanation of the model).
This behaviour is captured by the binary asymmetric channel, in which $0$
becomes $1$ with probability $p$ and $1$ becomes $0$ with probability $q\geq
p$. The binary asymmetric channel is in fact a family of channels, which
comprises both the binary symmetric channel (obtained for $p=q$) and the
Z-channel (obtained for $p=0$).

In this work, we study the mathematical properties of the binary asymmetric
channel and the structure of binary codes in connection with it. Very
interesting progress has been recently made in this context, which we now
briefly summarize. In 2016 it was proved in [9] that the binary asymmetric
channel is metrizable in the weak sense of Massey [8]. Shortly after that,
Qureshi showed that the binary asymmetric channel admits a matched metric
[10], establishing a conjecture of Firer and Walker [6]. The approach of [10]
develops criteria (and algorithms) to understand when a discrete memoryless
channel admits a metric for which the maximum likelihood decoder coincides
with the nearest neighbour decoder. A current open problem is to explicitly
describe the metrics matching the binary asymmetric channel.

### Our contribution.

In this paper, we bring forward the theory of binary codes for the asymmetric
channel, with a focus on their structural properties and parameters. We
introduce two notions of discrepancy between binary vectors
$x,y\in\mathbb{F}_{2}^{n}$, which we denote by $\delta(x,y)$ and
$\hat{\delta}(x,y)$ respectively. Although these are not metrics in general,
they are relatively simple functions that nicely relate to the probability law
defining the binary asymmetric channel. In particular, as we will see,
$\delta$ matches such a channel (in the sense of our Theorem 2.5). We also
establish some general properties of $\delta$ and $\hat{\delta}$, showing the
connection between these and the more traditional Hamming distance. The
function $\delta$ is not symmetric but satisfies the triangular inequality in
general. In contrast, $\hat{\delta}$ is symmetric but does not satisfy the
triangular inequality.

Each of the two discrepancy functions mentioned above naturally defines a
fundamental parameter of a code for the binary asymmetric channel. We call
these minimum discrepancy and minimum symmetric discrepancy. Moreover, we show
that they give incomparable upper bounds for the probability that the maximum
likelihood decoder fails.

We devote the second part of the paper to bounds on the size of binary codes
having prescribed minimum (symmetric) discrepancy. We show how some first
bounds can be obtained from the theory of block codes endowed with the Hamming
distance. We then argue why techniques from classical coding theory do not
easily extend to the discrepancy setting, showing that the graphs that
naturally arise in the latter context do not have the same regularity as the
corresponding “Hamming-metric” graphs. Finally, we derive upper and lower
bounds for the size of binary codes using combinatorial arguments. The most
interesting of these involves a code parameter that is finer than the
cardinality, namely, the weight distribution. We illustrate how to apply the
various bounds and provide examples of codes meeting them with equality.

##  1\. Preliminaries and Notation

Throughout the paper, $\mathbb{F}_{2}=\\{0,1\\}$ is the binary field,
$\mathbb{N}=\\{0,1,2,\ldots\\}$ is the set of natural numbers, and $n\geq 2$
is an integer. We study a family of channels indexed by a pair of real numbers
$(p,q)$ in the interval $[0,1/2)$. These are defined as follows.

######  Definition 1.1.

Let $0\leq p\leq q<1/2$ be real numbers and let

$\mathbb{P}_{p,q}(1\mid 0):=p,\qquad\mathbb{P}_{p,q}(0\mid
0):=1-p,\qquad\mathbb{P}_{p,q}(0\mid 1):=q,\qquad\mathbb{P}_{p,q}(1\mid
1):=1-q.$

The binary asymmetric channel associated with $(n,p,q)$ is the triple
$\mathcal{K}^{n}=(\mathbb{F}_{2}^{n},\mathbb{F}_{2}^{n},\mathbb{P}_{p,q}^{n})$,
where
$\mathbb{P}_{p,q}^{n}:\mathbb{F}_{2}^{n}\times\mathbb{F}_{2}^{n}\longrightarrow\mathbb{R}$
is the function defined by

$\mathbb{P}_{p,q}^{n}(y\mid x)=\prod_{i=1}^{n}\mathbb{P}_{p,q}(y_{i}\mid
x_{i})\quad\mbox{for all $x,y\in\mathbb{F}_{2}^{n}$}.$ (1)

The previous definition models a discrete memoryless channel where the noise
acts independently on the individual components of a binary vector. The
assumption $p\leq q$ tells us that it is more probable that a $1$ becomes a
$0$ than a $0$ becomes a $1$; see Figure 1. The function
$\mathbb{P}_{p,q}^{n}$ expresses the transition probabilities when the channel
is used $n$ times.

$0$$0$$1$$1$$1-p$$p$$q$$1-q$ Figure 1.

The main motivation for us to consider the binary asymmetric channel comes
from recent developments in the theory of neural codes. More precisely, it has
been shown in [3] that binary codes for the asymmetric channel can be seen as
a discretization of receptive field codes. These are neural codes describing
the brain’s representation of the so called space of stimuli covered by the
receptive fields. In this context, binary codes are sometimes called
combinatorial neural codes. We refer to [4, 3] for further details and to [4,
Figure 1] for a graphical representation of the link between stimuli and
binary vectors.

Following [3], we define codes for the binary asymmetric channel as follows.

######  Definition 1.2.

A code is a subset $C\subseteq\mathbb{F}_{2}^{n}$ with $|C|\geq 2$. Its
elements are called codewords.

To simplify the discussion in the sequel, we introduce the following symbols.

######  Notation 1.3.

We denote by $\omega^{\textnormal{H}}(x):=|\\{1\leq i\leq n\,:\,x_{i}=1\\}|$
the Hamming weight of a binary vector $x\in\mathbb{F}_{2}^{n}$. Moreover, for
all $x,y\in\mathbb{F}_{2}^{n}$ we let

$\displaystyle d_{00}(y,x)$ $\displaystyle:=|\\{i\,:\,y_{i}=x_{i}=0\\}|,$
$\displaystyle d_{01}(y,x)$ $\displaystyle:=|\\{i\,:\,y_{i}=0\mbox{ and
}x_{i}=1\\}|,$ $\displaystyle d_{11}(y,x)$
$\displaystyle:=|\\{i\,:\,y_{i}=x_{i}=1\\}|,$ $\displaystyle d_{10}(y,x)$
$\displaystyle:=|\\{i\,:\,y_{i}=1\mbox{ and }x_{i}=0\\}|.$

We start with a preliminary result that gives a convenient expression for
$\mathbb{P}_{p,q}^{n}$. We will need it later.

######  Lemma 1.4.

For all $x,y\in\mathbb{F}_{2}^{n}$ we have

$\mathbb{P}_{p,q}^{n}(y\mid
x)=\left(\frac{q}{1-p}\right)^{d_{01}(y,x)}\left(\frac{p}{1-q}\right)^{d_{10}(y,x)}(1-q)^{\omega^{\textnormal{H}}(y)}\,(1-p)^{n-\omega^{\textnormal{H}}(y)},$

where we set $0^{0}:=1$.

###### Proof.

Using the definition of $\mathbb{P}_{p,q}^{n}(y\mid x)$ directly, with the
convention that $0^{0}=1$, one finds

$\mathbb{P}_{p,q}^{n}(y\mid
x)=(1-p)^{d_{00}(y,x)}\,p^{d_{10}(y,x)}\,q^{d_{01}(y,x)}\,(1-q)^{d_{11}(y,x)}.$
(2)

By definition we have

$d_{11}(y,x)=\omega^{\textnormal{H}}(y)-d_{10}(y,x),\qquad
d_{00}(y,x)=n-\omega^{\textnormal{H}}(y)-d_{01}(y,x).$

In particular, the result immediately follows from (2) when $p=0$. If $p>0$ we
write

$\displaystyle\mathbb{P}_{p,q}^{n}(y\mid x)$
$\displaystyle=(1-p)^{n-\omega^{\textnormal{H}}(y)-d_{01}(y,x)}\,p^{d_{10}(y,x)}\,q^{d_{01}(y,x)}\,(1-q)^{\omega^{\textnormal{H}}(y)-d_{10}(y,x)}$
$\displaystyle=\left(\frac{q}{1-p}\right)^{d_{01}(y,x)}\left(\frac{p}{1-q}\right)^{d_{10}(y,x)}(1-q)^{\omega^{\textnormal{H}}(y)}\,(1-p)^{n-\omega^{\textnormal{H}}(y)},$

which is the desired expression. ∎

######  Remark 1.5.

The binary asymmetric channel generalizes both the Z-channel and the binary
symmetric channel, which are obtained for particular choices of the parameters
$p$ and $q$. More precisely, $p=0$ (and $q$ arbitrary) gives the Z-channel,
while $p=q$ gives the binary symmetric channel; see e.g. [1] and [2],
respectively.

##  2\. Discrepancy

In this section we introduce two functions that measure how “different” binary
vectors are with respect to the binary asymmetric channel. We call these
discrepancy and symmetric discrepancy. We then prove that the maximum
likelihood decoder for the binary asymmetric channel coincides with the
decoder naturally associated with the first discrepancy function.

In the second part of the section we define two new parameters of a code
$C\subseteq\mathbb{F}_{2}^{n}$ (one for each discrepancy notion) and establish
their main properties. In later sections we will give evidence that these
parameters measure the quality of a code for the binary asymmetric channel.

######  Notation 2.1.

In the remainder of the paper we work with fixed real numbers $p$ and $q$ that
satisfy $0\leq p\leq q<1/2$. We also let

$\gamma:=\log_{\frac{q}{1-p}}\left(\frac{p}{1-q}\right)\in\mathbb{R}\cup\\{+\infty\\},$

with the convention that $\gamma=+\infty$ if $p=0$ (and for any value of $q$).

The quantity $\gamma$ (or better its inverse) has already been studied in
connection with the binary asymmetric channel. More precisely, the authors of
[11] use the expression

$S(p,q)=\frac{\textup{ln}(1-p)-\textup{ln}(q)}{\textup{ln}(1-q)-\textup{ln}(p)}=1/\gamma$

to classify binary asymmetric channels up to equivalence. In this paper we
will instead use $\gamma$ to define a discrepancy function between binary
vectors and new parameters of codes for the binary asymmetric channel. We
start with the following numerical facts.

######  Lemma 2.2.

  1. (1)

We have $0\leq\frac{p}{1-q}\leq\frac{q}{1-p}<1$. Moreover,
$\frac{p}{1-q}=\frac{q}{1-p}$ if and only if $p=q$.

  2. (2)

We have $\gamma\geq 1$, with equality if and only if $0<p=q$.

###### Proof.

Since $0\leq p\leq q<1/2$, we have $0\leq\frac{p}{1-q}<1$ and
$0\leq\frac{q}{1-p}<1$. If $p=q$ then we clearly have
$\frac{p}{1-q}=\frac{q}{1-p}$. On the other hand, if $p<q$ then $p+q<1$
implies $(p+q)(q-p)<q-p$. The latter inequality can be re-written as
$p(1-p)<q(1-q)$, i.e., as $\frac{p}{1-q}<\frac{q}{1-p}$. Finally, since
$\frac{p}{1-q}\leq\frac{q}{1-p}<1$, we have $\gamma\geq 1$. ∎

The first notion of discrepancy we propose is the following.

######  Definition 2.3.

The discrepancy between $y,x\in\mathbb{F}_{2}^{n}$ is
$\delta_{p,q}(y,x):=\gamma_{p,q}\,d_{10}(y,x)+d_{01}(y,x)$, with the
convention that $+\infty\cdot 0=0$.

Notice that if $0<p=q$ then $\gamma=1$ and therefore $\delta_{p,q}$ coincides
with the Hamming distance $d^{\textnormal{H}}$ on $\mathbb{F}_{2}^{n}$. The
latter is defined by $d^{\textnormal{H}}(x,y):=|\\{i\,:\,x_{i}\neq y_{i}\\}|$
for all $x,y\in\mathbb{F}_{2}^{n}$, which is clearly symmetric. If $p<q$, then
$\delta_{p,q}$ is not a symmetric function in general. For example, if $p\neq
0$, $x=(1,1,1)$, and $y=(1,0,0)$, then
$\delta_{p,q}(y,x)=2<2\gamma=\delta_{p,q}(x,y)$.

A natural way to decode a received message $y$ is to return the codeword $x\in
C$ that maximizes $\mathbb{P}_{p,q}^{n}(y\mid x)$. The following definition is
therefore standard in information theory111As in this paper we do not focus on
complexity theory, decoders are defined as (deterministic) functions rather
than algorithms..

######  Definition 2.4.

For a code $C\subseteq\mathbb{F}_{2}^{n}$, the maximum likelihood decoder is
the function $D_{C}:\mathbb{F}_{2}^{n}\to C\cup\\{\bm{f}\\}$ defined by

$D_{C}(y):=\left\\{\begin{array}[]{cl}x&\mbox{if $x$ is the unique codeword
that maximizes $\mathbb{P}_{p,q}^{n}(y\mid x)$,}\\\
\bm{f}&\mbox{otherwise,}\end{array}\right.$

where $\bm{f}\notin\mathbb{F}_{2}^{n}$ denotes a failure message.

The following result shows that the discrepancy function $\delta_{p,q}$
matches (in the sense of the natural generalization of a concept of Séguin to
functions that are not necessarily distances; see [12]) the binary asymmetric
channel.

######  Theorem 2.5.

Let $x,x^{\prime},y\in\mathbb{F}_{2}^{n}$. The following are equivalent:

  1. (1)

$\delta_{p,q}(y,x)<\delta_{p,q}(y,x^{\prime})$,

  2. (2)

$\mathbb{P}^{n}_{p,q}(y\mid x)>\mathbb{P}^{n}_{p,q}(y\mid x^{\prime})$.

###### Proof.

By Lemma 1.4, proving that $\mathbb{P}^{n}(y\mid
x^{\prime})<\mathbb{P}^{n}(y\mid x)$ is equivalent to showing that

$\left(\frac{q}{1-p}\right)^{d_{01}(y,x^{\prime})}\left(\frac{p}{1-q}\right)^{d_{10}(y,x^{\prime})}<\left(\frac{q}{1-p}\right)^{d_{01}(y,x)}\left(\frac{p}{1-q}\right)^{d_{10}(y,x)},$
(3)

where $0^{0}=1$ by convention. Assume $p>0$. Then using the definition of
discrepancy the inequality in (3) can be re-written as

$\left(\frac{q}{1-p}\right)^{\delta_{p,q}(y,x^{\prime})}<\left(\frac{q}{1-p}\right)^{\delta_{p,q}(y,x)}.$

Since $\frac{q}{1-p}<1$ by Lemma 2.2, the latter inequality holds if and only
if $\delta_{p,q}(y,x)<\delta_{p,q}(y,x^{\prime})$, as desired.

Now assume $p=0$ and $q$ arbitrary (possibly $q=0$ as well). Then (3) is
equivalent to

$q^{d_{01}(y,x^{\prime})}\,0^{d_{10}(y,x^{\prime})}<q^{d_{01}(y,x)}\,0^{d_{10}(y,x)}.$

This happens if and only if one of the following holds:

  * •

$d_{10}(y,x^{\prime})=d_{10}(y,x)=0$ and $d_{01}(y,x^{\prime})>d_{01}(y,x)$,

  * •

$d_{10}(y,x)=0$ and $d_{10}(y,x^{\prime})>0$.

By definition of $\delta_{p,q}$, this is equivalent to
$\delta_{p,q}(y,x)<\delta_{p,q}(y,x^{\prime})$, concluding the proof. ∎

Theorem 2.5 shows that, for any code $C\subseteq\mathbb{F}_{2}^{n}$, the
maximum likelihood decoder $D_{C}$ coincides with the minimum discrepancy
decoder $D^{\delta}_{C}:\mathbb{F}_{2}^{n}\to C\cup\\{\bm{f}\\}$. This is
defined by

$D^{\delta}_{C}(y):=\left\\{\begin{array}[]{cl}x&\mbox{if $x$ is the unique
codeword that minimizes $\delta_{p,q}(y,x)$,}\\\
\bm{f}&\mbox{otherwise,}\end{array}\right.$

where $\bm{f}$ is the same failure message as in Definition 2.4.

######  Remark 2.6.

It is natural to compare the minimum discrepancy decoder $D^{\delta}_{C}$ (or
equivalently the maximum likelihood decoder $D_{C}$) with the minimum Hamming
distance decoder, denoted by $D_{C}^{\textnormal{H}}$. These two decoders are
different in general. For example, let $p=0.1$ and $q=0.4$. Then
$\gamma_{p,q}\approx 2.21$. Let

$\displaystyle
C=\\{(0,0,0),(0,1,0),(1,1,0),(1,1,1)\\}\subseteq\mathbb{F}_{2}^{3}$

and $y=(0,0,1)$. One can check that $D^{\delta}_{C}(y)=(1,1,1)$, while
$D_{C}^{\textnormal{H}}(y)=(0,0,0)$.

######  Notation 2.7.

In the reminder of the paper we focus on the structure of codes endowed with
the discrepancy function $\delta_{p,q}$. For this type of study we will need
to exclude the extreme case of the Z-channel from our treatment. Therefore,
from now on, we will always assume

$0<p\leq q<1/2$.

To simplify the notation, we will also omit the subscript “$p,q$” in symbols,
writing for example $\mathbb{P}^{n}$ for $\mathbb{P}^{n}_{p,q}$ and $\delta$
for $\delta_{p,q}$.

We continue by introducing a second discrepancy function, which we denote by
$\hat{\delta}$. In Section 3 we will use both notions of discrepancy ($\delta$
and $\hat{\delta}$) to estimate the failure probability of the maximum
likelihood decoder.

######  Definition 2.8.

symmetric discrepancy between vectors $y,x\in\mathbb{F}_{2}^{n}$ is
$\hat{\delta}(y,x):=\delta(y,x)-\omega^{\textnormal{H}}(y)(\gamma-1)$.

As we will see throughout the paper, the functions $\delta$ and $\hat{\delta}$
have very different mathematical properties. For example, while $\delta$ is
not symmetric but satisfies the triangular inequality, $\hat{\delta}$ is
symmetric but does not satisfy the triangular inequality.

We now show that $\hat{\delta}$ is indeed a symmetric function. We start with
the following preliminary result.

######  Lemma 2.9.

Let $x,y\in\mathbb{F}_{2}^{n}$. The following hold:

  1. (1)

$d_{10}(y,x)=d_{10}(x,y)+\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x)$,

  2. (2)

$d_{01}(y,x)=d_{01}(x,y)+\omega^{\textnormal{H}}(x)-\omega^{\textnormal{H}}(y)$,

  3. (3)

$\delta(y,x)=\delta(x,y)+(\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x))(\gamma-1)$.

  4. (4)

$\delta(y,x)=d^{\textnormal{H}}(y,x)+(\gamma-1)d_{10}(y,x)$.

  5. (5)

$\hat{\delta}(y,x)=d^{\textnormal{H}}(y,x)-(\gamma-1)d_{11}(y,x)$.

###### Proof.

In order to prove the first equality, observe that
$d_{10}(y,x)+d_{11}(y,x)=\omega^{\textnormal{H}}(y)$, from which

$d_{10}(y,x)=\omega^{\textnormal{H}}(y)-d_{11}(y,x)=\omega^{\textnormal{H}}(y)-d_{11}(x,y)=\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x)+d_{10}(x,y).$

Analogously, the second equality follows from the fact that
$d_{01}(y,x)+d_{11}(y,x)=\omega^{\textnormal{H}}(x)$. The third equality is a
consequence of the first and the second. The fourth equality follows from the
fact that $d^{\textnormal{H}}(y,x)=d_{10}(y,x)+d_{01}(y,x)$. Finally,
combining the fourth equality with
$d_{10}(y,x)+d_{11}(y,x)=\omega^{\textnormal{H}}(y)$, we have

$\hat{\delta}(y,x)=\delta(y,x)-\omega^{\textnormal{H}}(y)(\gamma-1)=d^{\textnormal{H}}(y,x)-(\gamma-1)d_{11}(y,x).$

This concludes the proof. ∎

The following result follows from Lemma 2.9 and the fact that
$d^{\textnormal{H}}(y,x)=d^{\textnormal{H}}(x,y)$ and
$d_{11}(x,y)=d_{11}(y,x)$ for all $x,y\in\mathbb{F}_{2}^{n}$

######  Proposition 2.10.

For all $x,y\in\mathbb{F}_{2}^{n}$ we have
$\hat{\delta}(y,x)=\hat{\delta}(x,y)$.

In the remainder of the section we turn to the structure of codes
$C\subseteq\mathbb{F}_{2}^{n}$. Each discrepancy notion ($\delta$ and
$\hat{\delta}$) defines a code parameter as follows.

######  Definition 2.11.

For a code $C$, let

$\displaystyle\delta(C)$
$\displaystyle:=\min\\{\delta(x,x^{\prime})\,:\,x,x^{\prime}\in C,\,x\neq
x^{\prime}\\},$ $\displaystyle\hat{\delta}(C)$
$\displaystyle:=\min\\{\hat{\delta}(x,x^{\prime})\,:\,x,x^{\prime}\in
C,\,x\neq x^{\prime}\\}.$

We call these the minimum discrepancy and the minimum symmetric discrepancy of
$C$, respectively.

######  Remark 2.12.

For any code $C$ we have $\hat{\delta}(C)\leq\delta(C)$. Indeed, if
$x,x^{\prime}\in C$ satisfy $\delta(x,x^{\prime})=\delta(C)$, then
$\hat{\delta}(C)\leq\hat{\delta}(x,x^{\prime})=\delta(x,x^{\prime})-\omega^{\textnormal{H}}(x)(\gamma-1)\leq\delta(x,x^{\prime})=\delta(C)$.
The numbers $\delta(C)$ and $\hat{\delta}(C)$ are very different in general.
Moreover, while $\delta(C)$ is always a non-negative number, $\hat{\delta}(C)$
can even be negative.

######  Example 2.13.

Let $p:=0.1$ and $q:=0.3$, from which $\gamma\approx 1.77$. One can check that
for $C=\\{(1,0,0),(0,1,1),(1,1,1)\\}$ we have $\delta(C)=1$ and
$\hat{\delta}(C)=\hat{\delta}((0,1,1),(1,1,1))\approx-0.54$.

The following result gives sufficient conditions under which a vector
$y\in\mathbb{F}_{2}^{n}$ decodes to a codeword $x\in C$, in terms of the
minimum (symmetric) discrepancies of $C$. In Theorem 3.6 we will use these
conditions to obtain bounds for the probability that the maximum likelihood
decoder fails.

######  Proposition 2.14.

Let $C\subseteq\mathbb{F}_{2}^{n}$ be a code. Let $x\in C$ and
$y\in\mathbb{F}_{2}^{n}$. We have $D_{C}(y)=x$, provided that one of the
following holds:

  1. (1)

$\delta(y,x)<\frac{\delta(C)+(\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x))(\gamma-1)}{2}$,
or

  2. (2)

$\delta(y,x)<\frac{\hat{\delta}(C)+\omega^{\textnormal{H}}(y)(\gamma-1)}{2}$ .

The proof of Proposition 2.14 relies on the following triangular inequality
for $\delta$.

######  Lemma 2.15.

For all $x,y,z\in\mathbb{F}_{2}^{n}$ we have

$\delta(z,x)\leq\delta(z,y)+\delta(y,x).$

###### Proof.

Since the discrepancy is additive on the vector components, it is enough to
prove the result for $n=1$. The case-by-case analysis is summarized in the
following table:

$a$ | $b$ |  $c$ | $\delta(c,a)$ | $\delta(c,b)$ | $\delta(b,a)$
---|---|---|---|---|---
0 | 0 | 0  | 0 | 0 | 0
1 | 0 | 0  | $1$ | 0 | $1$
0 | 1 | 0  | 0 | $1$ | $\gamma$
0 | 0 | 1  | $\gamma$ | $\gamma$ | 0
1 | 1 | 0  | $1$ | $1$ | 0
1 | 0 | 1  | 0 | $\gamma$ | $1$
0 | 1 | 1  | $\gamma$ | 0 | $\gamma$
1 | 1 | 1  | 0 | 0 | 0

This concludes the proof by additivity. ∎

######  Remark 2.16.

Although $\hat{\delta}$ is symmetric, it does not satisfy a natural triangular
inequality. More precisely, in general we have that
$\hat{\delta}(z,x)\not\leq\hat{\delta}(z,y)+\hat{\delta}(y,x)$. For example,
suppose that $\gamma>1$ and let $x=(0,0,0)$, $y=(1,0,0)$, and $z=(1,1,0)$.
Then $\hat{\delta}(z,x)=2>3-\gamma=\hat{\delta}(z,y)+\hat{\delta}(y,x)$. The
closest “triangular-type inequality” we could derive for $\hat{\delta}$ is

$\hat{\delta}(z,x)\leq\hat{\delta}(z,y)+\hat{\delta}(y,x)+\omega^{\textnormal{H}}(y)(\gamma-1),$

which holds for all $x,y,z\in\mathbb{F}_{2}^{n}$ and contains
$\omega^{\textnormal{H}}(y)(\gamma-1)$ as correction term.

###### Proof of Proposition 2.14.

We start by observing that, for any $x,x^{\prime},y\in\mathbb{F}_{2}^{n}$,
Lemmas 2.9 and 2.15 combined imply

$\delta(y,x^{\prime})\geq\delta(x,x^{\prime})-\delta(y,x)+(\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x))(\gamma-1).$
(4)

We now fix $x\in C$, $y\in\mathbb{F}_{2}^{n}$ and prove the two statements
separately.

  1. (1)

For every $x^{\prime}\in C$ with $x^{\prime}\neq x$, the inequality in (4) and
our assumption on $\delta(y,x)$ give

$\displaystyle\delta(y,x^{\prime})$
$\displaystyle\geq\delta(x,x^{\prime})-\delta(y,x)+(\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x))(\gamma-1)$
$\displaystyle>\delta(C)-\frac{\delta(C)+(\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x))(\gamma-1)}{2}+(\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x))(\gamma-1)$
$\displaystyle=\frac{\delta(C)+(\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x))(\gamma-1)}{2}$
$\displaystyle>\delta(y,x).$

The desired statement now follows from Theorem 2.5 and the definition of
maximum likelihood decoder.

  2. (2)

Analogously, for every $x^{\prime}\in C$ with $x^{\prime}\neq x$, the
inequality in (4) and the assumption on $\delta(y,x)$ imply

$\displaystyle\delta(y,x^{\prime})$
$\displaystyle\geq\delta(x,x^{\prime})-\delta(y,x)+(\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x))(\gamma-1)$
$\displaystyle\geq\hat{\delta}(C)-\frac{\hat{\delta}(C)+\omega^{\textnormal{H}}(y)(\gamma-1)}{2}+\omega^{\textnormal{H}}(y)(\gamma-1)$
$\displaystyle=\frac{\hat{\delta}(C)+\omega^{\textnormal{H}}(y)(\gamma-1)}{2}$
$\displaystyle>\delta(y,x).$

Again, the statement follows from Theorem 2.5. ∎

######  Remark 2.17.

In analogy with the Hamming distance, one may ask if $\delta(y,x)<\delta(C)/2$
implies $D_{C}(y)=x$, where $D_{C}$ is the maximum likelihood decoder; see
Definition 2.4. This is not true in general. Take e.g. the code
$C=\\{(1,0,0),(0,1,1)\\}$, with $p=0.1$ and $q=0.4$. We have $\delta(C)\approx
4.21$. Consider the vector $y=(0,0,0)$. Then the set of codewords at
discrepancy strictly less then $\delta(C)/2$ from $y$ is $C$, while the only
codeword that minimizes the discrepancy from $y$ is $(1,0,0)$.

######  Remark 2.18.

It is interesting to observe that the condition in Proposition 2.14(1) is
equivalent to $d^{\textnormal{H}}(y,x)<\delta(C)/(\gamma+1)$, which shows a
connection between $\delta$ and the Hamming distance.

##  3\. Unsuccessful Decoding

In this section we establish two upper bounds for the probability that the
maximum likelihood decoder is unsuccessful. The first bound uses the notion of
discrepancy (Definition 2.3), while the second uses the symmetric discrepancy
(Definition 2.8). We show that the two bounds are in general not comparable
with each other, giving evidence that both discrepancy notions are relevant
and independent concepts.

######  Notation 3.1.

We let $\mathcal{S}:=\\{a+\gamma\,b\mid a,b\in\mathbb{N}\\}$ and, for
$h\in\mathbb{N}$, $\mathcal{S}(h):=\\{s\in\mathcal{S}\mid 0\leq s<h\\}$.
Moreover, for $a,b\in\mathbb{R}$ we let

$\binom{a}{b}_{\mathbb{R}}:=\begin{cases}\binom{a}{b}&\textup{if}\;a,b\in\mathbb{N},\\\
\phantom{0}0&\textup{otherwise}.\end{cases}$

We start with the following preliminary result.

######  Lemma 3.2.

Let $x,x^{\prime}\in\mathbb{F}_{2}^{n}$ be vectors of the same Hamming weight.
Let $i\in\\{1,\ldots,n\\}$ and $s\in\mathcal{S}$. We have

$|\\{y\in\mathbb{F}_{2}^{n}\mid\omega^{\textnormal{H}}(y)=i,\,\delta(y,x)=s\\}|\,=\,|\\{y\in\mathbb{F}_{2}^{n}\mid\omega^{\textnormal{H}}(y)=i,\,\delta(y,x^{\prime})=s\\}|.$

Moreover, if $j$ denotes the Hamming weight of $x$, then

$|\\{y\in\mathbb{F}_{2}^{n}\mid\omega^{\textnormal{H}}(y)=i,\,\delta(y,x)=s\\}|=\binom{j}{\frac{i\gamma-s+j}{\gamma+1}}_{\mathbb{R}}\binom{n-j}{\frac{s-j+i}{\gamma+1}}_{\mathbb{R}}.$

###### Proof.

Let $x\in\mathbb{F}_{2}^{n}$ be a vector and let
$j=\omega^{\textnormal{H}}(x)$. It is not difficult to see that the number of
vectors $y\in\mathbb{F}_{2}^{n}$ with $\omega^{\textnormal{H}}(y)=i$ and
$\delta(y,x)=s$ is

$\sum_{\begin{subarray}{c}0\leq a\leq j\\\ 0\leq b\leq n-j\\\ a+b=i\\\
j-a+\gamma b=s\end{subarray}}\binom{j}{a}\binom{n-j}{b}.$

This number does not depend on $x$ but only on $j$. Moreover, the values of
$a$ and $b$ are fully determined by the final constraints in the sum, and so
the formula reduces to the product of binomial coefficients given in the
statement of the lemma. This concludes the proof. ∎

######  Notation 3.3.

In the sequel, for $i,j\in\mathbb{N}$ and $s\in\mathbb{R}$ we denote by
$\lambda(i,j,s)$ the number of vectors $y\in\mathbb{F}_{2}^{n}$ of weight $i$
and with $\delta(y,x)=s$, where $x\in\mathbb{F}_{2}^{n}$ is any vector of
weight $j$. By Lemma 3.2, this quantity $\lambda(i,j,s)$ is well-defined and
given by

$\lambda(i,j,s)=\binom{j}{\frac{i\gamma-s+j}{\gamma+1}}_{\mathbb{R}}\binom{n-j}{\frac{s-j+i}{\gamma+1}}_{\mathbb{R}}.$

Let $C\subseteq\mathbb{F}_{2}^{n}$ be a code, $x\in C$. The probability that
the maximum likelihood decoder $D_{C}$ returns a vector $x^{\prime}\neq x$ or
$\bm{f}$ is

$\sum_{\begin{subarray}{c}y\in\mathbb{F}_{2}^{n}\\\ D_{C}(y)\neq
x\end{subarray}}\mathbb{P}^{n}(y\mid
x){{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0},}}}$

where we recall that $\mathbb{P}^{n}(y\mid x)$ is interpreted as the
probability that $y\in\mathbb{F}_{2}^{n}$ is received, given that $x\in C$ was
sent.

Under the (standard) assumption that all the codewords are transmitted with
the same probability, we define the following concept.

######  Definition 3.4.

The probability of unsuccessful decoding for a code
$C\subseteq\mathbb{F}_{2}^{n}$ is the average

$\textup{PUD}(C)=\frac{1}{|C|}\;\sum_{x\in
C}\sum_{\begin{subarray}{c}y\in\mathbb{F}_{2}^{n}\\\ D_{C}(y)\neq
x\end{subarray}}\mathbb{P}^{n}(y\mid x).$

We will study the PUD associated with a code $C$ in connection with its weight
distribution. The latter is defined as follows.

######  Definition 3.5.

For a code $C\subseteq\mathbb{F}_{2}^{n}$ and an integer
$i\in\\{0,\ldots,n\\}$, we denote by $W^{\textnormal{H}}_{i}(C)$ the number of
codewords $x\in C$ with Hamming weight $\omega^{\textnormal{H}}(x)=i$. The
tuple $(W^{\textnormal{H}}_{0}(C),\ldots,W^{\textnormal{H}}_{n}(C))$ is the
weight distribution of $C$.

We are now ready to establish the main result of this section.

######  Theorem 3.6.

Let $C\subseteq\mathbb{F}_{2}^{n}$ be a code. We have:

  1. (1)

$\displaystyle\textup{PUD}(C)\leq
1-\frac{1}{|C|}\sum_{j=0}^{n}W^{\textnormal{H}}_{j}(C)\sum_{i=0}^{n}(1-q)^{i}(1-p)^{n-i}\sum_{s\in\mathcal{S}\left(\frac{\delta(C)+(\gamma-1)(i-j)}{2}\right)}\left(\frac{q}{1-p}\right)^{s}\lambda(i,j,s)$,

  2. (2)

$\displaystyle\textup{PUD}(C)\leq
1-\frac{1}{|C|}\sum_{j=0}^{n}W^{\textnormal{H}}_{j}(C)\sum_{i=0}^{n}(1-q)^{i}(1-p)^{n-i}\sum_{s\in\mathcal{S}\left(\frac{\hat{\delta}(C)+i(\gamma-1)}{2}\right)}\left(\frac{q}{1-p}\right)^{s}\lambda(i,j,s)$.

###### Proof.

We start by showing the first bound in the statement. By Lemma 1.4 and the
definitions of $\gamma$ and $\delta$ (Notation 2.1 and Definition 2.3
respectively), we have

$\displaystyle\textup{PUD}(C)$ $\displaystyle=1-\frac{1}{|C|}\sum_{x\in
C}\sum_{\begin{subarray}{c}y\in\mathbb{F}_{2}^{n}\\\
D(y)=x\end{subarray}}\mathbb{P}^{n}(y\mid x)$
$\displaystyle=1-\frac{1}{|C|}\sum_{x\in
C}\sum_{\begin{subarray}{c}y\in\mathbb{F}_{2}^{n}\\\
D(y)=x\end{subarray}}\left(\frac{q}{1-p}\right)^{\delta(y,x)}(1-q)^{\omega^{\textnormal{H}}(y)}(1-p)^{n-\omega^{\textnormal{H}}(y)}.$
(5)

Proposition 2.14 implies

$\\{y\in\mathbb{F}_{2}^{n}\;|\;\delta(y,x)<a(y,x)\\}\subseteq\\{y\in\mathbb{F}_{2}^{n}\;|\;D(y)=x\\}\quad\mbox{for
all $x\in C$},$ (6)

where

$a(y,x)=\frac{\delta(C)+(\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x))(\gamma-1)}{2}.$

Combining (5) with (6) we then obtain

$\displaystyle\textup{PUD}(C)$ $\displaystyle\leq 1-\frac{1}{|C|}\sum_{x\in
C}\sum_{\begin{subarray}{c}y\in\mathbb{F}_{2}^{n}\\\
\delta(y,x)<a(y,x)\end{subarray}}\left(\frac{q}{1-p}\right)^{\delta(y,x)}(1-q)^{\omega^{\textnormal{H}}(y)}(1-p)^{n-\omega^{\textnormal{H}}(y)}$
$\displaystyle=1-\frac{1}{|C|}\sum_{j=0}^{n}\sum_{\begin{subarray}{c}x\in C\\\
\omega^{\textnormal{H}}(x)=j\end{subarray}}\sum_{i=0}^{n}\sum_{s\in\mathcal{S}\left(\frac{\delta(C)+(\gamma-1)(i-j)}{2}\right)}\sum_{\begin{subarray}{c}y\in\mathbb{F}_{2}^{n}\\\
\omega^{\textnormal{H}}(y)=i\\\
\delta(y,x)=s\end{subarray}}\left(\frac{q}{1-p}\right)^{s}(1-q)^{i}(1-p)^{n-i}.$

Finally, using Notation 3.3 we conclude that

$\displaystyle\textup{PUD}(C)$ $\displaystyle\leq
1-\frac{1}{|C|}\sum_{j=0}^{n}\sum_{\begin{subarray}{c}x\in C\\\
\omega^{\textnormal{H}}(x)=j\end{subarray}}\sum_{i=0}^{n}\sum_{s\in\mathcal{S}\left(\frac{\delta(C)+(\gamma-1)(i-j)}{2}\right)}\left(\frac{q}{1-p}\right)^{s}(1-q)^{i}(1-p)^{n-i}\lambda(i,j,s)$
$\displaystyle=1-\frac{1}{|C|}\sum_{j=0}^{n}W^{\textnormal{H}}_{j}(C)\sum_{i=0}^{n}\sum_{s\in\mathcal{S}\left(\frac{\delta(C)+(\gamma-1)(i-j)}{2}\right)}\left(\frac{q}{1-p}\right)^{s}(1-q)^{i}(1-p)^{n-i}\lambda(i,j,s),$

which is precisely the first bound in the statement of the theorem. The proof
of the second bound is analogous, using the fact that Proposition 2.14 implies

$\\{y\in\mathbb{F}_{2}^{n}\;|\;\delta(y,x)<b(y,x)\\}\subseteq\\{y\in\mathbb{F}_{2}^{n}\;|\;D(y)=x\\}\quad\mbox{for
all $x\in C$},$ (7)

where

$b(y,x)=\frac{\hat{\delta}(C)+\omega^{\textnormal{H}}(y)(\gamma-1)}{2}.\qed$

######  Example 3.7.

Let $C=\\{(0,1,0,1,1),(1,1,0,0,0),(1,0,1,1,1)\\}$ and $p=0.1$. Figure 2 shows
how the values of the two bounds of Theorem 3.6 change as $q$ ranges between
$0.1$ and $0.49$. Moreover, one can also observe the relation between our
bound and the trivial bound on the PUD stated above.

$0.1$$0.2$$0.3$$0.4$$0.5$$0$$0.2$$0.4$$0.6$$0.8$$1$Values of $q$PUD$(C)$
Figure 2.  The first (blue) and second (orange) bound of Theorem 3.6 for the
code of Example 3.7, $p=0.1$ and some values of $q$. The plots show that the
two bounds are not comparable in general. We also include the exact value of
the PUD (green).

Notice that the two bounds of Theorem 3.6 are not comparable in general, as
the following example shows.

######  Example 3.8.

Take $p=0.1$ and $q=0.3$.

  1. (1)

Let $C=\\{(0,0,1),(0,1,0),(1,1,1)\\}$ and we have $\mbox{PUD}(C)\approx 0.34$.
The first bound in Theorem 3.6 for $\mbox{PUD}(C)$ is $\approx 0.51$, while
the second bound is $\approx 0.36$.

  2. (2)

Let $C=\\{(0,0,0),(0,1,1),(1,1,1)\\}$ and we have $\mbox{PUD}(C)\approx 0.24$.
The first bound in Theorem 3.6 for $\mbox{PUD}(C)$ is $\approx 0.50$, while
the second bound is $\approx 0.74$.

It turns out that the two bounds of Theorem 3.6 are incomparable even when $p$
and $C$ are fixed, and $q$ varies. We illustrate this with the following
examples.

######  Example 3.9.

Let $C=\\{(1,1,1,1),(1,0,0,1),(0,0,0,0)\\}$ and $p=0.1$. Figure 3 shows how
the values of the two bounds of Theorem 3.6 change as $q$ ranges between $0.1$
and $0.49$.

$0.1$$0.2$$0.3$$0.4$$0.5$$0$$0.2$$0.4$$0.6$$0.8$$1$Values of $q$PUD$(C)$
Figure 3.  The first (blue) and second (orange) bound of Theorem 3.6 for the
code of Example 3.9, $p=0.1$ and some values of $q$. The plots show that the
two bounds are not comparable in general. We also include the exact value of
the PUD (green).

##  4\. Bounds

In this section we investigate the cardinality of a code
$C\subseteq\mathbb{F}_{2}^{n}$ as a function of the fundamental parameters
$n$, $\gamma$, and $\delta(C)$ or $\hat{\delta}(C)$. We obtain various bounds
and compare them with each other. We also give examples of codes meeting them.

######  Remark 4.1.

Before presenting our statements and their proofs, we illustrate why several
arguments classically applied to study codes with the Hamming metric do not
extend to the case of our interest (codes endowed with discrepancy functions).
Many of these arguments rely, implicitly or explicitly, on the regularity
properties of certain graphs defined via the Hamming metric. Unfortunately,
the natural analogues of these graphs for discrepancy functions do not exhibit
the same regularity.

Specifically, it is natural to interpret codes with minimum (symmetric)
discrepancy bounded from below as cliques in the graphs
$\mathcal{G}(n,\delta)$ and $\hat{\mathcal{G}}(n,\delta)$ defined as follows.
The vertices of both graphs are the elements of $\mathbb{F}_{2}^{n}$. Vertices
$x$, $y$ are adjacent in $\mathcal{G}(n,\delta)$ if
$\min\\{\delta(y,x),\delta(x,y)\\}\geq\delta$ and $x\neq y$, and are adjacent
in $\hat{\mathcal{G}}(n,\delta)$ if $\hat{\delta}(x,y)\geq\delta$ and $x\neq
y$. When $\gamma=1$, the graph $\mathcal{G}(n,\delta)$ is vertex-transitive, a
property that greatly simplifies the study of code parameters via anticliques;
see in particular [5].

As the next two examples illustrate, the graphs $\mathcal{G}(n,\delta)$ and
$\hat{\mathcal{G}}(n,\delta)$ are in general not vertex-transitive, preventing
the application of the arguments mentioned above.

######  Example 4.2.

  1. (1)

Let $p=0.1$ and $q=0.2$, from which $\gamma\approx 1.38$. A graphical
representation of $\mathcal{G}(4,\gamma+1)$, where the vertex $u$ corresponds
to the unique element $x=(x_{0},x_{1},x_{2},x_{3})$ of $\mathbb{F}_{2}^{4}$
with $x_{0}+2x_{1}+4x_{2}+8x_{3}=u$, can be found in Figure 4. One can check
that $\mathcal{G}(4,\gamma+1)$ is not vertex-transitive (e.g., vertices $0$
and $1$ have different degrees).

  2. (2)

Let $p=0.1$ and $q=0.3$, which gives $\gamma\approx 1.77$. A graphical
representation of $\hat{\mathcal{G}}(3,1)$ can be seen in Figure 5, where the
vertex $u$ corresponds to the unique element $x=(x_{0},x_{1},x_{2})$ of
$\mathbb{F}_{2}^{3}$ with $x_{0}+2x_{1}+4x_{2}=u$. Again,
$\hat{\mathcal{G}}(3,1)$ is not vertex-transitive (again, vertices $0$ and $1$
have different degrees).

1514131211109876543210 Figure 4.  76543210 Figure 5.

First bounds for codes of minimum discrepancy bounded from below can be
obtained from bounds for codes with the Hamming metric. We start by showing
how the functions $\delta$ and $d^{\textnormal{H}}$ relate to each other.

######  Proposition 4.3.

Let $x,y\in\mathbb{F}_{2}^{n}$. The following hold:

  1. (1)

$\hat{\delta}(x,y)\leq d^{\textnormal{H}}(x,y)\leq\delta(x,y)$,

  2. (2)

$\delta(x,y)+\delta(y,x)=(\gamma+1)\,d^{\textnormal{H}}(x,y)$,

  3. (3)

$\min\\{\delta(x,y),\delta(y,x)\\}\leq\frac{\gamma+1}{2}\,d^{\textnormal{H}}(x,y)$.

In particular, for all codes $C\subseteq\mathbb{F}_{2}^{n}$ we have

$\hat{\delta}(C)\leq
d^{\textnormal{H}}(C)\leq\delta(C)\leq\frac{\gamma+1}{2}\,d^{\textnormal{H}}(C).$

###### Proof.

Let $x,y\in\mathbb{F}_{2}^{n}$ and recall that $\gamma\geq 1$ by Lemma 2.2. By
Lemma 2.9(5), we have

$\hat{\delta}(x,y)=d^{\textnormal{H}}(x,y)-(\gamma-1)d_{11}(x,y)\leq
d^{\textnormal{H}}(x,y)$

and, by Lemma 2.9(4), we have

$d^{\textnormal{H}}(x,y)\leq
d^{\textnormal{H}}(x,y)+(\gamma-1)d_{10}(x,y)=\delta(x,y).$

This implies (1). Moreover, by the very definition of $\delta$ we have

$\displaystyle\delta(x,y)+\delta(y,x)$
$\displaystyle=d_{01}(x,y)+\gamma\,d_{10}(x,y)+d_{01}(y,x)+\gamma\,d_{10}(y,x)$
$\displaystyle=d_{01}(x,y)+\gamma\,d_{10}(x,y)+d_{10}(x,y)+\gamma\,d_{01}(x,y)$
$\displaystyle=(\gamma+1)\,(d_{01}(x,y)+d_{10}(x,y))$
$\displaystyle=(\gamma+1)\,d^{\textnormal{H}}(x,y),$

establishing (2). We also have

$2\min\left\\{\delta(x,y),\delta(y,x)\right\\}\leq\delta(x,y)+\delta(y,x)=(\gamma+1)d^{\textnormal{H}}(x,y),$

which shows (3). To prove the last part of the statement, fix a code
$C\subseteq\mathbb{F}_{2}^{n}$. Then (1) implies

$\displaystyle d^{\textnormal{H}}(C)$
$\displaystyle=\min\\{d^{\textnormal{H}}(x,y)\mid x,y\in
C\\}\leq\min\\{\delta(x,y)\mid x,y\in C\\}=\delta(C),$
$\displaystyle\hat{\delta}(C)$ $\displaystyle=\min\\{\hat{\delta}(x,y)\mid
x,y\in C\\}\leq\min\\{d^{\textnormal{H}}(x,y)\mid x,y\in
C\\}=d^{\textnormal{H}}(C).$

Finally, let $x,y\in C$ such that
$d^{\textnormal{H}}(C)=d^{\textnormal{H}}(x,y)$. By (3) we have

$2\,\delta(C)\leq
2\,\min\\{\delta(x,y),\delta(y,x)\\}\leq(\gamma+1)\,d^{\textnormal{H}}(x,y)=(\gamma+1)\,d^{\textnormal{H}}(C),$

which concludes the proof. ∎

######  Remark 4.4.

The inequalities in the last part of Proposition 4.3 are typically not
equalities. Take for example $p=0.1$ and $q=0.4$, from which $\gamma\approx
2.21$. Let $C=\\{(1,1,0,0),(1,0,1,1)\\}\subseteq\mathbb{F}_{2}^{4}$. We have
$\hat{\delta}(C)\approx 1.79$, $d^{\textnormal{H}}(C)=3$, $\delta(C)\approx
4.21$ and $(\gamma+1)d^{\textnormal{H}}(C)/2\approx 4.81$. Therefore all the
inequalities in Proposition 4.3 are strict for this code.

The next result shows how bounds for codes with the Hamming metric translate
into bound for codes endowed with discrepancy functions. In order to state the
bounds in a general and compact form, for $\Delta\in\mathbb{R}$ we let

$\displaystyle\mathcal{A}(n,\Delta)$
$\displaystyle:=\max\\{|C|\,:\,C\subseteq\mathbb{F}_{2}^{n},\,|C|\geq
2,\,\delta(C)\geq\Delta\\},$ $\displaystyle\hat{\mathcal{A}}(n,\Delta)$
$\displaystyle:=\max\\{|C|\,:\,C\subseteq\mathbb{F}_{2}^{n},\,|C|\geq
2,\,\hat{\delta}(C)\geq\Delta\\},$
$\displaystyle\mathcal{A}^{{\textnormal{H}}}(n,\Delta)$
$\displaystyle:=\max\\{|C|\,:\,C\subseteq\mathbb{F}_{2}^{n},\,|C|\geq
2,\,d^{\textnormal{H}}(C)\geq\Delta\\},$

where the maximum of the empty set is taken to be 1 (indicating a zero rate).
The following is an easy consequence of the last part of Proposition 4.3.

######  Proposition 4.5.

For all $\Delta\in\mathbb{R}$ we have

$\hat{\mathcal{A}}(n,\Delta)\leq\mathcal{A}^{\textnormal{H}}(n,\Delta)\leq\mathcal{A}(n,\Delta)\leq\mathcal{A}^{\textnormal{H}}(n,2\Delta/(\gamma+1)).$

######  Remark 4.6.

Again, the inequalities in Proposition 4.5 are typically not equalities. For
example, let $p=0.1$ and $q=0.4$, from which $\gamma\approx 2.21$. For $n=4$
and $\Delta=3$, we have $\hat{\mathcal{A}}(4,3)=1$,
$\mathcal{A}^{\textnormal{H}}(4,3)=2$, $\mathcal{A}(4,3)=6$ and
$\mathcal{A}(4,6/(\gamma+1))=8$. Therefore all the inequalities in Proposition
4.5 are strict in this case.

By combining the previous result with bounds from classical coding theory we
obtain the following results.

######  Corollary 4.7.

Let $C\subseteq\mathbb{F}_{2}^{n}$ be a code. The following hold:

  1. (1)

$\displaystyle|C|\leq
2^{n-\left\lceil\frac{2\delta(C)}{\gamma+1}\right\rceil+1}$,

  2. (2)

$\displaystyle|C|\leq\frac{2^{n}}{\sum_{i=0}^{t}\binom{n}{i}}$, where $t$ is
the largest integer with $t<\delta(C)/(\gamma+1)$,

  3. (3)

$\displaystyle|C|\leq\left\lfloor\frac{2d}{2d-n}\right\rfloor$, where
$d=\lceil 2\delta(C)/(\gamma+1)\rceil$ and under the assumption that $2d>n$.

###### Proof.

The three bounds follow from the fact that $2\delta(C)/(\gamma+1)\leq
d^{\textnormal{H}}(C)$ by Proposition 4.3 and from the Singleton, the Hamming,
and the Plotkin bound (respectively). We refer the reader to [7] for the
statements of these bounds. ∎

It is interesting to observe that there are two classes of codes for which the
parameter $\gamma$ does not play a major role when focusing on bounds. These
are linear codes and constant-weight codes (i.e., codes whose codewords all
have the same Hamming weight), for which the theory fully reduces to Hamming-
metric codes.

######  Proposition 4.8.

Let $C\subseteq\mathbb{F}_{2}^{n}$ be a code. The following hold:

  1. (1)

If $C$ is linear, then $\delta(C)=d^{\textnormal{H}}(C)$,

  2. (2)

If $C$ is constant-weight, then
$\delta(x,y)=\frac{(\gamma+1)}{2}\,d^{\textnormal{H}}(x,y)$ for all $x,y\in
C$. In particular, $\delta(C)=\frac{(\gamma+1)}{2}d^{\textnormal{H}}(C)$.

###### Proof.

Suppose that $C$ is linear. By Proposition 4.3 we have $\delta(C)\geq
d^{\textnormal{H}}(C)$. Thus it remains to show that $\delta(C)\leq
d^{\textnormal{H}}(C)$. Since $C$ is linear, there exists $x\in C$ with
$d^{\textnormal{H}}(C)=\omega^{\textnormal{H}}(x)$. We then have

$d^{\textnormal{H}}(C)=\omega^{\textnormal{H}}(x)=d^{\textnormal{H}}(0,x)=d_{01}(0,x)=\delta(0,x),$

which implies $\delta(C)\leq d^{\textnormal{H}}(C)$, as desired.

Now suppose that $C$ is constant-weight and let $x,y\in C$. One can easily
check that

$d_{01}(x,y)=\omega^{\textnormal{H}}(y)-d_{11}(x,y)=\omega^{\textnormal{H}}(x)-d_{11}(x,y)=d_{10}(x,y).$

Therefore we have

$\displaystyle\delta(x,y)$ $\displaystyle=\gamma
d_{10}(x,y)+d_{01}(x,y)=(\gamma+1)\,d_{01}(x,y),$ $\displaystyle
d^{\textnormal{H}}(x,y)$
$\displaystyle=d_{10}(x,y)+d_{01}(x,y)=2\,d_{01}(x,y),$

which imply $\delta(x,y)=\frac{(\gamma+1)}{2}\,d^{\textnormal{H}}(x,y)$.
Finally, we have

$\displaystyle\delta(C)$ $\displaystyle=\min\\{\delta(x,y)\mid x,y\in
C,\,x\neq y\\}$
$\displaystyle=\min\left\\{\frac{(\gamma+1)}{2}\,d^{\textnormal{H}}(x,y)\mid
x,y\in C,\,x\neq y\right\\}$
$\displaystyle=\frac{(\gamma+1)}{2}\,d^{\textnormal{H}}(C),$

concluding the proof. ∎

In the remainder of the section we use two arguments to relate the cardinality
of a code to its minimum (symmetric) discrepancy. Our bounds involve an
invariant that is finer than the cardinality, namely the weight distribution;
see Definition 3.5.

######  Lemma 4.9.

Let $C\subseteq\mathbb{F}_{2}^{n}$ be a code. For all $x\in C$ define

$\displaystyle S_{1}(x)$
$\displaystyle:=\left\\{y\in\mathbb{F}_{2}^{n}\,:\,\delta(y,x)<\frac{\delta(C)+(\gamma-1)(\omega^{\textnormal{H}}(y)-\omega^{\textnormal{H}}(x))}{2}\right\\},$
$\displaystyle S_{2}(x)$
$\displaystyle:=\left\\{y\in\mathbb{F}_{2}^{n}\,:\,\delta(y,x)<\frac{\hat{\delta}(C)+\omega^{\textnormal{H}}(y)(\gamma-1)}{2}\right\\}.$

Then for all $x,x^{\prime}\in C$ with $x\neq x^{\prime}$ we have $S_{1}(x)\cap
S_{1}(x^{\prime})=\emptyset$ and $S_{2}(x)\cap S_{2}(x^{\prime})=\emptyset$.

###### Proof.

Let $x,x^{\prime}\in C$, with $x\neq x^{\prime}$, and suppose towards a
contradiction that there exists $y\in S_{1}(x)\cap S_{1}(x^{\prime})$.
Proposition 2.14(1) implies that $x=D_{C}(y)=x^{\prime}$, a contradiction. The
proof that $S_{2}(x)\cap S_{2}(x^{\prime})=\emptyset$ is analogous using
Proposition 2.14(2). ∎

The next result provides two bounds relating the weight distribution of a code
with its parameters $\delta(C)$ and $\hat{\delta}(C)$.

######  Theorem 4.10.

Let $C\subseteq\mathbb{F}_{2}^{n}$ be a code. The following holds for all
$i\in\\{0,\ldots,n\\}$:

  1. (1)

$\displaystyle\sum_{j=0}^{n}\sum_{s\in\mathcal{S}\left(\frac{\delta(C)+(\gamma-1)(i-j)}{2}\right)}\lambda(i,j,s)\,W^{\textnormal{H}}_{j}(C)\leq\binom{n}{i}$,

  2. (2)

$\displaystyle\sum_{j=0}^{n}\sum_{s\in\mathcal{S}\left(\frac{\hat{\delta}(C)+(\gamma-1)i}{2}\right)}\lambda(i,j,s)\,W^{\textnormal{H}}_{j}(C)\leq\binom{n}{i}$.

###### Proof.

For $x\in C$ and $i\in\\{0,\ldots,n\\}$ define the sets

$\displaystyle S_{1}(x,i)$
$\displaystyle:=\left\\{y\in\mathbb{F}_{2}^{n}\,:\,\omega^{\textnormal{H}}(y)=i\;\textup{
and
}\;\delta(y,x)<\frac{\delta(C)+(\gamma-1)(i-\omega^{\textnormal{H}}(x))}{2}\right\\},$
$\displaystyle S_{2}(x,i)$
$\displaystyle:=\left\\{y\in\mathbb{F}_{2}^{n}\,:\,\omega^{\textnormal{H}}(y)=i\;\textup{
and }\;\delta(y,x)<\frac{\hat{\delta}(C)+i(\gamma-1)}{2}\right\\}.$

Lemma 4.9 implies that $S_{t}(x,i)\cap S_{t}(x^{\prime},i)=\emptyset$ for any
$t\in\\{1,2\\}$ and all $x,x^{\prime}\in C$ with $x\neq x^{\prime}$. By Lemma
3.2, for all $x\in C$ of Hamming weight $j$ there exist

$\lambda(i,j,s)=\binom{j}{\frac{i\gamma-s+j}{\gamma+1}}_{\mathbb{R}}\binom{n-j}{\frac{s-j+i}{\gamma+1}}_{\mathbb{R}}$

vectors of $\mathbb{F}_{2}^{n}$ of Hamming weight $i$ and such that
$\delta(y,x)=s$. This, along with the fact that the number of vectors of
Hamming weight $i$ in $\mathbb{F}_{2}^{n}$ is $\binom{n}{i}$, implies

$\displaystyle\binom{n}{i}$ $\displaystyle\geq\left|\bigcup_{x\in
C}S_{1}(x,i)\right|=\sum_{x\in
C}|S_{1}(x,i)|=\sum_{j=0}^{n}W^{\textnormal{H}}_{j}(C)\sum_{s\in\mathcal{S}\left(\frac{\delta(C)+(\gamma-1)(i-j)}{2}\right)}\lambda(i,j,s),$
$\displaystyle\binom{n}{i}$ $\displaystyle\geq\left|\bigcup_{x\in
C}S_{2}(x,i)\right|=\sum_{x\in
C}|S_{2}(x,i)|=\sum_{j=0}^{n}W^{\textnormal{H}}_{j}(C)\sum_{s\in\mathcal{S}\left(\frac{\delta(C)+(\gamma-1)i}{2}\right)}\lambda(i,j,s),$

as desired. ∎

Theorem 4.10 gives upper bounds on the cardinality of a code via integer
linear programming. We illustrate this with an example.

######  Example 4.11.

Let $p=0.1$ and $q=0.25$ which imply $\gamma\approx 1.57$. We wish to find the
maximum cardinality of a code $C\subseteq\mathbb{F}_{2}^{5}$ with
$\delta(C)=\gamma+2$. To this end, we solve an integer linear program in order
to maximize $|C|$ under the constraints given by Theorem 4.10(1), for $0\leq
i\leq 5$. For ease of notation, we write $W^{\textnormal{H}}_{j}$ instead of
$W^{\textnormal{H}}_{j}(C)$ for $0\leq j\leq 5$. We want to maximize the sum

$\Sigma=W^{\textnormal{H}}_{0}+W^{\textnormal{H}}_{1}+W^{\textnormal{H}}_{2}+W^{\textnormal{H}}_{3}+W^{\textnormal{H}}_{4}+W^{\textnormal{H}}_{5}$

under the seven constraints:

$\displaystyle
W^{\textnormal{H}}_{0},W^{\textnormal{H}}_{1},W^{\textnormal{H}}_{2},W^{\textnormal{H}}_{3},W^{\textnormal{H}}_{4},W^{\textnormal{H}}_{5}$
$\displaystyle\geq 0,$ $\displaystyle
W^{\textnormal{H}}_{0}+W^{\textnormal{H}}_{1}$ $\displaystyle\leq 1,$
$\displaystyle
5W^{\textnormal{H}}_{0}+W^{\textnormal{H}}_{1}+2W^{\textnormal{H}}_{2}$
$\displaystyle\leq 5,$ $\displaystyle
4W^{\textnormal{H}}_{1}+W^{\textnormal{H}}_{2}+3W^{\textnormal{H}}_{3}$
$\displaystyle\leq 10,$ $\displaystyle
3W^{\textnormal{H}}_{2}+W^{\textnormal{H}}_{3}+4W^{\textnormal{H}}_{4}$
$\displaystyle\leq 10,$ $\displaystyle
2W^{\textnormal{H}}_{3}+W^{\textnormal{H}}_{4}+5W^{\textnormal{H}}_{5}$
$\displaystyle\leq 5,$ $\displaystyle
W^{\textnormal{H}}_{4}+W^{\textnormal{H}}_{5}$ $\displaystyle\leq 1.$

One can check that the maximum value for $\Sigma$ is $4$, achieved for example
by

$\displaystyle W^{\textnormal{H}}_{0}=W^{\textnormal{H}}_{4}$
$\displaystyle=1,$ $\displaystyle
W^{\textnormal{H}}_{1}=W^{\textnormal{H}}_{2}=W^{\textnormal{H}}_{5}$
$\displaystyle=0,$ $\displaystyle W^{\textnormal{H}}_{3}$ $\displaystyle=2.$

The bound is in fact sharp and
$C=\\{(1,0,1,0,1),(0,0,0,1,1),(0,1,1,0,0),(1,1,0,1,0)\\}$ is a code that meets
it with equality.

Our next result is a constraint on the parameters of a code with given
symmetric discrepancy. The proof is inspired by the classical Plotkin bound.

######  Theorem 4.12.

Let $C\subseteq\mathbb{F}_{2}^{n}$ be a code. We have

$|C|\geq\left\lceil\frac{(\gamma+1)T(C)-\hat{\delta}(C)-n(\gamma-1)}{2n-\hat{\delta}(C)}\right\rceil,$

where $T(C)=\sum_{j=1}^{n}jW^{\textnormal{H}}_{j}(C)$.

######  Remark 4.13.

The bound in the previous theorem is trivial when $\gamma=1$ and $C$ is a
linear nondegenerate code. Indeed, if $C$ is such a code, then
$\sum_{j=1}^{n}jW^{\textnormal{H}}_{j}(C)=n2^{k-1}$, where $k$ is the
dimension of $C$. Moreover, $\hat{\delta}(C)=d^{\textnormal{H}}(C)$ and since
$d^{\textnormal{H}}(C)\leq n$ we have

$\left\lceil\frac{n2^{k}-d^{\textnormal{H}}(C)}{2n-d^{\textnormal{H}}(C)}\right\rceil\leq\left\lceil\frac{n2^{k}-d^{\textnormal{H}}(C)}{n}\right\rceil=\left\lceil
2^{k}-\frac{d^{\textnormal{H}}(C)}{n}\right\rceil\leq 2^{k}=|C|.$

###### Proof of Theorem 4.12.

We evaluate in two different ways the sum

$\Sigma:=\sum_{x\in C}\sum_{y\in C}\delta(y,x).$

For ease of notation we denote by $M$ the cardinality of $C$ and write
$\hat{\delta}$, $T$ and $W^{\textnormal{H}}_{j}$ instead of $\hat{\delta}(C)$,
$T(C)$ and $W^{\textnormal{H}}_{j}(C)$ respectively. We have

$\displaystyle\Sigma$ $\displaystyle=\sum_{x\in
C}\sum_{\tiny\begin{matrix}y\in C\\\ y\neq
x\end{matrix}}\left(\delta(y,x)-\omega^{\textnormal{H}}(y)(\gamma-1)\right)+\sum_{x\in
C}\sum_{\tiny\begin{matrix}y\in C\\\ y\neq
x\end{matrix}}\omega^{\textnormal{H}}(y)(\gamma-1)$
$\displaystyle\geq\sum_{x\in C}\sum_{\tiny\begin{matrix}y\in C\\\ y\neq
x\end{matrix}}\hat{\delta}+\sum_{x\in C}\sum_{\tiny\begin{matrix}y\in C\\\
y\neq x\end{matrix}}\omega^{\textnormal{H}}(y)(\gamma-1)$
$\displaystyle=\hat{\delta}\,M(M-1)+(\gamma-1)(M-1)T$
$\displaystyle\geq\hat{\delta}\,\frac{T}{n}(M-1)+(\gamma-1)(M-1)T,$ (8)

where the latter inequality follows from the fact that $nM\geq T$. On the
other hand we have

$\displaystyle\Sigma$ $\displaystyle=\sum_{i=1}^{n}\sum_{x\in C}\sum_{y\in
C}\delta(y_{i},x_{i})$
$\displaystyle=\sum_{i=1}^{n}\sum_{\begin{subarray}{c}x\in C\\\
x_{i}=1\end{subarray}}\sum_{\begin{subarray}{c}y\in C\\\
y_{i}=0\end{subarray}}\delta(0,1)+\sum_{i=1}^{n}\sum_{\begin{subarray}{c}x\in
C\\\ x_{i}=0\end{subarray}}\sum_{\begin{subarray}{c}y\in C\\\
y_{i}=1\end{subarray}}\delta(1,0)$
$\displaystyle=\sum_{i=1}^{n}\sum_{\begin{subarray}{c}x\in C\\\
x_{i}=1\end{subarray}}\sum_{\begin{subarray}{c}y\in C\\\
y_{i}=0\end{subarray}}1+\sum_{i=1}^{n}\sum_{\begin{subarray}{c}x\in C\\\
x_{i}=0\end{subarray}}\sum_{\begin{subarray}{c}y\in C\\\
y_{i}=1\end{subarray}}\gamma.$ (9)

Write $D_{i}(C):=|\\{x\in C\,:\,x_{i}=1\\}|$ for $i\in\\{1,\ldots,n\\}$. Then
(9) becomes

$\Sigma=(1+\gamma)\sum_{i=1}^{n}(M-D_{i}(C))D_{i}(C)=(1+\gamma)\left(M\sum_{i=1}^{n}D_{i}(C)-\sum_{i=1}^{n}D_{i}(C)^{2}\right).$

Observe moreover that

$\sum_{i=1}^{n}D_{i}(C)=|\\{(x,i)\,:\,x\in C,\,1\leq i\leq
n,\,x_{i}=1\\}|=\sum_{x\in C}|\\{i\,:\,1\leq i\leq n,\,x_{i}=1\\}|=T.$

We now apply the Cauchy-Schwarz inequality to the vectors
$(D_{1}(C),\ldots,D_{n}(C))$ and $(1,\ldots,1)$, obtaining

$n\left(\sum_{i=1}^{n}D_{i}(C)^{2}\right)\geq T^{2}.$

We thus have

$\displaystyle\Sigma\leq(1+\gamma)T\left(M-\frac{T}{n}\right).$ (10)

The desired statement now follows by combining (4) with (10), after tedious
computations. ∎

We provide an example of a code that meets the bound of Theorem 4.12 with
equality.

######  Example 4.14.

Let $p=0.1$, $q=0.4$, for which we have $\gamma\approx 2.21$. Consider the
code $C=\\{(1,1,1,1),(1,0,1,1),(1,0,1,0)\\}$. We have $T(C)=9$ and
$\hat{\delta}(C)=-2.63$. Therefore

$\left\lceil\frac{(\gamma+1)T(C)-\hat{\delta}(C)-n(\gamma-1)}{2n-\hat{\delta}(C)}\right\rceil=\left\lceil\frac{3.21\cdot
9+2.63-4\cdot 1.21}{8+2.63}\right\rceil=\left\lceil 2.51\right\rceil=3=|C|.$

In particular $C$ meets the bound of Theorem 4.12 with equality.

##  5\. Conclusions

In this paper, we used two notions of discrepancy between binary vectors to
define new parameters of codes for the binary asymmetric channel. We then
showed how these parameters measure the probability that the maximum
likelihood decoder fails, and related them with more classical code parameters
(such as the minimum Hamming distance). Finally, we derived bounds for the
size of a code in terms of these parameters, giving examples of codes meeting
the bounds with equality.

A natural open question is how to construct families of codes for the binary
asymmetric channel having large cardinality and large minimum discrepancy
simultaneously.

## Acknowledgement

The authors are grateful to the Referees of this paper for their very helpful
suggestions and remarks.

## References

  * [1] S. D. Constantin and T. R. N. Rao, _On the theory of binary asymmetric error correcting codes_ , Information and Control 40 (1979), no. 1, 20–36.
  * [2] T. M. Cover and J. A. Thomas, _Elements of information theory_ , second ed., Wiley, 2006.
  * [3] C. Curto, V. Itskov, K. Morrison, Z. Roth, and J. L. Walker, _Combinatorial neural codes from a mathematical coding theory perspective_ , Neural Computation 25 (2013), no. 7, 1891–1925.
  * [4] C. Curto, V. Itskov, A. Veliz-Cuba, and N. Youngs, _The neural ring: an algebraic tool for analyzing the intrinsic structure of neural codes_ , Bulletin of Mathematical Biology 75 (2013), no. 9, 1571–1611.
  * [5] S. Y. El Rouayheb, C. N. Georghiades, E. Soljanin, and A. Sprintson, _Bounds on codes based on graph theory_ , 2007 IEEE International Symposium on Information Theory, 2007, pp. 1876–1879.
  * [6] M. Firer and J. L. Walker, _Matched metrics and channels_ , IEEE Transactions on Information Theory 62 (2016), no. 3, 1150–1156.
  * [7] Florence Jessie MacWilliams and Neil James Alexander Sloane, _The theory of error correcting codes_ , vol. 16, Elsevier, 1977.
  * [8] J. L. Massey, _Notes on coding theory_ , Cambridge, MA, USA: MIT Press, 1967\.
  * [9] A. Poplawski, _On matched metric and channel problem_ , arXiv:1606.02763 (2016).
  * [10] C. M. Qureshi, _Matched metrics to the binary asymmetric channels_ , IEEE Transactions on Information Theory 65 (2018), no. 2, 1106–1112.
  * [11] C. M. Qureshi, S. I. R. Costa, C. B. Rodrigues, and M. Firer, _On equivalence of binary asymmetric channels regarding the maximum likelihood decoding_ , IEEE Transactions on Information Theory 64 (2018), no. 5, 3528–3537.
  * [12] Gérald Séguin, _On metrics matched to the discrete memoryless channel_ , Journal of the Franklin Institute 309 (1980), no. 3, 179–189.