Non-binary Two-Deletion Correcting Codes and Burst-Deletion
Correcting Codes

Wentu Song and Kui Cai
Science, Mathematics and Technology Cluster

Singapore University of Technology and Design, Singapore 487372

Email: {wentu_song<EMAIL_ADDRESS>
In this paper, we construct systematic $q$-ary two-deletion
correcting codes and burst-deletion correcting codes, where $q\geq
2$ is an even integer. For two-deletion codes, our construction
has redundancy $5\log n+O(\log q\log\log n)$ and has encoding
complexity near-linear in $n$, where $n$ is the length of the
message sequences. For burst-deletion codes, we first present a
construction of binary codes with redundancy $\log n+9\log\log
n+\gamma_t+o(\log\log n)$ bits $(\gamma_t$ is a constant that
depends only on $t)$ and capable of correcting a burst of at most
$t$ deletions, which improves the Lenz-Polyanskii Construction
(ISIT 2020). Then we give a construction of $q$-ary codes with
redundancy $\log n+(8\log q+9)\log\log n+o(\log q\log\log
n)+\gamma_t$ bits and capable of correcting a burst of at most $t$

§ INTRODUCTION

DNA-based data storage has been a hot topic in information theory
society. As deletion/insertion are common in DNA data storage
[1], codes correcting such errors have attracted
significant attention in recent years.

It was proved in [2] that the optimal redundancy
of binary $t$-deletion correcting codes is asymptotically between
$t\log n+o(\log n)$ and $2t\log n+o(\log n)$, where $n$ is the
length of the code and the redundancy of a binary code $\mathcal
C$ is defined as $n-\log|\mathcal C|$.[In this paper, for
any positive real number $x$, $\log_qx$ is the logarithm of $x$
with base $q$, where $q\geq 2$ is a positive integer. If the base
$q=2$, then for simplicity, we write $\log_2x=\log x$.] The
well-known Varshamov-Tenengolts (VT) codes [3],
which is defined as

\begin{align*}\text{VT}_a(n)\!=\!\left\{\!(c_1,\ldots,c_n)
\!\in\!\{0,1\}^n\!: \!\sum_{i=1}^nic_i\!\equiv a
is a class of binary
single-deletion correcting codes with asymptotically optimal

Construction of multiple-deletion correcting codes with low
redundancy were considered in
[6]$-\!\!$[14]. By using the higher
order VT syndromes and the syndrome compression technique
[12], Sima et al. constructed a family of
systematic $t$-deletion correcting codes with $4t\log n+o(\log n)$
bits [13]. The method in [13] was improved in
[14] to give a construction of $t$-deletion correcting
codes with redundancy $(4t-1)\log n+o(\log n)$, which is the best
known result in redundancy. For the special case of $t=2$, an
explicit construction of $2$-deletion correcting codes with
redundancy $4\log n+o(\log n)$ was proposed by Guruswami and Håstad [9], which matches the existential upper bound of
the asymptotically optimal codes.

As a special case of deletion errors, a burst of $t$ deletions
$($or a $t$-burst-deletion$)$ refers to $t$ deletions that occur
at consecutive positions. It was proved in [15] that
the redundancy of a $t$-burst-deletion-correcting code is
approximately lower bounded by $\log n+t-1$. Levenshtein
[16] constructed a class of binary codes that can
correct a burst of at most two deletions with asymptotically
optimal redundancy of $\log n+1$. Binary codes capable of
correcting a burst of exact $t$ deletions for $t\geq 2$ are
constructed in [15], which also have an
asymptotically optimal redundancy of $\log n+(t-1)\log\log
n+t-\log t$. In [18], binary codes capable of correcting
a burst of at most $t$ deletions are constructed, which
also have an asymptotically optimal redundancy of $\log
n+(t(t-1)/2)\log\log n+\gamma_t$, where $\gamma_t$ is a constant
that depends only on

Besides binary codes, nonbinary deletion correcting codes are also
investigated in the literature. In [19], it was
shown that the optimal redundancy of a $q$-ary $t$-deletion
correcting code is asymptotically lower bounded by $t\log n+t\log
q+o(\log q\log n)$ and upper bounded by $2t\log n+t\log q+o(\log
q\log n)$ in bits $(q\geq 2)$. A class of $q$-ary single-deletion
correcting codes with redundancy close to the asymptotic
optimality was constructed in [20]. For $q$-ary
$t$-deletion correcting codes, the best known construction is
presented in [23], which achieve optimal redundancy up
to a constant factor. Quaternary codes capable of correcting a
single edit error for DNA data storage were studied in
[24]. In [26], a $q$-ary code that can correct a
burst of at most $2$ deletions with redundancy $\log n+O(\log q
\log\log n)$ bits was constructed, where $q\geq 2$ is an even

In this paper, we construct nonbinary two-deletion correcting
codes and burst-deletion correcting codes. Our contributions

1) We construct a class of systematic $q$-ary two-deletion
correcting codes, with redundancy $5\log n+O(\log q\log\log n)$,
where $q\geq 2$ is an even integer and $n$ is the length of the
message sequences.

2) We present a construction of binary codes with redundancy $\log
n+9\log\log n+\gamma_t+o(\log\log n)$ bits $(\gamma_t$ is a
constant that depends only on $t)$ and capable of correcting a
burst of at most $t$ deletions, which improves the Lenz-Polyanskii
Construction (ISIT 2020).

2) We give a construction of $q$-ary codes with redundancy
$\log n+(8\log q+9)\log\log n+o(\log q\log\log n)+\gamma_t$ bits
and capable of correcting a burst of at most $t$ deletions,
where $q\geq 2$ is an even integer.

Note that each symbol in $\mathbb Z_q$ can be viewed as a binary
string of length $\lceil\log q\rceil$, so a binary code of length
$\lceil\log q\rceil n$ and capable of correcting a burst of
$\lceil\log q\rceil t$ deletions can also be viewed as a $q$-ary
code of length $n$ and capable of correcting a burst of $t$
deletions. By this observation and by the construction in
[18], we can obtain a $q$-ary code of length $n$ and
capable of correcting a burst of $t$ deletions that has redundancy

$$\log(n\log q)+\frac{t\log q (t\log q+1)}{2}\log\log(n\log
Our construction has improved redundancy than this
naive construction.

The rest of this paper is organized as follows. In Section
2, we introduce some basic
concepts and notations of deletion correcting codes, and review
some related constructions in the literature. In Section
3, we construct $q$-ary
two-deletion correcting codes. In Section
4, we present an improved
construction of binary codes correcting a burst of at most $t$
deletions. In Section 5, we
construct of $q$-ary codes correcting a burst of at most $t$
deletions. The paper is concluded in Section

§ PRELIMINARIES

For any integers $m$ and $n$ such that $m\leq n$, we denote
$[m,n]=\{m,m+1,\ldots,n\}$ and call it an interval. If
$m>n$, let $[m,n]=\emptyset$. For simplicity, denote $[n]=[1,n]$
for any positive integer $n$. For any positive real number $x$,
$\log x$ is the logarithm of $x$ with base $2$, i.e., $\log
x=\log_2x$. The size (cardinality) of any set $S$ is denoted by
$|S|$. For any positive integer $q\geq 2$, denote $\mathbb
Z_q=\{0,1,2,\cdots,q-1\}$, which will be used as the alphabet of
$q$-ary codes.

For any string (also called a sequence) $\bm{x}\in\mathbb Z_q^n$,
$n$ is called the length of $\bm{x}$ and denote $|\bm x|=n$.
Unless otherwise specified, we use $x_i$ to denote the $i$th
coordinate of $\bm{x}$, where $i\in[n]$. Usually, we denote
$\bm{x}=(x_1,x_2,\ldots,x_n)$ or $\bm{x}=x_1x_2\cdots x_n$. For
any $I=\{i_1, i_2, \ldots, i_d\}\subseteq [n]$ such that
$i_1<i_2<\cdots<i_d$, denote $x_I=x_{i_1} x_{i_2} \cdots x_{i_d}$
and call $x_D$ a subsequence of $\bm x$. If $I\subseteq[n]$
is an interval $($i.e., $I=[i,j]$ for some $i,j\in[1,n]$, $i\leq
j)$, then $x_{I}=x_{[i,j]}=x_{i}x_{i+1}\cdots x_{j}$ is called a
substring of $\bm x$. In other words, a substring of
$\bm{x}$ is a subsequence of $\bm{x}$ consisting of some
consecutive symbols of $\bm{x}$. We say that $\bm x$ contains $\bm
p~($or $\bm p$ is contained in $\bm x)$ if $\bm{p}$ is a substring
of $\bm{x}$. For two substrings $x_{I}$ and $x_{I'}$ of $\bm x$,
where $I,I'\subseteq[n]$ are two intervals, we say that $x_{I}$
and $x_{I'}$ are disjoint if $I\cap I'=\emptyset$.

Let $t\leq n$ be a nonnegative integer. For any $\bm{x}\in\mathbb
Z_q^n$, let $\mathcal D_t(\bm x)$ denote the set of subsequences
of $\bm x$ of length $n-t$, and let $\mathcal B_{t}(\bm x)$ denote
the set of subsequences $\bm y$ of $\bm x$ that can be obtained
from $\bm x$ by a burst of $t$ deletions, that is $\bm y=x_{I}$
such that $I=[n]\backslash D$ for some interval $D\subseteq[n]$ of
length $t~($i.e., $D=[i,i+t-1]$ for some $i\in[n-t+1])$. Moreover,
let $\mathcal B_{\leq t}(\bm x)=\bigcup_{t'=0}^t\mathcal
B_{t'}(\bm x)$ be the set of subsequences of $\bm x$ that can be
obtained from $\bm x$ by a burst of at most $t$ deletions.
Clearly, $\mathcal D_{ 1}(\bm x)=\mathcal B_{1}(\bm x)=\mathcal
B_{\leq 1}(\bm x)$. However, $\mathcal B_{t}(\bm x)\subseteq
\mathcal D_{t}(\bm x)\cap\mathcal B_{\leq t}(\bm x)$ for $t\geq

A code $\mathcal C\subseteq\mathbb Z_q^n$ is said to be a
$t$-deletion correcting code if for any $\bm x\in\mathcal
C$ and any $\bm y\in\mathcal D_t(\bm x)$, $\bm x$ can be uniquely
recovered from $\bm y$; the code $\mathcal C\subseteq\mathbb
Z_q^n$ is said to be capable of correcting a burst of at
most $t$ deletions if for any $\bm x\in\mathcal C$ and any $\bm
y\in\mathcal B_{\leq t}(\bm x)$, $\bm x$ can be uniquely recovered
from $\bm y$.

§.§ Some Constructions Related to Binary Single-deletion
and Two-deletion Correcting Codes

From the VT construction, we can obtain the following lemma about
single-deletion correcting codes.

For any integer $n\geq 3$, there exists a function $\text{VT}:
\{0,1\}^n\rightarrow\{0,1\}^{\log n}$, computable in linear time,
such that for any $\bm{c}\in\{0,1\}^n$, given $\text{VT}(\bm c)$
and any $\bm b\in\mathcal D_1(\bm c)$, one can uniquely recover
$\bm c$.

The following lemma can be obtained from the results of
[8], and so its proof is omitted.

For any integer $n\geq 3$, there exists a function $\xi:
\{0,1\}^n\rightarrow\{0,1\}^{7\log n+o(\log n)}$, computable in
linear time, such that for any $\bm{c}\in\{0,1\}^n$, given
$\xi(\bm c)$ and any $\bm b\in\mathcal D_2(\bm c)$, one can
uniquely recover $\bm c$.

Lemma <ref> can be used to construct systematic
binary two-deletion correcting codes with redundancy not greater
than $7\log n+o(\log n)$. Another construction, which uses the
so-called regular strings and has lower redundancy, was proposed
in [9], but it is not systematic.

A binary string
$\bm{c}\in\{0,1\}^n$ is said to be regular if each
(contiguous) sub-string of $\bm c$ of length at least $d\log n$
contains both $00$ and $11$.

In Definition <ref>, $d$ is a constant that can be chosen
properly. In this paper, we will always choose $d=7$. The
following two lemmas are from [9].

There exist an integer $M\geq 2^{n-1}$ and a one-to-one mapping
$\text{RegEnc}: \{1,2,\cdots,M\}\rightarrow\{0,1\}^n$ such that
its image is contained in the set of regular strings. Moreover,
the function $\text{RegEnc}$ can be computed in near-linear time
with a polynomial size lookup table.

There is a function $\eta$, computable in linear time, that maps
$n$ bits to $4\log n+10\log\log n+O(1)$ bits such that for any
regular $\bm{c}\in\{0,1\}^n$, given $\eta(\bm c)$ and any $\bm
b\in\mathcal D_2(\bm c)$, one can uniquely recover $\bm c$.

§.§ Some Constructions Related to Binary Burst-Deletion Correcting

The following lemma can be obtained from the results in Section IV
of [12].

Suppose $t$ is a constant with respect to $n$. There is a function
$\phi:\{0,1\}^n\rightarrow\{0,1\}^{4\log n+o(\log n)}$, computable
in time $O(2^tn^3)$, such that for any $\bm c\in\{0,1\}^n$, given
$\phi(\bm c)$ and any $\bm b\in\mathcal B_{\leq t}(\bm c)$, one
can uniquely recover $\bm c$.

Let $m\leq\delta\leq n$ be positive integers and $\bm
p\in\{0,1\}^m$, where $\bm p$ is called a pattern. A string
$\bm c\in\{0,1\}^n$ is called $(\bm p, \delta)$-dense, if
each substring of $\bm c$ of length $\delta$ contains at least one
pattern $\bm p$.

As in [18], in this paper, we take

$$\delta=t2^{t+1}\log n\footnotemark{}$$

$$\bm p=0^t1^t,$$
where $0^t$ is the string consists of $t$ symbol $0$s, and
$1^t$ is the string consists of $t$ symbol $1$s. In other words,
$\bm p=p_1p_2\cdots p_{2t}$ such that $p_1=p_2=\cdots=p_t=0$ and
$p_{t+1}=p_{t+2}=\cdots=p_{2t}=1$. It was proven in [18]
that one bit of redundancy is sufficient to construct $(\bm p,
\delta)$-dense string. In [18], $\delta$ is
taken to be $t2^{t+1}\lceil\log n\rceil\footnotemark[2]$. In this
paper, for notational simplicity, we omit the ceiling function and
write $\delta=t2^{t+1}\log n$.

For any $n\geq 5$, the number of $(\bm p, \delta)$-dense strings
of length $n$ is at least
$$2^n(1-n^{1-\log e})\geq 2^{n-1}.$$

The following lemma can be obtained from Construction 1 and Lemma
2 of [18] and so its proof is omitted.

For any positive integer $n$, there is a function $\mu$,
computable in linear time, that maps $n$ bits to $\log n+3$ bits
such that for any $(\bm p, \delta)$-dense $\bm c\in\{0,1\}^n$,
given $\mu(\bm c)$ and any $\bm b\in\mathcal B_{\leq t}(\bm c)$,
one can find in time $O(n)$ an interval $L\subseteq[n]$ of length
at most $\delta+t$ such that $\bm b=c_{[n]\backslash D}$ for some
interval $D\subseteq L~($i.e., the deletions are located in the
interval $L)$.

§.§ Matrix Representation of $q$-ary Strings

In the rest of this paper, we always assume $q>2$ is a fixed even
integer. As in [23], each $q$-ary string
$\bm{x}=x_1x_2\ldots x_n\in\mathbb Z_q^{n}$ can be represented by
a $\lceil\log q\rceil\times n$ binary matrix

\begin{align}\label{q-B-Repr}
c_{1,1} & \cdots & c_{1,n} \\
\vdots & \ddots & \vdots \\
c_{\lceil\log q\rceil,1} &
\cdots & c_{\lceil\log q\rceil,n} \\
\end{array}\right),
\end{align}

where $c_{i,j}\in\{0,1\}$, such that the $j$th column of
$M_{\bm{x}}$ is the binary representation of $x_j$. Specifically,
$x_j=\sum_{i=1}^{\lceil\log q\rceil}c_{i,j}2^{i-1}$. We call
$M_{\bm{x}}$ the matrix representation of $\bm x$. For any
$i\in\{1,2,\cdots,\lceil\log q\rceil\}$ and any interval
$J=[j_1,j_2]=\{j_1,j_1+1,\cdots,j_2\}\subseteq[n]$, where $1\leq
j_1<j_2\leq n$, denote

\begin{align}\label{1-row-Repr}
c_{i,J}\triangleq c_{i,j_1}c_{i,j_1+1}\cdots c_{i,j_2},\end{align}

which is a substring of the $i$th row of $M_{\bm x}$ consisting of
$c_{i,j_1}$, $c_{i,j_1+1}$, $\cdots$, $c_{i,j_2}$. In particular,
$c_{i,[n]}$ is the $i$th row of $M_{\bm x}$.

Clearly, if $\bm y\in\mathbb Z_q^{n-t}$ is obtained from $\bm x$
by deleting $x_{j_1},\cdots,x_{j_t}$, then the matrix
representation $M_{\bm{y}}$ of $\bm y$ can be obtained from
$M_{\bm{x}}$ by deleting columns $j_1, \cdots,j_t$ of
$M_{\bm{x}}$. Moreover, $\bm x$ can be recovered from $\bm y$ if
and only if its matrix representation $M_{\bm{x}}$ can be
recovered from $M_{\bm{y}}$.

Suppose $\mathcal E_{0}:\{0,1\}^{n-1}\rightarrow\{0,1\}^{n}$ is a
one-to-one mapping and $q>2$ is an even integer. Then there is a
one-to-one mapping $\bar{\mathcal E}_{0}:\mathbb
Z_q^{n-1}\rightarrow\mathbb Z_q^{n}$, with the same computing time
as $\mathcal E_{0}$, such that for any $\bm u\in\mathbb Z_q^{n-1}$
and $\bm x=\bar{\mathcal E}_{0}(\bm u)$, if
$M_{\bm{u}}=(b_{i,j})_{\lceil\log q\rceil\times(n-1)}$ and
$M_{\bm{x}}=(c_{i,j})_{\lceil\log q\rceil\times n}$ are the matrix
representation of $\bm u$ and $\bm x$ respectively, then

$$c_{1,[n]}=\mathcal E_{0}(b_{1,[n-1]}).$$

For each $\bm u\in\mathbb Z_q^{n-1}$, where the matrix
representation of $\bm u$ is

\begin{align*}
b_{1,1} & \cdots & b_{1,n-1} \\
b_{2,1} & \cdots & b_{2,n-1} \\
\vdots & \ddots & \vdots \\
b_{\lceil\log q\rceil,1} &
\cdots & b_{\lceil\log q\rceil,n-1} \\
\end{array}\right),
\end{align*}

denote $\mathcal E_{0}(b_{1,[n-1]})=\bm c=c_{1,1}\cdots
c_{1,n-1}c_{1,n}$ and let

\begin{align*}
c_{1,1} & \cdots & c_{1,n-1} & c_{1,n} \\
b_{2,1} & \cdots & b_{2,n-1} & 0 \\
\vdots & \ddots & \vdots & \vdots \\
b_{\lceil\log q\rceil,1} &
\cdots & b_{\lceil\log q\rceil,n-1} & 0 \\
\end{array}\right).
\end{align*}

Specifically, $M=(c_{i,j})$ is a $\lceil\log q\rceil\times n$
binary matrix satisfying the following three properties: i) the
first row of $M$ is equal to $\bm c$; ii) $c_{2,j}\cdots
c_{\lceil\log q\rceil,j}=b_{2,j}\cdots b_{\lceil\log q\rceil,j}$
for each $j\in[n-1]$; iii) $c_{2,n}\cdots c_{\lceil\log
q\rceil,n}=0^{\lceil\log q\rceil-1}$, where $0^{\lceil\log
q\rceil-1}$ is the string consisting of $\lceil\log q\rceil-1$
symbol $0$s.

