# Tail-Erasure-Correcting Codes

Boaz Moav, Ryan Gabrys, Eitan Yaakobi B. Moav and E. Yaakobi are with the
Henry and Marilyn Taub Faculty of Computer Science, Technion - Israel
Institute of Technology, Haifa 3200003, Israel (e-mail:
{boazmoav,yaakobi}@cs.technion.ac.il). R. Gabrys is with University of
California, San Diego, California, USA (e-mail: rgabrys@ucsd.edu).The research
was funded by the European Union (ERC, DNAStorage, 865630). Views and opinions
expressed are however those of the authors only and do not necessarily reflect
those of the European Union or the European Research Council Executive Agency.
Neither the European Union nor the granting authority can be held responsible
for them. This work was also supported in part by NSF Grant CCF2212437.

###### Abstract

The increasing demand for data storage has prompted the exploration of new
techniques, with molecular data storage being a promising alternative. In this
work, we develop coding schemes for a new storage paradigm that can be
represented as a collection of two-dimensional arrays. Motivated by error
patterns observed in recent prototype architectures, our study focuses on
correcting erasures in the last few symbols of each row, and also correcting
arbitrary deletions across rows. We present code constructions and explicit
encoders and decoders that are shown to be nearly optimal in many scenarios.
We show that the new coding schemes are capable of effectively mitigating
these errors, making these emerging storage platforms potentially promising
solutions.

###### Index Terms:

Coding theory, DNA data storage, deletions, tail-erasure, RT-metric.

##  I Introduction

The DNA Data Storage market is rapidly growing and is expected to approach $2
billion (USD) in valuation by 2028 [1]. This rapid growth is driven by several
promising technologies that depart form existing storage practices.
Traditional approaches to DNA storage, including the pioneering works of [2,
3], typically represent data using individual base pairs of DNA (i.e., adenine
(A) and thymine (T), cytosine (C) and guanine (G)).

More recently, companies and researchers have moved away from this paradigm,
and in an effort to drive down the cost of synthesis and overcome some of the
practical limitations of reading with traditional DNA sequencers, they have
begun to investigate using collections of DNA molecules, sometimes referred to
as cassettes, in order to encode logical ’0’s and ‘1’s, such as in the Iridia
system [4]. These DNA cassettes are sequentially chained together and stored
within an atomic unit, which is referred to as a nano-memory cell (NMC) within
a larger storage architecture.

In order to accommodate these new storage paradigms while also keeping the
broader (traditional) storage technology stack intact, these memory cells are
logically organized into larger collections of cells analogous to sectors in a
hard drive. This organization is beneficial in several ways. First, it allows
one to parallelize the read/write process enabling faster access times. In
addition, this logical organization of NMCs can leverage addressing schemes
that are typically employed in the context of traditional magnetic media
storage thus reducing the potential cost or impact for transition.

Such systems can be modeled as collections of two dimensional binary arrays,
which are referred to as a DNA storage arrays, whereby each row of the array
represents a particular NMC and the sequence of bits in the row represents the
logical information contained within that NMC. An illustration of such a
system architecture is being shown in Figure 1 where each cell consists of an
individual strand of DNA and this data can be partitioned into information
pertaining to the address of the NMC, the data itself, and additional data
such as ECC.

Figure 1: Illustration of a collection of Iridia’s NMC [4, Fig. 72]

One of the key challenges, and one which is essential to making emerging DNA
storage architectures practically viable, is constructing error correcting
coding schemes. The design of such schemes not only further increases the
already exceptional durability of DNA storage, but it also enables greater
speeds and flexibility when it comes to reading information back from the
underlying data storage medium. In this way, the problem of reading
information from a DNA storage system is no longer equivalent to the
challenges faced by existing biological DNA sequencers today which is to
determine (exactly) the underlying sequence of nucleotides that comprises a
given strand of DNA.

Designing error correcting coding schemes for DNA data storage systems is
fundamentally different than the design of coding schemes for traditional
storage media [5]. Traditional storage typically experiences errors in the
form of substitutions whereas data stored within DNA can experience insertion,
deletion, and substitution errors. Insertions can be the result of the
improper blocking of some bits whereas deletions can be caused by a failure of
the bit addition chemistry. On top of this, cells within the DNA storage array
can be lost either partially, which occurs when a defective bit prematurely
terminates the chain, or the data within a cell can be corrupted completely.
Initial experiments have reported error rates as high as 10% [6].

Despite these high numbers, we are unaware of any existing works that attempt
to construct coding schemes for systems that can be modeled as DNA storage
arrays, and this work represents the first effort towards the development of
such a system.

Although the observed error rates are high, there appear to be certain
commonly occurring error patterns, which may be useful in the design of future
coding schemes. In particular, when a large number of errors occur, often only
the tail end of the strand is affected. For shorthand, we say that an _$e$
-tail-erasure_ (TE for short) has occurred if we are unable to recover the
last $e$ symbols of the strand stored in the cell.

In the realm of error correction, we envision coding schemes that provide two
levels of protection. The first level of protection corrects errors that may
occur within each NMC, including insertions, deletions, and substitutions in
DNA strands whereas the second level addresses more severe corruption. We
propose a new class of codes, which we refer to as _tail erasure codes_ (_TE
codes_ for short), for the second level of our envisioned two-level scheme.

The $e$-tail-erasure model that we study in this paper has also applications
to the _slow-fading channel_ as suggested in [7] and the _reliable-to-
unreliable channel_ as described in [8]. According to the reliable-to-
unreliable channel model, data is transmitted over $n$ channels in a
distributed way, and each channel switches from reliable transmission into an
unreliable one. This switch happens during the transmission, and the position
where it occurs may be different in every channel. The rest of the
transmission, since the moment where it became unreliable and until the end,
is considered as an erasure. Therefore, each of these channels can be modeled
as a row in a two dimensional array, where the last $e$ bits of each row are
considered as erasures since the channel became unreliable, and this results
in a TE.

In this work, we initiate the study of TE codes. Our main result, which
appears in Section III, is the development of novel error-correcting codes
that we show in many cases are nearly optimal. We also consider a
generalization of our problem to account for the setup where both deletions
and TEs may occur and derive codes and bounds for this setup as well.

This paper is organized as follows. In Section II we formally introduce our
problem statement and discuss related work. In Section III we present a
general construction for TE codes. Sections IV and V extend our problem to
include the scenario where in addition to TEs, deletions are allowed to occur.
In Section VI, bounds are derived for both TE codes and codes capable of
correcting TEs and deletions. Finally, Section VII concludes the paper.

##  II Notations, Definitions, Problems Statement, and Related Work

Throughout this paper, let $\mathbb{F}_{2}$ be the field of size two, denote
$[n]=\\{1,\dots,n\\}$ and additionally let $\mathbb{Z}_{\geq
0}=\\{m\in\mathbb{Z}\colon m\geq 0\\}$. Also, for any vector
$\bm{x}=(x_{1},\dots,x_{n})$, denote the subsequence of a vector $\bm{x}$, as
$\bm{x}_{[i\colon j]}=(x_{i},\dots,x_{j})$. Moreover, denote a binary array as
$\bm{X}=(\bm{x}_{1},\dots,\bm{x}_{n})\in{\mathbb{F}_{2}}^{n\times L}$, where
$\\{\bm{x}_{i}\\}_{i=1}^{n}$ are binary row vectors of length $L$, which means
$\bm{x}_{i}=(x_{i,1},\dots,x_{i,{L}})\in\mathbb{F}_{2}^{L}$ for any $i\in[n]$.
Finally, for $\bm{x}=(x_{1},\dots,x_{n})\in\mathbb{F}_{2}^{n}$, let
$\|\bm{x}\|_{1}=\sum_{i=1}^{n}|x_{i}|$, and
$\|\bm{x}\|_{\infty}=\max\\{|x_{1}|,\ldots,|x_{n}|\\}$. Next, we lay the goals
of this paper and the error models we study.

###  II-A Definitions of the Error Models

If it is not possible to recover the last bits from a row in the array, it is
said that a _tail-erasure_ has occurred in this row. In this case, the row
vector $\bm{x}_{i}\in\mathbb{F}_{2}^{L},\leavevmode\nobreak\ i\in[n]$, suffers
from an _$e$ -row-tail-erasure_ if the bits $\\{x_{i,L-e+1},\dots,x_{i,L}\\}$
are all erased. This definition is generalized as follows.

######  Definition 1.

Let $\bm{X}\in\mathbb{F}_{2}^{n\times L}$. It is said that $\bm{X}$ suffers
from an _$e$ -tail-erasure_, for a positive integer $e$, if there exists a
positive integer $t\leq n$, positive integers $e_{1},\dots,e_{t}$, such that
$e_{1}+\dots+e_{t}=e$, and $t$ distinct row indices
$i_{1},i_{2},\ldots,i_{t}$, such that for $j\in[t]$, the $i_{j}$-th row in
$\bm{X}$ suffers an $e_{j}$-row-tail-erasure.

For shorthand, this paper will refer to an $e$-tail-erasure simply as an _$e$
-TE_. A code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n\times L}$ capable of
correcting an $e$-tail-erasure is referred as an _$e$ -TE code_, or a _TE
code_ when $e$ is not specified.

Subsequently, our model yields a definition to a distance function, which
corresponds with the definition of the _$m$ -metric_, as presented first in
[9] and then further studied by [10, 11, 12].

Most of these papers focus on fields of large cardinality, and when reduced to
the binary field, their constructions work for a very small number of rows,
$n$. In our paper we study specifically binary codes for arbitrary $n$, and
present a new construction method, based on parity check matrices designed for
this metric. This yields a new family of explicit codes, which in many cases
is also better than the previous constructions in terms of the number of
redundancy bits. This will be discussed more in detail in Sections II-B, and
III. The first goal of the paper is as follows.

######  Problem 1.

Construct optimal TE codes.

The results for this problem are presented in Sections III and VI-A and are
summarized in Table I. Next, it is said that an array
$\bm{X}\in\mathbb{F}_{2}^{n\times L}$ suffers from a _$(t,s)$ -deletion_ if at
most $t\leq n$ rows suffer at most $s\leq L$ arbitrary deletions each. A code
that can correct any $(t,s)$-deletion is referred to as a _$(t,s)$ -DC_ or a
_DC code_ for short when $t,s$ are unspecified. The second goal of this paper
is summarized in the next problem.

######  Problem 2.

Construct optimal DC codes.

The results for this problem are presented in Sections IV and VI-B. Finally,
this paper studies the combined model of TEs and deletions. More specifically,
a _$(t,s,e)$ -tail-erasure-deletion_, abbreviated as a _$(t,s,e)$ -TED_, is a
combination of an $e$-TE and a $(t,s)$-deletion.

It can be shown that the order of occurrence between the TEs and deletions in
each row does not matter, and thus for simplicity it is assumed that first the
$e$-TE has occurred, which is then followed by the $(t,s)$-deletion. However,
it is worth mentioning that since the output of this channel is just an array
with some truncated rows, we cannot distinguish between the scenarios where a
TE occurs in a row or a deletion based on its length alone. A code that can
correct any $(t,s,e)$-TED is a _$(t,s,e)$ -TED code_, or a _TED code_ when
$t,s,e$ are unspecified. The third goal of the paper is described next.

######  Problem 3.

Construct optimal TED codes.

The results for this problem are presented in Sections V and VI-C.

###  II-B Related Work

Several previous works have proposed models and coding schemes for the
emerging DNA storage system. In [13], the authors modeled the DNA storage
system as an ordered set of sequences of a certain length where each sequence
can experience insertions, deletions, and substitutions. Other works such as
[14] and [15] considered the problem of developing constrained codes that
result in input sequences that are less likely to experience errors that may
result from the DNA storage channel. Recently, [16] developed codes for DNA
storage that protect against errors but are also amenable to a broad class of
coding constraints.

The motivation for our work stems from its connection to storage systems that
fall under the DNA storage array where DNA molecules are stored within nano-
memory cells such as [4] rather than as an unordered multiset. Under this
setting, when a particular cell is severely corrupted the errors manifest
themselves as erasures that occur typically at the very end of the strand. As
discussed in Section I, one can model each cell as a row of a binary array,
and therefore the entire system can be modeled as an $n\times L$ binary array,
where $n$ is the number of cells, and $L$ is the length of the data in the
strand that is saved in each cell. Moreover, since the cells are ordered by
hardware design, there is no need to reserve bits to index the strands as in
other DNA systems.

This model, where it is assumed that the indices are given, can also be
applied to another common model of DNA storage systems, where all the
information strands are stored in one container, which results a loss of
ordering. Therefore, in this unordered information model, one usually
dedicates part of the information for storing indices, as was suggested by
[17] and studied by [18, 19, 20] and more.

Since it can either be assumed that the indices are error-free, or that there
is a dedicated ECC for the indices, it can be verified easily that the final
resulted read of the strands in the unordered model, after ordering and
removing the indices, is a binary array as in our model.

The work on TE codes is strongly related to many works on codes over either
the so-called $m$-metric (also called the _RT-metric_ in other papers), where
$m$ corresponds to the number of rows in the array, which was introduced first
in [9]. The $m$-metric is found to be useful in the case of evaluating codes
that correct erasures in arrays, which occur at the end of each column.
Therefore, it is easy to verify, using array transposition, that TE codes are
equivalent to codes in the $m$-metric. Another relevant metric is the so-
called _$\rho$ -metric_, that was first studied in [10], where the metric
corresponds to erasures that occur at the beginning of each row. Moreover, in
Section III-A, we define our _$\rho_{\text{TE}}$ -metric_ for evaluating TE
codes. However, as will be discussed in this section, the $m$-metric, the
$\rho$-metric and the $\rho_{\text{TE}}$-metric are all equivalent in terms of
metric spaces isomorphism. Lastly, we note that we prefer to define our new
metric although it is equivalent to the previous one, since it better fits the
error patterns studied in our paper, and will make the reading easier.

Next will be a discussion regarding the current state of the art results under
the mentioned metrics. In [11, 10] the case of erasures at the beginning of
the row was considered, and in [9, 12, 8] it was at the end of the columns.
Moreover, in [9, 10, 12, 11] mostly the case of large fields was considered,
and several bounds were found, as will be described in Section VI-A. Also, two
results of [11] for $q=2$ can be applied to Problem 1, but the problem they
solved is more strict, in terms of linearity. Their model treats every row as
a symbol in $\mathbb{F}_{q^{L}}$ and requires linearity of the length-$n$
codewords over $\mathbb{F}_{q^{L}}$. Therefore, under our model, our
construction is less restrictive, since linearity demands are only over
$\mathbb{F}_{q}$. Lastly, in [8] a BCH code for the RT-metric is presented,
and therefore a construction for a binary TE code can be derived where the
length of each row is a power of two. However, their construction has concrete
results only for TE codes of size $3\times 4$, and for the general case there
is no explicit lower bound on the cardinality of such codes. Therefore, one
cannot derive a proper comparison between their results and the results in our
paper.

Another related area of research involves the design of Universally Decodable
Matrices (UDM), which is originated from the slow-fading channel problem, such
as in [7, 11]. Specifically, in [11] a construction is given for the case
where the rows are seen as a symbol over $\mathbb{F}_{q^{L}}$ and $q>n$, which
does not generalize into the binary array model in this paper. Moreover, it is
proved in [7, Theorem 4] that a necessary condition for the existence of
$\\{A_{i}\\}_{i=0}^{n-1}$ UDM over $\mathbb{F}_{q}$ is that $q>n$, and
therefore any construction based strictly on UDM, cannot be used in the binary
case.

We note that our problem bears resemblance to the problem of coding for
segmented edit channels [21], [22]. However, unlike the segmented edit model,
we assume that the location of the tail-erasure is also known. Nevertheless,
we also face the model of $(t,s)$-deletions, that can be seen as a segmented
edit channel, where at most $t$ segments are erroneous and the separation to
segements is given.

Our problem is also reminiscent of constructing unequal error protection (UEP)
codes [23], [24], [25]. UEP codes are codes with the property that some
information bits are more protected against a greater number of errors than
other information symbols. Under the UEP model, each coordinate, say $i$, in a
codeword is pre-assigned a protection which is referred to as $f_{i}$. Under
this setting, if $f$ errors occur in the underlying codeword, then we can
determine the value of any coordinate $j$ in the original codeword if
$f_{j}\geq f$ regardless of whether the original codeword can be determined.
As will be discussed in the next section, the distance metric of interest for
constructing TE codes is fundamentally different in the sense that our schemes
aim to recover the entire codeword under the setting where the locations of
the errors are non-independent and satisfy certain spatial properties in the
underlying arrays.

##  III Tail-Erasure Codes

In this section, constructions of TE codes, and also linear TE codes, are
presented. The main result of the section is in Section III-C, where a
construction of a linear $e$-TE code when $e\leq L$ is presented. Moreover,
several results for the case where $e>L$ can be found in Section III-D.

###  III-A The TE Distance

The focus of this subsection is introducing a suitable distance function for
TE codes, while also providing a definition of a TE pattern. We begin with the
definition of the $\rho_{\text{TE}}$ distance, as follows.

######  Definition 2.

Let $\bm{X}=(\bm{x}_{1},\dots,\bm{x}_{n})$ and
$\bm{Y}=(\bm{y}_{1},\dots,\bm{y}_{n})$ be arrays in $\mathbb{F}_{q}^{n\times
L}$. Then, for every $j\in[n]$,

$\displaystyle\rho_{\text{TE}}(\bm{x}_{j},\bm{y}_{j})=\begin{cases}L\\!-\\!\min\\{i\colon
x_{j,i}\neq y_{j,i}\\}+1&\text{ if }\bm{x}_{j}\neq\bm{y}_{j}\\\ 0&\text{ if
}\bm{x}_{j}=\bm{y}_{j}\end{cases}\leavevmode\nobreak\ .$

And,

$\displaystyle\rho_{\text{TE}}(\bm{X},\bm{Y})=\sum_{j=1}^{n}\rho_{\text{TE}}(\bm{x}_{j},\bm{y}_{j})\leavevmode\nobreak\
.$

This distance function is closely related to the $\rho$-metric, which was
introduced in [10], while noting that the difference between the definitions
is that $\rho(\bm{x}_{j},\bm{y}_{j})=\max\\{i\colon x_{j,i}\neq y_{j,i}\\}$ if
$\bm{x}_{j}\neq\bm{y}_{j}$, and one can easily find the isomorphism between
these two distance definitions, by reversing the order of each row. Thus,
Moreover,, we also immediately deduce that the $\rho_{\text{TE}}$-distance is
a metric and from now on we will refer to it as the $\rho_{\text{TE}}$-metric
or the TE-metric. The relation to the RT-metric is by transposing the array,
and therefore, in terms of code parameters, all of the above mentioned metrics
give equivalent codes and a comparison between the codes that are derived in
each metric will be given at the end of Section III-C.

Next, a mathematical definition of a _TE pattern_ is given. This definition
resembles with the ones in [7, 11], but is more suitable for the notations of
this paper.

######  Definition 3.

For $e,L,n$, the _TE-pattern set_ is defined to be

$P(e,L,n)=\left\\{\bm{p}\in\mathbb{Z}_{\geq 0}^{n}\colon\|\bm{p}\|_{1}\leq
e,\|\bm{p}\|_{\infty}\leq L\right\\}\leavevmode\nobreak\ .$

In other words, $P(e,L,n)$ is the set of all length-$n$ vectors $\bm{p}$,
which are called TE patterns, where the sum of entries in $\bm{p}$ is at most
$e$ and the value of each entry in $\bm{p}$ is at most $L$. A pattern
$\bm{p}\in P(e,L,n)$ will be used next as an indicator, such that the $i$-th
entry in $\bm{p}$ represents the number of erased bits in the $i$-th row of
the array. Following this, the concept of a $\bm{p}$-pattern-TE is introduced.

######  Definition 4.

Let $\bm{X}\in\mathbb{F}_{2}^{n\times L}$ and $\bm{p}\in P(e,L,n)$. Then, the
_$\bm{p}$ -pattern-TE_ of $\bm{X}$, denoted by
$\bm{X}^{(\bm{p})}\in(\mathbb{F}_{2}\cup\\{?\\})^{n\times L}$, is defined as
follows:

$\displaystyle x^{(\bm{p})}_{i,j}=\begin{cases}?&\text{if }p_{i}>0\text{ and
}j\geq L-p_{i}+1\\\ x_{i,j}&\text{else.}\end{cases}\leavevmode\nobreak\ .$

Loosely speaking, $\bm{X}^{(\bm{p})}$ represents the array that is obtained by
replacing the last $p_{i}$ symbols in the $i$-th row of $\bm{X}$ with the
erasure symbol ”$?$”. An example is given next.

######  Example 1.

Let $\bm{X}=\begin{bmatrix}1&0&1\\\ 0&0&1\end{bmatrix}\leavevmode\nobreak\
,\quad\bm{p}=(2,1)$. Then,

$\bm{X}^{(\bm{p})}=\begin{bmatrix}1&?&?\\\
0&0&?\end{bmatrix}\leavevmode\nobreak\ ,$

is a $\bm{p}$-pattern-TE of $\bm{X}$.

Next, we provide a claim that connects Definitions 3 and 4 to the
$\rho_{\text{TE}}$-metric definition.

######  Claim 1.

Let $\bm{X},\bm{Y}\in\mathbb{F}_{2}^{n\times L}$. Then,

$\rho_{\text{TE}}(\bm{X},\bm{Y})=\min_{\bm{p}\in
P(nL,L,n)}\left\\{\|\bm{p}\|_{1}\colon\bm{X}^{(\bm{p})}=\bm{Y}^{(\bm{p})}\right\\}.$

###### Proof:

By definition, for every row $j\in[n]$, the distance
$\rho_{\text{TE}}(\bm{x}_{j},\bm{y}_{j})$ is exactly the minimal number of
erasures required in the end of both $\bm{x}_{j}$ and $\bm{y}_{j}$ so they
appear the same. In other words, this is the value of $p_{j}$ for some vector
$\bm{p}=(p_{1},\dots,p_{n})$, such that
$(\bm{X}^{(\bm{p})})_{j}=(\bm{Y}^{(\bm{p})})_{j}$. Thus, a vector $\bm{p}$
that obtains the minimum $\|\bm{p}\|_{1}$, for which
$\bm{X}^{(\bm{p})}=\bm{Y}^{(\bm{p})}$ as in the left hand side, is constructed
in a way such that every entry $p_{j}$, represents also the minimal number of
erasures required in the end of both $\bm{x}_{j}$ and $\bm{y}_{j}$, such that
$(\bm{X}^{(\bm{p})})_{j}=(\bm{Y}^{(\bm{p})})_{j}$, or otherwise it results a
contradiction to the minimality, since one can choose a smaller value for the
$j$-th entry of $\bm{p}$. Therefore, for the above minimal $\bm{p}$ it holds
that

$\|\bm{p}\|_{1}=\sum_{i=1}^{n}p_{i}=\sum_{j=1}^{n}\rho_{\text{TE}}(\bm{x}_{j},\bm{y}_{j})=\rho_{\text{TE}}(\bm{X},\bm{Y})\leavevmode\nobreak\
,$

which completes the proof.

∎

A short example of computing the $\rho_{\text{TE}}$-metric by using a TE
pattern is given next.

######  Example 2.

Let $\bm{X},\bm{Y}\in\mathbb{F}_{2}^{2\times 3}$ be defined as follows,
$\bm{X}=\begin{bmatrix}1&0&1\\\ 0&0&1\end{bmatrix},\leavevmode\nobreak\
\bm{Y}=\begin{bmatrix}1&0&0\\\ 0&1&1\end{bmatrix}.$ It can be readily verified
that $\rho_{\text{TE}}(\bm{X},\bm{Y})=3$ using $\bm{p}=(1,2)$, or using
Definition 2.

Compared to the Hamming distance, note that under this model, erasures do not
independently contribute to the $\rho_{\text{TE}}$-distance between two
codewords. For example, consider the case where $\bm{X}$ is as in Example 2.
Then, the vectors

${\mathbf{Y}}=\begin{bmatrix}1&\bm{1}&\bm{0}\\\
0&0&\bm{0}\end{bmatrix},\quad{\mathbf{Z}}=\begin{bmatrix}1&\bm{1}&1\\\
0&0&\bm{0}\end{bmatrix}\leavevmode\nobreak\ ,$

are each at the same TE distance (of three) to ${\mathbf{X}}$ despite the fact
that the set of coordinates in which ${\mathbf{X}}$ and ${\mathbf{Z}}$ differ
is a subset of the set of coordinates where ${\mathbf{X}}$ and ${\mathbf{Y}}$
do not agree.

Finally, a definition of a minimum distance of a code under the
$\rho_{\text{TE}}$ distance follows.

######  Definition 5.

Let $\mathcal{C}\subseteq\mathbb{F}_{2}^{n\times L}$ be a TE code. Then, the
_minimum $\rho_{\text{TE}}$-distance of $\mathcal{C}$_ is defined as follows

$\rho_{\text{TE}}(\mathcal{C})=\min_{\bm{X},\bm{Y}\in\mathcal{C}\colon\bm{X}\neq\bm{Y}}\rho_{\text{TE}}(\bm{X},\bm{Y})\leavevmode\nobreak\
.$

Next, denote by $(n\times L,M,e+1)_{\text{TE}}$ a code of cardinality $M$, and
minimum $\rho_{\text{TE}}$-distance of $e+1$ over binary arrays of length
$n\times L$. Then, a basic theorem regarding the minimum
$\rho_{\text{TE}}$-distance of a code is given. This theorem illustrates one
of the similarities between the properties of classical codes under the
Hamming metric, and the TE codes in our paper, as we show that an $(n\times
L,M,e+1)_{\text{TE}}$ code can correct $e$ erasures.

######  Theorem 1.

A code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n\times L}$ is an $e$-TE-
correcting code if and only if $\rho_{\text{TE}}(\mathcal{C})\geq e+1$.

###### Proof:

Let $\bm{X}\in\mathcal{C}$. If $\mathcal{C}$ is an $e$-TE code, it means that
there is no other $\bm{Y}\in\mathcal{C}$ such that
$\bm{X}^{(\bm{p})}=\bm{Y}^{(\bm{p})}$ for any $\bm{p}\in P(e,L,n)$, where
$\|\bm{p}\|_{1}=t$, and $t\leq e$. Assume, for the sake of contradiction, that
such $\bm{p}$ exists. It means that if $\bm{X}$ suffers from a TE pattern
$\bm{p}$ where $\|\bm{p}\|_{1}=t$, and $t\leq e$, it cannot be distinguished
from $\bm{Y}$ that suffers from the same TE pattern $\bm{p}$. Therefore, this
TE cannot be corrected, which yields a contradiction to $\mathcal{C}$ being a
$e$-TE code. So, conclude that $\rho_{\text{TE}}(\mathcal{C})>e$. Conversely,
if $\rho_{\text{TE}}(\mathcal{C})\geq e+1$, let $\bm{X}\in\mathcal{C}$ and
assume an $e$-TE occurred in $\bm{X}$, and we want to show that the code can
correct it. Assume, for the sake of contradiction, that there exists a
$\bm{Y}\in\mathcal{C}$ and $\bm{p}\in P(e,n,L)$ such that
$\bm{X}^{(\bm{p})}=\bm{Y}^{(\bm{p})}$ and $\|\bm{p}\|_{1}\leq e$, and
therefore the code cannot correct this $e$-TE, since it cannot distinguish
between $\bm{X}$ and $\bm{Y}$. But then $\rho_{\text{TE}}(\bm{X},\bm{Y})\leq
e$ and this contradicts the minimum $\rho_{\text{TE}}$-distance of the code.
We conclude that after at most $e$-TE occurred, $\bm{X}$ is the only codeword
that could be the result of those $e$-TEs, and conclude that $\mathcal{C}$ can
correct up to $e$-TEs.

∎

###  III-B Tail-Erasure Linear Codes

Next, linear TE codes are constructed. First, the notation of a parity check
matrix for linear codes over arrays under under the
$\rho_{\text{TE}}$-distance is presented.

######  Definition 6.

Let $\mathcal{C}\subseteq\mathbb{F}_{2}^{n\times L}$ be a linear code. A _TE
parity check matrix_ of $\mathcal{C}$ is a three-dimensional array
$\bm{\mathcal{H}}\in\mathbb{F}_{2}^{r\times n\times L}$,

$\bm{\mathcal{H}}=\begin{bmatrix}\bm{h}_{1,1}&\dots&\bm{h}_{1,L}\\\
\vdots&\ddots&\vdots\\\
\bm{h}_{n,1}&\dots&\bm{h}_{n,L}\end{bmatrix}\leavevmode\nobreak\
,\bm{h}_{i,j}\in\mathbb{F}_{2}^{r}\leavevmode\nobreak\ ,$

where it holds that

$\bm{X}=\left(x_{i,j}\right)_{i\in[n],j\in[L]}\in\mathcal{C}\iff\sum_{i=1}^{n}\sum_{j=1}^{L}x_{i,j}\bm{h}_{i,j}=\bm{0}.$

Note that the matrix $\bm{\mathcal{H}}$ can be interpreted as $r$ layers of
matrices, $\\{H_{\ell}\\}_{\ell=1}^{r}$, of size $n\times L$. Then,

$\dim(\mathcal{C})=nL-\text{rank}(\bm{\mathcal{H}})=nL-\dim\left(\\{H_{\ell}\\}_{\ell=1}^{r}\right)\leavevmode\nobreak\
,$

and refer to a linear TE code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n\times
L}$, as an $[n\times L,k,d]_{\text{TE}}$ code, where $k=\dim(\mathcal{C})$ and
$d=\rho_{\text{TE}}(\mathcal{C})$. Next, an expression of
$\rho_{\text{TE}}(\mathcal{C})$ for linear codes will be developed, using
several preliminary definitions. First, let

$\mathcal{J}(\bm{\mathcal{H}},\bm{p})=\left\\{\left\\{\bm{h}_{i,j}\in\mathbb{F}_{2}^{r}\colon
p_{i}>0,\text{ and }j\geq L-p_{i}+1\right\\}\right\\}\leavevmode\nobreak\ ,$

where $\bm{p}\in P(e,L,n)$. This multiset of columns represents the columns of
$\bm{\mathcal{H}}$ which are located in the matching entries of the erasure
pattern $\bm{p}$. The reason for choosing the multiset over a set, is the fact
that there could be a repetition of columns in $\bm{\mathcal{H}}$, and it
clearly affects the linear dependency of the multiset.

######  Example 3.

Let $H=[\bm{h}_{1},\dots,\bm{h}_{7}]$ be a parity check matrix of the
$[7,4,3]$ Hamming code. Let

$\displaystyle\bm{\mathcal{H}}=$
$\displaystyle\begin{bmatrix}\bm{h}_{2}&\bm{h}_{1}\\\ \bm{h}_{3}&\bm{h}_{2}\\\
\bm{h}_{4}&\bm{h}_{3}\\\ \bm{h}_{5}&\bm{h}_{4}\\\ \bm{h}_{6}&\bm{h}_{5}\\\
\bm{h}_{7}&\bm{h}_{6}\\\
\bm{h}_{1}&\bm{h}_{7}\end{bmatrix}\in\mathbb{F}_{2}^{3\times 7\times
2},\leavevmode\nobreak\ \bm{p}=\begin{pmatrix}1\\\ 0\\\ 0\\\ 0\\\ 0\\\ 0\\\
2\end{pmatrix}.$

Then,
$\mathcal{J}(\bm{\mathcal{H}},\bm{p})=\\{\\{\bm{h}_{1},\bm{h}_{1},\bm{h}_{7}\\}\\}$.
Notice that there are repetitions of columns and therefore this multiset is
linearly dependent. This is one of the cases where a TE pattern cannot be
corrected, and this observation will be generalized in Claim 2.

In addition to the above, define the _TE-weight_ of $\bm{X}$ as
$w_{\text{TE}}(\bm{X})\\!=\\!\rho_{\text{TE}}(\bm{X},\bm{0})$. It is possible
to show that
$\rho_{\text{TE}}(\bm{X},\bm{Y})\\!=\\!\rho_{\text{TE}}(\bm{X}\\!-\bm{Z}\\!,\bm{Y}\\!-\bm{Z})$
for any $\bm{Z}$. Then, if $\bm{Z}\\!=\\!\bm{Y}$,
$\rho_{\text{TE}}(\bm{X}\\!,\bm{Y})\\!=\\!w_{\text{TE}}(\bm{X}\\!-\\!\bm{Y})$.
In [8] they indicated another similarity between the Hamming distance and the
$\rho_{\text{TE}}$-distance, which is,

$d=\min_{\bm{X}\in\mathcal{C}\setminus\\{\bm{0}\\}}w_{\text{TE}}(\bm{X})\leavevmode\nobreak\
.$

Lastly, a connection between the TE parity check matrix and the minimum
$\rho_{\text{TE}}$-distance of its code is presented.

######  Claim 2.

Let $\bm{\mathcal{H}}$ be a TE parity check matrix of a code
$\mathcal{C}\subseteq\mathbb{F}_{2}^{n\times L}$. Then,
$\rho_{\text{TE}}(\mathcal{C})$ is the largest integer $d$, such that for any
$\bm{p}\in P(d-1,L,n)$, the vectors in $\mathcal{J}(\bm{\mathcal{H}},\bm{p})$
are linearly independent.

###### Proof:

Let $\bm{X}\in\mathcal{C}$ with TE weight of $t>0$. This implies the existence
of $\bm{p}\in P(t,e,n),\|\bm{p}\|_{1}=t$ such that
$\mathcal{J}(\bm{\mathcal{H}},\bm{p})$ is of cardinality $t$, and denote the
column indices in $\mathcal{J}(\bm{\mathcal{H}},\bm{p})$ as $J$. From the
definition of TE weight, any $(i,j)\notin J$ implies $x_{i,j}=0$ and since
$\bm{X}$ is a codeword,

$\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{e}\bm{h}_{i,j}x_{i,j}=\sum_{(i,j)\in
J}\bm{h}_{i,j}x_{i,j}=\bm{0}\leavevmode\nobreak\ ,$

which implies $\mathcal{J}(\bm{\mathcal{H}},\bm{p})$ is a linearly dependent
multiset by definition. Conversely, let
$\mathcal{J}^{\prime}(\bm{\mathcal{H}},\bm{p}^{\prime})$ be a multiset of
$t^{\prime}$ linearly dependent columns of $\bm{\mathcal{H}}$, for some
$\bm{p}^{\prime}\in P(t^{\prime},e,n)$, and denote the column indices in
$\mathcal{J}^{\prime}(\bm{\mathcal{H}},\bm{p}^{\prime})$ as $J^{\prime}$,
i.e., $\sum_{(i,j)\in J^{\prime}}\alpha_{i,j}\bm{h}_{i,j}=\bm{0}$, which
implies the existence of a codeword $\bm{Y}$ which is zero in every entry
except the indices in $J^{\prime}$, thus $0<w_{\text{TE}}(\bm{Y})\leq
t^{\prime}$, and then $d\leq t^{\prime}$, so we can conclude that there are no
patterns $\bm{p}^{\prime}\in P(t^{\prime},L,n)$, for $t^{\prime}<d$, such that
the vectors in $\mathcal{J}(\bm{\mathcal{H}},\bm{p}^{\prime})$ are linearly
dependent.

∎

###  III-C Linear Tail Erasure Code Construction

In this subsection, we give a construction for linear codes where $e\leq L$.
Note that if $e\leq L$, then the first $L-e$ bits of a row cannot be
erroneous. So, unless stated otherwise, it is assumed throught this subsection
that $e=L$. In Section III-D a discussion on codes where $e>L$ is given, and
also a construction of a linear code for this case will be given in Section
III-D.

First, since one can take a parity check matrix and construct a generator
matrix from it, we can derive an efficient (polynomial-time) encoding scheme.
For decoding, since the locations of the errors are known under this model, a
system of linear equations can be used to correct erasures, using the same
parity check matrix. Therefore, an efficient decoding scheme is also implied.
Following the above discussion, a construction of an
$[n\times(d-1),k,d]_{\text{TE}}$ code, $\mathcal{C}$, is presented, using a TE
parity check matrix.

######  Construction 1.

Let $d$ be an odd positive integer and denote $t\\!=\\!\frac{d-1}{2}$. Also,
let $\mathcal{C}_{B}$ be a binary $[nt,k_{B},d]$ error-correcting code,
referred as the _base code_ , with a parity check matrix
$H_{B}=[\bm{h}_{1}\,\bm{h}_{2}\cdots\bm{h}_{nt}]$. Then,

$\displaystyle\bm{\mathcal{H}}=\left[\begin{array}[]{ccc|ccc}\bm{h}_{1}&\cdots&\bm{h}_{t}&\bm{h}_{2t}&\cdots&\bm{h}_{t+1}\\\
\bm{h}_{t+1}&\cdots&\bm{h}_{2t}&\bm{h}_{3t}&\cdots&\bm{h}_{2t+1}\\\
\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\\
\bm{h}_{(n-1)t+1}&\cdots&\bm{h}_{nt}&\bm{h}_{t}&\cdots&\bm{h}_{1}\end{array}\right]\leavevmode\nobreak\
,$

is a TE parity check matrix of a TE-correcting code $\mathcal{C}_{\text{TE}}$.

######  Remark 1.

For $n=2$, this construction is degenerate, since it requires a
$[2t,k_{B},2t+1]$ base code.

For example, the code with the TE parity check matrix $\bm{\mathcal{H}}$ in
Example 3 is a $[7\times 2,11,3]_{\text{TE}}$ code. The next claim emphasizes
an important property of Construction 1.

######  Claim 3.

Let $\bm{p}\in P(e,2t,n)$, where $e\leq 2t$, and $\bm{\mathcal{H}}$ as in
Construction 1. Then, the multiset $\mathcal{J}(\bm{\mathcal{H}},\bm{p})$ does
not contain any column vector with multiplicity greater than $1$.

###### Proof:

Assume, for the sake of contradiction, that there exists a column vector with
multiplicity $2$ in $\mathcal{J}(\bm{\mathcal{H}},\bm{p})$ (according to the
construction it cannot have a greater multiplicity). By definition, for an
arbitrary $k\in[nt]$, $\bm{h}_{k}$ appears in $\bm{\mathcal{H}}$ at locations
$(i,j)$ and $(i-1,2t-j+1)$ (up to modulo $n$ and $2t$, respectively). But this
implies that ${\bm{h}}_{i,j}$ and ${\bm{h}}_{i-1,2t-j+1}$ are both in
$\mathcal{J}(\bm{\mathcal{H}},\bm{p})$, which is not possible since
$j+2t-j+1=2t+1>e=\|\bm{p}\|_{1}$, and $\bm{p}\in P(e,2t,n)$.

∎

Following, using Claim 3, is a proof of the correctness of Construction 1.

######  Theorem 2.

Let $\mathcal{C}_{B}$ be the $[nt,k_{B},d]$ base code, where
$t=\frac{d-1}{2}$. Let $\mathcal{C}$ be the resulting TE-correcting code from
Construction 1. Then, $\mathcal{C}$ is an $[n\times
2t,k_{B}+nt,d]_{\text{TE}}$ code. Furthermore, the redundancy of the code
$\mathcal{C}$ is $nt-k_{B}$.

###### Proof:

One can verify that this construction yields a code of length $n\times 2t$ and
that $\dim(\mathcal{C})=2nt-\text{rank}(\bm{\mathcal{H}})=2nt-(nt-
k_{B})=k_{B}+nt$, since $\bm{\mathcal{H}}$ is constructed from the columns of
$H_{B}$, repeated two times, and therefore
$\text{rank}(\bm{\mathcal{H}})=\text{rank}(H_{B})=nt-k_{B}$. It is left to
prove that $\rho_{\text{TE}}(\mathcal{C})=d$. Based on Claim 2, to show that
$\rho_{\text{TE}}(\mathcal{C})\geq d$, it is required to show that for any
arbitrary $\bm{p}\in P(2t,2t,n)$, the multiset
$\mathcal{J}(\bm{\mathcal{H}},\bm{p})$, is linearly independent. Since every
$2t=d-1$ columns in the base code are linearly independent, the fact that
$\rho_{\text{TE}}(\mathcal{C})\geq d$, immediately follows from Claim 3.
Lastly, the fact that $\rho_{\text{TE}}(\mathcal{C})=d$ can be easily
verified, e.g. using the vector $\bm{p}=(2t,0,\dots,0,1)$, which results in
$\mathcal{J}(\bm{\mathcal{H}},\bm{p})$, which is a linearly dependent
multiset.

∎

Construction 1 results in codes with odd minimum $\rho_{\text{TE}}$-distance.
The case of even minimum $\rho_{\text{TE}}$-distance is considered next.
First, note that for minimum $\rho_{\text{TE}}$-distance 2, it is
straightforward to see that a single parity bit suffices. For even minimum
$\rho_{\text{TE}}$-distance greater than $2$, denote again $t=\frac{d-1}{2}$,
where $d$ is odd. Then, let $\mathcal{C}_{B}$ be the $[nt+1,k_{b},d+1]$ base
code, i.e., a code with even minimum (Hamming) distance $d+1$ (w.l.o.g, based
on the same base code from Construction 1, with odd minimum distance, after
adding one parity bit, so that $d+1$ is even), where
$H_{B}^{*}=[\bm{h}_{1}\cdots\bm{h}_{nt+1}]$ is a parity check matrix of
$\mathcal{C}_{B}$. Then,

$\displaystyle\bm{\mathcal{H}^{*}}=\left[\begin{array}[]{ccc|c|ccc}h_{1}&\cdots&h_{t}&h_{nt+1}&h_{2t}&\cdots&h_{t+1}\\\
h_{t+1}&\cdots&h_{2t}&h_{nt+1}&h_{3t}&\cdots&h_{2t+1}\\\
\vdots&&\vdots&\vdots&\vdots&&\vdots\\\
h_{(\\!n\\!-\\!1\\!)t\\!+\\!1}&\cdots&h_{nt}&h_{nt+1}&h_{t}&\cdots&h_{1}\end{array}\right].$

Similarly to Construction 1, it can be shown that $\bm{\mathcal{H}^{*}}$ is a
parity check matrix for a $[n\times(2t+1),k_{b}+n(t+1)-1,d+1]_{\text{TE}}$
code. Therefore, the redundancy of such a code is $nt-k_{b}+1$. In order to
analyze the redundancy result of Construction 1, and its extension for the
even minimum $\rho_{\text{TE}}$-distance case, let $R(n,d)$ be the minimum
redundancy of any length-$n$ linear code with minimum (Hamming) distance $d$.
It is known that [26, p. 160-161],

$\displaystyle
R(n,d)\leq\begin{cases}\frac{d-1}{2}\lceil\log(n+1)\rceil,&d\text{ is odd}\\\
1+\left(\frac{d}{2}-1\right)\lceil\log(n+1)\rceil,&d\text{ is
even.}\end{cases}$

Next, for an $[n\times(d-1),k,d]_{\text{TE}}$ code that can be achieved by
Construction 1, let $R_{\text{TE}}(n,d)$ be the minimum number of redundancy
bits of the code. The next corollary considers the redundancy of Construction
1 and provides an upper bound on the redundancy of TE-codes.

######  Corollary 1.

It holds that

  1. 1.

$R_{\text{TE}}(n,d)\leq R\left(\frac{n(d-1)}{2},d\right)$. Thus, when $d$ is
odd,

$R_{\text{TE}}(n,d)\leq\frac{d-1}{2}\left\lceil\log\left(n\left(d-1\right)+2\right)\right\rceil-\frac{d-1}{2}\leavevmode\nobreak\
.$

  2. 2.

$R_{\text{TE}}(n,d)\leq R\left(\frac{n(d-2)+2}{2},d\right)$. Thus, when $d$ is
even and greater than 2,

$R_{\text{TE}}(n,d)\leq\left(\frac{d}{2}-1\right)\lceil\log(n\left(d-2\right)+4)\rceil-\frac{d-4}{2}\leavevmode\nobreak\
.$

Note that a trivial construction of TE codes can be achieved by considering
the array of size $n\times(d-1)$ as a vector of length $n(d-1)$, and then
correcting $d-1$ TEs using a linear $[n(d-1),k,d]$ code. This was presented in
[8] as the _vector construction_. The minimal number of redundancy bits of the
vector construction will be denoted by $R\left(n(d-1),d\right)$. Then, from
the previous discussion along with Corollary 1,

$R\left(n(d-1),d\right)\geq R\left(\frac{n(d-1)}{2},d\right)\geq
R_{\text{TE}}(n,d)\leavevmode\nobreak\ ,$

for any $n$ and odd $d$, and similarly for the even $d$ case. More explicitly,
the savings in Construction 1 is roughly $d/2$ bits of redundancy. Next,
$[n\times(d-1),k,d]_{\text{TE}}$ codes are presented, which imply some
additional constructive upper bounds on the redundancy of TE codes.

######  Claim 4.

Let $n$ be a positive integer and $r=\lceil\log_{2}(n+1)\rceil$. Then,

  1. 1.

An $[n\times 2,2n-r,3]_{\text{TE}}$ code exists, and thus the bound
$R_{\text{TE}}(n,3)\leq\lceil\log_{2}(n+1)\rceil$.

  2. 2.

An $[n\times 3,3n-r-1,4]_{\text{TE}}$ code exists, and thus the bound
$R_{\text{TE}}(n,4)\leq\lceil\log_{2}(n+1)\rceil+1$.

###### Proof:

Let $\mathcal{C}_{B}$ be an $[n,n-r,3]$ base code, which is a shortening of a
$(2^{r}-1)$-length Hamming code (where if $r=\log_{2}(n+1)$ exactly, no
shortening is required), and $\mathcal{C}_{B}^{*}$ be a $[n+1,n-r,4]$ code,
which is the extended version of $\mathcal{C}_{B}$, which one gets by adding a
parity bit. Therefore,

  1. 1.

Using Theorem 2, there exists a $[n\times 2,2n-r,3]_{\text{TE}}$ code.

  2. 2.

From the discussion on TE codes with even $\rho_{\text{TE}}(\mathcal{C})$,
there exists a $[n\times 3,3n-r-1,4]_{\text{TE}}$ code.

∎

By Claim 4 one derives an explicit upper bound on the redundancy of codes
which correct 2 or 3 TEs, based on Construction 1. Next, another upper bound
on the redundancy of codes that correct 4 TEs is derived from linear cyclic
codes, using a specific construction which is different than Construction 1.

######  Claim 5.

Let $n>0$ be an integer, $m=\lceil\log_{2}(n+5)\rceil$ and $r=2m+1$. Then,
there exist a $[n\times 4,4n-r,5]_{\text{TE}}$ code.

###### Proof:

For this proof, a proprietary construction is given, similar to Construction
1, but with different ordering of the entries. Let $\mathcal{C}_{B}$ be an
$[n+4,n+4-r,\geq 6]$ base code, which is a shortening (if needed) of the
$[2^{m}-1,2^{m}-2m-2,\geq 6]$ cyclic code in [26, Example 8.10], with a parity
check matrix $H=[\bm{h}_{1}\leavevmode\nobreak\
\bm{h}_{2}\cdots\bm{h}_{n+4}]$. Then,

$\displaystyle\bm{\mathcal{H}}=\left[\begin{array}[]{cc|cc}\bm{h}_{n+4}&\bm{h}_{n+3}&\bm{h}_{2}+\bm{h}_{3}&\bm{h}_{1}\\\
\bm{h}_{n+4}&\bm{h}_{n+3}&\bm{h}_{3}+\bm{h}_{4}&\bm{h}_{2}\\\
\vdots&\vdots&\vdots&\vdots\\\
\bm{h}_{n+4}&\bm{h}_{n+3}&\bm{h}_{n+1}+\bm{h}_{n+2}&\bm{h}_{n}\\\
\end{array}\right]\leavevmode\nobreak\ ,$

is a TE parity check matrix of $\mathcal{C}$, an $[n\times 4,4n-r,5]$ TE-
correcting code. It is clear why the length is $n\times 4$ and the dimension
is $4n-r$, since the redundancy stays the same as in the base code. What is
left to prove is that $\rho_{\text{TE}}(\mathcal{C})=5$, and the method will
be to show that for any $\bm{p}\in P(4,4,n)$, the vectors in
$\mathcal{J}(\bm{\mathcal{H}},\bm{p})$ are linearly independent. It can be
verified that every vector $\bm{p}$ that does not contain exactly two entries
of value $2$ satisfies the condition of $\mathcal{J}(\bm{\mathcal{H}},\bm{p})$
being linearly independent, since it will be a sum of at most $5$ distinct
vectors of $H$, which is a parity check matrix of a code with minimum Hamming
distance of at least $6$.

Therefore, observe next on the case where there are two entries of $\bm{p}$,
say $\bm{p}_{i},\bm{p}_{j}$, where $i<j$, such that $\bm{p}_{i}=\bm{p}_{j}=2$.
If $j-i\leq 2$, the sum of elements in $\mathcal{J}(\bm{\mathcal{H}},\bm{p})$
is again only at most $5$ distinct vectors of $H$. So the last case one needs
to check is where $j-i>2$, therefore $\mathcal{J}(\bm{\mathcal{H}},\bm{p})$
can be written as
$\left\\{\left\\{h_{i},h_{i+1}+h_{i+2},h_{j},h_{j+1}+h_{j+2}\right\\}\right\\}$.
To verify those vectors are independent, observe the equation,
$\alpha_{1}h_{i}+\alpha_{2}h_{i+1}+\alpha_{3}h_{i+2}+\alpha_{4}h_{j}+\alpha_{5}h_{j+1}+\alpha_{6}h_{j+2}=0$,
where $\alpha_{1},\ldots,\alpha_{6}\in\mathbb{F}_{2}$, and all the six
elements are distinct.

It is assumed that either $\alpha_{1}=\alpha_{2}=\cdots=\alpha_{6}=0$ or
$\alpha_{1}=\alpha_{2}=\cdots=\alpha_{6}=1$, since there cannot be a linear
dependent set of five distinct vectors. If those are all zero, the proof is
done. So, assume, for sake of contradiction, that
$h_{i}+h_{i+1}+h_{i+2}+h_{j}+h_{j+1}+h_{j+2}=0$, which means there is a
codeword in $\mathcal{C}_{B}$ of Hamming weight $6$, with ones only in the
entries $\\{i,i+1,i+2,j,j+1,j+2\\}$, denoted as $\bm{X}_{1}$. Since the code
is cyclic, there exists a codeword with ones only in the entries
$\\{i+1,i+2,i+3,j+1,j+2,j+3\\}$, denoted as $\bm{X}_{2}$. But then, also the
sum $\bm{X}=\bm{X}_{1}+\bm{X}_{2}$ is another codeword, but the Hamming weight
of $\bm{X}$ is at most $4$, which is a contradiction.

∎

One can verify that $2\lceil\log_{2}(n+5)\rceil+1<2\lceil\log_{2}(2n+1)\rceil$
for $n\geq 4$, if
$n\notin\bigcup_{i=3}^{\infty}\\{2^{i}-4,2^{i}-3,2^{i}-2,2^{i}-1\\}$. This
implies that for most (but not all) values of $n$, the construction in Claim 5
gives a tighter upper bound for $d=5$ than Construction 1 by one bit.

To conclude, the results are summarised in Table I, where the upper bound is
the constructive one from the above discussion and the lower bounds from
Section VI-A. Moreover, a comparison of the results presented in this section
and some previous results under the $m$-metric is given next.

In [9], a family of MDS codes is proved to exist, since those achieve the
Singleton bound in Claim 9. Similarly to the classical MDS codes for
length-$n$ vectors, for the family of array codes to fit large $n$ (and
arbitrary $L$), where $n$ is the number of rows in the array, it is required
to use a large field size, i.e., $q\geq n$, where $q$ is the size of the
field. Nevertheless, restricting to the binary case, one can construct a code
for $n=2$, which is a $[2\times L,2L-d+1,d]_{\text{TE}}$ code, where $d$ is
arbitrary, and which uses only $d-1$ bits of redundancy. The construction in
[9] also solves the case where $e>L$, still only for $n=2$ in the binary case,
as will be discussed in Section III-D. Contrary to that, the first
construction in [11], while also be an MDS code for $n=2$, do come with a
restriction of $e\leq L$. However, they give a more explicit construction of
an MDS code for the $2\times L$ binary array case. As mentioned in Remark 1,
Construction 1 is degenerated in the $n=2$ case and therefore one cannot
compare between the two constructions.

Another important family of codes, introduced in [8], is the construction of
BCH codes for the $m$-metric. In this paper, a construction of Reed-Solomon
codes for the $m$-metric is given, using Galois-Fourier transform and Hasse
derivatives, and then a BCH code is derived using alternant code [26, Section
5.5]. However, there are no specific bounds mentioned, and they only provide a
specific construction example for the case where $n=3$ and $L=4$. Therefore, a
comparison between their construction and this paper is parameter-dependent.
As for their construction for $3\times 4$ binary arrays [8, Table I], one can
see that for $d\leq 5$ ($e\leq L$), a comparison can be done using Claims 4
and 5. In our construction, we use at most $1,2,3,6$ bits of redundancy for
$d=2,3,4,5$, respectively, while their optimal choice of parameters yields at
most $1,3,4,6$ bits of redundancy for $d=2,3,4,5$, respectively, therefore our
construction improves some of their result, or achieves the same result for
the other cases. Other types of basic general construction ideas in [8] are
the vector construction, that we mentioned before, and the _Cartesian product
construction_ , which will be both discussed more in Section III-D, but in
their paper they claim that these two constructions are inferior compared to
their BCH codes. In [11], they gave mostly constructions for larger fields,
but two constructions are relevant for the binary case. The first was
mentioned before, as an MDS code for $n=2$, and the second will be discussed
next in Section III-D.

Table I: Bounds on the Redundancy of TE-Correcting Codes. Array Length | Minimum $\rho_{\text{TE}}$-distance | Constructive Upper Bound | Lower Bound | Gap
---|---|---|---|---
$n\\!\times\\!1$ | 2 | 1 | 1 | 0
$n\\!\times\\!2$ | 3 | $\lceil\log_{2}(n+1)\rceil$ | $\lceil\log_{2}(n+1)\rceil$ | 0
$n\\!\times\\!3$ | 4 | $\lceil\log_{2}(n+1)\rceil+1$ | $\lceil\log_{2}(n+1)\rceil$ | $\lesssim 1$
$n\\!\times\\!4$ | 5 | $\min\\{2\lceil\log_{2}(n+5)\rceil+1,2\lceil\log_{2}(2n+1)\rceil\\}$ | $2\lceil\log_{2}(n+1)\rceil-1$ | $\lesssim 4$
$n\\!\times\\!2t$ | $2t+1$ | $t\lceil\log_{2}\left(nt+1\right)\rceil$ | $t\lceil\log_{2}(n)\rceil$ | $\lesssim t\log_{2}(t)$
$n\\!\times\\!(2t+2)$ | $2t+2$ | $t\lceil\log_{2}\left(nt+2\right)\rceil+1$ | $t\lceil\log_{2}(n)\rceil+1$ | $\lesssim t\log_{2}(t)$

###  III-D $e$-TE Codes Where $e>L$

Claim 3 holds only when $e\leq L$. As of the writing of this paper, it is
still an open problem whether Construction 1 can be extended for the case
where $e>L$, or not. The challenge becomes perceptible when one just examines
the scenario in which $e=L+1$. In this case, the multiset
$\mathcal{J}(\bm{\mathcal{H}},\bm{p})$ for $\bm{p}$ such that
$\|\bm{p}\|_{1}=L+1$, can have an entire row of $\bm{\mathcal{H}}$ and also
one other entry from the last column. Since we cannot know which entry it will
be, every entry in the first column should differ from any other entry in
$\bm{\mathcal{H}}$, which results in an immediate decrease in terms of the
optimality of the code. However, there exist other constructions, where the
assumption on $e$ is not required, and those will be discussed next.

First, the vector construction, where the $n\times L$ array is treated as an
length-$nL$ vector. Therefore, the classical theory of erasure-correcting
codes satisfies the model and no requirements such as $e\leq L$ exists, but
the construction does not use the special structure of the position of the
erasures. Next, we describe the Cartesian product construction as in [8]. The
main idea here is to use independent erasure-correcting codes for every
column. That is, the $j$-th column, $j\in[L]$, is a codeword in an
$(n,M_{j},\lceil d/(L-j+1)\rceil)$, where $d$ represents the merged code being
a $(d-1)$-TE code. Also in this code, as in the vector construction, the
correctness of the code does not rely on the condition of $e\leq L$. Moreover,
the entire BCH codes that were constructed in [8] can correct erasures without
restrictions on the number of erasures. Also, the construction from [11,
Section 3.5] can correct at most $r$ erasures at the end of every row, which
is $nr$ erasures in total, but with a restriction on the number of erasures in
each row. The other condition for this code to exist, is $L\geq n\geq r$.

Next, we propose a construction of an $e$-TE code, in which the restriction
that $e\leq L$ is removed. The results we achieved for $L=2,3,4$ and
$e=2,3,4,5$, using this construction are summarized in Table II. The bold
entries represent cases in which Construction 2 is at least as good as the
known state of the art results, in terms of the number of redundancy bits.

This construction is inspired by ideas from [7, 8], and is based on the _Hasse
derivative_ , as defined in [27] and is presented next. Before continuing, we
first introduce some useful notation. For any non-negative integer $i$, the
$i$-th Hasse derivative of a polynomial
$f(x)=\sum_{k=0}^{d}a_{k}x^{k}\in\mathbb{F}_{q}[x]$ is

$f^{(i)}(x)\triangleq\sum_{k=0}^{d}\binom{k}{i}a_{k}x^{k-i}\leavevmode\nobreak\
,$

where $\binom{k}{i}=0$ for all $k<i$. Moreover, a fundamental property of the
Hasse derivative [7, Lemma 6] is that for every non-zero polynomial
$f(x)\in\mathbb{F}_{q}[x]$, an element $\beta\in\mathbb{F}$ (where
$\mathbb{F}$ is $\mathbb{F}_{q}$ or any extension field of $\mathbb{F}_{q}$),
is a root of multiplicity $\ell$ if and only if $f^{(s)}(x)=0$ for $0\leq
s<\ell$ and $f^{(\ell)}(x)\neq 0$. The following is a construction which is
based on the Hasse derivative.

######  Construction 2.

Let $n,L,e$ be arbitrary positive integers, and let $m$ be the smallest
integer such that $q=2^{m}>n$, that is, $m=\lceil\log_{2}(n+1)\rceil$. Let
$\alpha\in\mathbb{F}_{q}$ be a primitive element. Then, the TE parity check
matrix of the code $\mathcal{C}$ follows,

$\displaystyle\bm{\mathcal{H}}=\left[\begin{array}[]{ccccc}\bm{h}_{1,1}&\cdots&\bm{h}_{1,j}&\cdots&\bm{h}_{1,L}\\\
\bm{h}_{2,1}&\cdots&\bm{h}_{2,j}&\cdots&\bm{h}_{2,L}\\\
\vdots&\ddots&\vdots&\ddots&\vdots\\\
\bm{h}_{n,1}&\cdots&\bm{h}_{n,j}&\cdots&\bm{h}_{n,L}\\\
\end{array}\right]\leavevmode\nobreak\ ,$