Let $\bar{\mathcal E}_{0}(\bm u)=\bm x$ such that the matrix
representation of $\bm x$ is $M_{\bm{x}}=M$. It is easy to see
that $c_{1,[n]}=\mathcal E_{0}(b_{1,[n-1]})$ and the computing
time of $\bar{\mathcal E}_{0}$ is the same as that of $\mathcal
E_{0}$. Moreover, since $\mathcal E_{0}$ is a one-to-one mapping,
it is also easy to see that $\bar{\mathcal E}_{0}$ is a one-to-one

It remains to prove that $\bm x\in\mathbb Z_q^{n}$, equivalently,
each column of $M_{\bm{x}}$ is the binary representation of some
integer in $\mathbb Z_q$.

According to property iii) of the constructed matrix $M$, we have
$c_{\lceil\log q\rceil,n}\cdots c_{2,n}c_{1,n}=0^{\lceil\log
q\rceil-1}c_{1,n}$, so the last column of $M$ is the binary
representation of $c_{1,n}\in\{0,1\}\subseteq\mathbb Z_q$. For
each $j\in[n-1]$, according to property ii) of $M$, we have
$c_{\lceil\log q\rceil,j}\cdots c_{2,j}c_{1,j}=b_{\lceil\log
q\rceil,j}\cdots b_{2,j}c_{1,j}$, so $x_j=\sum_{i=1}^{\lceil\log
q\rceil}b_{i,j}2^{i-1}+c_{1,j}=u_{j}-b_{1,j}+c_{1,j}$, where the
last equality holds because according to the definition of the
matrix representation, $b_{\lceil\log q\rceil,j}\cdots
b_{2,j}b_{1,j}$ is the binary representation of $u_j$. If
$b_{1,j}=1$, then $x_j=u_{j}-b_{1,j}+c_{1,j}\leq u_j\leq q-1$. If
$b_{1,j}=0$, then $u_{j}$ is even. Noticing that $q$ is even, so
$u_{j}\leq q-2$, and hence
$x_j=u_{j}-b_{1,j}+c_{1,j}=u_{j}+c_{1,j}\leq q-1$. In both cases,
we have $x_j\in\mathbb Z_q$. Thus, each column of $M$ is the
binary representation of some integer in $\mathbb Z_q$, and so
$\bm x\in\mathbb Z_q^{n}$.

§ NONBINARY TWO-DELETION CORRECTING CODES

In this section, we consider $q$-ary two-deletion correcting
codes. We assume that $q>2$ is an even integer and is a constant
with respect to the code length $n$. Each binary sequence $\bm a$
will also be viewed as a non-negative integer whose binary
representation is $\bm a$, and conversely, each non-negative
integer $m$ will also be viewed as a binary sequence with length
$\lceil\log (m+1)\rceil$, i.e., the binary representation of $m$.
Therefore, summation and multiplication of binary strings and
integers are performed in the set of integers.

We need to introduce some concepts and notations for binary
strings, which will be used in our construction.

Let $\bm c\in\{0,1\}^n$ be a binary string of length $n$. A
run of $\bm c$ is a maximal substring of $\bm c$ consisting
of identical symbols.[We say that a substring of $\bm c$
satisfying a certain property is maximal if it is contained by no
other substring of $\bm c$ that satisfies the same property.
Hence, a maximal run of the string $\bm c$ is not contained by any
other run of $\bm c$.] A substring $c_{[i_1,i_2]}$ of $\bm c$,
where $i_1<i_2$, is called an alternative substring of $\bm
c$ if $c_{i+1}\neq c_{i}$ for all $i\in[i_1,i_2-1]$.

From Definition <ref>, it is easy to see that if
$\bm{c}\in\{0,1\}^n$ is regular, then each substring of $\bm c$ of
length $d\log n$ can not be a run or an alternative substring of
$\bm c$ because it contains both $00$ and $11$. Equivalently, each
run and each alternative substring of $\bm c$ have length at most
$d\log n$.