where, for $\beta_{i}=\alpha^{i}$, each entry is the vector

$\displaystyle\bm{h}_{i,j}=\left[\begin{array}[]{c}\binom{0}{L-j}\beta_{i}^{0-L+j}\\\
\binom{1}{L-j}\beta_{i}^{1-L+j}\\\ \vdots\\\
\binom{e-1}{L-j}\beta_{i}^{e-1-L+j}\\\
\end{array}\right]\in\mathbb{F}_{q}^{e}\leavevmode\nobreak\
,i\in[n],j\in[L]\leavevmode\nobreak\ .$

######  Remark 2.

The key observation here is that for each vector $\bm{h}_{i,j}$, it holds that
for any vector $f=(f_{0},f_{1},\ldots,f_{e-1})\in\mathbb{F}_{q}^{e}$, which
represents a polynomial
$f(x)=\sum_{\ell=0}^{e-1}f_{\ell}x^{\ell}\in\mathbb{F}_{q}[x]$, the inner
product $f\cdot\bm{h}_{i,j}$ is the $(L-j)$-th Hasse derivative of $f$,
evaluated at $\beta_{i}$. Specifically, if there exists an index $j$, such
that $f\cdot\bm{h}_{i,\ell}\\!=\\!0$ for $\ell\in\\{L,L\\!-\\!1,\ldots,j\\}$
and $f\cdot\bm{h}_{i,j-1}\\!\neq\\!0$, then $\beta_{i}$ is a root of
multiplicity $L\\!-\\!j\\!+\\!1$ of $f$.

The following is a claim, proving that Construction 2 is an $e$-TE code.
Although the proof follows from the same ideas as in [7] we include it for
completeness.

######  Claim 6.

Let $\mathcal{C}$ be the resulting code from Construction 2. Then,
$\rho_{\text{TE}}(\mathcal{C})=e+1$.

###### Proof:

By using Claim 2, it needs to be proved that any multiset
$\mathcal{J}(\bm{\mathcal{H}},\bm{p})$ of cardinality $e$ is a linearly
independent multiset, and therefore let $\mathcal{J}$ be an arbitrary multiset
as such. Next, let $A\in\mathbb{F}_{q}^{e\times e}$ be the matrix that is
obtained from placing all the vectors in $\mathcal{J}$ as columns of $A$. We
want to show that $A$ has full rank. Therefore, assume, for the sake of
contradiction, that there exists a nonzero vector $f\in\mathbb{F}_{q}^{e}$
such that $f\cdot A=0$. Then, using the observation in Remark 2, the
polynomial $f(x)$ must have at least $e$ roots (including multiplicities), but
it is of degree $e-1$, which is a contradiction.

∎

In order to analyze the number of redundancy bits that Construction 2
requires, one needs to expand the entries in every $\bm{h}_{i,j}$ into binary
columns of length $m$, and then to compute the rank of the binary expansion of
$\bm{\mathcal{H}}$. This procedure is similar to the one done in analysis of
alternant codes. Therefore, the actual number of redundancy bits depends on
the specific parameters.

However, we provide next an example of a proof technique, for achieving a
better upper bound for specific cases. The technique includes modifying the
construction slightly by adding an additional row of parity. This will be
demonstrated on a $5$-TE code of length $n\times 2$ that uses only
$2(\lceil\log_{2}(n)\rceil+1)$ redundancy bits. This is better than the vector
construction (by $1$ bit, as one can verify), which is the only construction
that fits those parameters.

######  Claim 7.

Let $n$ be a positive integer and $q=2^{m}$, where $m$ is the smallest integer
such that $2^{m}>n$. Let $\alpha\in\mathbb{F}_{q}$ be a primitive element and
$\beta_{i}=\alpha^{i}$.

$\displaystyle\bm{\mathcal{H}}=\left[\begin{array}[]{cc}\bm{h}_{1,1}&\bm{h}_{1,2}\\\
\bm{h}_{2,1}&\bm{h}_{2,2}\\\ \vdots&\vdots\\\ \bm{h}_{n,1}&\bm{h}_{n,2}\\\
\end{array}\right]\leavevmode\nobreak\ ,$

where

$\displaystyle\bm{h}_{i,1}=\left[\begin{array}[]{cc}1\\\ 0\\\ 1\\\
\beta_{i}^{2}\\\ \end{array}\right]\leavevmode\nobreak\
,\quad\bm{h}_{i,2}=\left[\begin{array}[]{cc}0\\\ 1\\\ \beta_{i}\\\
\beta_{i}^{3}\\\ \end{array}\right]\leavevmode\nobreak\ .$

Then, $\bm{\mathcal{H}}$ is a TE parity check matrix of a $5$-TE code.

###### Proof:

First, let

$\displaystyle\bm{\mathcal{H}}^{\prime}=\left[\begin{array}[]{cc}\bm{h}_{1,1}^{\prime}&\bm{h}_{1,2}^{\prime}\\\
\bm{h}_{2,1}^{\prime}&\bm{h}_{2,2}^{\prime}\\\ \vdots&\vdots\\\
\bm{h}_{n,1}^{\prime}&\bm{h}_{n,2}^{\prime}\\\ \end{array}\right],$

where,

$\displaystyle\bm{h}_{i,1}^{\prime}=\left[\begin{array}[]{cc}1\\\ 0\\\ 1\\\
0\\\ \beta_{i}^{2}\\\ 0\\\ \end{array}\right],\leavevmode\nobreak\
\bm{h}_{i,2}^{\prime}=\left[\begin{array}[]{cc}0\\\ 1\\\ \beta_{i}\\\
\beta_{i}^{2}\\\ \beta_{i}^{3}\\\ \beta_{i}^{4}\\\
\end{array}\right]\leavevmode\nobreak\ .$

Notice that an entry is added in the beginning of each
$\bm{h}_{i,j}^{\prime}$, although from Claim 6 one can verify that
$\bm{\mathcal{H}}^{\prime}$ is a $5$-TE code. The way to prove this, is by
showing that the removed rows ($4$-th and $6$-th) in every
$\bm{h}_{i,j}^{\prime}$ can be recovered from the retained rows. Let $\bm{p}$
be a pattern of erasures and $\mathcal{J}(\bm{\mathcal{H}}^{\prime},\bm{p})$
be the respective multiset of columns from $\bm{\mathcal{H}}^{\prime}$.
Suppose that
$\mathcal{I}=\\{(i_{1},j_{1}),(i_{2},j_{2}),\ldots,(i_{5},j_{5})\\}$ denotes
the indices of those columns in
$\mathcal{J}(\bm{\mathcal{H}}^{\prime},\bm{p})$. Also, let
$\mathcal{I}_{2}=\\{i\colon(i,2)\in\mathcal{I}\\}$, that is all the indices
that indicate erasures in the second (i.e. last) column, and
$\mathcal{I}_{1}=\\{i\colon(i,1)\in\mathcal{I}\\}$, that is, the indices of
erasures in the first (i.e., penultimate) column.

Next, denote

$\displaystyle
R_{\ell}=\sum_{(i,j)\in\mathcal{I}}c_{i,j}(\bm{h}_{i,j}^{\prime})_{\ell}=\sum_{i\in\mathcal{I}_{1}}c_{i,j}(\bm{h}_{i,1}^{\prime})_{\ell}+\sum_{i\in\mathcal{I}_{2}}c_{i,j}(\bm{h}_{i,2}^{\prime})_{\ell}\leavevmode\nobreak\
,$

where $c_{i,j}\in\mathbb{F}_{2}$, and notice that $\mathcal{I}_{1}$ and
$\mathcal{I}_{2}$ are not disjoint, which is desired. Next, we prove that
$R_{4}=(R_{3})^{2}+R_{1}$, so that $R_{4}$ can be removed from the parity
check matrix, using the characteristic of $\mathbb{F}_{q}$, which is $2$, as
follows,

$R_{4}=\sum_{i\in\mathcal{I}_{1}}c_{i,j}(\bm{h}_{i,1}^{\prime})_{4}+\sum_{i\in\mathcal{I}_{2}}c_{i,j}(\bm{h}_{i,2}^{\prime})_{4}=\sum_{i\in\mathcal{I}_{2}}c_{i,j}\beta_{i}^{2}\\\
=\sum_{i\in\mathcal{I}_{2}}c_{i,j}\beta_{i}^{2}+\sum_{i\in\mathcal{I}_{1}}c_{i,j}\cdot
1+\sum_{i\in\mathcal{I}_{1}}c_{i,j}\cdot 1\\\
=\left(\sum_{i\in\mathcal{I}_{2}}c_{i,j}\beta_{i}+\sum_{i\in\mathcal{I}_{1}}c_{i,j}\cdot
1\right)^{2}+\sum_{i\in\mathcal{I}_{1}}c_{i,j}\cdot 1\\\
=(R_{3})^{2}+R_{1}\leavevmode\nobreak\ .$

Noting that also $R_{6}=(R_{4})^{2}$ completes the proof, since by removing
$R_{4},R_{6}$, the matrix $\bm{\mathcal{H}}^{\prime}$ becomes the desired
$\bm{\mathcal{H}}$.

∎

The same ideas from the proof of the previous claim can be applied to a few
additional parameter regimes, which are highlighted in Table II, that achieve
the best known results.

Table II: Upper Bounds On The Redundancy Bits Of Construction 2. | $L=2$ | $L=3,4$
---|---|---
$e=2$ | $\bm{\log_{2}(n)+1}$ | $\bm{\log_{2}(n)+1}$
$e=3$ | $\bm{\log_{2}(n)+2}$ | $\log_{2}(n)+3$
$e=4,5$ | $\bm{2\log_{2}(n)+2}$ | $\bm{2\log_{2}(n)+3}$

##  IV $(t,s)$-Deletion-Correcting Codes

In the process of constructing optimal $(t,s)$-DC codes, we first introduce a
construction of a $(t,1)$-DC code, and an explicit encoder for this
construction will be presented afterwards. Then, a generalization for an
encoder of a $(t,s)$-DC code will conclude this Section. In Section VI-B, it
is shown that, in some cases, those constructions are optimal.

###  IV-A $(t,1)$-DC Codes

In order to correct a single deletion in a length-$n$ vector, the Varshamov-
Tenengolts (VT) codes [28] are the common solution and will also form the
basis of the following construction. For $0\leq a\leq L$, denote
$\text{VT}_{a}(L)$, as defined in [28],

$\displaystyle\text{VT}_{a}(L)=\left\\{\bm{x}\in\\{0,1\\}^{L}\colon\sum_{j=1}^{L}jx_{j}\equiv
a\ (\mathrm{mod}\ L+1)\right\\}\leavevmode\nobreak\ .$

Next, we want to define a variant of VT codes, including some new notations,
in order to construct a tensor product code, an idea that was introduced in
[29], which underlies the VT codes.

Denote $h=\lceil\log_{2}(L+1)\rceil$, such that $\mathbb{F}_{2^{h}}$, the
field of $2^{h}$ elements, is the smallest extension field of $\mathbb{F}_{2}$
that has at least $L+1$ elements. For each row
$\bm{x}_{i}=(x_{i,1},\dots,x_{i,L})$, define the _$q$ -syndrome_ to be
$s_{q}(\bm{x}_{i})\equiv\sum_{j=1}^{L}jx_{i,j}\ (\mathrm{mod}\ q)$. Let
$\phi:\mathbb{Z}_{2^{h}}\to\mathbb{F}_{2^{h}}$ be a bijection and denote
$\phi(s_{2^{h}}(\bm{x}_{i}))$ as $\sigma(\bm{x}_{i})$, which is the syndrome
of $\bm{x}_{i}$ as an element of the field $\mathbb{F}_{2^{h}}$.

A definition for a variation of the binary VT codes of length $L$ follows,

$\text{VT}^{2^{h}}_{a}(L)=\left\\{\bm{x}\in\mathbb{F}_{2}^{L}\colon\sum_{j=1}^{L}jx_{j}\equiv
a\ (\mathrm{mod}\ 2^{h})\right\\}\leavevmode\nobreak\ ,$

where now it holds that $0\leq a\leq 2^{h}-1$. One can verify that
$\text{VT}^{2^{h}}_{a}(L)$ can correct a single deletion using the same
decoding algorithm as the original VT codes [30]. The following is an implicit
construction of a $(t,1)$-DC code.

######  Construction 3.

Let $\mathcal{C}$ be a code of length $n$, that can correct $t$ erasures over
$\mathbb{F}_{2^{h}}$. Then,

$\displaystyle\mathcal{C}_{\text{DC}}(n,L,t,\mathcal{C})\coloneqq\big{\\{}\bm{X}=\left(\bm{x}_{1},\dots,\bm{x}_{n}\right)\in\mathbb{F}_{2}^{n\times
L}\colon$
$\displaystyle\left(\sigma\left(\bm{x}_{1}\right),\dots,\sigma(\bm{x}_{n})\right)\in\mathcal{C}\big{\\}}\leavevmode\nobreak\
.$

As discussed before, Construction 3 yields a tensor product code that relies
on the syndromes of the variant of the VT code, such that the possible values
of the syndrome can be treated as field elements, and therefore the $n$
syndromes comprise the symbols from a codeword of the non-binary code
$\mathcal{C}$ over the same field.

######  Remark 3.

Note that increasing the parameter $h$ results in codes with larger
redundancy. One can choose to work with the original VT code, and then
construct the non-binary code over the ring $\mathbb{Z}_{L+1}$, instead of a
field, if there exists an optimal code over this ring with the required
parameters.

Next, we prove that Construction 3 is a $(t,1)$-DC code.

######  Lemma 1.

The code $\mathcal{C}_{\text{DC}}(n,L,t,\mathcal{C})$ is a $(t,1)$-DC code.

###### Proof:

The proof is based on the idea that due to the deletions, each erroneous row
is shorter, and therefore the location (index) of these rows is known. Next,
assume that $s\leq t$ rows suffer from one deletion each and denote its
indices as $i_{1},\dots,i_{s}$. Since $n-s$ rows are error-free, their
syndromes can be computed and mapped into $\sigma(\bm{x}_{j})$, where
$j\in[n]\setminus\\{i_{1},\dots,i_{s}\\}$. Now $\mathcal{C}$ can recover
$\sigma(\bm{x}_{i_{1}}),\dots,\sigma(\bm{x}_{i_{s}})$ such that
$\left(\sigma\left(\bm{x}_{1}\right),\dots,\sigma(\bm{x}_{n})\right)$ can be
used truthfully as syndromes for each of the
$\text{VT}^{2^{h}}_{\sigma(\bm{x}_{i})}(L)$ codewords, which is the $i$-th
row. Therefore, the rows $\bm{x}_{i_{1}},\dots,\bm{x}_{i_{s}}$ can be
recovered.

∎

Before we present an explicit encoder for Construction 3, we give an upper
bound on the minimal number of redundancy bits that are required to constuct a
$(t,1)$-DC code, based on Construction 3.

######  Theorem 3.

Let $R_{\text{Opt}}$ be the number of redundancy symbols of
$\mathcal{C}_{\text{Opt}}$, a linear code of length $n$, that can corrects $t$
erasures over $\mathbb{F}_{2^{h}}$. Then, there exists a code
$\mathcal{C}_{\text{DC}}(n,L,t,\mathcal{C}_{\text{Opt}})$ with a redundancy of
at most $R_{\text{Opt}}\cdot
h=R_{\text{Opt}}\cdot\left\lceil\log_{2}(L+1)\right\rceil$ bits.

###### Proof:

Note that any coset of $\mathcal{C}_{\text{Opt}}$ is a distinct $t$-erasures-
correcting code, and there are $q^{R_{\text{Opt}}}$ cosets, where $q=2^{h}$.
Thus, there are $q^{R_{\text{Opt}}}$ distinct
$\mathcal{C}_{\text{DC}}(n,L,t,\cdot)$ codes, one for each coset, and all
those distinct $\mathcal{C}_{\text{DC}}(n,L,t,\cdot)$ codes create a partition
of the space of all the $2^{nL}$ binary arrays of size $n\times L$. Therefore,
using the pigeonhole principle, there exists at least one code with
$2^{nL}/q^{R_{\text{Opt}}}=2^{nL-
R_{\text{Opt}}\cdot\left\lceil\log_{2}(L+1)\right\rceil}$ codewords.

∎

Note that it implies the existence of a $(1,1)$-DC code with only
$\log_{2}(L+1)$ bits of redundancy. Also, if $\mathcal{C}_{\text{Opt}}$ is an
MDS code, the upper bound on the redundancy is exactly
$t\lceil\log_{2}(L+1)\rceil$ bits, and by looking at the discussion after
Theorem 6, one can verify optimality, assuming the VT codes are optimal
$1$-deletion-correcting codes.

######  Corollary 2.

There exists a $\mathcal{C}_{\text{DC}}(n,L,t,\mathcal{C}_{\text{Opt}})$ code
with a redundancy bits of at most

$t(\log_{2}(n)+\lceil\log_{2}(L+1)\rceil).$

###### Proof:

By using alternant code over $\mathbb{F}_{2^{h}}$ as in [26, Section 5.5], one
has a code $\mathcal{C}$ with a redundancy of at most $t\cdot m$ symbols,
where $m$ is an integer such that $2^{m}\geq(2^{h})^{n}$.

Therefore, $\lceil\log_{2^{h}}(n)\rceil$ is an optimal choosing of $m$.
Finally, using the same proof as in Theorem 3, where $R\leq
t\cdot\lceil\log_{2^{h}}(n)\rceil$ and thus there exists a code with a
redundancy of at most

$\displaystyle R\cdot h$ $\displaystyle\leq
t\cdot\lceil\log_{2^{h}}(n)\rceil\cdot h$
$\displaystyle=t\cdot\left\lceil\frac{\log_{2}(n)}{h}\right\rceil\cdot h$
$\displaystyle\leq t(\log_{2}(n)+h)\leavevmode\nobreak\ .$

∎

######  Remark 4.

Note that if $n=c\cdot 2^{h}$ for some positive integer $c$, then the bound in
Corollary 2 is $t(\log_{2}(n))$.

Finally, an explicit encoder of Construction 3 is presented. In [31], a
systematic encoder of $\text{VT}_{a}(L)$, where the redundancy bits are in the
$\\{2^{i}\\}_{i=0}^{h-1}$ coordinates was introduced. Then, an encoder for
$\text{VT}^{2^{h}}_{a}(L)$, denoted as $\mathcal{E}_{\text{VT}}^{(L,a)}$, can
be obtained using the same idea, since one can verify that it requires exactly
the same entries, $\\{2^{i}\\}_{i=0}^{h-1}$, for the encoding process.
$\mathcal{E}_{\text{VT}}^{(L,a)}$ is defined as follows. First, it receives a
binary input vector $\bm{d}$ of length $L-h$, then outputs a codeword $\bm{x}$
of length $L$, such that
$\mathcal{E}_{\text{VT}}^{(L,a)}(\bm{d})=\bm{x}\in\text{VT}^{2^{h}}_{a}(L)$.

######  Encoder 1.

Let $\text{E}\colon{(\mathbb{F}_{2^{h}})}^{n-R}\to{(\mathbb{F}_{2^{h}})}^{n}$
be a systematic encoder of a linear code $\mathcal{C}$ of length $n$, that can
correct $t$ erasures over $\mathbb{F}_{2^{h}}$. Lastly, denote
$K\\!=\\!nL\\!-\\!Rh$.

Input: $\bm{D}=(d_{1},\dots,d_{K})\in\mathbb{F}_{2}^{K}$.

Output:
$\bm{X}=\left(\bm{x}_{1},\dots,\bm{x}_{n}\right)\in\mathbb{F}_{2}^{n\times
L}$.

  1. 1.

For $i\in[n-R],j\in[L]\colon x_{i,j}\leftarrow d_{(i-1)L+j}$.

  2. 2.

Compute $(\sigma(\bm{x}_{1}),\dots,\sigma(\bm{x}_{n-R}))$. Then, encode it
into $\text{E}\left(\sigma(\bm{x}_{1}),\dots,\sigma(\bm{x}_{n-R})\right)$, and
denote the output of E as $(\sigma(\bm{x}_{1}),\dots,\sigma(\bm{x}_{n}))$.

  3. 3.

Take the remaining $R(L-h)$ bits of $\bm{D}$ and split them into $R$ vectors
of $L-h$ bits, denoted by $\\{\bm{d}_{1},\dots,\bm{d}_{R}\\}$.

  4. 4.

For $i\in[R]\colon
a_{n\\!-R\\!+i}\leftarrow\phi^{-1}\left(\sigma(\bm{x}_{n\\!-R\\!+i})\right)$,
that is recovering from $\sigma(\cdot)$ the expected syndrome value of the
$(n-R+i)$-th row, which is denoted as $a_{n-R+i}$.

  5. 5.

For
$i\in[R]\colon\bm{x}_{n-R+i}\leftarrow\mathcal{E}_{\text{VT}}^{(L,a_{n\\!-R\\!+i})}(\bm{d}_{i})$,
i.e., encode the VT codeword $\bm{x}_{n-R+i}$ from $\bm{d}_{i}$ as defined in
step 3, based on the given syndrome value $a_{n\\!-R\\!+i}$.

  6. 6.

Return $\bm{X}$.

The decoding steps are straightforward, using the decoders of $\mathcal{C}$
and $\text{VT}^{2^{h}}_{a}(L)$ in the same way as in the proof of Lemma 1,
which proves the correctness, since one can readily verify that the output of
Encoder 1 is a codeword of $\mathcal{C}_{\text{DC}}(n,L,t)$ from Construction
3. Moreover, as one can verify, Encoder 1 uses exactly
$R_{\text{Opt}}\cdot\left\lceil\log_{2}(L+1)\right\rceil$ bits of redundancy,
which is an explicit construction for the existance proof in Theorem 3.
Finally, we give an example of Encoder 1, for constructing a $(2,1)$-DC code
over the space of $7\times 5$ binary arrays.

######  Example 4.

In Figure 2, observe an example of an output of Encoder 1. It receives $29$
bits as an input, denoted as,

$\bm{D}=(x_{1,1},\ldots,x_{5,5},x_{6,3},x_{6,5},x_{7,3},x_{7,5})\in\mathbb{F}_{2}^{29},$

and are shown with the white background in the $7\times 5$ array codeword. The
encoder computes the syndromes
$(\sigma(\bm{x}_{1}),\ldots,\sigma(\bm{x}_{5}))$ and then, using an encoder of
a $[7,5,3]$ code over $\mathbb{F}_{2^{3}}$, computes also $\sigma(\bm{x}_{6})$
and $\sigma(\bm{x}_{7})$. The syndromes are presented with dashed lines on the
right side of the codeword. Lastly, using the systematic encoder for the VT
codes, it computes the redundancy values in the last $2$ rows, marked with
gray background. Therefore, it is an example of size $(7\times 5)$ binary
array code with $6$ bits of redundancy.

Figure 2: Example of an output of Encoder 1 for a $(2,1)$-DC code over binary
arrays of length $7\times 5$. Illustration of Example 4.

###  IV-B Construction of a $(t,s)$-DC Code

The next section is based on the construction in [32]. First, denote by
$\mathcal{C}_{s}$ the $s$-deletion-correcting code over the vector space
$\mathbb{F}_{2}^{L+r}$, which is composed from all the codewords
$\left(\bm{c},g(\bm{c})\right)$, where $\bm{c}\in\mathbb{F}_{2}^{L}$, and
$g(\bm{c})$111For shortening, we use $g$ instead of the modular version in
[32], which is denoted by $g_{c}$ they use is an $s$-deletion correcting hash
for $\bm{c}$ of size $r=4s\log_{2}(L)+o(\log_{2}(L))$. The existence of such a
code is proved in [32]. Finally, denote by $\Gamma(\bm{c})$ the mapping of
$g(\bm{c})$ to an element of $\mathbb{F}_{2^{r}}$.

######  Construction 4.

Let $n$, $L$, $t$ and $s$ be positive integers, and let $r$ be the constant
described previously. Next, let $\mathcal{C}$ be a code of length $n$, that
can correct $t$ erasures over $\mathbb{F}_{2^{r}}$. Then,

$\displaystyle\mathcal{C}_{s\text{-DC}}(n,L,t,\mathcal{C})\coloneqq\big{\\{}\bm{X}=\left(\bm{x}_{1},\dots,\bm{x}_{n}\right)\in\mathbb{F}_{2}^{n\times
L}\colon$
$\displaystyle\left(\Gamma\left(\bm{x}_{1}\right),\dots,\Gamma\left(\bm{x}_{n}\right)\right)\in\mathcal{C}\big{\\}}\leavevmode\nobreak\
.$

The next lemma follows a proof outline similar to that of Lemma 1.

######  Lemma 2.

The code $\mathcal{C}_{s\text{-DC}}(n,L,t,\mathcal{C})$ is a $(t,s)$-DC code.

###### Proof:

As in Lemma 1, due to the deletions, each erroneous row is shorter, and
therefore the index of these rows is known. Assume that $w\leq t$ rows suffer
from one deletion each and denote its indices as $i_{1},\dots,i_{w}$. Since
$n-w$ rows are error-free, the value of their $g$ function can be computed and
mapped into $\Gamma(\bm{x}_{j})$, where
$j\in[n]\setminus\\{i_{1},\dots,i_{w}\\}$. Now $\mathcal{C}$ can recover
$\Gamma(\bm{x}_{i_{1}}),\dots,\Gamma(\bm{x}_{i_{s}})$ such that
$\left(\Gamma\left(\bm{x}_{1}\right),\dots,\Gamma(\bm{x}_{n})\right)$ can be
mapped back to valid values of
$\left(g\left(\bm{x}_{1}\right),\dots,g(\bm{x}_{n})\right)$, and then the rows
$\bm{x}_{i_{1}},\dots,\bm{x}_{i_{w}}$ can be recovered using the decoder from
[32], since each of these rows suffers at most $s$ deletions, and therefore
the set of words $\\{(\bm{x}_{i_{j}},g(\bm{x}_{i_{j}}))\\}_{j=1}^{w}$ also,
which is the input to the decoder in [32].

∎

Moreover, the next theorem is also using similar techniques as in Theorem 3.

######  Theorem 4.

Let $R_{\text{Opt}}$ be the number of redundancy symbols of
$\mathcal{C}_{\text{Opt}}$, a linear code of length $n$, that can corrects $t$
erasures over $\mathbb{F}_{2^{r}}$. Then, there exists a code
$\mathcal{C}_{s\text{-DC}}(n,L,t,\mathcal{C})$ with a redundancy of at most
$R_{\text{Opt}}\cdot r\approx R_{\text{Opt}}\cdot 4s\log_{2}(L)$ bits.

###### Proof:

Note that any coset of $\mathcal{C}_{\text{Opt}}$ is a distinct $t$-erasures-
correcting code, and there are $q^{R_{\text{Opt}}}$ cosets, where $q=2^{r}$.
Thus, there are $q^{R_{\text{Opt}}}$ distinct
$\mathcal{C}_{s\text{-DC}}(n,L,t,\cdot)$ codes, one for each coset, and all
those distinct $\mathcal{C}_{s\text{-DC}}(n,L,t,\cdot)$ codes create a
partition of the space of all the $2^{nL}$ binary arrays of size $n\times L$.
Therefore, using the pigeonhole principle, there exists at least one code with
$2^{nL}/q^{R_{\text{Opt}}}=2^{nL-R_{\text{Opt}}\cdot r}$ codewords.

∎