For each $\bm c\in\{0,1\}^n$, let $c_{I_i}$ be the $i$th run
$($counting from the left$)$ of $\bm c$, where $I_i\subseteq[n]$
is the index set of $c_{I_i}$. Then we denote $\mathcal I_{\bm
c}=\{c_{I_1},\cdots,c_{I_{n'}}\}$ and call it the set of
runs of $\bm c$, where $n'$ is the number of runs of $\bm c$.

Let $\text{VT}$, $\xi$ and $\eta$ be the functions constructed by
Lemma <ref>, Lemma <ref> and Lemma
<ref>, respectively. Denote
$$\rho=3d\log n$$

\begin{equation}\label{def-Ji-intvl}
J_j=\!\left\{\!\begin{aligned} &[(j-1)\rho\!+1, (j+1)\rho],
~\text{for}~j\in\!\{1,\cdots, \left\lceil n/\rho\right\rceil-2\},\\
&[(j-1)\rho\!+1, n], ~~~~~~~~~\text{for}~j=\left\lceil
\end{aligned}\right.
\end{equation}

Note that each interval $J_j$ has length $2\rho$ and the
intersection of two successive intervals $J_{j}$ and $J_{j+1}$ is
an interval of length $\rho$. It is easy to see the following

The intervals $J_j$, $j=1,\cdots,\left\lceil n/\rho\right\rceil-1$

1) For any interval $J\subseteq[n]$ of length at most
$\rho$, we can find an
$j_0\in\{1,2,\cdots,\left\lceil n/\rho\right\rceil-1\}$
such that $J\subseteq J_{j_0}$.

2) $J_j\cap J_{j'}=\emptyset$ for all $j,j'\in\{1,2,\cdots,
\left\lceil n/\rho\right\rceil-1\}$ such that $|j-j'|\geq 2$.

For each $q$-ary string $\bm x\in\mathbb Z_q^n$, let $M_{\bm
x}=(c_{i,j})$ be the matrix representation of $\bm x$ as defined
by (<ref>) and $c_{1,[n]}$ be the first row of $M_{\bm
x}$. We construct a function $f$ as follows.

Construction 1: For each $\bm x\in\mathbb Z_q^n$, let
$\mathcal I_{\bm c}=\{c_{I_1},\cdots,c_{I_{n'}}\}$ be the set of
runs of $\bm c=c_{1,[n]}$ as defined in Definition
<ref>. For each $i\in[n']$, let

$$g_i(\bm x)=\left(\text{VT}(c_{2,I_i}), \text{VT}(c_{3,I_i}),
\cdots, \text{VT}(c_{\lceil\log q\rceil,I_i})\right),$$
and for
each $\ell\in\{0,1\}$, let

\begin{align}\label{def-2del-g-ell}
g^{(\ell)}(\bm x)=\sum_{i=1}^{n'}i^\ell
g_i(\bm x)~\text{mod}~2n^\ell N_1,\end{align}

$$N_1=q^{\log\log n+3}.$$
Moreover, for each
$j\in\{1,\cdots,\left\lceil n/\rho\right\rceil-1\}$, let

$$h_j(\bm x)=\left(\xi(c_{2,J_j}),\xi(c_{3,J_j}),\cdots,\xi(c_{\lceil\log
and for each
$\ell\in\{0,1\}$, let

\begin{align}\label{Constr1-h-ell}
h^{(\ell)}(\bm x)=\sum_{\substack{j\in\{1,\cdots,\left\lceil
j\!~\equiv\!~\ell~\text{mod}~2}} h_j(\bm
$$N_2=q^{7\log\log n+o(\log\log
Finally, let

$$f(\bm x)=\left(\eta(c_{1,[n]}),g^{(0)}(\bm x),g^{(1)}(\bm x),
h^{(0)}(\bm x),h^{(1)}(\bm x)\right).$$
Note that
Lemma <ref> requires that each $|I_j|\geq 3$. If
$|I_j|<3$, we can just let $\xi(c_{i,I_j})=c_{i,I_j}$. Then
$c_{i,I_j}$ can also be recovered from $\xi(c_{i,I_j})$. This is
feasible because in our construction, we only need that each
$\xi(c_{i,I_j})$ is a sequence of length not greater than
$7\log\log n+o(\log\log n)$.

Let $\mathcal R_n$ denote the set of all $\bm x\in\mathbb Z_q^{n}$
such that $c_{1,[n]}$ is a regular string with $d=7~($according to
Definition <ref>$)$. Then we have the following Theorem.

The function $f(\bm x)$ is computable in linear time and the
length $|f(\bm x)|$ of $f(\bm x)$ satisfies
$$|f(\bm x)|\leq 5\log
n+O(\log q\log\log n).$$
Moreover, if $\bm{x}\in\mathcal R_n$,
then $\bm x$ can be uniquely recovered from $f(\bm x)$ and any
given $\bm y\in\mathcal D_2(\bm x)$.

To prove Theorem <ref>, we need the following

Suppose $\bm c\in\{0,1\}^n$ is regular and $\bm b\in\{0,1\}^{n-2}$
such that $\bm b$ can be obtained from $\bm c$ by deleting two
symbols of $\bm c$. Then exact one of the following holds.

1) There are two distinct runs $c_{I_{j_1}}$ and $c_{I_{j_2}}$ of $\bm
c$, uniquely determined by $\bm b$ and $\bm c$,
such that $\bm b$ can be obtained from $\bm c$ by deleting one symbol
in $c_{I_{j_1}}$ and one symbol in $c_{I_{j_2}}$.

2) There is an interval $J\subseteq[n]$ of length at most
$\rho$ such that $\bm b$ can be obtained from $\bm c$ by deleting two
symbols in $c_{J}$.

This Lemma is proved in Appendix A.

Now, we can prove Theorem <ref>.

Note that by Lemma <ref>, Lemma <ref>
and Lemma <ref>, the functions $\text{VT}$, $\xi$
and $\eta$ are all computable in linear time. By Construction 1,
the functions $g^{(\ell)}(\bm x)$ and $h^{(\ell)}(\bm x)$,
$\ell\in\{0,1\}$, are computable in linear time. Hence, $f(\bm
x)=\left(\eta(c_{1,[n]}),g^{(0)}(\bm x),g^{(1)}(\bm x),
h^{(0)}(\bm x),h^{(1)}(\bm x)\right)$ is computable in linear

For each $\bm x\in\mathbb Z_q^n$, by Construction 1, the length
$|g^{(\ell)}(\bm x)|$ of $g^{(\ell)}(\bm x)$, $\ell\in\{0,1\}$,

\begin{align*}|g^{(\ell)}(\bm x)|&\leq \log (2n^\ell
N_1)\\&=\ell\log n+\log q\log\log n+1\end{align*}
Similarly, the
length $|h^{(\ell)}(\bm x)|$ of $h^{(\ell)}(\bm x)$,
$\ell\in\{0,1\}$, satisfies

\begin{align*}|h^{(\ell)}(\bm x)|&\leq \log N_2\\
&=\log q(7\log\log n+o(\log\log n))\end{align*}
Moreover, by Lemma
<ref>, the length of $\eta(c_{1,[n]})$ satisfies

$$|\eta(c_{1,[n]})|\leq4\log n+10\log\log n+O(1).$$
Thus, by
Construction 1, the length of $f(\bm x)$ satisfies

\begin{align*}|f(\bm x)|&=|\eta(c_{1,[n]})|
+|g^{(0)}(\bm x)|+|g^{(1)}(\bm x)|\\&~~~~+|h^{(0)}(\bm
x)|+|h^{(1)}(\bm x)|\\&\leq 5\log n+(16\log q+10)\log\log
n\\&~~~~+o(\log q\log\log n)\\&=5\log n+O(\log q\log\log

It remains to prove that for each $\bm{x}\in\mathcal R_n$, given
$f(\bm x)$ and any $\bm y\in\mathcal D_2(\bm x)$, one can uniquely
recover $\bm x$. To prove this, we first prove that $g_j(\bm
x)<N_1$ for each $j\in[n']$ and $h_j(\bm x)<N_2$ for each
$j\in\{1,2,\cdots,\left\lceil n/\rho\right\rceil-1\}$.

Since $\bm{x}\in\mathcal R_n$, by Remark <ref>,
each run of $c_{1,[n]}$ has length at most $7\log n~($noticing
that we take $d=7$ in this paper$)$, so for each
$i\in[2,\left\lceil\log q\right\rceil]$ and $j\in[n']$, we have
$c_{i,I_j}\in\{0,1\}^{\leq 7\log n}$. By Lemma <ref>,
for each $j\in[2,\left\lceil\log q\right\rceil]$, the length of
$\text{VT}(c_{j,I_i})$ satisfies $|\text{VT}(c_{j,I_i})|\leq
\log(7\log n)\leq\log\log n+3.$ By Construction 1, the length of
$g_j(\bm x)$ satisfies
\begin{align*}|g_j(\bm x)|&\leq
(\left\lceil\log q\right\rceil-1)(\log\log n+3)\\&<(\log
q)(\log\log n+3),\end{align*}

$$g_j(\bm x)<q^{\log\log n+3}=N_1.$$

Similarly, for each $i\in[2,\left\lceil\log q\right\rceil]$ and
each $j\in\{1,2,\cdots,\left\lceil n/\rho\right\rceil-1\}$, by
(<ref>), the length of the interval $c_{i,J_j}$
satisfies $|c_{i,J_j}|\leq 2\rho=42\log n$, so by Lemma
<ref>, we have

\begin{align*}|\xi(c_{i,I_j})|&\leq 7\log(42\log n)+o(\log(42\log
n))\\&=7\log\log n+o(\log\log n).\end{align*}
By Construction 1,

\begin{align*}|h_j(\bm x)|&\leq(\left\lceil\log q\right\rceil-1)(7\log\log
n+o(\log\log n))\\&<(\log q)(7\log\log n+o(\log\log

$$h_j(\bm x)<q^{7\log\log n+o(\log\log n)}=N_2.$$

Now, we prove that each $\bm{x}\in\mathcal R_n$ can be uniquely
recovered from $f(\bm x)=\left(\eta(c_{1,[n]}),g^{(0)}(\bm
x),g^{(1)}(\bm x), h^{(0)}(\bm x),h^{(1)}(\bm x)\right)$ and any
given $\bm y\in\mathcal D_2(\bm x)$. Let
y}=(d_{i,j})_{\left\lceil\log q\right\rceil\times (n-2)}$$
be the
matrix representation of $\bm y$. Then $M_{\bm y}$ can be obtained
from $M_{\bm x}$ by deleting two columns, so
$d_{1,[n-2]}\in\mathcal D_2(c_{1,[n]})$, where $d_{1,[n-2]}$ is
the first row of $M_{\bm y}$. Since $\bm x\in\mathcal R_n$, then
$c_{1,[n]}$ is regular. By Lemma <ref>, $\bm
c\triangleq c_{1,[n]}$ can be correctly recovered from $\bm
d\triangleq d_{1,[n-2]}$ and $\eta(c_{1,[n]})$. Moreover, by Lemma
<ref>, exact one of the following two cases holds:

Case 1: There are two distinct runs $c_{1,I_{j_1}}$ and
$c_{1,I_{j_2}}$ of $c_{1,[n]}$ such that $d_{1,[n-2]}$ is obtained
from $c_{1,[n]}$ by deleting one symbol in $c_{1,I_{j_1}}$ and one
symbol $c_{1,I_{j_2}}$. Correspondingly, $M_{\bm y}$ can be
obtained from $M_{\bm x}$ by deleting one column in $I_{j_1}$ and
one column in $I_{j_2}$. Without loss of generality, assume
$j_1<j_2$. Denoting $I_{j}=[p_{j-1}+1,p_j]$, where
$p_0=0<p_1<p_2<\cdots <p_{n'}=n$, then by comparing the symbols of
$M_{\bm x}$ and $M_{\bm y}$, we have the following observation:

i) $c_{i,I_j}=d_{i,I_j}$ for $1\leq j<j_1$ and each
$i\in[2,\left\lceil\log q\right\rceil]$;

ii) $d_{i,[p_{j_1-1}+1,p_{j_1}-1]}\in \mathcal
D_1(c_{i,I_{j_1}})$ for each
$i\in[2,\left\lceil\log q\right\rceil]$;

iii) $c_{i,I_j}=d_{i,I_j-1}$ for each $j_1<j<j_2$ and
$i\in[2,\left\lceil\log q\right\rceil]$, where
$I_j-1=\{\ell-1:\ell\in I_{j}\}=[p_{j-1},p_j-1]$;

iv) $d_{i,[p_{j_2-1},p_{j_2}-2]}\in \mathcal
D_1(c_{i,I_{j_2}})$ for each
$i\in[2,\left\lceil\log q\right\rceil]$;

v) $c_{i,I_j}=d_{i,I_j-2}$ for each $j_2<j\leq n'$ and
$i\in[2,\left\lceil\log q\right\rceil]$, where
$I_j-2=\{\ell-2:\ell\in I_{j}\}=[p_{j-1}-1,p_j-2]$.

Then $c_{i,[n]}$, $i\in[2,\left\lceil\log q\right\rceil]$, can be
recovered by the following three steps.

Step 1: By observations i), iii) and v), $c_{i,I_j}$ can
be directly obtained from $M_{\bm y}$ for all
$i\in[2,\left\lceil\log q\right\rceil]$ and

Step 2: Compute $g_j(\bm x)$ from $c_{2,I_j}, \cdots,
c_{\left\lceil\log q\right\rceil,I_j}$ for all
$j\in[n']\backslash\{j_1,j_2\}$. This is possible because for all
$i\in[2,\left\lceil\log q\right\rceil]$ and
$j\in[n']\backslash\{j_1,j_2\}$, $c_{i,I_j}$ have been obtained
from $M_{\bm y}$ in Step 1. Then by taking $\ell=0$ in
(<ref>), we can obtain

\begin{align*}g_{j_1}(\bm x)+g_{j_2}(\bm x)\equiv \left(\!g^{(0)}(\bm
Since $g_{j}(\bm x)<N_1$
for all $j\in[n']$, we in fact have

\begin{align}\label{slv-g1}
g_{j_1}(\bm x)+g_{j_2}(\bm x)= \left(\!g^{(0)}(\bm
Similarly, taking $\ell=1$
in (<ref>) and noticing that $0<j_1g_{j_1}(\bm
x)+j_2g_{j_2}(\bm x)<2nN_1$, we can obtain

\begin{align}\label{slv-g2}&j_1g_{j_1}(\bm x)+j_2g_{j_2}(\bm x)\nonumber\\
\end{align}

So, $g_{j_1}(\bm x)$ and $g_{j_2}(\bm x)$ can be solved from
(<ref>) and (<ref>). By Construction 1, we have

$$g_{j_1}(\bm x)=\left(\text{VT}(c_{2,I_{j_1}}),
\text{VT}(c_{3,I_{j_1}}), \cdots, \text{VT}(c_{\lceil\log
x)=\left(\text{VT}(c_{2,I_{j_2}}), \text{VT}(c_{3,I_{j_2}}),
\cdots, \text{VT}(c_{\lceil\log q\rceil,I_{j_2}})\right).$$

Step 3: By observation ii),
$d_{i,[p_{j_1-1}+1,p_{j_1}-1]}\in \mathcal D_1(c_{i,I_{j_1}})$ for
each $i\in[2,\left\lceil\log q\right\rceil]$. Then by Lemma
<ref>, $c_{i,I_{j_1}}$ can be recovered from
$\text{VT}(c_{i,I_{j_1}})$ and $d_{i,[p_{j_1-1}+1,p_{j_1}-1]}$.
Similarly, since by observation iv),
$d_{i,[p_{j_2-1},p_{j_2}-2]}\in \mathcal D_1(c_{i,I_{j_2}})$ for
each $i\in[2,\left\lceil\log q\right\rceil]$, then by Lemma
<ref>, $c_{i,I_{j_2}}$ can be recovered from
$\text{VT}(c_{i,I_{j_2}})$ and $d_{i,[p_{j_2-1},p_{j_2}-2]}$.

Thus, for case 1, $c_{i,[n]}$, $i\in[2,\left\lceil\log
q\right\rceil]$, can be recovered from $\eta(c_{1,[n]})$,
$g^{(0)}(\bm x)$, $g^{(1)}(\bm x)$ and $\bm y$.

Case 2: There is an interval $J\subseteq[n]$ of length at
most $\rho=3d\log n$ such that $\bm d\triangleq d_{1,[n-2]}$ can
be obtained from $\bm c\triangleq c_{1,[n]}$ by deleting two
symbols in $c_{1,J}$. Correspondingly, $M_{\bm y}$ can be obtained
from $M_{\bm x}$ by deleting two columns in $J$. By 1) of Remark
<ref>, we can always find an $J_{j_0}$ for some
$j_0\in\{1,2,\cdots,\left\lceil n/\rho\right\rceil-1\}$ such that
$J\subseteq J_{j_0}$. Denoting $J_{j_0}=[\lambda, \lambda']$, then
by comparing the symbols of $M_{\bm x}$ and $M_{\bm y}$, we obtain
that for each $i\in[2,\left\lceil\log q\right\rceil]$,

$$d_{i,[\lambda,\lambda'-2]}\in\mathcal D_{\leq 2}(c_{i,[\lambda,\lambda']}).$$

Hence, $c_{i,[1,\lambda-1]}$ and $c_{i,[\lambda'+1,n]}$ can be
directly obtained from $M_{\bm y}$. Moreover, each
$c_{i,[\lambda,\lambda']}$ can be recovered from
$d_{i,[\lambda,\lambda'-2]}$ and $h^{(\ell)}(\bm x)$,
$\ell\in\{0,1\}$, as follows.

By 2) of Remark <ref>, $J_j\subseteq[1,\lambda-1]$ for
all $j\in\{1$, $2$, $\cdots$, $j_0-2\}$, so $c_{i,J_j}$ can be
obtained from $d_{i,[1,\lambda-1]}=c_{i,[1,\lambda-1]}$.
Similarly, $c_{i,J_j}$ can be obtained from
$d_{i,[\lambda'+1-t,n]}=c_{i,[\lambda'+1,n]}$ for all
$j\in\{j_0+2,\cdots,\left\lceil n/\delta'\right\rceil-1\}$. Hence,
we can compute $h_j(\bm
q\rceil,J_j})\right)$ for each $j\in\{1,2,\cdots,\left\lceil
n/\delta'\right\rceil-1\}\backslash\{j_0\}$. Let $\ell\in\{0,1\}$
be such that $j_0\equiv\ell\mod 2$. Then by (<ref>),
and noticing that $h_{j_0}(\bm x)<N_2$, we can obtain

\begin{align*}
h_{j_0}(\bm x)=h^{(\ell)}(\bm
j\!~\equiv\!~\ell~\text{mod}~2}} h_j(\bm
Note that
$b_{i,[\lambda,\lambda'-2]}\in\mathcal D_{\leq
2}(c_{i,[\lambda,\lambda']})=\mathcal D_{\leq 2}(c_{i,J_{j_0}})$,
and by Construction 1,

Then by Lemma <ref>, for
each $i\in[2,\left\lceil\log q\right\rceil]$,
$c_{i,[\lambda,\lambda']}=c_{i,J_{j_0}}$ can be recovered from
$d_{i,[\lambda,\lambda'-2]}$ and $h_{j_0}(\bm x)$.

Thus, for case 2, $c_{i,[n]}$, $i\in[2,\left\lceil\log
q\right\rceil]$, can be recovered from $\eta(c_{1,[n]})$,
$h^{(\ell)}(\bm x)$ and $\bm y$.

By the above discussions, we proved that $M_{\bm x}~($and so $\bm
x)$ can be uniquely recovered from $f(\bm x)$ and $\bm y$, which
completes the proof.

By representing each binary string of length at most
$\lfloor\log q\rfloor$ as an integer in $\mathbb Z_q$, each binary
string $\bm a$ can be represented as a $q$-ary string of length
$\left\lceil|\bm a|/\lfloor\log q\rfloor\right\rceil$. We denote
this $q$-ary string by $\mathcal Q(\bm a)$ and call it the
$q$-ary representation of $\bm a$ for convenience of use.
Specifically, divide $\bm a$ into $\left\lceil|\bm a|/\lfloor\log
q\rfloor\right\rceil$ disjoint substrings, each having length
$\lfloor\log q\rfloor$ except the last substring which has length
$|\bm a|-\left(\left\lceil|\bm a|/\lfloor\log
q\rfloor\right\rceil-1\right)\lfloor\log q\rfloor$. Then by
representing each of these substrings as an integer in $\mathbb
Z_q$, we can obtain a $q$-ary string $\mathcal Q(\bm a)$ of length
$\left\lceil|\bm a|/\lfloor\log q\rfloor\right\rceil$.

Let $\text{RegEnc}: \{1,2,\cdots,M\}\rightarrow\{0,1\}^n$ be the
one-to-one mapping constructed in Lemma <ref>. Since
$M\geq 2^{n-1}$, then $\text{RegEnc}$ can also be viewed as a
mapping from $\{0,1\}^{n-1}$ to $\{0,1\}^n$. By Lemma
<ref>, the mapping $\text{RegEnc}$ can be extended to a
one-to-one mapping, denoted by
$$\mathcal E_{\text{Reg}}:\mathbb
Z_q^{n-1}\rightarrow\mathbb Z_q^{n},$$
such that for any $\bm
u\in\mathbb Z_q^{n-1}$ and $\bm x=\mathcal E_{\text{Reg}}(\bm u)$,
if $M_{\bm{u}}=(b_{i,j})_{\lceil\log q\rceil\times(n-1)}$ and
$M_{\bm{x}}=(c_{i,j})_{\lceil\log q\rceil\times n}$ are the matrix
representation of $\bm u$ and $\bm x$ respectively, then

By Lemma
<ref>, $c_{1,[n]}=\text{RegEnc}(b_{1,[n-1]})$ is
regular, so for any $\bm u\in\mathbb Z_q^{n-1}$, we have $\bm
x=\mathcal E_{\text{Reg}}(\bm u)\in\mathcal R_n$.

Using the mapping $\mathcal E_{\text{Reg}}:\mathbb
Z_q^{n-1}\rightarrow\mathcal R_n$ and the function $f$ constructed
in Construction 1, we can give an encoding function of a $q$-ary
two-deletion correcting code as follows.

Let $\mathcal E$ be the function defined on $\mathbb Z_q^{n-1}$ of
the form

\begin{align}\label{2del-enc-fun}
\mathcal E(\bm u)=(\bm v, \bm v', \bm v''), ~\forall \!~\bm
u\in\mathbb Z_q^{n-1},
\end{align}

such that $\bm v=\mathcal E_{\text{Reg}}(\bm u)$, $\bm v'=\mathcal
E_{\text{Reg}}(\mathcal Q(f(\bm v)))$ and $\bm
v''=\text{Rep}_3(\mathcal Q(f(\bm v')))$, where
$\text{Rep}_{3}(\cdot)$ is the encoding function of the $3$-fold
repetition code.

The code $\mathcal C=\{\mathcal E(\bm u): \bm u\in\mathbb
Z_q^{n-1}\}$, where $\mathcal E$ is given by (<ref>),
is a $q$-ary two-deletion correcting code with redundancy $5\log
n+O(\log q\log\log n)$ in bits. The encoding complexity of
$\mathcal C$ is near-linear in $n$ with a polynomial size lookup

$$\bm x=\mathcal E(\bm u)=(\bm v, \bm v', \bm v'')\in\mathcal
where $\bm u\in\mathbb Z_q^{n-1}$, $\bm v=\mathcal
E_{\text{Reg}}(\bm u)$, $\bm v'=\mathcal Q(f(\bm v))$ and $\bm
v''=\text{Rep}_3(\mathcal Q(f(\bm v')))$ as in
(<ref>). Given any $\bm y\in\mathcal D_2(\bm x)$, we
have $y_{[1,m_1-2]}\in\mathcal D_2(\bm v)$,
$y_{[m_1,m_2-2]}\in\mathcal D_2(\bm v')$ and
$y_{[m_2,m_3-2]}\in\mathcal D_2(\bm v'')$, where $|\bm v|=m_1,
|(\bm v,\bm v')|=m_2$ and $|\bm x|=|(\bm v,\bm v',\bm v'')|=m_3$.
First, since $\bm v''=\text{Rep}_3(\mathcal Q(f(\bm v')))$ is a
codeword of a two-deletion code, then $\mathcal Q(f(\bm v'))$ can
be recovered from $y_{[m_2,m_3-2]}$, and hence $f(\bm v')$ can be
recovered from $\mathcal Q(f(\bm v'))$. Then by Theorem
<ref>, $\bm v'$ can be recovered from
$y_{[m_1,m_2-2]}$ and $f(\bm v')$, and hence $f(\bm v)$ can be
recovered from $\bm v'=\mathcal E_{\text{Reg}}(\mathcal Q(f(\bm
v)))$. Finally, by Theorem <ref> again, $\bm v$
can be recovered from $y_{[1,m_1-2]}$ and $f(\bm v)$. Thus, $\bm
x=(\bm v, \bm v', \bm v'')$ can be recovered from any $\bm
y\in\mathcal D_2(\bm x)$, which proves that $\mathcal C$ is a
two-deletion correcting code.

Since $\bm u\in\mathbb Z_q^{n-1}$ and $\bm v=\mathcal
E_{\text{Reg}}(\bm u)\in\mathbb Z_q^{n}$, so $\bm v$ has $\log q$
bits redundancy. Moreover, by Theorem <ref>, the
length of $\bm v'$ is
$$|\bm v'|=5\log n+O(\log q\log\log n)$$

bits and the length of $\bm v''$ is
$$|\bm v''|=3(5\log |\bm
v'|+O(\log q\log\log |\bm v'|))=O(\log\log n)$$
bits. So the total
redundancy of $\bm x=\mathcal E(\bm u)$ is

\begin{align*}\text{redundancy~of}~\bar{\mathcal
C}&=\log q+|\bm v'|+|\bm v''|\\&=5\log n+O(\log q\log\log
in bits.

By Lemma <ref> and Lemma <ref>, the
encoding complexity of $\bm v=\mathcal E_{\text{Reg}}(\bm u)$ is
near-linear in $n$ with a polynomial size lookup table. Moreover,
by Theorem <ref>, the encoding complexity of $\bm
v'=\mathcal E_{\text{Reg}}(\mathcal Q(f(\bm v)))$ and $\bm
v''=\text{Rep}_3(\mathcal Q(f(\bm v')))$ is linear in $n$ and
$\log n$ respectively. Therefore, the encoding complexity of
$\mathcal E(\bm u)=(\bm v, \bm v', \bm v'')$ is near-linear in $n$
with a polynomial size lookup table, which completes the proof.

§ BINARY CODES CORRECTING A BURST OF AT MOST $T$ DELETIONS

In this section, we present a construction of binary codes that
are capable of correcting a bursting of at most $t$ deletions
improving the Lenz-Polyanskii Construction in [18]. We
assume that $t$ is a constant with respect to the code length $n$,
and for notational simplicity, we use $\gamma_t$ to denote any
constant that depends only on $t$. As in Section III, each binary
sequence $\bm a$ is identified with the positive integer whose
binary representation is $\bm a$, and summation and multiplication
of binary strings and integers are performed in the set of

Recall that a string $\bm c\in\{0,1\}^n$ is called $(\bm p,
\delta)$-dense, if each substring of $\bm c$ of length $\delta$
contains at least one pattern $\bm p$. As stated in Section II, we

$$\delta=t2^{t+1}\log n$$

$$\bm p=0^t1^t.$$

The basic idea of our construction is to replace the shifted VT
code in the Lenz-Polyanskii Construction with the function $\phi$
constructed in Lemma <ref>. To apply the
function $\phi$, we need to divide each binary string into
substrings of length at most $2(\delta+t)$. Specifically, we
denote $\delta'=\delta+t$ and let

\begin{equation}\label{def-Li-intvl}
L_i=\!\left\{\!\begin{aligned} &[(i-1)\delta'\!+1, (i+1)\delta'],
~\text{for}~i\in\!\{1,\cdots, \left\lceil n/\delta'\right\rceil-2\},\\
&[(i-1)\delta'\!+1, n], ~~~~~~~\!~~~\text{for}~i=\left\lceil
\end{aligned}\right.
\end{equation}

where $i\in\{1,\cdots, \left\lceil n/\delta'\right\rceil-1\}$, be
the index sets of the expected substrings. Then we can construct a
function $\bar{f}^{\text{b}}$ over $\{0,1\}^n$ as follows, which
is the main component of our construction of binary burst-deletion
correcting codes.

Construction 2: Let $\phi$ and $\mu$ be the functions
constructed in Lemma <ref> and Lemma
<ref> respectively. For each $\bm
c\in\{0,1\}^n$, let

\begin{align*}%\label{Constr2-f-b}
\bar{f}^{\text{b}}(\bm c)=\left(\mu(\bm c), \bar{g}^{(0)}(\bm c),
\bar{g}^{(1)}(\bm c)\right),\end{align*}
such that for each

\begin{align}\label{Constr2-g-b}
\bar{g}^{(\ell)}(\bm
i~\equiv~ \ell~\text{mod}~2}}
\phi(c_{L_i})~\text{mod}~\overline{N}^{\text{b}},\end{align}

\begin{align*}\overline{N}^{\text{b}}\triangleq
n+\gamma_t+o(\log\log n)}.\footnotemark{}\end{align*}

Since $\delta'=\delta+t=t2^{t+1}(\log n+2^{-t-1})$,
so more accurately, it should be
n+2^{-t-1})+\gamma_t+o(\log\log n)}$. However, because
$\overline{N}^{\text{b}}$ is an integer, so for sufficiently large
$n$, we can always obtain $\overline{N}^{\text{b}}\triangleq
n+\gamma_t+o(\log\log n)}$.

For Construction 2, we have the following theorem.

For each $\bm c\in\{0,1\}^n$, $\bar{f}^{\text{b}}(\bm c)$ is
computable in linear time and the length $|\bar{f}^{\text{b}}(\bm
c)|$ of $\bar{f}^{\text{b}}(\bm c)$ satisfies

$$|\bar{f}^{\text{b}}(\bm c)|\leq\log n+8\log\log
n+\gamma_t+o(\log\log n).$$
Moreover, if $\bm c$ is $(\bm p,
\delta)$-dense, then given $\bar{f}^{\text{b}}(\bm c)$ and any
$\bm b\in\mathcal B_{\leq t}(\bm c)$, one can uniquely recover
$\bm c$.

Before proving Theorem <ref>, we give some
remark on the properties of the sets $L_j,
j=1,2,\cdots,\left\lceil n/\delta'\right\rceil-1$.

Similar to Remark <ref>, it is easy to see that

1) For each interval $L\subseteq[n]$ of length at most
$\delta'=\delta+t$, we can always find an
$i_0\in\{1,2,\cdots,\left\lceil n/\delta'\right\rceil-1\}$
such that $L\subseteq L_{i_0}$.

2) $L_i\cap L_{i'}=\emptyset$ for all $i,i'\in\{1,2,\cdots,
\left\lceil n/\delta'\right\rceil-1\}$ such that $|i-i'|\geq 2$.

Now, we can prove Theorem <ref>.

Note that by Lemma <ref>, $\mu(\bm c)$ is
computable in linear time. By Lemma <ref>,
each $\phi(c_{L_i})$ is computable in time
$O(2^t(2\delta)^3)=O((\log n)^3)$, so $(\bar{g}^{(0)}(\bm
c),\bar{g}^{(1)}(\bm c))$ are also computable in linear time.
Hence, by Construction 2, $\bar{f}^{\text{b}}(\bm c)=\left(\mu(\bm
c), \bar{g}^{(0)}(\bm c), \bar{g}^{(1)}(\bm c)\right)$ is
computable in linear time. Moreover, by Lemma
<ref> and (<ref>), the length
$|\bar{f}^{\text{b}}(\bm c)|$ of $\bar{f}^{\text{b}}(\bm c)$

\begin{align*}|\bar{f}^{\text{b}}(\bm c)|&=|\mu(\bm c)|+
|\bar{g}^{(0)}(\bm c)|+|\bar{g}^{(1)}(\bm c)|\\&\leq\log
n+3+2\big(4\log\log n+\gamma_t+o(\log\log n)\big)\\&=\log
n+8\log\log n+\gamma_t+o(\log\log n).\end{align*}

Suppose $\bm c$ is $(\bm p, \delta)$-dense and $\bm b\in\mathcal
B_{\leq t}(\bm c)$. We need to prove that $\bm c$ can be uniquely
recovered from $\bm b$ and $\bar{f}^{\text{b}}(\bm c)$.

By Lemma <ref>, we can find an interval
$L\subseteq[n]$ of length at most $\delta'=\delta+t$ such that
$\bm b=c_{[n]\backslash D}$ for some interval $D\subseteq L$ of
length $t'=|\bm c|-|\bm b|$. By 1) of Remark <ref>, we
can always find an $i_0\in\{1,2,\cdots,\left\lceil
n/\delta'\right\rceil-1\}$ such that $L\subseteq L_{i_0}$.
Denoting $L_{i_0}=[\lambda, \lambda']$, then we can obtain

$$b_{[\lambda,\lambda'-t']}\in\mathcal B_{\leq t}(c_{[\lambda,\lambda']}).$$

Therefore, $c_{[1,\lambda-1]}$ and $c_{[\lambda'+1,n]}$ can be
directly obtained from $\bm b$. In the following, we will show how
to recover $c_{[\lambda,\lambda']}$ from
$b_{[\lambda,\lambda'-t']}$ and $\bar{g}^{(\ell)}(\bm c)$ for some

By 2) of Remark <ref>, for all
$i\in\{1,2,\cdots,i_0-2\}$, we have $L_i\subseteq[1,\lambda-1]$,
so $c_{L_i}$ can be obtained from $b_{[1,\lambda-1]}$ and hence
$\phi(c_{L_i})$ can be computed. Similarly, for all
$i\in\{i_0+2,\cdots,\left\lceil n/\delta'\right\rceil-1\}$,
$c_{L_i}$ can be obtained from $b_{[\lambda'-t'+1,n]}$ and hence
$\phi(c_{L_i})$ can be computed. Let $\ell_0\in\{0,1\}$ be such
that $\ell_0~\equiv~ i_0~\text{mod}~2$. By (<ref>), we

\begin{align*}
\phi(c_{L_{i_0}})\equiv\bar{g}^{(\ell_0)}(\bm
i\!~\neq\!~ i_0\!~\text{and}\!~ i\!~\equiv\!~
\ell_0\!~\text{mod}\!~2}}
\phi(c_{L_i})~\text{mod}~\overline{N}^{\text{b}}.\end{align*}
(<ref>), $|L_{i_0}|=2\delta'=2(\delta+t)$, so by
Lemma <ref>, $\phi(c_{L_{i_0}})\leq
Therefore, we actually have

\begin{align*}
\phi(c_{L_{i_0}})=\bar{g}^{(\ell_0)}(\bm
i\!~\neq\!~ i_0\!~\text{and}\!~ i\!~\equiv\!~
\ell_0\!~\text{mod}\!~2}}
\phi(c_{L_i})~\text{mod}~\overline{N}^{\text{b}}.\end{align*}

Since $b_{[\lambda,\lambda'-t']}\in\mathcal B_{\leq
t}(c_{[\lambda,\lambda']})$, again by Lemma
<ref>, we can recover $c_{[\lambda,\lambda']}$
from $b_{[\lambda,\lambda'-t]}$ and $\phi(c_{L_{i_0}})$. Note that
we have obtained $c_{[1,\lambda-1]}=b_{[1,\lambda-1]}$ and
$c_{[\lambda'+1,n]} =b_{[\lambda'-t+1,n]}$, so $\bm c$ can be
uniquely recovered, which completes the proof.

Let $\mathcal S^{\text{b}}_n$ be the set of all $(\bm p,
\delta)$-dense binary strings $\bm c\in\{0,1\}^{n}$, where $\bm
p=0^t1^t$ and $\delta=t2^{t+1}\lceil\log n\rceil$. By Lemma
<ref>, there is a one-to-one mapping that maps each
binary string of length $n-1$ to a string in $\mathcal
S^{\text{b}}_n$. For convenience, we denote this mapping by

\begin{align}\label{E-B-Den}\mathcal
Using the function $\bar{f}^{\text{b}}$
constructed in Construction 2, we can construct an encoding
function of a binary code capable of correcting a burst of at most
$t$ deletions.

Let $\bar{\mathcal E}^{\text{b}}$ be a function defined on
$\{0,1\}^{n-1}$ of the form

\begin{align}\label{BBtdel-enc-fun}
\bar{\mathcal E}^{\text{b}}(\bm a)=(\bm b, \bm b', \bm b''),
~~\forall\!~\bm a\in\{0,1\}^{n-1},
\end{align}

such that $\bm b=\mathcal E^{\text{b}}_{\text{Den}}(\bm a)$, $\bm
b'=\mathcal E^{\text{b}}_{\text{Den}}(\bar{f}^{\text{b}}(\bm b))$
and $\bm b''=\text{Rep}_{t+1}(\bar{f}^{\text{b}}(\bm b'))$, where
$\text{Rep}_{t+1}(\cdot)$ is the encoding function of the
$(t+1)$-fold repetition code.

The code $\bar{\mathcal C}^{\text{b}}=\{\bar{\mathcal
E}^{\text{b}}(\bm a): \bm a\in\{0,1\}^{n-1}\}$, where
$\bar{\mathcal E}^{\text{b}}$ is given by (<ref>),
is a binary code with redundancy $\log n+9\log\log
n+\gamma_t+o(\log\log n)$ bits and capable of correcting a burst
of at
most $t$ deletions.

$$\bm c=\bar{\mathcal E}^{\text{b}}(\bm a)=(\bm b, \bm b', \bm
b'')\in\bar{\mathcal C}^{\text{b}},$$
where $\bm
a\in\{0,1\}^{n-1}$, $\bm b=\mathcal E^{\text{b}}_{\text{Den}}(\bm
a)$, $\bm b'=\mathcal
E^{\text{b}}_{\text{Den}}(\bar{f}^{\text{b}}(\bm b))$ and $\bm
b''=\text{Rep}_{t+1}(\bar{f}^{\text{b}}(\bm b'))$. Given any $\bm
d\in\mathcal B_{\leq t}(\bm c)$, denoting $t'=|\bm c|-|\bm b|$,
then $t'\leq t$ and we have $d_{[1,m_1-t']}\in\mathcal B_{\leq
t}(\bm b)$, $d_{[m_1,m_2-t']}\in\mathcal B_{\leq t}(\bm b')$ and
$d_{[m_2,m_3-t']}\in\mathcal B_{\leq t}(\bm b'')$, where $m_1=|\bm
b|, m_2=|(\bm b,\bm b')|$ and $m_3=|\bm c|=|(\bm b,\bm b',\bm
b'')|$. First, since $\bm
b''=\text{Rep}_{t+1}(\bar{f}^{\text{b}}(\bm b'))$ is a codeword of
a $t$-deletion code, then $\bar{f}^{\text{b}}(\bm b')$ can be
recovered from $d_{[m_2,m_3-t']}$. Further, by Theorem
<ref>, $\bm b'$ can be recovered from
$d_{[m_1,m_2-t']}$ and $\bar{f}^{\text{b}}(\bm b')$, and so
$\bar{f}^{\text{b}}(\bm b)$ can be recovered from $\bm b'=\mathcal
E^{\text{b}}_{\text{Den}}(\bar{f}^{\text{b}}(\bm b))$. Finally, by
Theorem <ref> again, $\bm b$ can be
recovered from $d_{[1,m_1-t']}$ and $\bar{f}^{\text{b}}(\bm b)$.
Thus, $\bm c=(\bm b, \bm b', \bm b'')$ can be recovered from any
$\bm d\in\mathcal B_{\leq t}(\bm c)$, which proves that
$\bar{\mathcal C}^{\text{b}}$ is capable of correcting a burst of
at most $t$ deletions.

Since $\bm a\in\{0,1\}^{n-1}$ and $\bm b=\mathcal
E^{\text{b}}_{\text{Den}}(\bm a)\in\mathcal
S^{\text{b}}_n\subseteq\{0,1\}^{n}$, so $\bm b$ has one bit
redundancy. Moreover, by Theorem <ref>, the
length of $\bm b'$ is
$$|\bm b'|=\log n+8\log\log
n+\gamma_t+o(\log\log n)$$
bits and the length of $\bm b''$ is

\begin{align*}
|\bm b''|&=\log |\bm b'|+8\log\log |\bm b'|+\gamma_t+o(\log\log
|\bm b'|)\\&=\log\log n+\gamma_t+o(\log\log n)\end{align*}
So the total redundancy of $\bm c=\bar{\mathcal E}^{\text{b}}(\bm
a)$ is

\begin{align*}\text{redundancy~of}~\bar{\mathcal
C}&=1+|\bm b'|+|\bm b''|\\&=\log n+9\log\log n+\gamma_t+o(\log\log

§ $Q$-ARY CODES CORRECTING A BURST OF AT MOST $T$ DELETIONS

In this section, we construct $q$-ary codes correcting a bursting
of at most $t$ deletions, where $q>2$ is an even integer. We
assume that $q$ and $t$ are constant with respect to the code
length $n$. As in Section III, we identify each binary string $\bm
a$ with the positive integer whose binary representation is $\bm
a$. As stated in Section II, we take

$$\delta=t2^{t+1}\log n$$

$$\bm p=0^t1^t.$$
A string $\bm c\in\{0,1\}^n$ is called $(\bm p,
\delta)$-dense, if each substring of $\bm c$ of length $\delta$
contains at least one pattern $\bm p$.

For each $\bm x\in\mathbb Z_q^n$, let
$M_{\bm{x}}=(c_{i,j})_{\lceil\log q\rceil\times n}$ be the matrix
representation of $\bm x$ as defined by (<ref>). Then for
each $t'\in[t]$, the deletion of $x_{i},x_{i+1},\cdots,x_{i+t'-1}$
results in the deletion of the columns $i,i+1,\cdots,i+t'-1$ of
$M_{\bm{x}}$. A basic idea is to protect the first row $\bm
c=c_{1,[n]}$ by a burst-deletion correcting code. However, in
general, if $\bm c$ can be recovered from a $\bm d\in\mathcal
B_{\leq t}(\bm c)$, the location of the deleted symbols can not be
determined. For example, consider $\bm c=0111011011010010$ and
$\bm d=0111011010010$. Then $\bm d$ can be obtained from $\bm c$
by deleting $c_3c_4c_5=110$, or deleting $c_4c_5c_6=101$. In fact,
$\bm d$ can be obtained from $\bm c$ by deleting
$c_ic_{i+1}c_{i+2}$ for all $i\in[3,10]$. To proceed, we need to
consider period of binary strings.

Let $\ell$ and $m$ be two positive integers such that $\ell\leq
m$. A string $\bm a\in\{0,1\}^m$ is said to have period
$\ell~($or $\bm a$ is called a period-$\ell$ string$)$ if
$a_{i+\ell}=a_i$ for all $i\in[m-\ell]=\{1,2,\cdots,m-\ell\}$.
Clearly, a run of $\bm c$ of length $m$ has period $\ell$ for any
$\ell\in[m]$; a period-$2$ substring of $\bm c$ is either a run of
$\bm c$ or an alternative substring of $\bm c$.

Suppose $\bm c\in\{0,1\}^n$ is $(\bm p, \delta)$-dense. Given any
$\bm d\in\mathcal B_{\leq t}(\bm c)$, it is possible to find an
interval $K\subseteq[n]$ of length at most $\delta-1$ such that if
$\bm d=c_{[n]\backslash D}$ and $D\subseteq[n]$ is an interval,
then it always holds that $D\subseteq K$.

Since $\bm d\in\mathcal B_{\leq t}(\bm c)$, there is an interval
$D'\subseteq[n]$ such that $\bm d=c_{[n]\backslash D'}$. Let
$K\subseteq[n]$ be the interval such that $c_K$ is the maximal
substring of $\bm c$ satisfying: 1) $c_K$ has period $t'=|\bm
c|-|\bm d|$; 2) $c_K$ contains $c_{D'}$. We will prove that
$D\subseteq K$ for any interval $D\subseteq[n]$ such that $\bm
d=c_{[n]\backslash D}$.

Suppose $D=[i_1, i_1+t'-1]$ and $D'=[i_2, i_2+t'-1]$. Without loss
of generality, assume $i_1\leq i_2$. Since $c_{[n]\backslash
D}=\bm d=c_{[n]\backslash D'}$, we have

\begin{align*}
~c_{i_2+t'}~\cdots ~c_n\\
=~&c_1~\cdots ~c_{i_1-1}~~c_{i_1}~~~~c_{i_1+1}~~~\!~\cdots
\end{align*}

By comparing the symbols of $c_{[n]\backslash D'}$ and
$c_{[n]\backslash D''}$ in each position, we can obtain
$c_i=c_{i+t'}$ for each $i\in[i_1,i_2-1]$. So,
$c_{[i_1,i_2+t'-1]}$ is a substring of $\bm c$ of period $t'$ and
contains both $c_{D}$ and $c_{D'}$. As $c_K$ is the maximal
substring of $\bm c$ of period $t'$ that contains $c_{D'}$, so
$c_{[i_1,i_2+t'-1]}$ is contained in $c_K$. Thus, $c_{D}$ is
contained in $c_K$, which implies that $D\subseteq K$.

Since $\bm c$ is $(\bm p, \delta)$-dense, where $\bm p=0^t1^t$,
then each substring of $\bm c$ of length $\delta$ contains at
least one pattern $\bm p$. Note that for each $t'\in[t]$, we have
$p_{t}=0\neq 1=p_{t+t'}$, so each substring of $\bm c$ of length
$\delta$ can not has period $t'$. In other words, the length of
any period-$t'$ substring of $\bm c$ is at most $\delta-1$. Thus,
the length of $c_I~($and the length of $I)$ is at most $\delta-1$.

\begin{equation}\label{def-Ki-intvl}
K_j=\!\left\{\!\begin{aligned} &[(j-1)\delta\!+1, (j+1)\delta],
~\text{for}~j\in\!\{1,\cdots, \left\lceil n/\delta\right\rceil-2\},\\
&[(j-1)\delta\!+1, n], ~~~~~~~\!~~\!~\text{for}~j=\left\lceil
\end{aligned}\right.
\end{equation}

Similar to Remark <ref>, it is easy to see that

1) For any interval $K\subseteq[n]$ of length at most
$\delta$, there is an
$j_0\in\{1,2,\cdots,\left\lceil n/\delta\right\rceil-1\}$
such that $K\subseteq K_{j_0}$.

2) $K_j\cap K_{j'}=\emptyset$ for all $j,j'\in\{1,2,\cdots,
\left\lceil n/\delta\right\rceil-1\}$ such that $|j-j'|\geq 2$.

Let $\phi$ be the function constructed by Lemma
<ref> and $\bar{f}^{\text{b}}$ be the function
constructed in Construction 2. For each $\bm x\in\mathbb Z_q^n$,
let $M_{\bm{x}}=(c_{i,j})_{\lceil\log q\rceil\times n}$ be the
matrix representation of $\bm x$ as defined by (<ref>).
We have the following construction.

Construction 3: For each $\bm x\in\mathbb Z_q^n$ and each
$j\in\{1,2,\cdots, \left\lceil n/\delta\right\rceil-1\}$, let

$$\bar{h}_j(\bm x)=\left(\phi(c_{2,K_j}),\phi(c_{3,K_j}),\cdots,\phi(c_{\lceil\log
and for each $\ell\in\{0,1\}$, let

\begin{align}\label{Con3-h-ell}
\bar{h}^{(\ell)}(\bm x)=\sum_{\substack{j\in\{1,2,\cdots,
\left\lceil n/\delta\right\rceil-1\}:\\
j\!~\equiv\!~\ell~\text{mod}~2}} \bar{h}_j(\bm

$$\overline{N}=q^{4\log\log n+o(\log\log n)+\gamma_t}.$$

Finally, let

\begin{align}\label{Constr2-f}
\bar{f}(\bm x)=\left(\bar{f}^{\text{b}}(c_{1,[n]}),
\bar{h}^{(0)}(\bm x), \bar{h}^{(1)}(\bm x)\right).\end{align}

We have the following theorem.

For any $\bm x\in\mathbb Z_q^n$, $\bar{f}(\bm x)$ is computable in
linear time, and when viewed as a binary string, the length
$|\bar{f}(\bm x)|$ of $\bar{f}(\bm x)$ satisfies

$$|\bar{f}(\bm x)|\leq\log n+8(\log q+1)\log\log
n+o(\log q\log\log n)+\gamma_t,$$
where $\gamma_t$ is a constant
depending only on $t$. Moreover, if $\bm c=c_{1,[n]}$ is $(\bm p,
\delta)$-dense, then given $\bar{f}(\bm x)$ and any $\bm
y\in\mathcal B_{\leq t}(\bm x)$, one can uniquely recover $\bm x$.

Note that by Theorem <ref>,
$\bar{f}^{\text{b}}(c_{1,[n]})$ is computable in linear time.
Moreover, by Lemma <ref> and
(<ref>), each $\phi(c_{2,K_j})$ is computable in time
$O(2^t(2\delta)^3)=O((\log n)^3)$, so by Construction 3,
$\bar{h}^{(\ell)}(\bm x), \ell=1,2,$ are computable in linear
time. Hence, $\bar{f}(\bm x)=\left(\bar{f}^{\text{b}}(c_{1,[n]}),
\bar{h}^{(0)}(\bm x), \bar{h}^{(1)}(\bm x)\right)$ is computable
in linear time.

By Theorem <ref>, the length of
$\bar{f}^{\text{b}}(c_{1,[n]})$ satisfies

$$|\bar{f}^{\text{b}}(c_{1,[n]})|\leq\log n+8\log\log
n+\gamma_t+o(\log\log n).$$
Moreover, by Construction 3, the
length of $\bar{h}^{(\ell)}(\bm x), \ell=1,2,$ satisfy

$$|\bar{h}^{(\ell)}(\bm x)|\leq\log\overline{N}
=\log q(4\log\log n+o(\log\log n)+\gamma_t).$$
Hence, the length
of $\bar{f}(\bm x)$ satisfies

\begin{align*}
x)|+|\bar{g}^{(1)}(\bm x)|\\&\leq\log n+8(\log q+1)\log\log
n+o(\log q\log\log n)\\&~~~+\gamma_t.\end{align*}

It remains to prove that if $\bm c=c_{1,[n]}$ is $(\bm p,
\delta)$-dense, then given $\bar{f}(\bm x)$ and any $\bm
y\in\mathcal B_{\leq t}(\bm x)$, one can uniquely recover $\bm x$.
To prove this, we first prove that
for each $j\in\{1,2,\cdots, \left\lceil
n/\delta\right\rceil-1\}$. In fact, by (<ref>), each
$c_{i,K_j}$, $i\in[2,\lceil\log q\rceil]$, has length
$2\delta=2t2^{t+1}\log n$, so by Lemma <ref>,
$\phi(c_{2,K_j})$ has length
$4\log(2\delta)+o(\log(2\delta))=4\log\log n+\gamma_t+o(\log\log
n)$. Hence, by Construction 3, we have

\begin{align*}
q\rceil,K_j})\right)|\\&=(\lceil\log q\rceil-1)\left(4\log\log
n+\gamma_t+o(\log\log n)\right)\\&<\log q\left(4\log\log
n+\gamma_t+o(\log\log n)\right),
\end{align*}
which implies that $\bar{h}_j(\bm
x)<q^{4\log\log n+\gamma_t+o(\log\log n)}=\overline{N}$.

Now, we prove that $\bm x$ can be uniquely recovered from
$\bar{f}(\bm x)$ and any given $\bm y\in\mathcal B_{\leq t}(\bm
x)$, provided that $\bm c=c_{1,[n]}$ is $(\bm p, \delta)$-dense.
$$M_{\bm y}=(d_{i,j})_{\left\lceil\log q\right\rceil\times
be the matrix representation of $\bm y$. Since $\bm
y\in\mathcal B_{\leq t}(\bm x)$ can be obtained from $\bm x$ by
deleting $t'$ consecutive symbols from $\bm x$, where $t'=n-|\bm
y|$ and $t'\in[t]$, then $M_{\bm y}$ can be obtained from $M_{\bm
x}$ by deleting $t'$ consecutive columns of $M_{\bm x}$. The
process of recovering $\bm x$ from $\bar{f}(\bm
x)=\left(\bar{f}^{\text{b}}(c_{1,[n]}), \bar{g}^{(0)}(\bm x),
\bar{g}^{(1)}(\bm x)\right)$ and $\bm y$ consists of the following
three steps.

Step 1: Since $\bm c=c_{1,[n]}$ is $(\bm p,
\delta)$-dense, then by Theorem <ref>,
$c_{1,[n]}$ can be recovered from $d_{1,[n-t']}$ and

Step 2: According to Lemma <ref>, there
is an interval $K\subseteq[n]$ of length at most $\delta-1$ such
that $d_{1,[n-t']}$ is obtained from $\bm c=c_{1,[n]}$ by deleting
$t'$ consecutive symbols in $K$. Correspondingly, $M_{\bm y}$ is
obtained from $M_{\bm x}$ by deleting $t'$ consecutive columns in
$K$. By 1) of Remark <ref>, there is an
$j_0\in\{1,2,\cdots,\left\lceil n/\delta\right\rceil-1\}$ such
that $K\subseteq K_{j_0}$. Denote $K_{j_0}=[\lambda,\lambda']$.
Then we have the following observations:

i) $c_{i,[1,\lambda-1]}=d_{i,[1,\lambda-1]}$ for each
$i\in[2,\lceil\log q\rceil]$.

ii) $d_{i,[\lambda,\lambda'-t']}\in
\mathcal B_{\leq t}(c_{i,[\lambda,\lambda']}$ for each
$i\in[2,\lceil\log q\rceil]$.

iii) $c_{i,[\lambda'+1,n]}=d_{i,[\lambda'-t'+1,n-t']}$ for each
$i\in[2,\lceil\log q\rceil]$.

By observations i) and iii), for each $i\in[2,\lceil\log
q\rceil]$, $c_{i,[1,\lambda-1]}$ and $c_{i,[\lambda'+1,n]}$ can be
directly obtained from $M_{\bm y}$.

Step 3: For $j\in\{1,\cdots, j_0-2\}$, we have $K_j\cap
K_{j_0}=\emptyset$, by 2) of Remark <ref>, so
$K_j\subseteq[1,\lambda-1]$ and by observation i), $\bar{h}_j(\bm
q\rceil,K_j})\right)$ can be computed from
$d_{i,[1,\lambda-1]}=c_{i,[1,\lambda-1]}$, $i=2,\cdots,\lceil\log
q\rceil$. Similarly, for $j\in\{j_0+2,\cdots,\left\lceil
n/\delta\right\rceil-1\}$, by 2) of Remark <ref>, we
have $K_j\cap K_{j_0}=\emptyset$, so $K_j\subseteq[\lambda'+1,n]$
and by observation iii), $\bar{h}_j(\bm
q\rceil,K_j})\right)$ can be computed from
$i=2,\cdots,\lceil\log q\rceil$. Let $\ell_0\in\{0,1\}$ be such
that $\ell_0\equiv j_0~\text{mod}~2$. By (<ref>), we
can obtain

\begin{align*}\bar{h}_{j_0}(\bm
\left\lceil n/\delta\right\rceil-1\}\backslash\{j_0\}:\\
j\!~\equiv\!~\ell_0~\text{mod}~2}} \bar{h}_j(\bm
Note that we have proved
that $\bar{h}_j(\bm x)<\overline{N}$ for each $j\in\{1,2,\cdots,
\left\lceil n/\delta\right\rceil-1\}$, so we actually have

\begin{align*}\bar{h}_{j_0}(\bm
x)=\bar{h}^{(\ell_0)}(\bm x)-\sum_{\substack{j\in\{1,2,\cdots,
\left\lceil n/\delta\right\rceil-1\}\backslash\{j_0\}:\\
j\!~\equiv\!~\ell_0~\text{mod}~2}} \bar{h}_j(\bm
where by Construction 3,

By observation ii) in Step 2, and by
Lemma <ref>, $c_{i,[\lambda,\lambda']}$,
$i=2,\cdots,\lceil\log q\rceil$, can be recovered from
$\bar{h}_{j_0}(\bm x)$ and $d_{i,[\lambda,\lambda'-t']}$,
$i=2,\cdots,\lceil\log q\rceil$.

By the above discussions, $M_{\bm x}~($and so $\bm x)$ can be
uniquely recovered from $\bar{f}(\bm x)$ and any given $\bm
y\in\mathcal B_{\leq t}(\bm x)$.

Let $\mathcal S_n$ be the set of all $q$-ary strings $\bm
x\in\mathbb Z_q^{n}$ such that the first row $c_{1,[n]}$ of
$M_{\bm{x}}$ is $(\bm p, \delta)$-dense, where
$M_{\bm{x}}=(c_{i,j})_{\lceil\log q\rceil\times n}$ is the matrix
representation of $\bm x$. Let

be the one-to-one mapping constructed as in
(<ref>), where $\mathcal S^{\text{b}}_n$ is the set of all
$(\bm p, \delta)$-dense strings in $\{0,1\}^{n}$. By Lemma
<ref>, the mapping $\mathcal E^{\text{b}}_{\text{Den}}$
can be extended to a one-to-one mapping, denoted by
E_{\text{Den}}:\mathbb Z_q^{n-1}\rightarrow\mathbb Z_q^{n},$$
that for each $\bm u\in\mathbb Z_q^{n-1}$ and $\bm x=\mathcal
E_{\text{Den}}(\bm u)$, if $M_{\bm{u}}=(b_{i,j})_{\lceil\log
q\rceil\times(n-1)}$ and $M_{\bm{x}}=(c_{i,j})_{\lceil\log
q\rceil\times n}$ are the matrix representation of $\bm u$ and
$\bm x$ respectively, then

Since $\mathcal
E^{\text{b}}_{\text{Den}}(b_{1,[n-1]})$ is $(\bm p,
\delta)$-dense, then for any $\bm u\in\mathbb Z_q^{n-1}$, we have
$\bm x=\mathcal E_{\text{Den}}(\bm u)\in\mathcal S_n$.

As in Section III, for each binary string $\bm a$, let $\mathcal
Q(\bm a)$ be the $q$-ary representation of $\bm a$. Note that
$\mathcal Q(\bm a)$ is a $q$-ary string of length $\left\lceil|\bm
a|/\lfloor\log q\rfloor\right\rceil$. Using the function $\bar f$
constructed in Construction 3 and the mapping $\mathcal
E_{\text{Den}}$, we can construct an encoding function of a
$q$-ary code capable of correcting a burst of at most $t$

Let $\bar{\mathcal E}$ be a function defined on $\mathbb
Z_q^{n-1}$ of the form

\begin{align}\label{Btdel-enc-fun}
\bar{\mathcal E}(\bm u)=(\bm v, \bm v', \bm v''), ~\forall\!~\bm
u\in\mathbb Z_q^{n-1},
\end{align}

where $\bm v=\mathcal E_{\text{Den}}(\bm u)$, $\bm v'=\mathcal
E_{\text{Den}}(\mathcal Q(\bar f(\bm v)))$ and $\bm
v''=\text{Rep}_{t+1}(\mathcal Q(\bar f(\bm v')))$ such that
$\text{Rep}_{t+1}(\cdot)$ is the encoding function of the
$(t+1)$-fold repetition code.

The code $\bar{\mathcal C}=\{\bar{\mathcal E}(\bm u): \bm
u\in\mathbb Z_q^{n-1}\}$, where $\bar{\mathcal E}$ is given by
(<ref>), is a $q$-ary code capable of correcting a
burst of at most $t$ deletions. The redundancy of $\bar{\mathcal
C}$ is at most $\log n+(8\log q+9)\log\log n+o(\log q\log\log
n)+\gamma_t$ in bits, where $\gamma_t$ is a constant depending
only on $t$.

To prove that $\bar{\mathcal C}$ is capable of correcting a burst
of at most $t$ deletions, we adopt a similar strategy as in the
proof of Theorem <ref>. Specifically, let

$$\bm x=\bar{\mathcal E}(\bm u)=(\bm v, \bm v', \bm
v'')\in\bar{\mathcal C},$$
where $\bm v=\mathcal
E_{\text{Den}}(\bm u)$, $\bm v'=\mathcal E_{\text{Den}}(\mathcal
Q(\bar f(\bm v)))$ and $\bm v''=\text{Rep}_{t+1}(\mathcal Q(\bar
f(\bm v')))$. Given any $\bm y\in\mathcal B_{\leq t}(\bm x)$,
denoting $t'=|\bm x|-|\bm y|$, then $t'\leq t$ and we have
$y_{[1,m_1-t']}\in\mathcal B_{\leq t}(\bm v)$,
$y_{[m_1,m_2-t']}\in\mathcal B_{\leq t}(\bm v')$ and
$y_{[m_2,m_3-t']}\in\mathcal B_{\leq t}(\bm v'')$, where $m_1=|\bm
v|, m_2=|(\bm v,\bm v')|$ and $m_3=|\bm x|=|(\bm v,\bm v',\bm
v'')|$. First, since $\bm v''=\text{Rep}_{t+1}(\mathcal Q(\bar
f(\bm v')))$ is a codeword of a $t$-deletion code, then $\mathcal
Q(\bar f(\bm v'))$, and so $\bar f(\bm v')$, can be recovered from
$y_{[m_2,m_3-t']}$. Further, by Theorem
<ref>, $\bm v'$ can be recovered from
$y_{[m_1,m_2-t']}$ and $\bar{f}(\bm v')$, and so $\bar{f}(\bm v)$
can be recovered from $\bm v'=\mathcal E_{\text{Den}}(\mathcal
Q(\bar f(\bm v)))$. Finally, by Theorem <ref>
again, $\bm v$ can be recovered from $y_{[1,m_1-t']}$ and
$\bar{f}(\bm v)$. Thus, $\bm x=(\bm v, \bm v', \bm v'')$ can be
recovered from any $\bm y\in\mathcal B_{\leq t}(\bm x)$, which
proves that $\bar{\mathcal C}$ is capable of correcting a burst of
at most $t$ deletions.

Since $\bm u\in\mathbb Z_q^{n-1}$ and $\bm v=\mathcal
E_{\text{Den}}(\bm u)\in\mathcal S_n\subseteq\mathbb Z_q^{n}$, so
$\bm v$ has $\log q$ bits redundancy. Moreover, by Theorem
<ref>, the length of $\bm v'$ is
v'|=\log n+8(\log q+1)\log\log n+o(\log q\log\log n)+\gamma_t$$

bits and the length of $\bm v''$ is
\begin{align*}|\bm
v''|&=\log|\bm v'|+8(\log q+1)\log\log |\bm v'|+o(\log q\log\log
|\bm b'|)\\&~~~+\gamma_t\\&=\log\log n+\gamma_t+o(\log q\log\log
in bits. So the total redundancy of $\bm
c=\bar{\mathcal E}^{\text{b}}(\bm a)$ is

\begin{align*}\text{redundancy~of}~\bar{\mathcal
C}&=\log q+|\bm v'|+|\bm v''|\\&=\log n+(8\log q+9)\log\log
n\\&~~~+o(\log q\log\log n)+\gamma_t\end{align*}

§ CONCLUSIONS

We constructed systematic $q$-ary two-deletion correcting codes
and $q$-ary burst-deletion correcting codes, where $q\geq 2$ is an
even integer. For $q$-ary two-deletion codes, the redundancy of
our construction is $\log n$ higher than the best known explicit
binary codes and is lower than all existing explicit $q$-ary
codes. For $q$-ary burst-deletion codes, our construction is
scaling-optimal in redundancy.

It is also an interesting problem to generalize our constructions
to odd $q$. Another interesting problem is to construct explicit
$q$-ary $t$-deletion correcting codes that improves upon the state
of the art constructions in redundancy.

§ PROOF OF LEMMA <REF>

In this appendix, we prove Lemma <ref>. We first
need to prove the following lemma.

Suppose $\bm{c}\in\{0,1\}^n$ and $\{j_1,j_2\},
\{j_1',j_2'\}\subseteq[n]$ such that $j_1<j_2, j'_1<j'_2$ and
$j_1\leq j_1'$. If $c_{[n]\backslash\{j_1,j_2\}}
=c_{[n]\backslash\{j'_1,j'_2\}}$, then one of the following holds:

1) $c_{j_1},c_{j'_1}$ are in the same run of $\bm{c}$,
and $c_{j_2},c_{j'_2}$ are in the same run of

2) There is an alternative substring $c_{[s_1,s_2]}$ of $\bm
c$ of length $\geq 3$ such that $c_{j_1}$ and $c_{s_1}$ are in the
same run of $\bm{c}$, $j_2=s_1+1$, $j_1'=s_2-1$ and
$c_{j_2'}$ and $c_{s_2}$ are in the same run of $\bm{c}$.

If $\{j_1,j_2\}=\{j'_1,j'_2\}$, then 1) holds. In the following,
we assume that $\{j_1,j_2\}\neq\{j'_1,j'_2\}$. Since
$c_{[n]\backslash\{j_1,j_2\}} =c_{[n]\backslash\{j'_1,j'_2\}}$, we
can denote $\bm b=c_{[n]\backslash\{j_1,j_2\}}
=c_{[n]\backslash\{j'_1,j'_2\}}.$ From $\bm
b=c_{[n]\backslash\{j_1,j_2\}}$ we can obtain

\begin{equation}\label{2-del-yc1}
&c_i, ~~~~\text{for}~i\in[1,j_1-1],\\
&c_{i+1}, ~\text{for}~i\in[j_1,j_2-2],\\
&c_{i+2}, ~\text{for}~i\in[j_2-1,n-2].
\end{aligned}\right.
\end{equation}

Similarly, from $\bm b=c_{[n]\backslash\{j'_1,j'_2\}}$ we can

\begin{equation}\label{2-del-yc2}
&c_i, ~~~~\text{for}~i\in[1,j'_1-1],\\
&c_{i+1}, ~\text{for}~i\in[j'_1,j'_2-2],\\
&c_{i+2}, ~\text{for}~i\in[j'_2-1,n-2].
\end{aligned}\right.
\end{equation}

Since $j_1<j_2$, $j'_1<j'_2$ and $j_1\leq j_1'$, then we can
divide our discussions into the following three cases:

Case 1: $j_1<j_2\leq j'_1<j'_2$. Combining (<ref>) and
(<ref>), we can obtain

\begin{align}\label{eq1-2del-cmpr}
\bm b=~&c_1\cdots c_{j_1-1}c_{j_1+1}c_{j_1+2}\cdots
c_{j'_2-1}~c_{j'_2}~~c_{j'_2+1}\cdots c_n\nonumber\\
=~&c_1\cdots c_{j_1-1}~c_{j_1}~~c_{j_1+1}\cdots
c_{j'_2-2}c_{j'_2-1}c_{j'_2+1}\cdots c_n.\end{align}
We further
need to divide this case into the following two subcases.

Case 1.1: $j_1'-j_2$ is odd. By comparing the symbols of the
corresponding positions in $c_{[n]\backslash\{j_1,j_2\}}$ and
$c_{[n]\backslash\{j'_1,j'_2\}}$, we can obtain

\begin{align*}

\begin{align*}

Case 1.2: $j_1'-j_2$ is even. By comparing the symbols of the
corresponding positions in $c_{[n]\backslash\{j_1,j_2\}}$ and
$c_{[n]\backslash\{j'_1,j'_2\}}$, we can obtain

\begin{align*}

\begin{align*}

For the both subcases, we can see that

* If $c_{j_1}=c_{j_2}$, then we have
$c_{j_1}=c_{j_1+1}=\cdots=c_{j_2'}$, so $c_{j_1},c_{j_2},c_{j'_1}$
and $c_{j'_2}$ are in the same run of $\bm c$, which implies that
1) of Lemma <ref> holds.
* If $c_{j_1}\neq
c_{j_2}$, then $c_{[j_2-1,j_1'+1]}$ is an alternative substring of
$\bm c$ of length $\geq 3$. By letting $s_1=j_2-1$ and
$s_2=j_1'+1$, we obtain 2) of Lemma

Example <ref>) is an illustration of this case.

Case 2: $j_1\leq j'_1<j_2\leq j'_2$. In this case, combining
(<ref>) and (<ref>), we can obtain

\begin{align}\label{eq2-2del-cmpr}
\bm b= &c_1\cdots c_{j_1-1}c_{j_1+1}c_{j_1+2}\cdots
c_{j'_2-1}~c_{j'_2}~~c_{j'_2+1}\cdots c_n\nonumber\\
=&c_1\cdots c_{j_1-1}~c_{j_1}~~c_{j_1+1}\cdots
c_{j'_2-2}c_{j'_2-1}c_{j'_2+1}\cdots c_n,\end{align}
from which we
see that

Hence, 1) of Lemma <ref> holds.

Case 3: $j_1\leq j'_1<j'_2<j_2$. In this case, combining
(<ref>) and (<ref>), we can obtain

\begin{align}\label{eq3-2del-cmpr}
\bm b= &c_1\cdots c_{j_1-1}c_{j_1+1}c_{j_1+2}\cdots
c_{j_2-1}c_{j_2+1}c_{j_2+2}\cdots c_n\nonumber\\
=&c_1\cdots c_{j_1-1}~c_{j_1}~~c_{j_1+1}\cdots
~c_{j_2}~~c_{j_2+1}c_{j_2+2}\cdots c_n,\end{align}
from which we
can see that

Hence, 1) of Lemma <ref> holds.

To illustrate the Case 1 in the proof of Lemma <ref>,
let's consider the following two examples.

* Consider $\bm c=01000101011110$. Let $j_1=3$,
$j_2=6$, $j_1'=9$ and $j_2'=12$. Then $c_{[n]\backslash\{j_1,j_2\}}
=c_{[n]\backslash\{j'_1,j'_2\}}=010001011110$ and $j_1'-j_2=9-6=3$
is odd. We can find that

* Consider $\bm c=01000101010001$. Let $j_1=3$,
$j_2=6$, $j_1'=10$ and $j_2'=12$. Then $c_{[n]\backslash\{j_1,j_2\}}
=c_{[n]\backslash\{j'_1,j'_2\}}=010001010001$ and $j_1'-j_2=10-6=4$
is even. We can find that
=c_{j'_1+1}=c_{j'_1+2}=\cdots=c_{j'_2}=0$ and

Now, we can prove Lemma <ref>.

Suppose $\bm c\in\{0,1\}^n$ is regular and $\bm b\in\{0,1\}^{n-2}$
such that $\bm b$ can be obtained from $\bm c$ by deleting two
symbols of $\bm c$. Then we can always find two symbols of $\bm
c$, say $c_{j_1}$ and $c_{j_2}~(j_1<j_2)$, such that, $\bm

First, suppose $c_{j_1}$ and $c_{j_2}$ are in the same run of $\bm
c$. Then for any $\{j_1',j_2'\}\subseteq[n]$ such that $\bm
b=c_{[n]\backslash\{j'_1,j'_2\}}$, it is easy to see that 2) of
Lemma <ref> can't hold. $($Otherwise, there is an
alternative substring $c_{[s_1,s_2]}$ of $\bm c$ of length $\geq
3$ such that $c_{j_1}$, $c_{s_1}$ are in the same run of $\bm{c}$
and $j_2=s_1+1$, which implies that $c_{j_1}=c_{s_1}\neq
c_{s_1+1}=c_{j_2}$, which contradicts to the assumption that
$c_{j_1}$ and $c_{j_2}$ are in the same run of $\bm c$.$)$
Therefore, 1) of Lemma <ref> must hold, which implies
that there is a run $c_{J}$ of $\bm c$, where $J\subseteq[n]$ is
an interval, such that $\bm b$ is obtained from $\bm c$ by
deleting two symbols in $c_{J}$. Since $\bm c\in\{0,1\}^n$ is
regular, by Remark <ref>, the length of $c_{J}$ is
at most $d\log n<\rho=3d\log n$. Thus, 2) of Lemma
<ref> holds.

In the following, we suppose that $c_{j_1}$ and
$c_{j_2}~(j_1<j_2)$ are in two different runs of $\bm c$.
Specifically, suppose $j_1\in J=[i_1,i_2]\subseteq[n]$ and $j_2\in
J'=[i'_1,i'_2]\subseteq[n]$ such that $c_{J}$ and $c_{J'}$ are two
different runs of $\bm c$. Since $j_1<j_2$, then
i_2<i_1'\leq i_2'.$$
We need to consider the following two cases.

Case 1: $i_1'>i_2+1$. Since $j_2\in J'=[i'_1,i'_2]$, then $j_2\geq
i_1'>i_2+1$. For any $\{j_1',j_2'\}\subseteq[n]$ such that $\bm
b=c_{[n]\backslash\{j'_1,j'_2\}}$, it is easy to see that 2) of
Lemma <ref> can't hold. $($Otherwise, there is an
alternative substring $c_{[s_1,s_2]}$ of $\bm c$ of length $\geq
3$ such that $c_{j_1}$, $c_{s_1}$ are in the same run of $\bm{c}$
and $j_2=s_1+1$, which implies that $s_1=i_2$ and
$j_2=s_1+1=i_2+1$, which contradicts to the fact that $j_2\geq
i_1'>i_2+1.)$ Therefore, 1) of Lemma <ref> must hold,
which implies that $j_1'\in J=[i_1,i_2]$ and $j_2'\in
J'=[i'_1,i'_2]'$. Thus, 1) of Lemma <ref> holds.

Case 2: $i_1'=i_2+1$. We need to consider the following two

Case 2.1: $|J|\geq 2$ and $|J'|\geq 2$. Then for any
$\{j_1',j_2'\}\subseteq[n]$ such that $\bm
b=c_{[n]\backslash\{j'_1,j'_2\}}$, it is easy to see that 2) of
Lemma <ref> can't hold because no such alternative
substring $c_{[s_1,s_2]}$ of $\bm c$ can be found. Therefore, 1)
of Lemma <ref> must hold, which implies that $j_1'\in
J=[i_1,i_2]$ and $j_2'\in J'=[i'_1,i'_2]'$. Thus, 1) of Lemma
<ref> holds.

Case 2.2: $|J|=1$ or $|J'|=1$. Without loss of generality, assume
$|J|=1$. Then $i_1=i_2$ and $c_{i_1-1}c_{i_1}c_{i_1+1}$ is an
alternative substring of $\bm c$. Let $c_{[\lambda_1,\lambda_2]}$
be the maximal alternative substring of $\bm c$ that contains
$c_{i_1-1}c_{i_1}c_{i_1+1}$, where
$[\lambda_1,\lambda_2]\subseteq[n]$ is an interval. Let
$c_{[\lambda_0,\lambda_1]}~($if $\lambda_1>1)$ and
$c_{[\lambda_2,\lambda_3]}~($if $\lambda_2<n)$ be two runs of $\bm
c$. For any $\{j_1',j_2'\}\subseteq[n]$ such that $\bm
b=c_{[n]\backslash\{j'_1,j'_2\}}$, by Lemma <ref>, we
have $\{j_1',j_2'\}\subseteq[\lambda_0,\lambda_3]$. Since $\bm
c\in\{0,1\}^n$ is regular, by Remark <ref>, the
length of the alternative substring $c_{[\lambda_1,\lambda_2]}$ of
$\bm c$ is at most $d\log n$, and the lengths of the runs
$c_{[\lambda_0,\lambda_1]}$, $c_{[\lambda_2,\lambda_3]}$ of $\bm
c$ are both at most $d\log n$. Hence, the length of
$c_{[\lambda_0,\lambda_3]}$ is at most $\rho=3d\log n$. Thus, 2)
of Lemma <ref> holds.

By the above discussions, we proved that exact one of the two
claims of Lemma <ref> holds.

As an example, suppose $\bm c=011000101011110100$. We consider the
following cases.

* If $\bm b=0110101011110100$, then $\bm b$ can be obtained
from $\bm c$ by deleting two symbols in the run $c_{[4,6]}=000$.

* If $\bm b=0110010011110100$, then $\bm b$ can be obtained
from $\bm c$ by deleting one symbol in the run $c_{[4,6]}=000$ and
one symbol in the run $c_{[9,9]}=1$. This case is an example of
Case 1 in the proof of Lemma <ref>.

* If $\bm b=0100101011110100$, then $\bm b$ can be obtained
from $\bm c$ by deleting one symbol in the run $c_{[2,3]}=11$ and
one symbol in the run $c_{[4,6]}=000$. This case is an example of
Case 2.1 in the proof of Lemma <ref>.

* If $\bm b=0110001011110100$, then $\bm b$ can be obtained
from $\bm c$ by deleting two symbols in the substring
$c_{[4,14]}=00010101111$, which may be any of the following cases:
i) one symbol in the run
$c_{[4,6]}=000$ and the symbol $c_{7}=1$; ii) the symbols
$c_i,c_{i+1}$ for $i\in\{7,8,9\}$; iii) one symbol in the run
$c_{[11,14]}=1111$ and the symbol $c_{10}=0$. This case is an example of
Case 2.2 in the proof of Lemma <ref>.

[1]
R. Heckel, G. Mikutis, and R. N. Grass, “A Characterization of
the DNA Data Storage Channel,” Scientific Reports, vol. 9,
no. 1, pp. 9663, 2019. Available online at:

[2]
V. I. Levenshtein, “Binary codes capable of correcting deletions,
insertions and reversals (in Russian),” Doklady Akademii
Nauk SSR, vol. 163, no. 4, pp. 845-848, 1965.

[3]
R. R. Varshamov and G. M. Tenengolts, “Codes which correct single
asymmetric errors (in Russian),” Automatika i
Telemkhanika, vol. 161, no. 3, pp. 288-292, 1965.

[6]
J. Brakensiek, V. Guruswami, and S. Zbarsky, “Efficient
low-redundancy codes for correcting multiple deletions,”
IEEE Trans. Inform. Theory, vol. 64, no. 5, pp. 3403-3410,

[7]
R. Gabrys and F. Sala, “Codes correcting two deletions,”
IEEE Trans. Inform. Theory, vol. 65, no. 2, pp. 965-974,
Feb 2019.

[8]
J. Sima, N. Raviv, and J. Bruck, “Two deletion correcting codes
from indicator vectors,” IEEE Trans. Inform. Theory, vol.
66, no. 4, pp. 2375-2391, April 2020.

[9]
V. Guruswami and J. Håstad, “Explicit two-deletion codes with
redundancy matching the existential bound,” IEEE Trans.
Inform. Theory, vol. 67, no. 10, pp. 6384-6393, October 2021.

[10]
J. Sima and J. Bruck, “Optimal $k$-Deletion Correcting Codes,”
in Proc. ISIT, 2019.

[11]
J. Sima and J. Bruck, “On Optimal $k$-Deletion Correcting
Codes,” IEEE Trans. Inform. Theory, vol. 67, no. 6, pp.
3360-3375, June 2021.

[12]
J. Sima, R. Gabrys, and J. Bruck, “Syndrome Compression for
Optimal Redundancy Codes,” in Proc. ISIT, 2020.

[13]
J. Sima, R. Gabrys, and J. Bruck, “Optimal Systematic
$t$-Deletion Correcting Codes,” in Proc. ISIT, 2020.

[14]
W. Song, N. Polyanskii, K. Cai, and X. He, “Systematic Codes
Correcting Multiple-Deletion and Multiple-Substitution Errors,”
IEEE Trans. Inform. Theory, vol. 68, no. 10, pp. 6402-6416,
October 2022.

[15]
C. Schoeny, A. Wachter-Zeh, R. Gabrys, and E. Yaakobi, “Codes
correcting a burst of deletions or insertions,” IEEE Trans.
Inform. Theory, vol. 63, no. 4, pp. 1971-1985, 2017.

[16]
V. Levenshtein, “Asymptotically optimum binary code with
correction for losses of one or two adjacent bits,”
Problemy Kibernetiki, vol. 19, pp. 293-298, 1967.

[18]
A. Lenz, N. Polyanskii, “Optimal Codes Correcting a Burst of
Deletions of Variable Length,” in Proc. ISIT, 2021.

[19]
V.I. Levenshtein, “Bounds for deletion/insertion correcting
codes,” in Proc. ISIT, 2002.

[20]
G. M. Tenengolts,  “Nonbinary codes, correcting single deletion
or insertion,” IEEE Trans. Inform. Theory, vol. 30, no. 5,
pp. 766-769, Sept. 1984.

[23]
J. Sima, R. Gabrys, and J. Bruck, “Optimal codes for the $q$-ary
deletion channel,” in Proc. ISIT, 2020.

[24]
K. Cai, Y. M. Chee, R. Gabrys, H. M. Kiah, and T. T. Nguyen,
“Optimal codes correcting a single indel/edit for DNA-based data
storage,” 2019, Available online at:

[26]
S. Wang, J. Sima, and F. Farnoud, “Non-binary Codes for
Correcting a Burst of at Most $2$ Deletions,” in Proc.
ISIT, 2021.