Table III: Bounds on the redundancy of $(t,s)$-DC codes, where $h=\lceil\log_{2}(L+1)\rceil$ and $c>0$ is an integer. Model | Restriction | Constructive Upper Bound | Asymptotic Lower Bound
---|---|---|---
$(t,1)$ | $n\leq 2^{h}+1$ | $th$ | $t\lceil\log_{2}(L)\rceil$
$(t,1)$ | $n=c\cdot 2^{h}$ | $t\log_{2}(n)$ | $\max\\{th,\lfloor t/2\rfloor\log_{2}(n)\\}$
$(t,1)$ | - | $t(\log_{2}(n)+h)$ | $\max\\{th,\lfloor t/2\rfloor\log_{2}(n)\\}$
$(t,s)$ | - | $t(\log_{2}(n)+4s\log_{2}(L)+o(\log_{2}(L))$ | $\lfloor t/2\rfloor(\log_{2}(n)+\lfloor s/2\rfloor\log_{2}(L))$

##  V $(t,1,e)$-TED-Correcting Code

In this section we present a method of constructing $(t,1,e)$-TED-correcting
code. This construction and its encoder use a non-binary code that is based
upon the following two pieces of information: (i) The VT syndrome for each
row, (ii) The value of the last $e$ bits of each row.

As in Section IV-A, let $h=\lceil\log_{2}(L+1)\rceil$, and for any array
$\bm{X}=\left(\bm{x}_{1},\dots,\bm{x}_{n}\right)\in\mathbb{F}_{2}^{n\times L}$
denote by $s_{i}$ the $2^{h}$-syndrome of the $i$-th row of $\bm{X}$ as in
Section IV-A, which is to say that $s_{i}=\sum_{j=1}^{L}jx_{i,j}\
(\mathrm{mod}\ 2^{h})$. Moreover, denote the last $e$ bits of the $i$-th row
of $\bm{X}$ by $\bm{x}_{i}^{(:e)}\triangleq(\bm{x}_{i})_{[L-e+1\colon L]}$.
Next, for each row of $\bm{X}$, define the tuple
$\left(s_{i},\bm{x}_{i}^{(:e)}\right)$. Finally, let $q=2^{h}\cdot
2^{e}=2^{h+e}$ and denote by $\theta_{\bm{x}_{i}}$ the mapping of the tuple
$\left(s_{i},\bm{x}_{i}^{(:e)}\right)$ to an element of $\mathbb{F}_{q}$.

######  Construction 5.

Let $\mathcal{C}$ be an $[n,k,t\\!+\\!e\\!+\\!1]$ code over $\mathbb{F}_{q}$.
Then,

$\displaystyle\mathcal{C}_{\text{TED}}(n,L,t,e)\\!\coloneqq\\!\big{\\{}\bm{X}\in\mathbb{F}_{2}^{n\times
L}\colon\left(\theta_{\bm{x}_{1}},\dots,\theta_{\bm{x}_{n}}\right)\in\mathcal{C}\big{\\}}.$

Next, is a proof for the correctness of Construction 5.

######  Lemma 3.

The code $\mathcal{C}_{\text{TED}}(n,L,t,e)$ is a $(t,1,e)$-TED code.

###### Proof:

A codeword $\bm{X}\in\mathcal{C}_{\text{TED}}(n,L,t,e)$ is received with at
most $t+e$ deletions, some of which are arbitrary deletions and some are tail-
erasures. Therefore, there are at most $t+e$ rows which one cannot compute
their tuple $\left(s_{i},\bm{x}_{i}^{(:e)}\right)$, and since $\mathcal{C}$
can correct $t+e$ erasures, the entire codeword
$\left(\theta_{\bm{x}_{1}},\dots,\theta_{\bm{x}_{n}}\right)\in\mathcal{C}$ can
be recovered. Next, one can recover the codeword $\bm{X}$ row by row. For each
row, if it is of length $L$, it does not suffer from any deletion. If it is of
length $L-1$, it can be recovered using the VT syndrome, regardless of the
source of the deletion (arbitrary or TE). Finally, if it is of length $L-k$
for some $1<k\leq e+1$, then it suffered from at most $1$ arbitrary deletion,
and the rest are $k-1$ TEs, or just $k$ TEs. Thus, one can recover the last
$k-1$ bits, as it is saved in the tuple
$\left(s_{i},\bm{x}_{i}^{(:e)}\right)$, and treat the last deleted bit as an
arbitrary deletion, regardless of the source.

∎

Similarly to Remark 3, one can choose to work with the original VT codes, and
then $q=2^{e}\cdot(L+1)$ is not a prime power, and afterwards construct the
non-binary code over the ring $\mathbb{Z}_{q}$, instead of a field. Moreover,
as a proof of existence of codes that are built according to Construction 5,
an explicit encoder is provided next.

######  Encoder 2.

Let $\text{E}\colon{(\mathbb{F}_{q})}^{n-R}\to{(\mathbb{F}_{q})}^{n}$ be a
systematic encoder of an optimal linear code $\mathcal{C}$ of length $n$, that
can correct $t+e$ erasures over $\mathbb{F}_{q}$. Also, let
$\mathcal{E}_{\text{VT}}^{(L,a)}$ be a systematic VT code encoder, as defined
in Section IV. Lastly, denote $K_{\text{TED}}=nL-R(e+h)$.

Input:
$\bm{D_{\text{TED}}}=(d_{1},\dots,d_{K_{\text{TED}}})\in\mathbb{F}_{2}^{K_{\text{TED}}}$.

Output:
$\bm{X}=\left(\bm{x}_{1},\dots,\bm{x}_{n}\right)\in\mathbb{F}_{2}^{n\times
L}$.

  1. 1.

For $i\in[n-R],j\in[L]\colon x_{i,j}\leftarrow d_{(i-1)L+j}$, and denote
$\bm{x}_{i}^{(:e)}=(x_{i,L-e+1},\ldots,x_{i,L})$.

  2. 2.

Compute $\\{s_{1},\dots,s_{n-R}\\}$, and
$\\{\theta_{\bm{x}_{1}},\dots,\theta_{\bm{x}_{n-R}}\\}$.

  3. 3.

Compute $\text{E}\left(\theta_{\bm{x}_{1}},\dots,\theta_{\bm{x}_{n-R}}\right)$
and denote the output as
$\left(\theta_{\bm{x}_{1}},\dots,\theta_{\bm{x}_{n}}\right)$.

  4. 4.

Take the remaining $R(L-e-h)$ bits of $\bm{D}$ and split them into $R$ vectors
of length $L-e-h$, denoted by $\\{\bm{d}_{1},\dots,\bm{d}_{R}\\}$.

  5. 5.

For $i\in\\{n-R+1,\ldots,n\\}$, extract the tuple
$\left(s_{i},\bm{x}_{i}^{(:e)}\right)$, computed as $\theta_{\bm{x}_{i}}$ in
Step 3.

  6. 6.

Let ${\widetilde{\bm{d}}}_{i}$ be the appending of $\bm{x}_{i}^{(:e)}$ to the
end of $\bm{d}_{i}$.

  7. 7.

Compute
$\bm{x}_{i}=\mathcal{E}_{\text{VT}}^{(L,s_{i})}({\widetilde{\bm{d}}}_{i})$,
i.e. encode the VT codeword $\bm{x}_{i}$ from ${\widetilde{\bm{d}}}_{i}$, such
that the last $e$ bits of $\bm{x}_{i}$ are $\bm{x}_{i}^{(:e)}$ and the
syndrome value of $\bm{x}_{i}$ is $s_{i}$.

  8. 8.

Return $\bm{X}$.

Note that Encoder 2 requires that $e<(L+1)-2^{h-1}$. Also, it can be verified
that Encoder 2 outputs a codeword of $\mathcal{C}_{\text{TED}}(n,L,t,e)$ from
Construction 5.

######  Corollary 3.

The following results regarding the redundancy of
$\mathcal{C}_{\text{TED}}(n,L,t,e)$, denoted as $R_{\text{TED}}$ are obtained.

  1. 1.

The redundancy of the code $\mathcal{C}_{\text{TED}}(n,L,t,e)$, using Encoder
2 is $nL-K_{\text{TED}}=R(e+h)$.

  2. 2.

Using an alternant code as $\mathcal{C}$ in Encoder 2 implies

$R_{\text{TED}}\leq\left(e+h\right)\left(\frac{t+e}{2}\right)\log_{2}(n)\leavevmode\nobreak\
.$

  3. 3.

If $n\leq 2^{h+e}$, using an MDS code code as $\mathcal{C}$ in Encoder 2
implies

$R_{\text{TED}}\leq\left(e+\lceil\log_{2}(L+1)\rceil\right)\left(t+e\right)\leavevmode\nobreak\
.$

  4. 4.

If $n\leq 2^{h+1}$, using an MDS code code as $\mathcal{C}$ in Encoder 2
implies a $(1,1,1)$-TED code with $2+\lceil 2\log_{2}(L+1)\rceil$ bits of
redundancy.

Note that the forth result in Corollary 3 is asymptotically optimal, when
compared to the result in Theorem 10. Finally, note that one can use a
$(t+e)$-deletion-correcting code over vectors of length $nL$ as in [32], with
a redundancy of

$4(t+e)(\log_{2}(nL))+o(\log(nL))\leavevmode\nobreak\ ,$

which in cases where $n>2^{h+e}$, can achieve better results in terms of
redundancy than Encoder 2.

##  VI Upper Bounds on the Code Cardinalities

In this section we consider upper bounds on the maximal cardinality of TE
codes, $(t,s)$-DC codes, and $(1,1,1)$-TED codes. These bounds are then
compared against the constructions presented in previous sections.

###  VI-A Upper Bounds on the Size of Tail-Erasure Codes

Let $\mathcal{A}_{\text{TE}}(n,d)$ denote the maximal cardinality of a
$(d-1)$-TE code over the set of $n\times(d-1)$ binary arrays. Let $A(n,d)$
denote the maximal cardinality of a binary vector code of length $n$ with
minimum Hamming distance $d$. The next observation follows, by noting that the
last column of any codeword in a $(d-1)$-TE code must have Hamming distance at
least $d$.

######  Claim 8.

$\mathcal{A}_{\text{TE}}(n,d)\leq A(n,d)\cdot 2^{n(d-2)}$.

###### Proof:

To prove the result, suppose
$\mathcal{C}_{TE}\subseteq\mathbb{F}_{2}^{n\times(d-1)}$ is an $(d-1)$-TE code
of maximal size. Next, decompose the codewords in $\mathcal{C}_{TE}$ into two
parts. Let $\mathcal{X}\subseteq\mathbb{F}_{2}^{n\times(d-2)}$ be equal to the
set of arrays that result by removing the last column from each of the
codeword arrays from $\mathcal{C}_{TE}$. For any $\textbf{Y}\in\mathcal{X}$,
let
$S_{\textbf{Y}}=\left\\{{\bm{v}}\in\mathbb{F}_{2}^{n}:\begin{bmatrix}\textbf{Y}&{\bm{v}}^{T}\end{bmatrix}\in\mathcal{C}_{TE}\right\\}$.
In other words, $S_{\textbf{Y}}$ is the set of vectors that can be appended to
Y as the last column to generate a codeword. Since $\mathcal{C}_{TE}$ can
correct $d-1$ TEs, that can all occur in the last column, it follows that the
minimum Hamming distance of the set of vectors in $S_{\textbf{Y}}$ is at least
$d$, which implies that for any $\textbf{Y}\in\mathbb{F}_{2}^{n\times(d-1)}$,
we have $\left|S_{\textbf{Y}}\right|\leq A(n,d)$. One can verify that
$|\mathcal{M}|\leq 2^{n(d-2)}$, and it follows that,

$\displaystyle\left|\mathcal{C}_{TE}\right|\\!=\\!\sum_{\textbf{Y}\in\mathcal{M}}|S_{\textbf{Y}}|\leq\sum_{\textbf{Y}\in\mathcal{M}}A(n,d)\leq
A(n,d)\cdot 2^{n(d-2)},$

which completes the proof.

∎

Using the notations of Section III-C, the above claim provides a simple lower
bound on $R_{\text{TE}}(n,d)$, which is

$R_{\text{TE}}(n,d)\geq
R(n,d)\geq\left\lceil\frac{d-1}{2}\right\rceil\log_{2}(n),$

where the second inequality is derived from the sphere packing bound for
vector codes of length $n$.

Next, a sphere packing bound is presented, which is tighter, but it is also
harder to compute for larger values of minimum $\rho_{\text{TE}}$-distance of
a TE code.

######  Lemma 4.

The volume of a ball of radius $r$ in $\mathbb{F}_{2}^{n\times L}$, under the
$\rho_{\text{TE}}$-metric, denoted as $V_{\text{TE}}(r)$, is given by

$\displaystyle
V_{\text{TE}}(r)=\sum_{k=0}^{r}\,\sum\limits_{\begin{subarray}{c}t_{1}+2t_{2}+\dots\\\
+k^{\prime}t_{k^{\prime}}=k\end{subarray}}\left({\binom{n}{t_{0},t_{1},t_{2},\dots,t_{k^{\prime}}}\cdot\prod_{i=1}^{k}2^{(i-1)t_{i}}}\right),$

where $k^{\prime}=\min\\{k,L\\}$.

Lemma 4 is the binary version of the one in [9, Proposition 1] and in [12,
Lemma 3], and since it was proved there, we omit the proof. A simplified
expression for the case where $e\leq L$ is given next.

######  Lemma 5.

The volume of a ball of radius $r$ in $\mathbb{F}_{2}^{n\times L}$, where
$r\leq L$ is,

$\displaystyle
V_{\text{TE}}(r)=1+\sum_{k=1}^{r}\sum_{i=1}^{k}\binom{n}{i}\binom{k-1}{i-1}2^{k-i}\leavevmode\nobreak\
.$

And $V_{\text{TE}}(0)$ is defined to be equal to $1$.

###### Proof:

Let $\bm{X}\in\mathbb{F}_{2}^{n\times L}$ and $k\leq n$ be the number of TEs
that occurred in $\bm{X}$. Moreover, let $i\leq k$ be the number of rows that
suffer from TEs in $\bm{X}$. Thus, there are $\binom{n}{i}$ possible
combinations of rows that suffer from those $k$ TEs, and for each such
possible combination of rows, there are $\binom{k-1}{i-1}$ ways to distribute
$k$ erasures into $i$ rows. Also, for each erroneous row, the first (leftmost)
erased bit is known (has to differ from $\bm{X}$), but the other bits
afterwards and until the end of the row, can be either $1$ or $0$. To
conclude, for each $k$ and $i$, there are
$\binom{n}{i}\binom{k-1}{i-1}2^{k-i}$ possible distinct
$\bm{Y}\in\mathbb{F}_{2}^{n\times L}$ such that
$\rho_{\text{TE}}(\bm{X},\bm{Y})=k$ and there are exactly $i$ distinct rows
between $\bm{X}$ and $\bm{Y}$. Then, the number of arrays
$\bm{Y}\in\mathbb{F}_{2}^{n\times L}$ such that
$\rho_{\text{TE}}(\bm{X},\bm{Y})=k$ is

$\sum_{i=1}^{k}\binom{n}{i}\binom{k-1}{i-1}2^{k-i}\leavevmode\nobreak\ ,$

which completes the proof.

∎

Equipped with the previous lemma, we can obtain the following sphere packing
bound.

######  Theorem 5.

Let $\mathcal{C}$ be a $(n\times L,M,d)_{\text{TE}}$ code. Then,

$\displaystyle M\cdot
V_{\text{TE}}\left(n,\left\lfloor(d-1)/2\right\rfloor\right)\leq 2^{n\cdot
L}\leavevmode\nobreak\ .$

Next are some examples for the size of the above volume.

######  Example 5.

The size of $V_{\text{TE}}(r)$, for $r=1,2,3$:

$\displaystyle V_{\text{TE}}(1)$ $\displaystyle=1+n,$ $\displaystyle
V_{\text{TE}}(2)$ $\displaystyle=1+\frac{n^{2}+5n}{2},$ $\displaystyle
V_{\text{TE}}(3)$ $\displaystyle=1+\frac{n^{3}+12n^{2}+29n}{6}.$

The results above are used to derive the bound from Theorem 5 for $d=3,5,7$,
and they achieve a tighter bound than the one in Claim 8, as can be verified
easily.

In Table I, one can find a summary of Corollary 1, Claims 4 and 5, Claim 8 and
Theorem 5. Finally, we note for completeness that in [9], a version of the
Singleton bound was derived for the $m$-metric, although it is mostly relevant
to cases of larger alphabets. The result is as follows.

######  Claim 9.

Let $\mathcal{C}$ be a $(n\times L,M,d)_{\text{TE}}$ code. Then, $d\leq
nL-\lceil\log_{2}(M)\rceil+1$.

###  VI-B Upper Bounds on the Cardinality of $(t,s)$-DC Codes

In the following subsection, three upper bounds on the cardinality of
$(t,s)$-DC codes are derived. First, we give an overview of the results, in
the order it will be proved afterwards through this section.

Moreover, a summary of the bounds for $(t,s)$-DC codes is in Table III. This
includes both the constructive upper bounds from Section IV and the lower
bounds that are derived next. Let $\mathcal{A}_{\text{DC}}(t,s)$ be the
largest cardinality of a $(t,s)$-DC code of dimension $n\times L$.
Furthermore, denote the largest cardinality of an $s$-deletion-correcting code
of vectors of length $L$ over ${\mathbb{F}}_{2}$ by $M_{s}(L)$.

######  Theorem 6.

The following are bounds on $\mathcal{A}_{\text{DC}}(t,s)$.

  1. 1.

For any positive integers $s,t$,

$\mathcal{A}_{\text{DC}}(t,s)\leq(M_{s}(L))^{t}\cdot
2^{L(n-t)}\leavevmode\nobreak\ .$

  2. 2.

For integers $t,s\geq 2$,

$\mathcal{A}_{\text{DC}}(t,s)\leq\frac{2^{nL}}{\left(\frac{n}{\lfloor
t/2\rfloor}\cdot{\left(\frac{L}{\lfloor s/2\rfloor}\right)}^{\lfloor
s/2\rfloor}\right)^{\lfloor t/2\rfloor}}\leavevmode\nobreak\ .$

  3. 3.

For an integer $t\geq 2$,

$\mathcal{A}_{\text{DC}}(t,1)\leq\frac{2^{nL}+1}{\left(\frac{n}{\lfloor
t/2\rfloor}\right)^{\lfloor t/2\rfloor}}\leavevmode\nobreak\ .$

The bounds in Theorem 6 imply lower bounds on the number of redundancy bits,
as summarized next.

######  Corollary 4.

The asymptotic lower bounds on the redundancy of a $(t,s)$-DC code are as
follows.

  1. 1.

$t(L-\log_{2}(M_{s}(L))$.

  2. 2.

$\lfloor t/2\rfloor(\log_{2}(n)+\lfloor s/2\rfloor\log_{2}(L))+O_{s,t}(1)$.

  3. 3.

$\lfloor t/2\rfloor\log_{2}(n)+O_{s,t}(1)$, for $s=1$.

Note that by observing the case of $s=1$, and comparing to the results in
Section IV-A, one can verify the following. First, in [33] a bound is
presented, such that $M_{1}(L)\leq\frac{2^{L}-2}{L-1}$, and therefore a lower
bound on the redundancy of a $(t,1)$-DC code is at least $t\log_{2}(L-1)$
bits, which is attained (up to one bit) in Construction 3, using an MDS code,
when $n\leq 2^{h}+1$. Secondly, when $n=c\cdot 2^{h}$ for some positive
integer $c$, the constructive bound from Construction 3 is $t\log_{2}(n)$,
which, compared to the third lower bound in Corollary 4, differ only by a
factor of 2.

Next, proofs for all the three bounds will be given, starting with the first
one. However, before the proofs, we give the definition of the _Fixed Length
Levenshtein_ (FLL) distance, as defined in [34], and repeated next. The FLL
distance between two binary words of length $n$, denoted as $d_{\ell}$, is
$s$, if a word $\bm{x}\in{\mathbb{F}}_{2}^{n}$ can be obtained from a word
$\bm{y}\in{\mathbb{F}}_{2}^{n}$ using $s$ deletions and $s$ insertions (where
$s$ is minimal).

###### Proof:

We want to show that $\mathcal{A}_{\text{DC}}(t,s)\leq(M_{s}(L))^{t}\cdot
2^{L(n-t)}$. Let $\mathcal{A}^{\prime}_{\text{DC}}(t,s)$ denote the largest
cardinality of a $(t,s)$-DC code, where the deletions can only occur in the
first $t$ rows. Since every $(t,s)$-DC code can also, in particular, correct
$(t,s)$-DC errors when they occur specifically in the first $t$ rows,
$\mathcal{A}_{\text{DC}}(t,s)\leq\mathcal{A}^{\prime}_{\text{DC}}(t,s)$, and
thus providing an upper bound for $\mathcal{A}^{\prime}_{\text{DC}}(t,s)$ is
also an upper bound for $\mathcal{A}_{\text{DC}}(t,s)$.

Next, let $\mathcal{C}$ be a $(t,s)$-DC code, where the deletions can only
occur in the first $t$ rows, and of cardinality
$\mathcal{A}^{\prime}_{\text{DC}}(t,s)$. We partition $\mathcal{C}$ into at
most $2^{L(n-t)}$ subcodes, such that any two codewords arrays,
$\bm{X},\bm{Y}\in\mathcal{C}_{\text{DC}}$, that belong to the same subcode,
have their last $n-t$ rows identical. But, since $\bm{X},\bm{Y}$ belong to a
code that corrects $(t,s)$-DC pattern in the first $t$ rows, $\bm{X}_{[1:t]}$
and $\bm{Y}_{[1:t]}$, the subarrays of $\bm{X}$ and $\bm{Y}$ that are obtained
only from their first $t$ rows, belong to a $(t,s)$-DC code over
${\mathbb{F}}_{2}^{t\times L}$. Thus, the cardinality of each subcode is at
most $D(t,s,L)$, where $D(t,s,L)$ is the largest cardinality of a $(t,s)$-DC
code over ${\mathbb{F}}_{2}^{t\times L}$, and there are $2^{L(n-t)}$ subcodes,
which imply
$\mathcal{A}_{\text{DC}}(t,s)\leq\mathcal{A}^{\prime}_{\text{DC}}(t,s)\leq
D(t,s,L)\cdot 2^{L(n-t)}$, and we wish to prove that
$D(t,s,L)\leq(M_{s}(L))^{t}$.

We provide a proof by induction on $t$. First, for $t=1$, the code is over
vectors of length $L$, and therefore the inequality $D(1,s,L)\leq M_{s}(L)$ is
given by definition. Next, we prove that if $D(i,s,L)\leq(M_{s}(L))^{i}$, then
$D(i+1,s,L)\leq(M_{s}(L))^{i+1}$. Let $\mathcal{C}$ be an $(i+1,s)$-DC code
over ${\mathbb{F}}_{2}^{(i+1)\times L}$ of cardinality $D(i+1,s,L)$, and let
$\bm{X}^{1}$ denote the set of all possible rows of the first row in
$\mathcal{C}$. If $|\bm{X}^{1}|\leq M_{s}(L)$, then for every
$\bm{x}^{1}\in\bm{X}^{1}$, denote by
$\mathcal{C}(\bm{x}^{1})\subset\mathcal{C}$, the subcode of $\mathcal{C}$, in
which the first row of every codeword array in $\mathcal{C}(\bm{x}^{1})$ is
$\bm{x}^{1}$. Note that $\mathcal{C}(\bm{x}^{1})$ can correct $s$ deletions in
each of its $i+1$ rows, as a subcode of $\mathcal{C}$, and since for every
codeword in $\mathcal{C}(\bm{x}^{1})$, its first row remains the same, it is
necessary that the last $i$ rows of every codeword in
$\mathcal{C}(\bm{x}^{1})$ be an $(i,s)$-DC correcting code, or else there
exists a pattern of deletions that one cannot recover from. Therefore,
$|\mathcal{C}(\bm{x}^{1})|\leq D(i,s,L)$, which by the induction step, yields
$|\mathcal{C}(\bm{x}^{1})|\leq(M_{s}(L))^{i}$, and since $|\bm{X}^{1}|\leq
M_{s}(L)$, we get that $D(i+1,s,L)=|\mathcal{C}|\leq(M_{s}(L))^{i+1}$.

Next, if $|\bm{X}^{1}|>M_{s}(L)$, we will construct, in a greedy manner,
another $(i+1,s)$-DC code, denoted as $\overline{\mathcal{C}}$, where
$|\overline{\mathcal{C}}|=|\mathcal{C}|$, and its set of all possible rows of
the first row for the code $\overline{\mathcal{C}}$, denoted
$\overline{{\bm{X}}}^{1}$, is of cardinality at most $M_{s}(L)$, which then
will finish the proof. First, arbitrarily choose any
$\bm{y}_{1}\in\overline{{\bm{X}}}^{1}$, and define the set
$Y_{\bm{y}_{1}}=\left\\{\bm{y}\in\overline{{\bm{X}}}^{1}\colon
d_{\ell}(\bm{y},\bm{y}_{1})\leq s\right\\}$, i.e., all the row vectors in
$\overline{{\bm{X}}}^{1}$, that can be reached from $\bm{y}_{1}$ after at most
$s$ deletions and insertions. Note that the set $Y_{\bm{y}_{1}}$ contains
$\bm{y}_{1}$. Next, we select any vector
$\bm{y}_{2}\in\overline{{\bm{X}}}^{1}\setminus Y_{\bm{y}_{1}}$, and we define
the set $Y_{\bm{y}_{2}}=\left\\{\bm{y}\in\overline{{\bm{X}}}^{1}\setminus
Y_{\bm{y}_{1}}\colon d_{\ell}(\bm{y},\bm{y}_{2})\leq s\right\\}$.

We keep repeating this procedure until we have $\nu$ sets $Y_{\bm{y}_{1}}$,
$Y_{\bm{y}_{2}}$, $\ldots,$ $Y_{\bm{y}_{\nu}}$ (which are disjoint by design)
and where $Y_{\bm{y}_{1}}\cup\cdots\cup
Y_{\bm{y}_{\nu}}=\overline{{\bm{X}}}^{1}$. By design,
$\\{\bm{y}_{i}\\}_{i=1}^{\nu}$ is an $s$-deletion-correcting code and so
$\nu\leq M_{s}(L)$.

Let $\mathcal{C}(\\{\bm{y}_{1},\bm{y}_{2},\ldots,\bm{y}_{k}\\})$ be the
subcode of $\mathcal{C}$, where the first row of every codeword array in
$\mathcal{C}(\\{\bm{y}_{1},\bm{y}_{2},\ldots,\bm{y}_{k}\\})$ belongs to the
set $\\{\bm{y}_{1},\bm{y}_{2},\ldots,\bm{y}_{k}\\}$. Then, let
$\overline{\mathcal{C}}$ be defined in the following way. For every
$i\in[\nu]$, we take all the codewords in $\mathcal{C}(Y_{\bm{y}_{i}})$, add
those to $\overline{\mathcal{C}}$, and set their first row as $\bm{y}_{i}$.

We claim that $|\overline{\mathcal{C}}|=|\mathcal{C}|$ and that
$\overline{\mathcal{C}}$ is an $(i+1,s)$-DC code.

  1. 1.

Assume, for the sake of contradiction, that $\overline{\mathcal{C}}$ is not an
$(i+1,s)$-DC code. Then, there exists
$\overline{\bm{X}},\overline{\bm{Y}}\in\overline{\mathcal{C}}$ such that these
arrays are confusable after a pattern of $(i+1,s)$ deletions. Specifically, it
means that their first rows, $\overline{\bm{x}}_{1},\overline{\bm{y}}_{1}$ are
confusable after $s$ deletions, and thus
$\overline{\bm{x}}_{1}=\overline{\bm{y}}_{1}$ as we chose the first row
vectors from an $s$-deletion-correcting code. Hence, in $\mathcal{C}$, there
exist $\bm{X},\bm{Y}$ such that $\bm{X}$ and $\overline{\bm{X}}$ coincide on
the last $i$ rows, and the same is true for $\bm{Y}$ and $\overline{\bm{Y}}$.
However, since $\overline{\bm{x}}_{1}=\overline{\bm{y}}_{1}$, the first row of
$\bm{X}$ and the first row of $\bm{Y}$ belong to the same set $Y_{i}$, which
implies that $\bm{x}_{1},\bm{y}_{1}$ are confusable after $s$ deletions, and
since $\mathcal{C}$ is an $(i+1,s)$-DC code, the last $i$ rows of $\bm{X}$ and
$\bm{Y}$ cannot be confusable after a pattern of $(i,s)$ deletions, which also
implies that $\overline{\bm{X}}$ and $\overline{\bm{Y}}$ cannot be confusable,
as they have the same last $i$ rows. In turn, this means that
$\overline{\bm{X}}$ and $\overline{\bm{Y}}$ are not confusable after $(i+1,s)$
deletions, and therefore a contradiction.

  2. 2.

We show that $|\overline{\mathcal{C}}|=|\mathcal{C}|$. Since every codeword of
$\overline{\mathcal{C}}$ was constructed from a unique codeword in
$\mathcal{C}$, it implies a surjective function from $\mathcal{C}$ to
$\overline{\mathcal{C}}$ and thus $|\overline{\mathcal{C}}|\leq|\mathcal{C}|$.
Next, suppose, for the sake of contradiction, that
$|\overline{\mathcal{C}}|<|\mathcal{C}|$, i.e., the function is not injective.

Then, we will have two codewords in $\mathcal{C}$ that differ only in their
first row (which was the only row that was changed), where one is $\bm{u}\in
Y_{i}$ and the other is $\bm{v}\in Y_{i}$. In this case, a pattern of
$s$-deletions in the first row results two confusable arrays, a contradiction
to $\mathcal{C}$ being an $(i+1,s)$-DC code.

To conclude, we constructed $\overline{\mathcal{C}}$, an $(i+1,s)$-DC code,
where $|\overline{\mathcal{C}}|=|\mathcal{C}|$, and its set of possible first
rows is of cardinality at most $M_{s}(L)$. Thus,
$|\overline{{\bm{X}}}^{1}|\leq M_{s}(L)$ and
$D(i+1,s,L)=|\mathcal{C}|\leq(M_{s}(L))^{i+1}$.

∎

Next, a proof for the second bound is given. Since the second bound uses a
sphere packing argument, a definition of a distance function is defined first.
To do that, we will use the FLL distance.

######  Definition 7.

Let $\bm{X},\bm{Y}\in{\mathbb{F}}_{2}^{n\times L}$ and $s\geq 0$ is an
integer. Then,

$\displaystyle d_{s\text{-DC}}(\bm{X},\bm{Y})=\begin{cases}\infty&\text{if
}\exists i\\!\in\\![n]\colon d_{\ell}(\bm{x}_{i},\bm{y}_{i})\\!>\\!s,\\\
|\\{i\colon\bm{x}_{i}\neq\bm{y}_{i}\\}|&\text{otherwise}.\end{cases}$

######  Remark 5.

If $s=0$, then for any $\bm{X},\bm{Y}\in{\mathbb{F}}_{2}^{n\times L}$,

$d_{0\text{-DC}}(\bm{X},\bm{Y})=\begin{cases}\infty&\text{if
}\bm{X}\neq\bm{Y}\leavevmode\nobreak\ ,\\\ 0&\text{otherwise}.\end{cases}$

The following theorem states the important connection between Definition 7 and
$(t,s)$-DC codes.

######  Theorem 7.

A code $\mathcal{C}_{s\text{-DC}}\subseteq{\mathbb{F}}_{2}^{n\times L}$ is a
$(t,s)$-DC code if and only if every
$\bm{X},\bm{Y}\in\mathcal{C}_{s\text{-DC}}$ satisfy
$d_{s\text{-DC}}(\bm{X},\bm{Y})>t$.

###### Proof:

First, let $\bm{X},\bm{Y}\in\mathcal{C}_{s\text{-DC}}$ and assume for the sake
of contradiction that $d_{s\text{-DC}}(\bm{X},\bm{Y})\leq t$. This implies
that there are only $w\leq t$ indices of rows, denoted as
$\mathcal{I}=\\{i_{1},\ldots,i_{w}\\}$, such that
$\bm{x}_{i_{j}}\neq\bm{y}_{i_{j}}$ for every $i_{j}\in\mathcal{I}$, and
$\bm{x}_{k}=\bm{y}_{k}$ for every $k\notin\mathcal{I}$. Moreover, it also
implies that $1\leq d_{\ell}(\bm{x}_{i_{j}},\bm{y}_{i_{j}})\leq s$ for every
$i_{j}\in\mathcal{I}$. Thus, for every row index $i_{j}\in\mathcal{I}$, one
can delete $s$ bits in $\bm{x}_{i_{j}}$ and $s$ bits in $\bm{y}_{i_{j}}$ such
that the resulted $(L-s)$-length rows are indistinguishable, as was stated in
[34]. Since $|\mathcal{I}|\leq t$, there exists a pattern of $(t,s)$ deletions
(i.e., choosing $t$ rows and then choose $s$ bits to delete in each of them)
on $\bm{X}$ and another pattern of $(t,s)$ deletions (over the same row
indices) on $\bm{Y}$, such that the resulted erroneous (punctured) arrays are
indistinguishable, which is a contradiction for $\bm{X},\bm{Y}$ being both
codewords of $\mathcal{C}_{s\text{-DC}}$.

Conversely, let $\mathcal{C}_{s\text{-DC}}$ be a code where every
$\bm{X},\bm{Y}\in\mathcal{C}_{s\text{-DC}}$ satisfy
$d_{s\text{-DC}}(\bm{X},\bm{Y})>t$, and we will show that it is a $(t,s)$-DC
code. Assume, for the sake of contradiction, that there exist two patterns of
$(t,s)$ deletions, $P_{1}$ and $P_{2}$, such that $\bm{X}$ suffers from
deletions according to $P_{1}$ and $\bm{Y}$ suffers from deletions according
to $P_{2}$, but the resulted erroneous arrays are indistinguishable. Then,
both $P_{1}$ and $P_{2}$ caused deletions in the same $w\leq t$ rows, so we
denote the indices of those rows as $\mathcal{I}=\\{i_{1},\ldots,i_{w}\\}$.
First, note that $\bm{x}_{i_{j}}=\bm{y}_{i_{j}}$ for every
$i_{j}\notin\mathcal{I}$. Also, since every $i_{j}$-th row, where
$i_{j}\in\mathcal{I}$, suffer at most $s$ deletions, it implies
$d_{\ell}(\bm{x}_{i_{j}},\bm{y}_{i_{j}})\leq s$, otherwise the resulted
erroneous arrays cannot be indistinguishable. But, this means that $\forall
i\in[n]\colon d_{\ell}(\bm{x}_{i},\bm{y}_{i})\leq s$ (either the rows are the
same, or they differ by at most $s$ deletions), and there are at most $t$ rows
such that $d_{\ell}(\bm{x}_{i},\bm{y}_{i})\geq s$, which is a contradiction,
since $d_{s\text{-DC}}(\bm{X},\bm{Y})>t$.

∎

Following is the definition for the volume of a ball, using the distance
function $d_{s\text{-DC}}$.

######  Definition 8.

Let $\bm{X}\in{\mathbb{F}}_{2}^{n\times L}$. Then, the volume of an
$(\tau,\sigma)$-ball, centered at $\bm{X}$, using the distance function
$d_{s\text{-DC}}$, is as follows,

$\displaystyle\text{V}_{\text{DC}}(\sigma,\tau,\bm{X})=\\{\bm{Y}\in{\mathbb{F}}_{2}^{n\times
L}\colon d_{\sigma\text{-DC}}(\bm{X},\bm{Y})\leq\tau\\}\leavevmode\nobreak\ .$

A sphere packing argument follows immediately.

######  Theorem 8.

Let $\mathcal{C}_{s\text{-DC}}=\\{\bm{X}_{i}\\}_{i=1}^{M}$ be a $(t,s)$-DC
code of cardinality $M$. Then,

$\displaystyle\sum_{i=1}^{M}\left|\text{V}_{\text{DC}}(\lfloor
t/2\rfloor,\lfloor s/2\rfloor,\bm{X}_{i})\right|\leq
2^{nL}\leavevmode\nobreak\ .$

###### Proof:

It is sufficient to prove that the $(\lfloor t/2\rfloor,\lfloor
s/2\rfloor)$-balls around each codeword, do not intersect. Assume, for the
sake of contradiction, that there exists $\bm{Y}\in{\mathbb{F}}_{2}^{n\times
L}$, such that

$\displaystyle\bm{Y}\in\text{V}_{\text{DC}}(\lfloor t/2\rfloor,\lfloor
s/2\rfloor,\bm{X}_{i})\leavevmode\nobreak\ \cap$
$\displaystyle\text{V}_{\text{DC}}(\lfloor t/2\rfloor,\lfloor
s/2\rfloor,\bm{X}_{j}).$

Since $d_{\lfloor s/2\rfloor\text{-DC}}(\bm{Y},\bm{X}_{i})$ is finite, there
are at most $\lfloor t/2\rfloor$ distinct rows between $\bm{Y}$ and
$\bm{X}_{i}$, and their FLL distance is at most $\lfloor s/2\rfloor$. Also,
since $d_{s\text{-DC}}(\bm{Y},\bm{X}_{j})$ is finite, there are at most
$\lfloor t/2\rfloor$ distinct rows between $\bm{Y}$ and $\bm{X}_{j}$, and
their FLL distance is at most $\lfloor s/2\rfloor$.

Combining those two observations, there are at most $2\lfloor t/2\rfloor\leq
t$ distinct rows between $\bm{X}_{i}$ and $\bm{X}_{j}$, and their FLL distance
is at most $2\lfloor s/2\rfloor\leq s$. But this means that
$d_{s\text{-DC}}(\bm{X}_{i},\bm{X}_{j})\leq t$, which is a contradiction to
Theorem 7.

∎

Since
$\text{V}_{\text{DC}}(r_{1},r_{2},\bm{X})\\!=\\!\dot{\bigcup}_{i=0}^{r_{1}}\\{\bm{Y}\\!\colon
d_{r_{2}\text{-DC}}(\bm{X},\bm{Y})\\!=\\!i\\}$, the next claim will be a step
towards estimating the volume of a ball.

######  Claim 10.

Let $\bm{X}\in{\mathbb{F}}_{2}^{n\times L}$. Then, for any positive integer
$s$, $|\\{\bm{Y}\colon
d_{s\text{-DC}}(\bm{X},\bm{Y})=t\\}|\geq\binom{n}{t}{\binom{L}{s}}^{t}$.

###### Proof:

First, each $\bm{Y}$ such that $d_{s\text{-DC}}(\bm{X},\bm{Y})=t$ is composed
of $t$ row indices $\mathcal{I}=\\{i_{1},\ldots,i_{t}\\}$ where
$d_{\ell}(\bm{x}_{i},\bm{y}_{i})\leq s$ and all the other row indices,
$j\in[n]\setminus\mathcal{I}$, satisfy $\bm{x}_{i}=\bm{y}_{i}$. Therefore, one
can divide those binary arrays $\bm{Y}$ into $\binom{n}{t}$ distinct sets,
that differ by their indices set $\mathcal{I}$. Next, let $\mathcal{I}$ be one
of these sets of indices. Then, the cardinality of
$\mathcal{B}_{\mathcal{I}}(\bm{X})=\\{\bm{Y}\mid\forall i\in\mathcal{I}\colon
d_{\ell}(\bm{x}_{i},\bm{y}_{i})\leq s,\text{ and }\forall
i\notin\mathcal{I}\colon\bm{x}_{i}=\bm{y}_{i}\\}$ is
$\prod_{i\in\mathcal{I}}|\mathcal{L}_{s}(\bm{x}_{i})|$, where
$\mathcal{L}_{s}(\bm{x}_{i})=\\{\bm{y}_{i}\colon
d_{\ell}(\bm{x}_{i},\bm{y}_{i})\leq s\\}$. Using [34, Corollary 3],
$|\mathcal{L}_{s}(\bm{x}_{i})|\geq\binom{L}{s}$ and thus
$\prod_{i\in\mathcal{I}}|\mathcal{L}_{s}(\bm{x}_{i})|\geq{\binom{L}{s}}^{t}$.
Since there are $\binom{n}{t}$ distinct sets, we conclude the proof.

∎

######  Remark 6.

It is clear from Remark 5 that for any positive integer $t$, $|\\{\bm{Y}\colon
d_{0\text{-DC}}(\bm{X},\bm{Y})=t\\}|=0$, and thus
$|\text{V}_{\text{DC}}(r,0,\bm{X})|=1$ for any integer $r$.

Next, a lemma is given, to conclude a lower bound for the volume of a ball.

######  Lemma 6.

Let $\bm{X}\in{\mathbb{F}}_{2}^{n\times L}$. Then, for any integer $s\geq 2$.

$\displaystyle|\text{V}_{\text{DC}}(\lfloor t/2\rfloor,\lfloor
s/2\rfloor,\bm{X})|\geq\sum_{i=0}^{\lfloor
t/2\rfloor}\binom{n}{i}{\binom{L}{\lfloor s/2\rfloor}}^{i}\leavevmode\nobreak\
.$

###### Proof:

Using Definition 8 and Claim 10,

$\displaystyle|\text{V}_{\text{DC}}(\lfloor t/2\rfloor,\lfloor
s/2\rfloor,\bm{X})|$ $\displaystyle=\sum_{i=0}^{\lfloor
t/2\rfloor}|\\{\bm{Y}\colon d_{(\lfloor
s/2\rfloor)\text{-DC}}(\bm{X},\bm{Y})=i\\}|$
$\displaystyle\geq\sum_{i=0}^{r}\binom{n}{i}{\binom{L}{\lfloor
s/2\rfloor}}^{i}\leavevmode\nobreak\ .$

∎

Next, follows the proof of the second bound.

###### Proof:

We show that if $\mathcal{C}_{s\text{-DC}}$ is a $(t,s)$-DC code,
$|\mathcal{C}_{s\text{-DC}}|=M$, $s\geq 2$, then,

$\displaystyle M\cdot\left(\frac{n}{\lfloor
t/2\rfloor}\cdot{\left(\frac{L}{\lfloor s/2\rfloor}\right)}^{\lfloor
s/2\rfloor}\right)^{\lfloor t/2\rfloor}\leq 2^{nL}\leavevmode\nobreak\ .$

Using Theorem 8,

$\displaystyle
2^{nL}\geq\sum_{i=1}^{M}\left|\text{V}_{s\text{-DC}}\left(\left\lfloor\frac{t}{2}\right\rfloor,\bm{X}_{i}\right)\right|\leavevmode\nobreak\
.$

Then, from Lemma 6,

$\displaystyle\sum_{i=1}^{M}\left|\text{V}_{s\text{-DC}}\left(\left\lfloor\frac{t}{2}\right\rfloor,\bm{X}_{i}\right)\right|\geq
M\cdot\sum_{i=0}^{\lfloor t/2\rfloor}\binom{n}{i}{\binom{L}{\lfloor
s/2\rfloor}}^{i}\leavevmode\nobreak\ .$

Then,

$\displaystyle M\cdot\sum_{i=0}^{\lfloor
t/2\rfloor}\binom{n}{i}{\binom{L}{\left\lfloor\frac{s}{2}\right\rfloor}}^{i}\geq
M\binom{n}{\left\lfloor\frac{t}{2}\right\rfloor}{\binom{L}{\left\lfloor\frac{s}{2}\right\rfloor}}^{\left\lfloor\frac{t}{2}\right\rfloor}\leavevmode\nobreak\
.$

And to conclude,

$\displaystyle
M\binom{n}{\left\lfloor\frac{t}{2}\right\rfloor}{\binom{L}{\left\lfloor\frac{s}{2}\right\rfloor}}^{\left\lfloor\frac{t}{2}\right\rfloor}\geq
M\left(\frac{n}{\left\lfloor\frac{t}{2}\right\rfloor}\\!\cdot\\!{\left(\frac{L}{\left\lfloor\frac{s}{2}\right\rfloor}\right)}^{\left\lfloor\frac{s}{2}\right\rfloor}\right)^{\left\lfloor\frac{t}{2}\right\rfloor}\leavevmode\nobreak\
.$

∎

Finally, the third bound is derived. It is needed, in addition to the previous
bound, since, as one can observe, the previous bound is not useful for the
$(t,1)$-DC case. Firstly, a definition of a simple distance function between
vectors is given.

######  Definition 9.

Let $\bm{x},\bm{y}\in{\mathbb{F}}_{2}^{L}$. Then,

$\displaystyle d^{1}(\bm{x},\bm{y})=\begin{cases}\infty&\text{if }\exists
j\in\\{2,\ldots,L\\}\colon x_{j}\neq y_{j}\leavevmode\nobreak\ ,\\\ 1&\text{if
}x_{1}\neq y_{1}\text{ and }\forall j\\!\in\\!\\{2,\ldots,L\\}\colon
x_{j}=y_{j}\leavevmode\nobreak\ ,\\\ 0&\text{otherwise}\leavevmode\nobreak\
.\end{cases}$

Then, based on the above distance function, a definition of a distance
function for arrays is given.

######  Definition 10.

Let $\bm{X},\bm{Y}\in{\mathbb{F}}_{2}^{n\times L}$. Then,

$\displaystyle d^{1}_{\text{DC}}(\bm{X},\bm{Y})=\begin{cases}\infty&\text{if
}\exists i\in[n]\colon d^{1}(\bm{x}_{i},\bm{y}_{i})\\!=\\!\infty,\\\
|\\{i\colon
d^{1}(\bm{x}_{i},\bm{y}_{i})=1\\}|&\text{otherwise}\leavevmode\nobreak\
.\end{cases}$

The next theorem demonstrates the relationship between the distance function
$d^{1}_{\text{DC}}$ and $(t,1)$-DC codes.

######  Theorem 9.

Let $\mathcal{C}_{\text{DC}}\subseteq{\mathbb{F}}_{2}^{n\times L}$ be a
$(t,1)$-DC code. Then, every $\bm{X},\bm{Y}\in\mathcal{C}_{\text{DC}}$ satisfy
$d^{1}_{\text{DC}}(\bm{X},\bm{Y})>t$.

###### Proof:

Assume, for the sake of contradiction, that there exists
$\bm{X},\bm{Y}\in\mathcal{C}_{\text{DC}}$ such that
$d^{1}_{\text{DC}}(\bm{X},\bm{Y})\leq t$. Then, since the distance is finite,
$\forall i\in[n]\colon d^{1}(\bm{x}_{i},\bm{y}_{i})\leq 1$. But since
$d^{1}_{\text{DC}}(\bm{X},\bm{Y})\leq t$, there are $w\leq t$ row indices,
denoted as $\mathcal{I}$, in which $d^{1}(\bm{x}_{i},\bm{y}_{i})=1$ for all
$i\in\mathcal{I}$. Moreover, all $\forall
j\notin\mathcal{I}\colon\bm{x}_{j}=\bm{y}_{j}$. Thus, a deletion in the first
bit of all the $w$ rows, whose indices are in $\mathcal{I}$, which is a valid
pattern of a $(t,1)$-DC error, will yield the same punctured arrays from
$\bm{X}$ and $\bm{Y}$, which is a contradiction for $\mathcal{C}_{\text{DC}}$
being a $(t,1)$-DC code.

∎

Following, as in the previous bound, is a sphere packing argument, starting
with a definition of a ball.

######  Definition 11.

Let $\bm{X}\in{\mathbb{F}}_{2}^{n\times L}$. Then, the volume of a ball of
radius $r$, centered at $\bm{X}$, using the distance function
$d^{1}_{\text{DC}}$, is $\text{V}^{1}_{\text{DC}}(r,\bm{X})=\\{\bm{Y}\colon
d^{1}_{\text{DC}}(\bm{X},\bm{Y})\leq r\\}.$

Next, we prove the connection between balls in the Hamming distance and balls
in the $d^{1}_{\text{DC}}$ distance.

######  Claim 11.

Let $\bm{X}\in{\mathbb{F}}_{2}^{n\times L}$. Then, using $\text{V}_{2}(r,n)$
as defined in [26, Section 4.2]

$\displaystyle|\text{V}^{1}_{\text{DC}}(r,\bm{X})|=\text{V}_{2}(r,n)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\sum_{i=0}^{r}\binom{n}{i}\leavevmode\nobreak\
$

###### Proof:

Since any two arrays $\bm{X},\bm{Y}\in{\mathbb{F}}_{2}^{n\times L}$ for which
their $d^{1}_{\text{DC}}$ distance is finite, can differ only by bits in the
first column, and then their $d^{1}_{\text{DC}}$ is equal to the Hamming
distance of their first column, there is a clear bijection between the volume
of balls in the Hamming distance, $\text{V}_{2}(r,n)$, and the volume of balls
in the $d^{1}_{\text{DC}}$ distance function,
$|\text{V}^{1}_{\text{DC}}(r,\bm{X})|$.

∎

Finally, the proof for the third bound follows.

###### Proof:

We show that if $\mathcal{C}_{\text{DC}}$ is a $(t,1)$-DC code of cardinality
$M$, then,

$\displaystyle M\cdot\text{V}_{2}(\lfloor t/2\rfloor,n)\leq
2^{nL}\leavevmode\nobreak\ .$

Again, it is sufficient to prove that the balls
$\text{V}^{1}_{\text{DC}}(\lfloor t/2\rfloor,\cdot)$ around codewords of
$\mathcal{C}_{\text{DC}}$ do not intersect. Assume, for the sake of
contradiction, that there exist an array

$\bm{Y}\in\text{V}^{1}_{\text{DC}}(\lfloor
t/2\rfloor,\bm{X}_{1})\cap\text{V}^{1}_{\text{DC}}(\lfloor
t/2\rfloor,\bm{X}_{2})\leavevmode\nobreak\ ,$

where $\bm{X}_{1},\bm{X}_{2}\in\mathcal{C}_{\text{DC}}$. Thus,
$d^{1}_{\text{DC}}(\bm{X}_{1},\bm{Y})<\infty$ and
$d^{1}_{\text{DC}}(\bm{X}_{1},\bm{Y})<\infty$, which implies that there are at
most $\lfloor t/2\rfloor$ indices of rows where $\bm{X}_{1}$ and $\bm{Y}$
differ only in the first bit of the row, and the same is true for $\bm{X}_{1}$
and $\bm{Y}$. Therefore, there are at most $t$ rows in which $\bm{X}_{1}$ and
$\bm{X}_{2}$ differ in their first bit, and all the other bits in those arrays
are the same. So $d^{1}_{\text{DC}}(\bm{X}_{1},\bm{X}_{1})<t$, thus a
contradiction to Theorem 9.

∎

###  VI-C Upper Bounds on the Size of $(1,1,1)$-TED Codes

In order to investigate whether a code is optimal in terms of redundancy, a
few notations are introduced.

######  Definition 12.

Let $\bm{X}\in{\mathbb{F}}_{2}^{n\times L}$, and also denote
$D^{\downarrow\uparrow}_{i}(\bm{X})\subset{\mathbb{F}}_{2}^{n\times L}$ as the
set of all possible arrays that can be received after deleting any bit from
the $i$-th row of $\bm{X}$, and then inserting an arbitrary bit at the end of
the same row of the resulting array.

Let $B_{\text{Del}}(\bm{x}_{i})\subset{\mathbb{F}}_{2}^{L-1}$ be the
$1$-deletion error ball of the $i$-th row of $\bm{X}$, i.e., the set of
vectors that are obtained by removing one bit from $\bm{x}_{i}$. Moreover, let
$(\bm{x}_{i})^{\prime}\in B_{\text{Del}}(\bm{x}_{i})$ be the vector that is
obtained by one TE, i.e., $(\bm{x}_{i})^{\prime}=(x_{i,1},\ldots,x_{i,L-1})$.
Therefore, for every $\bm{Z}\in D^{\downarrow\uparrow}_{i}(\bm{X})$, from the
way $\bm{Z}$ is defined, $(\bm{z}_{i})^{\prime}\in
B_{\text{Del}}(\bm{x}_{i})$. That is, $\bm{Z}\in
D^{\downarrow\uparrow}_{i}(\bm{X})$ with the last element in the $i$-th row
deleted, is a possible outcome of $\bm{X}$ after being transmitted through the
$(1,1,1)$-TED channel.

######  Example 6.

Let

$\bm{X}=\begin{bmatrix}0&1&1\\\ 1&1&0\\\ 0&0&1\\\
\end{bmatrix},\leavevmode\nobreak\ \bm{Y}=\begin{bmatrix}1&1&0\\\ 0&1&1\\\
0&0&1\\\ \end{bmatrix}\leavevmode\nobreak\ .$

Then,

$\displaystyle D^{\uparrow\downarrow}_{1}(\bm{X})\\!$
$\displaystyle=\\!\left\\{\\!\begin{bmatrix}0&1&1\\\ 1&1&0\\\ 0&0&1\\\
\end{bmatrix}\\!,\\!\begin{bmatrix}0&1&0\\\ 1&1&0\\\ 0&0&1\\\
\end{bmatrix}\\!,\\!\begin{bmatrix}1&1&0\\\ 1&1&0\\\ 0&0&1\\\
\end{bmatrix}\\!,\\!\begin{bmatrix}1&1&1\\\ 1&1&0\\\ 0&0&1\\\
\end{bmatrix}\\!\right\\}$ $\displaystyle
D^{\uparrow\downarrow}_{2}(\bm{Y})\\!$
$\displaystyle=\\!\left\\{\\!\begin{bmatrix}1&1&0\\\ 0&1&1\\\ 0&0&1\\\
\end{bmatrix}\\!,\\!\begin{bmatrix}1&1&0\\\ 0&1&0\\\ 0&0&1\\\
\end{bmatrix}\\!,\\!\begin{bmatrix}1&1&0\\\ 1&1&0\\\ 0&0&1\\\
\end{bmatrix}\\!,\\!\begin{bmatrix}1&1&0\\\ 1&1&1\\\ 0&0&1\\\
\end{bmatrix}\\!\right\\}.$

We want to show that $\bm{X}$ and $\bm{Y}$ cannot belong to the same
$(1,1,1)$-TED code. Indeed, assume, for sake of contradiction, that they do.
Let

$\bm{Z}=\begin{bmatrix}1&1&0\\\ 1&1&0\\\ 0&0&1\\\ \end{bmatrix}\in
D^{\uparrow\downarrow}_{1}(\bm{X})\cap
D^{\uparrow\downarrow}_{2}(\bm{Y})\leavevmode\nobreak\ .$

Therefore, let the array

$\widetilde{\bm{Z}}=\begin{bmatrix}1&1&\bullet\\\ 1&1&\bullet\\\ 0&0&1\\\
\end{bmatrix}\leavevmode\nobreak\ ,$

be an output of the $(1,1,1)$-TED channel, i.e., $\bm{Z}$ with the first two
rows suffer from a TE. Then, one cannot distinguish between the cases of a
deletion in the first row of $\bm{X}$ and a TE in the second, and a TE in the
first row of $\bm{Y}$ and a deletion in the second. Thus, $\bm{X}$ and
$\bm{Y}$ cannot belong to the same $(1,1,1)$-TED code.

Next, let
$\mathcal{D}^{\uparrow\downarrow}(\bm{X})=\bigcup_{i=1}^{n}D^{\uparrow\downarrow}_{i}(\bm{X})$
and the next claim follows, which generalize the previous example.

######  Claim 12.

Let $\mathcal{C}\subseteq{\mathbb{F}}_{2}^{n\times L}$ be a $(1,1,1)$-TED
code. Then, for any distinct $\bm{X},\bm{Y}\in\mathcal{C}$,

$\displaystyle\mathcal{D}^{\uparrow\downarrow}(\bm{X})\cap\mathcal{D}^{\uparrow\downarrow}(\bm{Y})=\emptyset\leavevmode\nobreak\
.$

###### Proof:

We need to show that for any distinct $\bm{X},\bm{Y}\\!\in\\!\mathcal{C}$, we
have $D^{\uparrow\downarrow}_{i_{1}}(\bm{X})\cap
D^{\uparrow\downarrow}_{i_{2}}(\bm{Y})=\emptyset$, for any arbitrary row
indices $i_{1},i_{2}$. Assume, for sake of contradiction, that there exists an
array $\bm{Z}\in D^{\uparrow\downarrow}_{i_{1}}(\bm{X})\cap
D^{\uparrow\downarrow}_{i_{2}}(\bm{Y})$. If $i_{1}=i_{2}$, then it implies
that for any other row than the $i_{1}$-th row, $\bm{X}$ and $\bm{Y}$
coincide, and that $B_{\text{Del}}(\bm{x}_{i})\cap
B_{\text{Del}}(\bm{y}_{i})\neq\emptyset$, and therefore there is a deletion in
the $i_{1}$-th row that cannot be recovered, while any deletion in the other
rows cannot be recovered, and therefore the contradiction. Next, assume
$i_{1}\neq i_{2}$. This implies again that $\bm{X}$ and $\bm{Y}$ coincide on
any row other than $i_{1},i_{2}$. Moreover, $\bm{z}_{i_{1}}=\bm{y}_{i_{1}}$
and $\bm{z}_{i_{2}}=\bm{x}_{i_{2}}$. Also, $(\bm{z}_{i_{1}})^{\prime}\in
B_{\text{Del}}(\bm{x}_{i_{1}})$ and $(\bm{z}_{i_{2}})^{\prime}\in
B_{\text{Del}}(\bm{y}_{i_{2}})$. Thus, the array

$\widetilde{\bm{Z}}=\begin{bmatrix}z_{1,1}&z_{1,2}&\cdots&z_{1,L-1}&z_{1,L}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
z_{i_{1},1}&z_{i_{1},2}&\cdots&z_{i_{1},L-1}&\bullet\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
z_{i_{2},1}&z_{i_{2},2}&\cdots&z_{i_{2},L-1}&\bullet\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
z_{n,1}&z_{n,2}&\cdots&z_{n,L-1}&z_{n,L}\\\ \end{bmatrix}$

is indeed a valid output of the transmission of either $\bm{X}$ or $\bm{Y}$
through the $(1,1,1)$-TED channel, while $\bm{X}$ suffers from an arbitrary
deletion in the $i_{1}$-th row and a TE in the $i_{2}$-th row, or $\bm{Y}$
suffers from a TE in the $i_{1}$-th row and an arbitrary deletion in the
$i_{2}$-th row. Thus, a contradiction to the fact that both $\bm{X}$ and
$\bm{Y}$ are codewords in $\mathcal{C}$.

∎

Next, we use Claim 12, to prove the following upper bound on the cardinality
of $(1,1,1)$-TED codes.

######  Theorem 10.

Let $\mathcal{A}_{\text{TED}}(n\times L)$ be the cardinality of the maximal
size $(1,1,1)$-TED code of $n\times L$ binary arrays. Then,

$\mathcal{A}_{\text{TED}}(n\times
L)\lesssim\frac{2^{nL}}{nL}\leavevmode\nobreak\ \text{,\,
i.e.,\leavevmode\nobreak\
}\lim_{n\to\infty}\frac{\mathcal{A}_{\text{TED}}(n\times
L)}{\frac{2^{nL}}{nL}}\leq 1.$

###### Proof:

First, following the definition in [34] of a _run_ in a vector, denoted as
$r(\bm{x}_{i}),\leavevmode\nobreak\ \bm{x}_{i}\in{\mathbb{F}}_{2}^{L}$, a
generalization is presented next. Let
$\bm{X}=(\bm{x}_{1},\dots,\bm{x}_{n})\in{\mathbb{F}}_{2}^{n\times L}$, then
_the sum of runs_ is defined as $R(\bm{X})=\sum_{i=1}^{n}r(\bm{x}_{i})$. It is
possible to show that $|D_{i}^{\uparrow\downarrow}(\bm{X})|=2r(\bm{x}_{i})$,
and then $\left|\mathcal{D}^{\uparrow\downarrow}(\bm{X})\right|=2R(\bm{X})$.
Next, assume that $\mathcal{C}$ is a $(1,1,1)$-TED code of size
$\mathcal{A}_{\text{TED}}(n\times L)$, and then define the following,

$\displaystyle\mathcal{C}_{0}=\left\\{\bm{X}\in\mathcal{C}\colon
R(\bm{X})\geq\frac{nL}{2}-\sqrt{nL\ln(nL)}\right\\}$

And $\mathcal{C}_{1}=\mathcal{C}\setminus\mathcal{C}_{0}$. From Claim 12,
every distinct codeword array $\bm{X}\in\mathcal{C}$ results a distinct
$\mathcal{D}(\bm{X})$, thus

$\displaystyle 2^{nL}$
$\displaystyle\geq\sum_{\bm{X}\in\mathcal{C}}|\mathcal{D}^{\uparrow\downarrow}(\bm{X})|$
$\displaystyle=\sum_{\bm{X}\in\mathcal{C}_{0}}|\mathcal{D}^{\uparrow\downarrow}(\bm{X})|+\sum_{\bm{X}\in\mathcal{C}_{1}}|\mathcal{D}^{\uparrow\downarrow}(\bm{X})|$
$\displaystyle\geq\sum_{\bm{X}\in\mathcal{C}_{0}}2R(\bm{X})\geq|\mathcal{C}_{0}|\cdot\left(nL-2\sqrt{nL\ln(nL)}\right),$

and therefore,

$\displaystyle|\mathcal{C}_{0}|$
$\displaystyle\leq\frac{2^{nL}}{nL-2\sqrt{nL\ln(nL)}}\approx\frac{2^{nL}}{nL}\leavevmode\nobreak\
.$

Where the last step above is due to the fact that

$\frac{2^{nL}}{nL-2\sqrt{nL\ln(nL)}}/\frac{2^{nL}}{nL}\xrightarrow{n\to\infty}=1\leavevmode\nobreak\
.$

Denoting $N=nL$ and $g(N)=\frac{N}{2}-\sqrt{N\ln(N)}$, we say

$\displaystyle|\mathcal{C}_{1}|$
$\displaystyle\leq\sum_{r=n}^{g(N)-1}|\\{\bm{X}\in\\{0,1\\}^{n\times L}\colon
R(\bm{X})=r\\}|$
$\displaystyle\leq\sum_{r=1}^{g(N)-1}|\\{\bm{X}\in\\{0,1\\}^{N}\colon
r(\bm{X})=r\\}|$
$\displaystyle=\sum_{r=1}^{g(N)-1}2\binom{N-1}{r-1}\leavevmode\nobreak\ .$

Where $r(\bm{X})$ is the number of runs in the vectorized array $\bm{X}$, that
is appending every row to the end of its previous row. Moreover, the second
inequality is due to the fact that any vectorized array can either have the
same number of runs (if every row ends with the same bit as the next row
starts with), or have an larger number of runs. Therefore, any array that is
in one of the sets on the l.h.s (of the second inequality), has to be in one
of the sets on the r.h.s. Now, using the lemma in [30],
$|\mathcal{C}_{1}|=o\left(\frac{2^{N}}{N^{2}}\right)$. To conclude,
$\frac{|\mathcal{C}_{1}|}{\frac{2^{nL}}{nL}}\xrightarrow[]{n\to\infty}0$ and
therefore,

$|\mathcal{C}_{0}|+|\mathcal{C}_{1}|\lesssim\frac{2^{nL}}{nL}\leavevmode\nobreak\
.$

∎

That means that the redundancy of an $n\times L$ binary array code capable of
correcting at most a single deletion and a single TE is asymptotically at
least $\log_{2}(n)+\log_{2}(L)$ bits.

##  VII Conclusions and Future Work

Our research has shown promising results. For TE and DC codes we provided some
optimal constructions, using some interesting techniques. The new coding
schemes developed in this work show that it is possible to correct many
frequently occurring error patterns by manipulating the parity check matrices
of existing linear codes, and using ideas based on tensor product codes. With
the ever-increasing demand for data storage, our findings contribute to the
growing body of research into alternative data storage solutions, offering a
new and innovative approach. Further research is necessary to fully assess the
potential of this technique, but our results are a step towards a future where
DNA storage is a reality.

## Acknowledgments

We want to acknowledge Prof. Ron M. Roth for suggesting us the expression in
Lemma 5 and its proof.

## References

  * [1] “DNA data storage market size is expected to reach usd 1926.7 million by 2028,” https://www.prnewswire.com/news-releases/, [Online; accessed January-2023].
  * [2] G. M. Church, Y. Gao, and S. Kosuri, “Next-generation digital information storage in dna,” _Science_ , vol. 337, no. 6102, pp. 1628–1628, 2012.
  * [3] N. Goldman et al., “Towards practical, high-capacity, low-maintenance information storage in synthesized dna,” _Nature_ , vol. 494, no. 1435, pp. 77–80, 2013.
  * [4] P. Predki and M. Cassidy, “Systems and methods for writing and reading data stored in a polymer,” U.S. Patent 2020/0224264 A1, Jul. 2020.
  * [5] B. Vasic and E. Kurtas, _Coding and signal processing for magnetic recording systems_. CRC press, 2004.
  * [6] K. Chen, J. Kong, J. Zhu, N. Ermann, P. Predki, and U. F. Keyser, “Digital data storage using dna nanostructures and solid-state nanopores,” _Nano Letters_ , vol. 19, no. 2, pp. 1210–1215, 2019. [Online]. Available: https://doi.org/10.1021/acs.nanolett.8b04715
  * [7] A. Ganesan and P. O. Vontobel, “On the existence of universally decodable matrices,” _IEEE Transactions on Information Theory_ , vol. 53, no. 7, pp. 2572–2575, 2007.
  * [8] W. Zhou, S. Lin, and K. A. Abdel-Ghaffar, “BCH codes for the rosenbloom–tsfasman metric,” _IEEE Transactions on Information Theory_ , vol. 62, no. 12, pp. 6757–6767, 2016.
  * [9] M. Y. Rosenbloom and M. A. Tsfasman, “Codes for the m-metric,” _Problemy Peredachi Informatsii_ , vol. 33, no. 1, pp. 55–63, 1997.
  * [10] S. Dougherty and M. Skriganov, “Maximum distance separable codes in the $\rho$ metric over arbitrary alphabets,” _Journal of Algebraic Combinatorics_ , vol. 16, pp. 71–81, 07 2002.
  * [11] N. Raviv, M. Schwartz, R. Cohen, and Y. Cassuto, “Hierarchical erasure correction of linear codes,” _Finite Fields and Their Applications_ , vol. 68, p. 101743, 2020.
  * [12] S. Jain, “Array codes in m-metric correcting independent and clustered errors simultaneously,” _World Applied Sciences Journal_ , vol. 22, pp. 36–40, 01 2013.
  * [13] A. Lenz, P. H. Siegel, A. Wachter-Zeh, and E. Yaakobi, “Anchor-based correction of substitutions in indexed sets,” in _IEEE International Symposium on Information Theory (ISIT)_ , 2019, pp. 757–761.
  * [14] K. Immink and K. Cai, “Design of capacity-approaching constrained codes for DNA-based storage systems,” _IEEE Communication Letters_ , vol. 22, no. 2, pp. 224–227, 2018.
  * [15] S. Yazdi, H. Kiah, R. Gabrys, and O. Milenkovic, “Mutually uncorrelated primers for DNA-based data storage,” _IEEE Transactions on Information Theory_ , vol. 64, no. 9, pp. 6283–6296, 2018.
  * [16] W. Press, J. Jones, J. Schaub, and I. Finkelstein, “Hedges error-correcting code for DNA storage corrects indels and allows sequence constraints,” _Proceedings of the National Academy of Sciences_ , vol. 117, no. 31, pp. 18 489–18 496, 2020.
  * [17] A. Lenz, P. Siegel, and E. Yaakobi, “Coding over sets for DNA storage,” _IEEE Transactions on Information Theory_ , vol. 66, no. 4, pp. 2331–2351, 2019.
  * [18] H. Wei and M. Schwartz, “Improved coding over sets for DNA-based data storage,” _IEEE Transactions on Information Theory_ , vol. 68, no. 1, pp. 118–129, 2022.
  * [19] A. Boruchovsky, D. Bar-Lev, and E. Yaakobi, “DNA-correcting codes: End-to-end correction in DNA storage systems,” in _2023 IEEE International Symposium on Information Theory (ISIT)_ , 2023, pp. 579–584.
  * [20] J. Sima, N. Raviv, and J. Bruck, “On coding over sliced information,” _IEEE Transactions on Information Theory_ , vol. 67, no. 5, pp. 2793–2807, 2021.
  * [21] Z. Liu and M. Mitzenmacher, “Codes for deletion and insertion channels with segmented errors,” _IEEE Transactions on Information Theory_ , vol. 56, no. 1, pp. 224–232, 2009.
  * [22] M. Abroshan, R. Venkataramanan, and A. Fàbregas, “Coding for segmented edit channels,” _IEEE Transactions on Information Theory_ , vol. 64, no. 4, pp. 3086–30 982, 2017.
  * [23] B. Masnick and J. Wolf, “On linear unequal error protection codes,” _IEEE Transactions on Information Theory_ , vol. 13, no. 4, p. 600–607, 1967.
  * [24] Z. Zhou and C. Xu, “An improved unequal error protection turbo codes,” in _Proceedings of 2005 International Conference on Wireless Communications, Networking and Mobile Computing_ , Piscataway, 2005, pp. 284–287.
  * [25] I. Boyafunov and G. Katsman, “Linear unequal error protection codes,” _IEEE Transactions on Information Theory_ , vol. 27, no. 2, pp. 168–175, 1981.
  * [26] R. Roth, _Introduction to Coding Theory_. USA: Cambridge University Press, 2006.
  * [27] H. Hasse, “Theorie der höheren differentiale in einem algebraischen funktionenkörper mit vollkommenem konstantenkörper bei beliebiger charakteristik.” _Journal für die reine und angewandte Mathematik_ , vol. 175, pp. 50–54, 1936. [Online]. Available: http://eudml.org/doc/149955
  * [28] R. Varshamov and G. Tenengolts, “Codes which correct single asymmetric errors (in russian),” _Automatika i Telemkhanika_ , vol. 161, no. 3, pp. 288–292, 1965.
  * [29] J. K. Wolf, “An introduction to tensor product codes and applications to digital storage systems,” in _2006 IEEE Information Theory Workshop - ITW ’06 Chengdu_ , 2006, pp. 6–10.
  * [30] V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions and reversals.” _Soviet Physics Doklady_ , vol. 10, no. 8, pp. 707–710, feb 1966, doklady Akademii Nauk SSSR, V163 No4 845-848 1965.
  * [31] K. Abdel-Ghaffar and H. Ferreira, “Systematic encoding of the varshamov-tenengol’ts codes and the constantin-rao codes,” _IEEE Transactions on Information Theory_ , vol. 44, no. 1, pp. 340–345, 1998.
  * [32] J. Sima, R. Gabrys, and J. Bruck, “Optimal systematic t-deletion correcting codes,” in _2020 IEEE International Symposium on Information Theory (ISIT)_ , 2020, pp. 769–774.
  * [33] A. Fazeli, A. Vardy, and E. Yaakobi, “Generalized sphere packing bound,” _IEEE Transactions on Information Theory_ , vol. 61, no. 5, pp. 2313–2334, 2015.
  * [34] D. Bar-Lev, T. Etzion, and E. Yaakobi, “On levenshtein balls with radius one,” in _2021 IEEE International Symposium on Information Theory (ISIT)_ , 2021, pp. 1979–1984.