#  $t$-Deletion-$s$-Insertion-Burst Correcting Codes

Ziyang Lu and Yiwei Zhang The authors are with Key Laboratory of Cryptologic
Technology and Information Security, Ministry of Education, and also with
School of Cyber Science and Technology, Shandong University, Qingdao,
Shandong, 266237, China. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>of this work was presented at IEEE International Symposium on Information
Theory (ISIT), 2022.Research supported by National Key Research and
Development Program of China under Grant Nos. 2020YFA0712100 and
2021YFA1001000, National Natural Science Foundation of China under Grant No.
12001323, and Shandong Provincial Natural Science Foundation under Grant No.
ZR2021YQ46.

###### Abstract

Motivated by applications in DNA-based storage and communication systems, we
study deletion and insertion errors simultaneously in a burst. In particular,
we study a type of error named $t$-deletion-$s$-insertion-burst ($(t,s)$-burst
for short) which is a generalization of the $(2,1)$-burst error proposed by
Schoeny et. al. Such an error deletes $t$ consecutive symbols and inserts an
arbitrary sequence of length $s$ at the same coordinate. We provide a sphere-
packing upper bound on the size of binary codes that can correct a
$(t,s)$-burst error, showing that the redundancy of such codes is at least
$\log n+t-1$. For $t\geq 2s$, an explicit construction of binary $(t,s)$-burst
correcting codes with redundancy $\log n+(t-s-1)\log\log n+O(1)$ is given. In
particular, we construct a binary $(3,1)$-burst correcting code with
redundancy at most $\log n+9$, which is optimal up to a constant.

###### Index Terms:

DNA storage, error-correcting codes, deletions, insertions, burst error.

##  I Introduction

DNA-based storage is a promising direction for future data storage due to its
advantages such as storage density and durability[7]. Due to the error
behavior in DNA sequences, codes correcting deletions and insertions have
recently attracted significant attention. Meanwhile, synchronization loss
occurs due to timing uncertainty in communication and storage systems[18, 6],
which also leads to deletions and insertions.

The study of error-correcting codes against deletions and insertions dates
back to 1965, when Levenshtein[15] showed that the Varshamov-Tenengol’ts (VT)
code[25] can correct a single deletion. In the same work, Levenshtein proved
the equivalence between $t$-deletion-correcting codes and $t$-insertion-
correcting codes, and showed that the redundancy of a $t$-deletion-correcting
code is asymptotically at least $t\log n$. It was not until recent years that
deletion correcting codes were reconsidered due to advances in DNA storage.
The general problem of correcting $t$ arbitrary deletions has been considered
in a series of works[1, 24, 12, 10, 11, 20, 21]. The state-of-the-art result
of them is the one from[21], which constructed a $t$-deletion-correcting code
with redundancy $4t\log n+o(\log n)$.

Both in DNA-based storage and communication systems, the deletion and
insertion errors tend to occur in bursts (i.e., consecutive errors) [26].
Therefore, it is of great significance to design codes capable of correcting a
burst of deletions/insertions. A code that can correct exactly $t$ consecutive
deletions is called a $t$-burst-deletion-correcting code, and a code that can
correct at most $t$ consecutive deletions is called a $t^{\leq}$-burst-
deletion-correcting code. In 1970, Levenshtein[16] constructed a
$2^{\leq}$-burst-deletion-correcting code, and provided asymptotic bounds on
$t$-burst-correcting codes indicating that the least redundancy to correct $t$
consecutive deletions is asymptotically $\log n+t-1$. Cheng et al.[4] provided
three constructions of $t$-burst-deletion-correcting codes, among which the
least redundancy is $t\log(\frac{n}{t}+1)$. Schoeny et al.[17] constructed a
$t$-burst-deletion-correcting code by combining the VT code with constrained
coding and utilizing the shifted VT (SVT) code, which has redundancy $\log
n+(t-1)\log\log n+t-\log t$. As for $t^{\leq}$-burst-deletion-correcting
codes, the construction of Schoeny et al.[17] has redundancy $(t-1)\log
n+(\binom{t}{2}-1)\log\log n+\binom{t}{2}+\log\log t$ and then Gabrys et al.
[9] reduced the redundancy to $\lceil\log t\rceil\log
n+(\frac{t(t+1)}{2}-1)\log\log n+O(1)$. The current best result for
$t^{\leq}$-burst-deletion-correcting codes is from Lenz and Polyanskii[14]
with redundancy $\log n+\frac{t(t+1)}{2}\log\log n+O(1)$. In addition, the
model of a burst of $t$ non-consecutive deletions (some $s\leq t$ deletions
occur within a block of size $t$) is also considered in [17, 2].

In addition to deletion or insertion error, substitution error is the most
widely considered type of error in classic coding theory. In current DNA
storage technology, ultimately one needs to design error-correcting codes
against a combination of deletion, insertion, and substitution errors, which
is by now a difficult problem[19, 3, 8, 23, 22].

In [17] Schoeny et al. proposed a type of error called a $(2,1)$-burst, which
deletes two consecutive symbols and then inserts one symbol at the same
coordinate. Codes against a $(2,1)$-burst error were applied in their model of
burst non-consecutive deletions [17]. In this paper, we generalize the error
type to a $t$-deletion-$s$-insertion-burst ($(t,s)$-burst for short), which
deletes a burst of $t$ consecutive symbols and then inserts an arbitrary
sequence of length $s$ at the same coordinate. Despite being naturally a
mixture of deletions and insertions, a $(t,s)$-burst can also be seen as a
mixture of substitutions and deletions/insertions. For example, when $t\geq
s$, a $(t,s)$-burst can be also seen as deleting a burst of $t-s$ consecutive
symbols and then substituting a subset of the next $s$ consecutive symbols. A
code that can correct a $(t,s)$-burst error will be called a
$t$-deletion-$s$-insertion-burst correcting code ($(t,s)$-burst correcting
code for short), and is the main objective of this paper.

The rest of the paper is organized as follows. In Section II, we give the
definitions and some notations used throughout the paper and review some
previous results that will be used in our constructions. In Section III, we
prove the equivalence between $(t,s)$-burst correcting codes and $(s,t)$-burst
correcting codes. A sphere-packing upper bound on the size of $(t,s)$-burst
correcting codes is given in Section IV, which leads to a lower bound of the
code redundancy. In Section V, we present a $(t,s)$-burst correcting code with
redundancy $\log n+(t-s-1)\log\log n+O(1)$ for $t\geq 2s$. In particular, we
present an almost optimal $(3,1)$-burst correcting code in Section VI. Lastly,
Section VII concludes the paper and discusses some future directions.

##  II Preliminaries and Related Work

###  II-A Notations and Definitions

Let $\mathbb{F}_{2}^{n}$ be the set of binary sequences of length $n$. In this
paper, a sequence $\boldsymbol{x}\in\mathbb{F}_{2}^{n}$ is denoted as either
$x_{1}x_{2}x_{3}\ldots x_{n}$ or $(x_{1},x_{2},x_{3},\ldots,x_{n})$. For
integers $i\leq j$, the length of an interval
$[i,j]\triangleq\\{i,i+1,\dots,j\\}$ is defined as $j-i+1$.

A run of $\boldsymbol{x}=(x_{1},x_{2},\dots,x_{n})$ is a maximal consecutive
subsequence of the same symbol. For binary sequences, a run is a maximal
consecutive 0s or 1s. Let $R(\boldsymbol{x})$ denote the run sequence of
$\boldsymbol{x}$, and the $i$th coordinate of $R(\boldsymbol{x})$ is denoted
as $R(\boldsymbol{x})_{i}$, known as the run index of $x_{i}$. Here
$R(\boldsymbol{x})_{i}=t$ indicates that $x_{i}$ lies in the $t$th run of
$\boldsymbol{x}$, where $t$ is counted starting from zero. Let
$Rsyn(\boldsymbol{x})=\sum_{1\leq i\leq n}R(\boldsymbol{x})_{i}$ and let
$r(\boldsymbol{x})$ be the total number of runs in $\boldsymbol{x}$. For
example, if $\boldsymbol{x}=1101110000$, then ‘11’, ‘0’, ‘111’, ‘0000’ are the
four runs, $R(\boldsymbol{x})=0012223333$, $Rsyn(\boldsymbol{x})=19$, and
$r(\boldsymbol{x})=4$.

A $t$-deletion-$s$-insertion-burst ($(t,s)$-burst for short) error over
$\boldsymbol{x}$ is a type of error which deletes $t$ consecutive symbols from
$\boldsymbol{x}$ and inserts an arbitrary sequence of length $s$ at the same
coordinate. That is, a $(t,s)$-burst error over
$\boldsymbol{x}=(x_{1},x_{2},\dots,x_{n})$ starting at the $i$th coordinate,
$1\leq i\leq n-t+1$, will result in
$(x_{1},\dots,x_{i-1},y_{1},\ldots,y_{s},x_{i+t},\dots,x_{n})$, where
$(x_{i},\dots,x_{i+t-1})$ is deleted and $(y_{1},\ldots,y_{s})$ is the
inserted sequence. Continuing with the example above for
$\boldsymbol{x}=1101110000$, if a $(3,1)$-burst error starts at the very
beginning then one gets either $01110000$ or $11110000$, and if a
$(1,3)$-burst error starts at the very beginning then one gets
$y_{1}y_{2}y_{3}101110000$ where $y_{1}y_{2}y_{3}$ is the inserted sequence.

The $(t,s)$-burst ball of $\boldsymbol{x}$ is the set of all possible
sequences obtained by a $(t,s)$-burst error over $\boldsymbol{x}$, denoted as
$B_{t,s}(\boldsymbol{x})$.

###### Example 1

Suppose $\boldsymbol{x}=101000111$, $t=4,s=1$, then

$B_{4,1}(\boldsymbol{x})=\\{000111,100111,110111,101111,101011,101001,101000\\}.$

A code $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ is called a $(t,s)$-burst
correcting code if it can correct a $t$-deletion-$s$-insertion-burst error.
That is, for any two distinct codewords
$\boldsymbol{c}_{1},\boldsymbol{c}_{2}\in\mathcal{C}$,
$B_{t,s}(\boldsymbol{c}_{1})\cap B_{t,s}(\boldsymbol{c}_{2})=\varnothing$. The
redundancy of such a code is given by $n-\log|\mathcal{C}|$.

###  II-B Related Work

In this subsection we briefly review some useful results about codes
correcting deletions or insertions.

Define the VT syndrome as $VT(\boldsymbol{x})=\sum_{i=1}^{n}ix_{i}$. For
$a\in\mathbb{Z}_{n+1}$, the Varshamov-Tenengol’ts (VT) code[25]

$VT_{a}(n)=\\{\boldsymbol{x}\in\mathbb{F}_{2}^{n}:VT(\boldsymbol{x})\equiv
a\pmod{n+1}\\}$

can correct a single deletion. Levenshtein [15] proved that the optimal
redundancy of $t$-deletion-correcting codes is between $t\log n$ and $2t\log
n$, so the VT code is optimal for a single deletion.

In 1970, Levenshtein[16] provided a code that can correct a burst of at most 2
deletions as follows:

$L_{a}(n)=\\{\boldsymbol{x}\in\mathbb{F}_{2}^{n}:Rsyn(0\boldsymbol{x})\equiv
a\pmod{2n}\\},$ (1)

where $a\in\mathbb{Z}_{2n}$ and the function $Rsyn(\cdot)$ is applied on
$0\boldsymbol{x}$, the concatenation of a single 0 and the sequence
$\boldsymbol{x}$.

For the $t$-burst-deletion-correcting codes, Cheng et al. [4] proposed a
framework which represents $\boldsymbol{x}$ as a $t\times\frac{n}{t}$ array
(throughout the paper, in an array representation we always assume that the
number of rows is a divisor of $n$) and applies some constraints for each row:

$A_{t}(\boldsymbol{x})=\begin{bmatrix}x_{1}&x_{t+1}&\cdots&x_{n-t+1}\\\
x_{2}&x_{t+2}&\cdots&x_{n-t+2}\\\ \vdots&\vdots&\ddots&\vdots\\\
x_{t}&x_{2t}&\cdots&x_{n}\end{bmatrix}.$

In their constructions the least redundancy is $t(\log(\frac{n}{t}+1))$.

Schoeny et al.[17] followed the framework as in [4] to represent a sequence as
the array above. In their construction the first row is encoded by a variation
of VT code with additional run-length constraints, and the other rows apply a
code called the shifted VT code (SVT):

$SVT(n;a,b,P)=\Big{\\{}\boldsymbol{x}\in\mathbb{F}_{2}^{n}:VT(\boldsymbol{x})\equiv
a\pmod{P},\sum_{i=1}^{n}x_{i}\equiv b\pmod{2}\Big{\\}}$

which can correct a single deletion given the additional knowledge of the
erroneous coordinate within an interval of length $P$ (this knowledge is
derived from decoding the first row). By choosing $P$ as $\log(n/t)+2$, the
redundancy of their codes is at most $\log n+(t-1)\log\log n+t-\log t$.

In the same paper[17], Schoeny et al. constructed a $(2,1)$-burst correcting
code, which was then applied to correcting a burst of $t$ non-consecutive
deletions:

$\mathcal{C}_{2,1}(n;a,b)=\Big{\\{}\boldsymbol{x}\in\mathbb{F}_{2}^{n}:VT(\boldsymbol{x})\equiv
a\pmod{2n-1},\sum_{i=1}^{n}x_{i}\equiv b\pmod{4}\Big{\\}}.$ (2)

###  II-C Summary of Our Contributions

In this paper, we first prove the equivalence of $(t,s)$-burst correcting
codes and $(s,t)$-burst correcting codes. Next we compute the size of the
error ball for the $(t,s)$-burst error. Unlike most situations in analyzing
deletions/insertions, for $(t,s)$-burst the size of the error ball is a
constant independent of the center and thus it leads to a neat sphere-packing
type upper bound, implying that the redundancy of $(t,s)$-burst correcting
codes is at least $\log n+t-1$. As for constructions, we can focus only on the
case $t\geq s$ due to the aforementioned equivalence. For $t\geq 2s$, we give
a general construction with redundancy $\log n+(t-s-1)\log\log n+O(1)$. In
particular, we construct a $(3,1)$-burst correcting code with redundancy at
most $\log n+9$, which is optimal up to a constant.

##  III Equivalence of $(t,s)$-Burst and $(s,t)$-Burst

In this section, we prove the equivalence of $(t,s)$-burst correcting codes
and $(s,t)$-burst correcting codes. Levenshtein [16] proved the equivalence of
$t$-deletion-correcting codes and $t$-insertion-correcting codes. Schoeny et
al.[17] proved the equivalence of codes against a burst of $t$ deletions and a
burst of $t$ insertions. Using a similar idea, we have the following theorem.

###### Theorem 1

Let $t\geq s$. A code $\mathcal{C}$ is a $(t,s)$-burst correcting code if and
only if it is an $(s,t)$-burst correcting code.

###### Proof:

We only prove the ‘only if’ part. The ‘if’ part can be proved analogously.
Suppose $\mathcal{C}$ is a $(t,s)$-burst correcting code but not an
$(s,t)$-burst correcting code. Then, there exist two distinct codewords
$\boldsymbol{x},\boldsymbol{y}\in\mathcal{C}$, such that
$B_{s,t}(\boldsymbol{x})\cap B_{s,t}(\boldsymbol{y})$ is nonempty and thus
contains some $\boldsymbol{z}\in\mathbb{F}_{2}^{n+t-s}$. Assume that
$\boldsymbol{z}$ is obtained by deleting $(x_{i},\ldots,x_{i+s-1})$ and
inserting $(a_{1},\ldots,a_{t})$ at the $i$th coordinate of $\boldsymbol{x}$,
and is also obtained by deleting $(y_{j},\ldots,y_{j+s-1})$ and inserting
$(b_{1},\ldots,b_{t})$ at the $j$th coordinate of $\boldsymbol{y}$. Without
loss of generality, we assume $i\leq j$. Then, $\boldsymbol{z}$ will have the
following two representations:

$\begin{split}&\boldsymbol{z}^{1}=(x_{1},\ldots,x_{i-1},a_{1},\ldots,a_{t},x_{i+s},\ldots,x_{n}),\\\
&\boldsymbol{z}^{2}=(y_{1},\ldots,y_{j-1},b_{1},\ldots,b_{t},y_{j+s},\ldots,y_{n}).\end{split}$

  1. 1.

If $j\geq i+t$, i.e., the coordinates of deletions of $\boldsymbol{y}$ are
disjoint with the coordinates of insertions of $\boldsymbol{x}$. By comparing
$\boldsymbol{z}^{1}$ and $\boldsymbol{z}^{2}$ we have

$\displaystyle(x_{1},\ldots,x_{i-1})=(y_{1},\ldots,y_{i-1})$
$\displaystyle,(a_{1},\dots,a_{t})=(y_{i},\dots,y_{i+t-1}),$
$\displaystyle(x_{i+s},\ldots,x_{j+s-t-1})=(y_{i+t},\ldots,y_{j-1}),(x_{j+s-t},\dots,x_{j+s-1})$
$\displaystyle=(b_{1},\dots,b_{t}),(x_{j+s},\ldots,x_{n})=(y_{j+s},\ldots,y_{n}).$

Therefore, if we delete $(x_{j+s-t},\ldots,x_{j+s-1})$ from $\boldsymbol{x}$
and insert $(y_{j},\ldots,y_{j+s-1})$ at this coordinate, then we get

$(x_{1},\ldots,x_{j+s-t-1},y_{j},\ldots,y_{j+s-1},x_{j+s},\ldots,x_{n}).$

If we delete $(y_{i},\ldots,y_{i+t-1})$ from $\boldsymbol{y}$ and insert
$(x_{i},\ldots,x_{i+s-1})$ at this coordinate, then we get

$(y_{1},\ldots,y_{i-1},x_{i},\ldots,x_{i+s-1},y_{i+t},\ldots,y_{n}).$

From the equations above, we have

$(x_{1},\ldots,x_{j+s-t-1},y_{j},\ldots,y_{j+s-1},x_{j+s},\ldots,x_{n})=(y_{1},\ldots,y_{i-1},x_{i},\ldots,x_{i+s-1},y_{i+t},\ldots,y_{n}).$

Thus, $B_{t,s}(\boldsymbol{x})\cap B_{t,s}(\boldsymbol{y})\neq\varnothing$,
which is a contradiction to the hypothesis that $\mathcal{C}$ is a
$(t,s)$-burst correcting code.

  2. 2.

If $j\leq i+t-1$, then the coordinates of deletions of $\boldsymbol{y}$ and
the coordinates of insertions of $\boldsymbol{x}$ have some intersection. We
still have

$(x_{1},\ldots,x_{i-1})=(y_{1},\ldots,y_{i-1}),(x_{j+s},\ldots,x_{n})=(y_{j+s},\ldots,y_{n}).$

In this case, if we delete $(x_{j-t+1},\ldots,x_{j})$ from $\boldsymbol{x}$
and insert $(y_{j-t+1},\ldots,y_{j-t+s})$ at this coordinate, then we get

$(x_{1},\ldots,x_{j-t},y_{j-t+1},\ldots,y_{j-t+s},x_{j+1},\ldots,x_{n}).$

For $\boldsymbol{y}$, if we delete $(y_{j-t+s+1},\ldots,y_{j+s})$ and insert
$(x_{j+1},\ldots,x_{j+s})$ at this coordinate, then we get

$(y_{1},\ldots,y_{j-t+s},x_{j+1},\ldots,x_{j+s},y_{j+s+1},\ldots,y_{n}).$

Since $j\leq i+t-1$, we have $(x_{1},\ldots,x_{j-t})=(y_{1},\ldots,y_{j-t})$.
Therefore, one can check that

$(x_{1},\ldots,x_{j-t},y_{j-t+1},\ldots,y_{j-t+s},x_{j+1},\ldots,x_{n})=(y_{1},\ldots,y_{j-t+s},x_{j+1},\ldots,x_{j+s},y_{j+s+1},\ldots,y_{n}).$

Thus, $B_{t,s}(\boldsymbol{x})\cap B_{t,s}(\boldsymbol{y})\neq\varnothing$,
which is again a contradiction to the hypothesis that $\mathcal{C}$ is a
$(t,s)$-burst correcting code.

∎

###### Remark 1

Note that in [16] Levenshtein proved a stronger result that $t$-deletion-
correcting codes and $t$-insertion-correcting codes are also equivalent to
codes correcting arbitrary $t_{1}$ deletions and $t_{2}$ insertions, as long
as $t_{1}+t_{2}=t$. It is tempting to ask if a similar result holds for the
burst error model: Is there a general equivalence between
$(t_{1},s_{1})$-burst correcting codes and $(t_{2},s_{2})$-burst correcting
codes, whenever $t_{1}+s_{1}=t_{2}+s_{2}$? However, this is not true. For
example, consider the following three strings
$\boldsymbol{x}=\boldsymbol{u}00100\boldsymbol{v}$,
$\boldsymbol{y}=\boldsymbol{u}11111\boldsymbol{v}$, and
$\boldsymbol{z}=\boldsymbol{u}01010\boldsymbol{v}$. $\boldsymbol{x}$ and
$\boldsymbol{y}$ may belong to a $(3,1)$-burst correcting code, but they
cannot belong to a $(2,2)$-burst correcting code, since
$\boldsymbol{u}11100\boldsymbol{v}\in B_{2,2}(\boldsymbol{x})\cap
B_{2,2}(\boldsymbol{y})$. $\boldsymbol{y}$ and $\boldsymbol{z}$ may belong to
a $(2,2)$-burst correcting code, but they cannot belong to a $(3,1)$-burst
correcting code, since $\boldsymbol{u}011\boldsymbol{v}\in
B_{3,1}(\boldsymbol{y})\cap B_{3,1}(\boldsymbol{z})$. Thus $(3,1)$-burst
correcting codes and $(2,2)$-burst correcting codes are not equivalent.

##  IV An Upper Bound on The Code Size

There are several upper bounds on the size of burst-deletion-correcting codes.
Levenshtein[16] provided an asymptotic upper bound on the size of $t$-burst-
deletion-correcting codes: if $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ is a
$t$-burst-correcting code, then $|\mathcal{C}|\leq 2^{n-t+1}/n$, which implies
that the redundancy is asymptotically at least $\log n+t-1$. Schoeny et
al.[17] constructed a hypergraph whose vertices are all sequences of
$\mathbb{F}_{2}^{n-t}$ and the hyperedges are the $t$-burst-deletion balls of
all sequences in $\mathbb{F}_{2}^{n}$. In this way the problem turns into
analyzing the matching number of the hypergraph and they provided an explicit
upper bound on the size of $t$-burst-deletion-correcting codes as
$|\mathcal{C}|\leq(2^{n-t+1}-2^{t})/(n-2t+1)$.

A sphere-packing type upper bound is usually not easy to obtain for most
models concerning insertions and deletions, since the size of the
corresponding error ball usually depends on the choice of the center. However,
in this section we derive an unexpected result that the size of a
$(t,s)$-burst ball is in fact a constant independent of the center, and thus
give a sphere-packing type upper bound on the size of $(t,s)$-burst correcting
codes. To analyze the size of the error ball, we first claim that
$B_{t,s}(\boldsymbol{x})$ can be partitioned into several disjoint parts.

For a $(t,s)$-burst of $\boldsymbol{x}$, let the deleted symbols be
$x_{i},\ldots,x_{i+t-1}$ where $1\leq i\leq n-t+1$, and the inserted symbols
be $y_{1},y_{2},\ldots,y_{s}$. Observe that, for example, if the deleted
symbols are 10101 and the inserted symbols are 111, then essentially this
$(5,3)$-burst can be seen as a $(3,1)$-burst deleting 010 and inserting 1.
Following this observation, let $B^{\prime}_{k,\ell}(\boldsymbol{x})$ denote
the sequences obtained by a $(k,\ell)$-burst over $\boldsymbol{x}$, where the
first and last inserted symbols are different from the first and last deleted
symbols, respectively. In other words,

$B^{\prime}_{k,\ell}(\boldsymbol{x})=\bigcup_{i=1}^{n-k+1}\Big{\\{}x_{1}\ldots
x_{i-1}y_{1}\ldots y_{\ell}x_{i+k}\ldots x_{n},\text{ where }x_{i}\neq
y_{1},x_{i+k-1}\neq y_{\ell}\Big{\\}}.$

For example, when $k=1$ and $\ell\geq 1$, we have $y_{1}=y_{\ell}\neq x_{i}$,
i.e., we delete a symbol $a\in\\{0,1\\}$ and insert a sequence of length
$\ell$ starting and ending with $1-a$. Similarly, when $\ell=1$ and $k\geq 1$,
we have $x_{i}=x_{i+k-1}\neq y_{1}$, i.e., we delete a sequence of length $k$
starting and ending with the symbol $a$ and insert $1-a$. When $k=0$ or
$\ell=0$, $B^{\prime}_{0,\ell}$ or $B^{\prime}_{k,0}$ is simply the burst
insertion ball or the burst deletion ball. In particular,
$B^{\prime}_{0,0}=\\{\boldsymbol{x}\\}$ contains the sequence $\boldsymbol{x}$
itself.

###### Lemma 1

When $t\geq s$, $B_{t,s}(\boldsymbol{x})$ is a disjoint union of
$B^{\prime}_{t-s+\ell,\ell}(\boldsymbol{x})$, $0\leq\ell\leq s$. Similarly,
when $t\leq s$, $B_{t,s}(\boldsymbol{x})$ is a disjoint union of
$B^{\prime}_{k,s-t+k}(\boldsymbol{x})$, $0\leq k\leq t$.

###### Proof:

We only prove the first part. The second part can be proved analogously.

First we need to prove that
$\bigcup_{\ell=0}^{s}B^{\prime}_{t-s+\ell,\ell}(\boldsymbol{x})=B_{t,s}(\boldsymbol{x})$.
Obviously,
$\bigcup_{\ell=0}^{s}B^{\prime}_{t-s+\ell,\ell}(\boldsymbol{x})\subseteq
B_{t,s}(\boldsymbol{x})$. For the other direction, consider $\boldsymbol{w}\in
B_{t,s}(\boldsymbol{x})$ and suppose $\boldsymbol{w}$ is obtained by deleting
$x_{i},\ldots,x_{i+t-1}$ from $\boldsymbol{x}$ and inserting
$y_{1},\ldots,y_{s}$. Let $p\in\\{1,2,\dots,s\\}$ be the smallest index such
that $y_{p}\neq x_{i+p-1}$, and let $q\in\\{1,2,\dots,s\\}$ be the largest
index such that $y_{q}\neq x_{i+t+q-s-1}$.

  * •

If such $p$ and $q$ exist and $p\leq q$, then $\boldsymbol{w}$ can be seen as
deleting $x_{i+p-1},\ldots,x_{i+t+q-s-1}$ and inserting $y_{p},\ldots,y_{q}$.
Thus $\boldsymbol{w}\in B^{\prime}_{t-s+q-p+1,q-p+1}(\boldsymbol{x})$, where
$q-p+1\in\\{1,\ldots,s\\}$.

  * •

If $p$ does not exist, it means that
$(y_{1},\ldots,y_{s})=(x_{i},\ldots,x_{i+s-1})$, i.e., the inserted sequence
is a prefix of the deleted sequence. Then $\boldsymbol{w}$ can be seen as
deleting $(x_{i+s},\ldots,x_{i+t-1})$ and thus $\boldsymbol{w}\in
B^{\prime}_{t-s,0}(\boldsymbol{x})$.

  * •

If $q$ does not exist, it means that
$(y_{1},\ldots,y_{s})=(x_{i+t-s},\ldots,x_{i+t-1})$, i.e., the inserted
sequence is a suffix of the deleted sequence. Then $\boldsymbol{w}$ can be
seen as deleting $(x_{i},\ldots,x_{i+t-s-1})$ and thus $\boldsymbol{w}\in
B^{\prime}_{t-s,0}(\boldsymbol{x})$.

  * •

Finally, if $p$ and $q$ exist and $p>q$, then it means that
$(y_{1},\ldots,y_{p-1})$ is a prefix of the deleted sequence and
$(y_{q+1},\ldots,y_{s})$ is a suffix of the deleted sequence. Then
$\boldsymbol{w}$ can be also seen as deleting
$(x_{i+p-1},\ldots,x_{i+p+t-s-2})$ and thus $\boldsymbol{w}\in
B^{\prime}_{t-s,0}(\boldsymbol{x})$.

Therefore,
$\bigcup_{\ell=0}^{s}B^{\prime}_{t-s+\ell,\ell}(\boldsymbol{x})=B_{t,s}(\boldsymbol{x})$
holds and it only remains to show the disjointness of
$B^{\prime}_{t-s+\ell,\ell}(\boldsymbol{x})$ for $0\leq\ell\leq s$. Suppose
there exist a sequence $\boldsymbol{z}\in
B^{\prime}_{t-s+\ell_{1},\ell_{1}}(\boldsymbol{x})\cap
B^{\prime}_{t-s+\ell_{2},\ell_{2}}(\boldsymbol{x})$, and $\boldsymbol{z}$ is
obtained by deleting $t-s+\ell_{1}$ (resp. $t-s+\ell_{2}$) symbols and
inserting $\ell_{1}$ (resp. $\ell_{2}$) symbols at the $i_{1}$th (resp.
$i_{2}$th) coordinate of $\boldsymbol{x}$.

If $i_{1}=i_{2}\triangleq i$, without loss of generality, we can assume
$\ell_{1}<\ell_{2}$. Then $\boldsymbol{z}$ has the following two
representations:

$\displaystyle\boldsymbol{z}^{1}=(x_{1},\ldots,x_{i-1},y_{1}^{1},\ldots,y_{\ell_{1}}^{1},x_{i+t-s+\ell_{1}+1},\ldots,x_{n}),$
$\displaystyle\boldsymbol{z}^{2}=(x_{1},\ldots,x_{i-1},y_{1}^{2},\ldots,y_{\ell_{2}}^{2},x_{i+t-s+\ell_{2}+1},\ldots,x_{n}).$

Comparing the $(i+t-s+\ell_{2})$th symbol, we have
$x_{i+t-s+\ell_{2}}=y_{\ell_{2}}^{2}$. However, since $\boldsymbol{z}\in
B^{\prime}_{t-s+\ell_{2},\ell_{2}}(\boldsymbol{x})$, in the representation of
$\boldsymbol{z}^{2}$ the last deleted symbol $x_{i+t-s+\ell_{2}}$ should be
different from the last inserted symbol $y_{\ell_{2}}^{2}$, a contradiction.

If $i_{1}\neq i_{2}$, without loss of generality let $i_{1}<i_{2}$. Comparing
the $i_{1}$th symbol of $\boldsymbol{z}^{1}$ and $\boldsymbol{z}^{2}$, we have
$y_{1}^{1}=x_{i_{1}}$. However, since $\boldsymbol{z}\in
B^{\prime}_{t-s+\ell_{1},\ell_{1}}(\boldsymbol{x})$, in the representation of
$\boldsymbol{z}^{1}$ the first deleted symbol $x_{i_{1}}$ should be different
from the first inserted symbol $y_{1}^{1}$, again a contradiction.

Thus, $B^{\prime}_{t-s+\ell_{1},\ell_{1}}(\boldsymbol{x})$ and
$B^{\prime}_{t-s+\ell_{2},\ell_{2}}(\boldsymbol{x})$ are disjoint for any
$\ell_{1}\neq\ell_{2}$, and the lemma is proved. ∎

Next, we need to calculate the size of each
$B^{\prime}_{k,\ell}(\boldsymbol{x})$.

When $\ell=0$, in [16] Levenshtein calculated the size of a $k$-burst-deletion
ball as:

$|B^{\prime}_{k,0}(\boldsymbol{x})|=1+\sum_{i=1}^{k}(r(A_{k}(\boldsymbol{x})_{i})-1),$
(3)

where $k\geq 1$, $A_{k}(\boldsymbol{x})_{i}$ is the $i$th row of the array
representation $A_{k}(x)$, and $r(A_{k}(\boldsymbol{x})_{i})$ is the number of
runs in the $i$th row. Further note that for the case $k=\ell=0$ we have
$B^{\prime}_{0,0}(\boldsymbol{x})=\\{\boldsymbol{x}\\}$ and thus
$|B^{\prime}_{0,0}(\boldsymbol{x})|=1$, which can be also seen as a special
case of Equation (3). In the next lemmas, we will compute the size of
$B^{\prime}_{k,\ell}(\boldsymbol{x})$ for the remaining cases.

###### Lemma 2

Let $\boldsymbol{x}\in\mathbb{F}_{2}^{n}$, $k\geq 1,\ell=1$, then

$|B^{\prime}_{k,1}(\boldsymbol{x})|=n-\sum_{i=1}^{k-1}r(A_{k-1}(\boldsymbol{x})_{i}).$
(4)

###### Proof:

First consider $k\geq 2$. Recall that any $\boldsymbol{y}\in
B^{\prime}_{k,1}(\boldsymbol{x})$ is obtained from $\boldsymbol{x}$ by
deleting a string of length $k$ starting and ending with the same symbol $a$
and inserting $1-a$. Let $\boldsymbol{y}_{1},\boldsymbol{y}_{2}\in
B^{\prime}_{k,1}(\boldsymbol{x})$ where the $(k,1)$-bursts start at the
$i_{1}$th and $i_{2}$th coordinate, respectively (WLOG, assume $i_{1}<i_{2}$).
That is,
$\boldsymbol{y}_{1}=(x_{1},\dots,x_{i_{1}-1},y_{1},x_{i_{1}+k},\dots,x_{n})$
and
$\boldsymbol{y}_{2}=(x_{1},\dots,x_{i_{2}-1},y_{2},x_{i_{2}+k},\dots,x_{n})$.
Note that since $x_{i_{1}}=x_{i_{1}+k-1}\neq y_{1}$, then $\boldsymbol{y}_{1}$
and $\boldsymbol{y}_{2}$ have distinct symbols on their $i_{1}$th coordinate
and thus $\boldsymbol{y}_{1}\neq\boldsymbol{y}_{2}$. Therefore,
$|B^{\prime}_{k,1}(\boldsymbol{x})|$ is exactly the number of coordinates $i$
such that $x_{i}=x_{i-k+1}$, $1\leq i\leq n-k+1$.

Write $\boldsymbol{x}$ as a $(k-1)\times\frac{n}{k-1}$ array:

$A_{k-1}(\boldsymbol{x})=\begin{bmatrix}x_{1}&x_{k}&\cdots&x_{n-k+2}\\\
x_{2}&x_{k+1}&\cdots&x_{n-k+3}\\\ \vdots&\vdots&\ddots&\vdots\\\
x_{k-1}&x_{2k-2}&\cdots&x_{n}\end{bmatrix}.$

In the representation of $A_{k-1}(\boldsymbol{x})$, $x_{i}$ and $x_{i-k+1}$
are two consecutive symbols in a row. The $i$th row contributes
$\frac{n}{k-1}-r(A_{k-1}(\boldsymbol{x})_{i})$ to the size of
$|B^{\prime}_{k,1}(\boldsymbol{x})|$. Therefore for $k\geq 2$ we have

$|B^{\prime}_{k,1}(\boldsymbol{x})|=\sum_{i=1}^{k-1}\Big{(}\frac{n}{k-1}-r(A_{k-1}(\boldsymbol{x})_{i})\Big{)}=n-\sum_{i=1}^{k-1}r(A_{k-1}(\boldsymbol{x})_{i}).$

In addition, when $k=1$, $B^{\prime}_{1,1}(\boldsymbol{x})$ is the Hamming
sphere of radius 1 (without the center) and thus
$|B^{\prime}_{1,1}(\boldsymbol{x})|=n$, which can also be seen as a special
case of Equation (4). ∎

###### Lemma 3

Let $\boldsymbol{x}\in\mathbb{F}_{2}^{n}$, $k\geq 1,\ell\geq 2$, then

$|B^{\prime}_{k,\ell}(\boldsymbol{x})|=(n-k+1)\cdot 2^{\ell-2}.$

###### Proof:

All the sequences in $B^{\prime}_{k,\ell}(\boldsymbol{x})$ have the form
$x_{1}\ldots x_{i-1}y_{1}\ldots y_{\ell}x_{i+k}\ldots x_{n}$, where $1\leq
i\leq n-k+1$ is the starting coordinate of the deletion. We claim that if the
starting coordinates are different, then the two obtained sequence must be
different. Suppose $\boldsymbol{y}_{1}$ and $\boldsymbol{y}_{2}$ are two
sequences in $B^{\prime}_{k,\ell}(\boldsymbol{x})$, and their errors start at
the $i_{1}$th and $i_{2}$th coordinate of $\boldsymbol{x}$, respectively
(WLOG, assume $i_{1}<i_{2}$). Then $\boldsymbol{y}_{1}$ and
$\boldsymbol{y}_{2}$ have distinct symbols on their $i_{1}$th coordinate and
thus $\boldsymbol{y}_{1}\neq\boldsymbol{y}_{2}$.

To calculate $|B^{\prime}_{k,\ell}(\boldsymbol{x})|$, we have $n-k+1$ choices
for $i$, and once $i$ is given the inserted sequence has $2^{\ell-2}$
possibilities since $y_{1}=1-x_{i}$ and $y_{\ell}=1-x_{i+k-1}$ are fixed. As a
consequence, there are altogether $(n-k+1)\cdot 2^{\ell-2}$ distinct sequences
in $B^{\prime}_{k,\ell}(\boldsymbol{x})$. ∎

###### Lemma 4

Let $\boldsymbol{x}\in\mathbb{F}_{2}^{n}$, $k=0,\ell\geq 1$, then

$|B^{\prime}_{0,\ell}(\boldsymbol{x})|=n\cdot 2^{\ell-1}+2^{\ell}.$

###### Proof:

For any $\boldsymbol{y}\in B^{\prime}_{0,\ell}(\boldsymbol{x})$, let $1\leq
i\leq n$ be the first coordinate where $\boldsymbol{x}$ and $\boldsymbol{y}$
differ, then $\boldsymbol{y}$ can be seen as inserting a sequence of length
$\ell$ at the $i$th coordinate and there are $2^{\ell-1}$ possibilities for
the inserted sequence. If no such $i$ exists, which means the first $n$
symbols of $\boldsymbol{y}$ equal $\boldsymbol{x}$, then $\boldsymbol{y}$ can
be seen as inserting a sequence of length $\ell$ at the end of
$\boldsymbol{x}$ and there are $2^{\ell}$ possibilities for the inserted
sequence. To sum up we have $|B^{\prime}_{0,\ell}(\boldsymbol{x})|=n\cdot
2^{\ell-1}+2^{\ell}$. ∎

Summarizing the previous lemmas, the size of
$|B^{\prime}_{k,\ell}(\boldsymbol{x})|$ is as follows:

$B^{\prime}_{k,\ell}(\boldsymbol{x})=\begin{cases}1+\sum_{i=1}^{k}(r(A_{k}(\boldsymbol{x})_{i})-1),&\mbox{if
}k\geq 0,\ell=0\\\ n-\sum_{i=1}^{k-1}r(A_{k-1}(\boldsymbol{x})_{i}),&\mbox{if
}k\geq 1,\ell=1\\\ (n-k+1)\cdot 2^{\ell-2},&\mbox{if }k\geq 1,\ell\geq 2\\\
n\cdot 2^{\ell-1}+2^{\ell},&\mbox{if }k=0,\ell\geq 1\end{cases}$

Now we are ready to compute the size of the error ball
$B_{t,s}(\boldsymbol{x})$.

###### Theorem 2

For $\boldsymbol{x}\in\\{0,1\\}^{n},t,s\in\mathbb{N}^{*}$, the size of a
$(t,s)$-burst error ball is

$|B_{t,s}(\boldsymbol{x})|=(n-t+2)\cdot 2^{s-1}.$

###### Proof:

If $t\geq s$, from Lemma 1, we can calculate

$\displaystyle|B_{t,s}(\boldsymbol{x})|$
$\displaystyle=\sum_{\ell=0}^{s}|B^{\prime}_{t-s+\ell,\ell}(\boldsymbol{x})|$
$\displaystyle=1+\sum_{i=1}^{t-s}(r(A_{t-s}(\boldsymbol{x})_{i})-1)+n-\sum_{i=1}^{t-s}r(A_{t-s}(\boldsymbol{x})_{i})+\sum_{\ell=2}^{s}(n-t+s-\ell+1)\cdot
2^{\ell-2}$ $\displaystyle=n+s-t+1+\sum_{\ell=0}^{s-2}(n-t+s-\ell-1)\cdot
2^{\ell}$

Let $S=\sum_{\ell=0}^{s-2}(n-t+s-\ell-1)\cdot 2^{\ell}$, then
$2S=\sum_{\ell=0}^{s-2}(n-t+s-\ell-1)\cdot
2^{\ell+1}=\sum_{\ell=1}^{s-1}(n-t+s-\ell)\cdot 2^{\ell}$. So, we can
calculate $S$ as

$\displaystyle 2S-S$ $\displaystyle=\sum_{\ell=1}^{s-1}(n-t+s-\ell)\cdot
2^{\ell}-\sum_{\ell=0}^{s-2}(n-t+s-\ell-1)\cdot 2^{\ell}$
$\displaystyle=(n-t+1)\cdot 2^{s-1}+\sum_{\ell=1}^{s-2}2^{\ell}-(n-t+s-1)$
$\displaystyle=(n-t+2)\cdot 2^{s-1}-n+t-s-1.$

Thus, the size of the error ball is

$\displaystyle|B_{t,s}(\boldsymbol{x})|$
$\displaystyle=n+s-t+1+\sum_{\ell=0}^{s-2}(n-t+s-i-1)\cdot 2^{\ell}$
$\displaystyle=n+s-t+1+(n-t+2)\cdot 2^{s-1}-n+t-s-1$
$\displaystyle=(n-t+2)\cdot 2^{s-1}.$

Similarly, if $t<s$, from Lemma 1, we can calculate

$\displaystyle|B_{t,s}(\boldsymbol{x})|$
$\displaystyle=\sum_{k=0}^{t}|B^{\prime}_{k,s-t+k}(\boldsymbol{x})|$
$\displaystyle=n\cdot 2^{s-t-1}+2^{s-t}+\sum_{k=1}^{t}(n-k+1)\cdot
2^{s-t+k-2}$ $\displaystyle=(n-t+2)\cdot 2^{s-1}.$

Summing up the above, we have proved that for any $t,s\in\mathbb{N}^{*}$,
$|B_{t,s}(\boldsymbol{x})|=(n-t+2)\cdot 2^{s-1}$. ∎

###### Example 2

Let $n=12,\boldsymbol{x}=101011100100$, $t=4,s=1$, then

$A_{3}(\boldsymbol{x})=\begin{bmatrix}1&0&1&1\\\ 0&1&0&0\\\
1&1&0&0\end{bmatrix}.$
$\begin{split}B^{\prime}_{3,0}(\boldsymbol{x})=\\{&011100100,111100100,101100100,101000100,101010100,101011100\\},\\\
B^{\prime}_{4,1}(\boldsymbol{x})=\\{&100100100,101011000,101011110,101011101\\}.\end{split}$

Hence,
$|B^{\prime}_{3,0}(\boldsymbol{x})|+|B^{\prime}_{4,1}(\boldsymbol{x})|=10=(12-4+2)\cdot
2^{0}.$

Theorem 2 shows that the size of the $(t,s)$-burst ball is independent of its
center, which is rather rare in other models concerning deletions or
insertions. A sphere-packing type upper bound naturally follows.

###### Theorem 3

Let $\mathcal{C}\subseteq\mathbb{F}_{2}^{n}$ be a $(t,s)$-burst correcting
code, then

$|\mathcal{C}|\leq\frac{2^{n-t+1}}{n-t+2}.$

###### Proof:

Given any two words $\boldsymbol{c}_{1},\boldsymbol{c}_{2}\in\mathcal{C}$,

$B_{t,s}(\boldsymbol{c}_{1})\cap B_{t,s}(\boldsymbol{c}_{2})=\varnothing.$

Now consider the union of all $(t,s)$-burst balls centered at the codewords in
$\mathcal{C}$. Obviously, their union is a subset of $\mathbb{F}_{2}^{n-t+s}$.
In other words,

$\Big{|}\bigcup_{\boldsymbol{c}\in\mathcal{C}}B_{t,s}(\boldsymbol{c})\Big{|}\leq
2^{n-t+s}.$

Since any two $(t,s)$-burst balls centered at distinct codewords in
$\mathcal{C}$ are disjoint,

$\Big{|}\bigcup_{\boldsymbol{c}\in\mathcal{C}}B_{t,s}(\boldsymbol{c})\Big{|}=\sum_{\boldsymbol{c}\in\mathcal{C}}|B_{t,s}(\boldsymbol{c})|=(n-t+2)\cdot
2^{s-1}\cdot|\mathcal{C}|$

Consequently,

$|\mathcal{C}|\leq\frac{2^{n-t+1}}{n-t+2}.$

∎

Note that for $t=s=1$ the upper bound above coincides with the Hamming bound
for a single substitution, and when $t=s$ our upper bound coincides with the
upper bound of burst-error correcting code for substitutions derived by
Dass[5]. Moreover, it is quite interesting that the upper bound above is
irrelevant to the number of inserted symbols $s$. Recall the equivalence of
$(t,s)$-burst correcting codes and $(s,t)$-burst correcting codes, $t$ can be
replaced by $s$ in the upper bound of Theorem 3, and the better bound is the
one using the relatively larger value between $t$ and $s$. Therefore, from now
on we only focus on the case $t\geq s$, and the redundancy of a $(t,s)$-burst
correcting code is lower bounded by

$n-\log|\mathcal{C}|\geq\log(n-t+2)+t-1\approx\log n+t-1.$

##  V A General Construction of $(t,s)$-Burst Correcting Codes for $t\geq 2s$

The equivalence allows us to focus only on the case $t\geq s$, i.e., the
number of deletions is no less than the number of insertions. In this section,
we provide a construction of $(t,s)$-burst correcting codes for $t\geq 2s$. We
start with an overall explanation of the main idea, and then proceed with the
detailed construction and analysis followed by some discussions.

###  V-A Sketch of the main Idea

In the array representation $A_{t-s}(\boldsymbol{x})$, if $t\geq 2s$, then it
is routine to check that a $(t,s)$-burst results in an array of size
$(t-s)\times(\frac{n}{t-s}-1)$ and each row of $A_{t-s}(\boldsymbol{x})$
suffers from either one deletion or a $(2,1)$-burst. To be more specific,
suppose the starting coordinate of the error is located at the $k$th row of
$A_{t-s}(\boldsymbol{x})$, then each of the rows indexed by
$k,k+1,\dots,k+s-1$ (indices are calculated modulo $t-s$) suffers from a
$(2,1)$-burst and each of the rest rows suffers from a single deletion. The
following toy example help visualize the error type on each row. Let $t=5$,
$s=2$, and $n=12$. Below are the error patterns if the error starts on the
3rd, 4th, or the 5th coordinate, correspondingly.

$\begin{bmatrix}x_{1}&\underline{x_{4}}&\underline{x_{7}}&x_{10}\\\
x_{2}&\underline{x_{5}}&x_{8}&x_{11}\\\
\underline{x_{3}}&\underline{x_{6}}&x_{9}&x_{12}\end{bmatrix}\rightarrow\begin{bmatrix}x_{1}&\underline{y_{2}}&x_{10}\\\
x_{2}&x_{8}&x_{11}\\\
\underline{y_{1}}&x_{9}&x_{12}\end{bmatrix},\begin{bmatrix}x_{1}&\underline{x_{4}}&\underline{x_{7}}&x_{10}\\\
x_{2}&\underline{x_{5}}&\underline{x_{8}}&x_{11}\\\
x_{3}&\underline{x_{6}}&x_{9}&x_{12}\end{bmatrix}\rightarrow\begin{bmatrix}x_{1}&\underline{y_{1}}&x_{10}\\\
x_{2}&\underline{y_{2}}&x_{11}\\\
x_{3}&x_{9}&x_{12}\end{bmatrix},\begin{bmatrix}x_{1}&x_{4}&\underline{x_{7}}&x_{10}\\\
x_{2}&\underline{x_{5}}&\underline{x_{8}}&x_{11}\\\
x_{3}&\underline{x_{6}}&\underline{x_{9}}&x_{12}\end{bmatrix}\rightarrow\begin{bmatrix}x_{1}&x_{4}&x_{10}\\\
x_{2}&\underline{y_{1}}&x_{11}\\\ x_{3}&\underline{y_{2}}&x_{12}\end{bmatrix}$

Recall that the $(2,1)$-burst correcting code as shown in Equation (2) can
also correct a single deletion, due to the VT syndrome in its definition. We
can let the first row of $A_{t-s}(\boldsymbol{x})$ be chosen from a
$(2,1)$-burst correcting code, and decoding this row will provide us some
additional knowledge about the location of the error in the other rows. To be
more specific, the decoding of the first row (using a decoder for a
$(2,1)$-burst correcting code) falls into three cases.

  * 1.

The first row suffers from a $(2,1)$-burst where the error is of the form
$00\rightarrow 1$ or $11\rightarrow 0$.

  * 2.

The first row suffers from a $(2,1)$-burst which does not belong to Case 1.

  * 3.

The first row suffers from a single deletion.

For Case 1, we can uniquely determine the two erroneous coordinates in the
first row. Since $t\leq 2(t-s)$, the deleted coordinates are within at most
three consecutive columns. Therefore, the erroneous coordinates in the other
rows are located within an interval of length at most 3. See the previous
example, if we have determined that the first row suffers from a $(2,1)$-burst
at the second coordinate (the left one and the middle one), then the erroneous
coordinates on the other rows are only of the following possibilities: a
$(2,1)$-burst at the first coordinate (3rd row in the left one), a
$(2,1)$-burst at the second coordinate (2nd row in the middle one), or a
single deletion at the second coordinate.

Case 2 can be also seen as a single deletion in the first row. Therefore we
can combine Case 2 and Case 3 together, and locate the single deletion in the
first row within a run, which might range from the $c_{1}$th to the $c_{2}$th
column, for some $c_{1}\leq c_{2}$. Then the errors in the other rows should
be within columns indexed from $c_{1}-1$ to $c_{2}$. By adding additional run-
length constraint on the first row, $c_{2}-c_{1}$ is bounded and then we may
apply a $(2,1)$-burst-SVT code (to be defined later), which can correct a
$(2,1)$-burst with the additional knowledge about the location of the error
within an interval of $P$ consecutive coordinates.

Here is an example to illustrate the whole decoding process.

###### Example 3

Let $\boldsymbol{x}=101011001101110$, $t=4,s=1$, and the erroneous sequence is
$\boldsymbol{x}^{\prime}=101010101110$. First write $\boldsymbol{x}^{\prime}$
in the form of an array,

$A_{3}(\boldsymbol{x}^{\prime})=\begin{bmatrix}1&0&1&1\\\ 0&1&0&1\\\
1&0&1&0\end{bmatrix}.$

Applying the decoder of a $(2,1)$-burst correcting code to the first row, we
get $10011$. In addition we know that the first row suffers from a single
deletion on either the second or the third coordinate. Therefore, the errors
in the remaining two rows are within their first three coordinates. Applying
the decoder of a $(2,1)$-burst SVT code with $P=3$ to them, we get the second
and third rows as $01001$, $11110$ respectively. Consequently,

$A_{3}(\boldsymbol{x})=\begin{bmatrix}1&0&0&1&1\\\ 0&1&0&0&1\\\
1&1&1&1&0\end{bmatrix},$

and $\boldsymbol{x}=101011001101110$ is correctly decoded.

We close this subsection by discussing the parameter $P$ in the run-length
constraint[13]. If $P$ is too large (e.g. linear in $n$), using $(2,1)$-burst
SVT codes does not reduce the total redundancy as compared to just using
$(2,1)$-burst correcting codes. Therefore, to further reduce the redundancy we
want to make $P$ small. Define $\mathcal{S}_{n}(f(n))$ to be the set of binary
sequences of length $n$ whose maximum run length is at most $f(n)$. An
algorithm is provided to efficiently encode any binary sequence to a $(\log
n+3)$-RLL sequence with only 1 bit of redundancy in [17], i.e.,
$|\mathcal{S}_{n}(\log n+3)|\geq 2^{n-1}$. Once we use a subcode of
$\mathcal{S}_{n}(\log n+3)$ in the first row, it is guaranteed that for the
other rows we have the additional knowledge about the location of the error
within a bounded interval.

Now, we are fully prepared to present our main construction.

###  V-B A general construction for $t\geq 2s$

We follow the array representation framework to write $\boldsymbol{x}$ as an
array $A_{t-s}(\boldsymbol{x})$ of size $(t-s)\times\frac{n}{t-s}$. The first
row $A_{t-s}(\boldsymbol{x})$ comes from the following code.

###### Construction 1

For arbitrary integers $n$ and $a\in\mathbb{Z}_{2n-1},b\in\mathbb{Z}_{4}$,
define $\mathcal{C}_{2,1}^{\mathrm{RLL}}(n;a,b,\log n+3)$ as

$\mathcal{C}_{2,1}^{\mathrm{RLL}}(n;a,b,\log
n+3)=\mathcal{C}_{2,1}(n;a,b)\cap\mathcal{S}_{n}(\log n+3).$

###### Theorem 4

For arbitrary integers $n$, there exists a code
$\mathcal{C}_{2,1}^{\mathrm{RLL}}(n;a,b,\log n+3)$ with redundancy at most
$\log n+4$.

###### Proof:

Recall that $|\mathcal{S}_{n}(\log n+3)|\geq 2^{n-1}$. Moreover, for
$a\in\mathbb{Z}_{2n-1},b\in\mathbb{Z}_{4}$,
$\bigcup_{a,b}\mathcal{C}_{2,1}(n;a,b)\cap\mathcal{S}_{n}(\log n+3)$ is a
disjoint partition of $\mathcal{S}_{n}(\log n+3)$. Thus according to the
pigeonhole principle, there must exist choices for $a\in\mathbb{Z}_{2n-1}$ and
$b\in\mathbb{Z}_{4}$, such that

$|\mathcal{C}_{2,1}^{\mathrm{RLL}}(n;a,b,\log
n+3)|\geq\frac{2^{n-1}}{4(2n-1)}.$

Therefore, the redundancy is at most

$n-\log|\mathcal{C}_{2,1}^{\mathrm{RLL}}(n;a,b,\log n+3)|=\log 4(2n-1)+1<\log
n+4.$

∎

Due to the RLL constraint of the first row, the starting coordinate of the
error on each remaining row will be limited to an interval of length $\log
n+4$. Now, we will provide a code which can correct a $(2,1)$-burst with this
additional knowledge.

###### Construction 2

For arbitrary integers $n$ and $c\in\mathbb{Z}_{2P-1},d\in\mathbb{Z}_{4}$,
$P\leq n$ define the $SVT_{2,1}^{\mathrm{burst}}(n;c,d,P)$ as

$SVT_{2,1}^{\mathrm{burst}}(n;c,d,P)=\Big{\\{}\boldsymbol{x}:VT(\boldsymbol{x})\equiv
c\pmod{2P-1},\sum_{i=1}^{n}x_{i}\equiv d\pmod{4}\Big{\\}}.$

###### Theorem 5

The $(2,1)$-burst-SVT code $SVT_{2,1}^{\mathrm{burst}}(n;c,d,P)$ can correct a
$(2,1)$-burst with the additional knowledge of the starting location of the
$(2,1)$-burst within an interval of $P$ consecutive coordinates. Furthermore,
there exist choices for $c$ and $d$ such that the redundancy of the code is at
most $\log P+3$.

###### Proof:

For any $\boldsymbol{u}\in\mathbb{F}_{2}^{n}$ that suffers from a
$(2,1)$-burst, denote the received sequence as
$\boldsymbol{u}^{\prime}\in\mathbb{F}_{2}^{n-1}$. Define
$\Delta=\sum_{i=1}^{n}u_{i}-\sum_{i=1}^{n-1}u^{\prime}_{i}\pmod{4}$,
$\Delta\in\\{0,1,2,3\\}$. The decoding starts with the observation of the
value $\Delta$.

We have $\Delta=3$ if and only if $00\rightarrow 1$ happens. Similarly, We
have $\Delta=2$ if and only if $11\rightarrow 0$ happens. For the remaining
cases, when $\Delta=0$ or $1$, the $(2,1)$-burst error could be seen as just a
single deletion. Since $SVT_{2,1}^{\mathrm{burst}}(n;c,d,P)$ is also an SVT
code (due to the VT syndrome in its definition), it can correct a single
deletion with the additional knowledge of the deleted coordinate within a
length-$P$ interval.

We are only left with the case when the error is $11\rightarrow 0$ or
$00\rightarrow 1$. We only prove the former case $11\rightarrow 0$. The latter
case $00\rightarrow 1$ can be proved analogously.

Suppose there exist $\boldsymbol{x},\boldsymbol{y}\in
SVT_{2,1}^{\mathrm{burst}}(n;c,d,P)$, such that $\boldsymbol{z}\in
B_{2,1}(\boldsymbol{x})\cap B_{2,1}(\boldsymbol{y})$. Suppose the
$(2,1)$-burst of the form $11\rightarrow 0$ starts at $i$th coordinate of
$\boldsymbol{x}$ and $j$th coordinate of $\boldsymbol{y}$, and without loss of
generality $i<j$. We have

$\begin{split}&\boldsymbol{x}=(x_{1},\ldots,x_{i-1},1,1,x_{i+2},\ldots,x_{j},0,x_{j+2},\ldots,x_{n}),\\\
&\boldsymbol{y}=(y_{1},\ldots,y_{i-1},0,y_{i+1},\ldots,y_{j-1},1,1,y_{j+2},\ldots,y_{n}),\end{split}$

where $x_{k}=y_{k}$ when $1\leq k\leq i-1$ and $j+2\leq k\leq n$,
$x_{k+1}=y_{k}$ when $i+1\leq k\leq j-1$.

Now we consider the difference of syndromes
$VT(\boldsymbol{x})-VT(\boldsymbol{y})$, which is equal to

$\sum_{i=1}^{n}ix_{i}-\sum_{i=1}^{n}iy_{i}=i+(i+1)+\text{wt}(x_{i+2},\ldots,x_{j})-j-(j+1)=2(i-j)+\text{wt}(x_{i+2},\ldots,x_{j})$

Since $0\leq\text{wt}(x_{i+2},\ldots,x_{j})\leq j-i-1$, we have

$2(i-j)\leq VT(\boldsymbol{x})-VT(\boldsymbol{y})\leq i-j-1.$

Furthermore, $i$ and $j$ are within an interval of length $P$, so $1\leq
j-i\leq P-1$. Hence,

$-2(P-1)\leq VT(\boldsymbol{x})-VT(\boldsymbol{y})\leq-2.$

Therefore, $VT(\boldsymbol{x})-VT(\boldsymbol{y})\neq 0$, which contradicts to
the fact that $\boldsymbol{x},\boldsymbol{y}\in
SVT_{2,1}^{\mathrm{burst}}(n;c,d,P)$. Thus
$SVT_{2,1}^{\mathrm{burst}}(n;c,d,P)$ can uniquely correct a $(2,1)$-burst
error with the additional knowledge of the starting location of the
$(2,1)$-burst within an interval of $P$ consecutive coordinates.

Moreover, since $\bigcup_{c,d}SVT_{2,1}^{\mathrm{burst}}(n;c,d,P)$ is a
partition of $\mathbb{F}_{2}^{n}$, according to the pigeonhole principle,
there must exist $c$ and $d$ such that the code size is at least
$\frac{2^{n}}{4(2P-1)}$, thus the redundancy of the code is at most
$\log(2P-1)+2<\log P+3$. ∎

Now, we are ready to present our construction of $(t,s)$-burst correcting
codes for $t\geq 2s$.

###### Construction 3

Let $t,s\in\mathbb{N}^{*}$ such that $t\geq 2s$. Let
$a\in\mathbb{Z}_{2n/(t-s)-1},b\in\mathbb{Z}_{4}$, and
$c_{i}\in\mathbb{Z}_{2P-1},d_{i}\in\mathbb{Z}_{4}$, where $2\leq i\leq t-s$,
$P=\log\frac{n}{t-s}+4$. The code $\mathcal{C}_{t,s}$ is constructed as
follows:

$\begin{split}\mathcal{C}_{t,s}\triangleq&\Big{\\{}\boldsymbol{x}:A_{t-s}(\boldsymbol{x})_{1}\in\mathcal{C}_{2,1}^{\mathrm{RLL}}\Big{(}\frac{n}{t-s};a,b,\log\frac{n}{t-s}+3\Big{)},\\\
&A_{t-s}(\boldsymbol{x})_{i}\in
SVT_{2,1}^{\mathrm{burst}}\Big{(}\frac{n}{t-s};c_{i},d_{i},\log\frac{n}{t-s}+4\Big{)},\text{
for }2\leq i\leq t-s\Big{\\}}.\end{split}$

###### Theorem 6

The code $\mathcal{C}_{t,s}$ is a $(t,s)$-burst correcting code, and there
exist choices for $a,b,c_{i},d_{i}$ such that the redundancy of the code is at
most $\log n+(t-s-1)\log\log n+O(1)$.

###### Proof:

Suppose $\boldsymbol{x}\in\mathcal{C}_{t,s}$ suffers from a $(t,s)$-burst and
the erroneous sequence is denoted as $\boldsymbol{y}$. Consider them in the
array form $A_{t-s}(\boldsymbol{x})$ and $A_{t-s}(\boldsymbol{y})$. The
$(t,s)$-burst will cause either a $(2,1)$-burst or a single deletion in the
first row, which could be correctly decoded since the first row comes from a
$(2,1)$-burst correcting code. After decoding $A_{t-s}(\boldsymbol{x})_{1}$
and comparing with $A_{t-s}(\boldsymbol{y})_{1}$, due to the run-length
constraint of the first row, we will get some additional knowledge.

On one hand, if the first row suffers from a single deletion, then we may
locate its deleted coordinate within an interval of length
$\log\frac{n}{t-s}+3$. The starting coordinate of error in the other rows will
be located within an interval of length $\log\frac{n}{t-s}+4$. Then the rest
rows can be uniquely decoded due to the property of the $(2,1)$-burst SVT
code.

On the other hand, if the first row suffers from a $(2,1)$-burst in the form
of $00\rightarrow 1$ or $11\rightarrow 0$, then we may locate the erroneous
coordinates on the first row and the erroneous coordinates on the other rows
are within an interval of length 3, thus again the rest rows can be uniquely
decoded due to the property of the $(2,1)$-burst SVT code.

To sum up, $\mathcal{C}_{t,s}$ is indeed a $(t,s)$-burst correcting code.

As for the size of the code, by the pigeonhole principle there must exist
choices for $a,b,c_{i},d_{i}$, $2\leq i\leq t-s$, such that

$|\mathcal{C}_{t,s}|\geq\frac{2^{\frac{n}{t-s}-1}\cdot(2^{\frac{n}{t-s}})^{t-s-1}}{4\cdot(\frac{2n}{t-s}-1)\cdot\Big{(}4\cdot\big{(}2(\log\frac{n}{t-s}+4)-1\big{)}\Big{)}^{t-s-1}}.$

Hence, the redundancy is at most

$4+\log\frac{n}{t-s}+(t-s-1)(\log(\log\frac{n}{t-s}+4)+3),$

which is $\log n+(t-s-1)\log\log n+O(1)$. ∎

###  V-C Further discussions

Note that, $(t,s)$-burst correcting codes can correct $(t-s,0)$-burst errors
(i.e., $(t-s)$-burst-deletion), then $(t,s)$-burst correcting codes are
naturally also $(t-s)$-burst-deletion-correcting codes. Regarding the
redundancy, the optimal redundancy of $(t,s)$-burst correcting codes should be
lower bounded by the optimal redundancy of $(t-s)$-burst-deletion-correcting
codes.

Up till now the best known construction of $(t-s)$-burst-deletion-correcting
codes is the one from [17], where the redundancy is about $\log
n+(t-s-1)\log\log n+O(1)$. Comparing with the redundancy of our $(t,s)$-burst
correcting codes from Construction 3, there is only a difference of a constant
term. Therefore, as a byproduct, our codes from Construction 3 also performs
well against only $(t-s)$-burst-deletions.

Furthermore, note that there is only a $\log\log n$ gap between the redundancy
of Construction 3 and the lower bound suggested by the sphere-packing bound.
In the next section, for $t=3$ and $s=1$ we manage to close this gap.

##  VI Optimal Codes Correcting a $(3,1)$-Burst

A $(2,1)$-burst error, except for the two forms $11\rightarrow 0$,
$00\rightarrow 1$, can be seen as a single deletion. The almost optimal
$(2,1)$-burst correcting code with redundancy $\log n+3$ from[17], as shown in
Equation (2), adds an additional constraint on the basis of the VT code, in
order to deal with the errors of the form $11\rightarrow 0$ and $00\rightarrow
1$. Motivated by this construction and the fact that a large proportion of
$(3,1)$-burst errors could be seen as a $2$-burst-deletion, we build our code
based on Levenshtein’s code for $2$-burst-deletions as shown in Equation (1),
and add some additional constraints in order to deal with the other kinds of
$(3,1)$-burst errors.

###### Construction 4

For $a\in\mathbb{Z}_{4n}$, $b,c\in\mathbb{Z}_{4}$, and $d\in\mathbb{Z}_{5}$,
the code $\mathcal{C}_{3,1}$ is defined as follows:

$\mathcal{C}_{3,1}(n;a,b,c,d)=\Big{\\{}\boldsymbol{x}:Rsyn(0\boldsymbol{x})\equiv
a~{}(\bmod{4n}),\sum_{i=1}^{n/2}x_{2i-1}\equiv b~{}(\bmod
4),\sum_{i=1}^{n/2}x_{2i}\equiv c~{}(\bmod 4),r(\boldsymbol{x})\equiv
d~{}(\bmod 5)\Big{\\}}.$

In order to show that $\mathcal{C}_{3,1}$ is a $(3,1)$-burst correcting code
we need several steps. First we divide all $(3,1)$-burst errors into two
types. The first type contains those which can be seen as a $2$-burst, for
example, $001\rightarrow 1$, $000\rightarrow 0$. The second type only consists
of the following: $\\{000\rightarrow 1,010\rightarrow 1,111\rightarrow
0,101\rightarrow 0\\}$. To verify which type of error occurs, we need to
observe the following two values. Suppose
$\boldsymbol{u}\in\mathbb{F}_{2}^{n}$ is a codeword in
$\mathcal{C}_{3,1}(n;a,b,c,d)$, and
$\boldsymbol{u}^{\prime}\in\mathbb{F}_{2}^{n-2}$ is the sequence obtained from
$\boldsymbol{u}$ by a $(3,1)$-burst. Let
$\Delta_{odd}(\boldsymbol{u})=\sum_{i=1}^{n/2}u_{2i-1}-\sum_{i=1}^{n/2-1}u^{\prime}_{2i-1}\pmod{4}$
and
$\Delta_{even}(\boldsymbol{u})=\sum_{i=1}^{n/2}u_{2i}-\sum_{i=1}^{n/2-1}u^{\prime}_{2i}\pmod{4}$.

###### Lemma 5

By observing $\Delta_{odd}(\boldsymbol{u})$ and
$\Delta_{even}(\boldsymbol{u})$, one can verify whether the $(3,1)$-burst
error is a $2$-burst-deletion or is of the form $\\{000\rightarrow
1,010\rightarrow 1,111\rightarrow 0,101\rightarrow 0\\}$.

###### Proof:

Suppose the $(3,1)$-burst starts at the $i$th coordinate of
$\boldsymbol{u}=(u_{1},u_{2},\dots,u_{n})$ and results in
$(u_{1},\dots,u_{i-1},y,u_{i+3},\dots,u_{n})$, where $y$ is the inserted
symbol. If $i$ is odd, then $\Delta_{odd}(\boldsymbol{u})=u_{i}+u_{i+2}-y$ and
$\Delta_{even}(\boldsymbol{u})=u_{i+1}$. Similarly, if $i$ is even then
$\Delta_{even}(\boldsymbol{u})=u_{i}+u_{i+2}-y$ and
$\Delta_{odd}(\boldsymbol{u})=u_{i+1}$. The correspondence of the error type
and $(\Delta_{odd}(\boldsymbol{u}),\Delta_{even}(\boldsymbol{u}))$ is as
follows:

  * •

$000\rightarrow 1$. Then
$(\Delta_{odd}(\boldsymbol{u}),\Delta_{even}(\boldsymbol{u}))$ is either
$(3,0)$ or $(0,3)$.

  * •

$010\rightarrow 1$. Then
$(\Delta_{odd}(\boldsymbol{u}),\Delta_{even}(\boldsymbol{u}))$ is either
$(3,1)$ or $(1,3)$.

  * •

$111\rightarrow 0$. Then
$(\Delta_{odd}(\boldsymbol{u}),\Delta_{even}(\boldsymbol{u}))$ is either
$(2,1)$ or $(1,2)$.

  * •

$101\rightarrow 0$. Then
$(\Delta_{odd}(\boldsymbol{u}),\Delta_{even}(\boldsymbol{u}))$ is either
$(2,0)$ or $(0,2)$.

  * •

If the error is a 2-deletion, the two deleted symbols are $00,01,10,11$ and
$(\Delta_{odd}(\boldsymbol{u}),\Delta_{even}(\boldsymbol{u}))\in\\{(0,0),(0,1),(1,0),(1,1)\\}$.

Thus, the disjointness of the possible values of
$(\Delta_{odd}(\boldsymbol{u}),\Delta_{even}(\boldsymbol{u}))$ allows us to
precisely determine the error type. ∎

The first step of our decoding process is to observe
$(\Delta_{odd}(\boldsymbol{x}),\Delta_{even}(\boldsymbol{x}))$ based on Lemma
5. Suppose that we have verified that the error is indeed a $2$-burst-
deletion. Then, as proved by Levenshtein[16], the constraint
$Rsyn(0\boldsymbol{x})\equiv a~{}(\bmod{4n})$ in the code $\mathcal{C}_{3,1}$
guarantees that we can successfully decode any $2$-burst-deletion error.
Therefore, it suffices to analyze the case when the error is of the form
$\\{000\rightarrow 1,010\rightarrow 1,111\rightarrow 0,101\rightarrow 0\\}$.
In the rest of this section we only prove that $\mathcal{C}_{3,1}$ is an
error-correcting code against the error type $000\rightarrow 1$ or the error
type $010\rightarrow 1$. The error types $111\rightarrow 0$ and
$101\rightarrow 0$ can be proved analogously and are thus omitted.

###### Lemma 6

$\mathcal{C}_{3,1}$ is an error-correcting code against a $000\rightarrow 1$
error.

###### Proof:

Suppose we have two distinct codewords
$\boldsymbol{x},\boldsymbol{y}\in\mathcal{C}_{3,1}(n;a,b,c,d)$ and
$\boldsymbol{z}\in\mathbb{F}_{2}^{n-2}$ can be derived from both
$\boldsymbol{x}$ and $\boldsymbol{y}$ by a $000\rightarrow 1$ error. Then
$\boldsymbol{x}$ and $\boldsymbol{y}$ should be of the form

$\begin{split}&\boldsymbol{x}=(x_{1},\ldots,x_{i-1},0,0,0,x_{i+3},\ldots,x_{j+1},1,x_{j+3},\ldots,x_{n}),\\\
&\boldsymbol{y}=(y_{1},\ldots,y_{i-1},1,y_{i+1},\ldots,y_{j-1},0,0,0,y_{j+3},\ldots,y_{n}).\end{split}$

where $x_{k}=y_{k}$ when $1\leq k\leq i-1$ and $j+3\leq k\leq n$,
$x_{k+2}=y_{k}$ when $i+1\leq k\leq j-1$.

We turn to the last constraint $r(\boldsymbol{x})$ in the definition of
$\mathcal{C}_{3,1}$, which is the number of runs. Let
$\Delta_{r}(\boldsymbol{x})=r(\boldsymbol{x})-r(\boldsymbol{z})\pmod{5}$ and
$\Delta_{r}(\boldsymbol{y})=r(\boldsymbol{y})-r(\boldsymbol{z})\pmod{5}$.
Since $\boldsymbol{x},\boldsymbol{y}$ are both codewords from
$\mathcal{C}_{3,1}$, we must have
$\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})$ and its value is of
the following possibilities:

  * •

If $i=1$, i.e., the $(3,1)$-burst starts at the very beginning, then depending
on whether $x_{4}=0$ or $x_{4}=1$, the error pattern is either
$0000\rightarrow 10$ or $0001\rightarrow 11$ and thus
$\Delta_{r}(\boldsymbol{x})$ is $4$ or $1$.

  * •

If $i=n-2$, i.e., the $(3,1)$-burst starts at the end, then depending on
whether $x_{n-3}=0$ or $x_{n-3}=1$, the error pattern is either
$0000\rightarrow 01$ or $1000\rightarrow 11$ and thus
$\Delta_{r}(\boldsymbol{x})$ is $4$ or $1$.

  * •

Otherwise, consider the four different cases for $x_{i-1}$ and $x_{i+3}$. The
error pattern is $00000\rightarrow 010,00001\rightarrow 011,10000\rightarrow
110,10001\rightarrow 111$ and the corresponding value of
$\Delta_{r}(\boldsymbol{x})$ is $3$, $0$, $0$, and $2$.

The rest of the proof falls into five cases. In each case we arrive at a
contradiction and thus prove that the assumption of the two distinct codewords
$\boldsymbol{x},\boldsymbol{y}\in\mathcal{C}_{3,1}(n;a,b,c,d)$ is not valid.

  * •

Case 1: $\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})=1$. Then
according to the analysis above, we have

$\boldsymbol{x}=(0,0,0,1,x_{5},\ldots,x_{n-2},1,1),~{}\boldsymbol{y}=(1,1,y_{3},\ldots,y_{n-4},1,0,0,0),$

where $x_{k+2}=y_{k}$ when $3\leq k\leq n-4$ and the $000\rightarrow 1$ error
starts at the first coordinate of $\boldsymbol{x}$ and the $(n-2)$th
coordinate of $\boldsymbol{y}$. Now we turn back to the constraint
$Rsyn(0\boldsymbol{x})$ for contradiction. The run sequence
$R(0\boldsymbol{x})$ is of the form

$(0,0,0,0,1)\sim(\text{run sequence corresponding to
}x_{5},\dots,x_{n-2})\sim(\lambda-1,\lambda-1)$

where $\lambda=r(0\boldsymbol{x})=r(\boldsymbol{x})$. The run sequence
$R(0\boldsymbol{y})$ is of the form

$(0,1,1)\sim(\text{run sequence corresponding to
}y_{3},\dots,y_{n-4})\sim(\lambda^{\prime}-2,\lambda^{\prime}-1,\lambda^{\prime}-1,\lambda^{\prime}-1)$

where $\lambda^{\prime}=r(0\boldsymbol{y})=r(\boldsymbol{y})+1$. Note that for
every $3\leq k\leq n-4$, the run index of $x_{k+2}$ in $R(0\boldsymbol{x})$
equals the run index of $y_{k}$ in $R(0\boldsymbol{y})$. Also note that
according to the definition of the code we must have
$r(\boldsymbol{x})=r(\boldsymbol{y})$. Thus we have

$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=(2\lambda-1)-(4\lambda^{\prime}-3)=-2r(\boldsymbol{x})-2\neq
0\pmod{4n},$

which is a contradiction to the constraint that $Rsyn(0\boldsymbol{x})\equiv
Rsyn(0\boldsymbol{y})\pmod{4n}$.

  * •

Case 2: $\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})=4$. Similarly
as the previous case, we have

$\boldsymbol{x}=(0,0,0,0,x_{5},\ldots,x_{n-2},0,1),~{}\boldsymbol{y}=(1,0,y_{3},\ldots,y_{n-4},0,0,0,0).$

where $x_{k+2}=y_{k}$ when $3\leq k\leq n-4$ and the $000\rightarrow 1$ error
starts at the first coordinate of $\boldsymbol{x}$ and the $(n-2)$th
coordinate of $\boldsymbol{y}$. The run sequence $R(0\boldsymbol{x})$ is of
the form

$(0,0,0,0,0)\sim(\text{run sequence corresponding to
}x_{5},\dots,x_{n-2})\sim(\lambda-2,\lambda-1)$

where $\lambda=r(0\boldsymbol{x})=r(\boldsymbol{x})$. The run sequence
$R(0\boldsymbol{y})$ is of the form

$(0,1,2)\sim(\text{run sequence corresponding to
}y_{3},\dots,y_{n-4})\sim(\lambda^{\prime}-1,\lambda^{\prime}-1,\lambda^{\prime}-1,\lambda^{\prime}-1)$

where $\lambda^{\prime}=r(0\boldsymbol{y})=r(\boldsymbol{y})+1$. Note that for
every $3\leq k\leq n-4$, the run index of $x_{k+2}$ in $R(0\boldsymbol{x})$ is
the run index of $y_{k}$ in $R(0\boldsymbol{y})$ minus two. Thus we have

$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=(2\lambda-3)-2(n-6)-(4\lambda^{\prime}-1)=-2n-2r(\boldsymbol{x})+6\pmod{4n}.$

From the representation of $\boldsymbol{x}$, we have $2\leq
r(\boldsymbol{x})\leq n-3$. Thus $-4n+12\leq-2n-2r(\boldsymbol{x})+6\leq-2n+2$
and thus $Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})$ is nonzero modulo $4n$,
a contradiction.

  * •

Case 3: $\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})=3$ and the
error pattern must be $00000\rightarrow 010$. We have

$\begin{split}&\boldsymbol{x}=(\ldots,\overset{a}{0},\overset{a}{0},\overset{a}{0},\overset{a}{0},\overset{a}{0},x_{i+4},\ldots,x_{j},\overset{b}{0},\overset{b+1}{1},\overset{b+2}{0},\ldots),\\\
&\boldsymbol{y}=(\ldots,\underset{a}{0},\underset{a+1}{1},\underset{a+2}{0},y_{i+2},\ldots,y_{j-2},\underset{b+2}{0},\underset{b+2}{0},\underset{b+2}{0},\underset{b+2}{0},\underset{b+2}{0},\ldots),\end{split}$

where the $a$’s and $b$’s are the run index of corresponding entries.
Moreover, for every $i+2\leq k\leq j-2$, the run index of $x_{k+2}$ in
$R(0\boldsymbol{x})$ is the run index of $y_{k}$ in $R(0\boldsymbol{y})$ minus
two. In this case,

$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=(5a+3b+3)-2(j-i-3)-(3a+5b+13)=2(a-b)-2(j-i)-4\pmod{4n}.$

From the representation of $\boldsymbol{x}$ we have $a\leq b\leq a+j-i-2$.
Hence, $-4(j-i)\leq Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\leq-2(j-i)-4$.
Moreover, $2\leq j-i\leq n-5$, thus we have $-4(n-5)\leq
Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\leq-8$, which is again a
contradiction to the constraint that
$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\equiv 0\pmod{4n}$.

  * •

Case 4: $\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})=2$ and the
error pattern must be $10001\rightarrow 111$. We have

$\begin{split}&\boldsymbol{x}=(\ldots,\overset{a}{1},\overset{a+1}{0},\overset{a+1}{0},\overset{a+1}{0},\overset{a+2}{1},x_{i+4},\ldots,x_{j},\overset{b}{1},\overset{b}{1},\overset{b}{1},\ldots),\\\
&\boldsymbol{y}=(\ldots,\underset{a}{1},\underset{a}{1},\underset{a}{1},y_{i+2},\ldots,y_{j-2},\underset{b-2}{1},\underset{b-1}{0},\underset{b-1}{0},\underset{b-1}{0},\underset{b}{1},\ldots).\end{split}$

In this case, for every $i+2\leq k\leq j-2$, the run index of $x_{k+2}$ in
$R(0\boldsymbol{x})$ is the run index of $y_{k}$ in $R(0\boldsymbol{y})$ plus
two. Then we have

$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=(5a+3b+5)+2(j-i-3)-(3a+5b-5)=2(a-b)+2(j-i)+4\pmod{4n}.$

From the representation of $\boldsymbol{x}$ we have $a+2\leq b\leq a+j-i$.
Hence, $4\leq Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\leq 2(j-i)$.
Moreover, $2\leq j-i\leq n-5$, thus we have $4\leq
Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\leq 2(n-5)$, which is again a
contradiction to the constraint that
$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\equiv 0\pmod{4n}$.

  * •

Case 5: $\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})=0$. This case
is further divided depending on whether each error is $00001\rightarrow 011$
or $10000\rightarrow 110$. We only present one subcase as an example and the
others can be proved analogously. Consider the subcase when both the error
patterns in $\boldsymbol{x}$ and $\boldsymbol{y}$ are $00001\rightarrow 011$.
We have

$\begin{split}&\boldsymbol{x}=(\ldots,\overset{a}{0},\overset{a}{0},\overset{a}{0},\overset{a}{0},\overset{a+1}{1},x_{i+4},\ldots,x_{j},\overset{b}{0},\overset{b+1}{1},\overset{b+1}{1},\ldots),\\\
&\boldsymbol{y}=(\ldots,\underset{a}{0},\underset{a+1}{1},\underset{a+1}{1},y_{i+2},\ldots,y_{j-2},\underset{b}{0},\underset{b}{0},\underset{b}{0},\underset{b}{0},\underset{b+1}{1},\ldots),\end{split}$

In this subcase, for every $i+2\leq k\leq j-2$, the run index of $x_{k+2}$ in
$R(0\boldsymbol{x})$ equals the run index of $y_{k}$ in $R(0\boldsymbol{y})$.
Then we have

$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=(5a+3b+3)-(3a+5b+3)=2(a-b)\pmod{4n}.$

In this subcase, $a+2\leq b\leq a+j-i-1$. Therefore, $-2(n-6)\leq-2(j-i-1)\leq
Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\leq-4$. Moreover, $2\leq j-i\leq
n-5$, $-2n+12\leq Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\leq-4$, which is
again a contradiction to the constraint that
$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\equiv 0\pmod{4n}$.

To sum up, we have assumed that we have two distinct codewords
$\boldsymbol{x},\boldsymbol{y}\in\mathcal{C}_{3,1}(n;a,b,c,d)$ and
$\boldsymbol{z}\in\mathbb{F}_{2}^{n-2}$ can be derived from both
$\boldsymbol{x}$ and $\boldsymbol{y}$ by a $000\rightarrow 1$ error. However,
in all cases we can deduce that $Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})$
is nonzero modulo $4n$, which contradicts to the definition of the code. Thus,
we have proven that $\mathcal{C}_{3,1}$ is an error-correcting code against a
$000\rightarrow 1$ error. ∎

###### Lemma 7

$\mathcal{C}_{3,1}$ is an error-correcting code against $010\rightarrow 1$
errors.

###### Proof:

The proof follows the same way as the previous lemma. Suppose that we have two
distinct codewords
$\boldsymbol{x},\boldsymbol{y}\in\mathcal{C}_{3,1}(n;a,b,c,d)$ and
$\boldsymbol{z}\in\mathbb{F}_{2}^{n-2}$ can be derived from both
$\boldsymbol{x}$ and $\boldsymbol{y}$ by a $010\rightarrow 1$ error. Then
$\boldsymbol{x}$ and $\boldsymbol{y}$ should be of the form

$\begin{split}&\boldsymbol{x}=(x_{1},\ldots,x_{i-1},0,1,0,x_{i+3},\ldots,x_{j+1},1,x_{j+3},\ldots,x_{n}),\\\
&\boldsymbol{y}=(y_{1},\ldots,y_{i-1},1,y_{i+1},\ldots,y_{j-1},0,1,0,y_{j+3},\ldots,y_{n}).\end{split}$

where $x_{k}=y_{k}$ when $1\leq k\leq i-1$ and $j+3\leq k\leq n$,
$x_{k+2}=y_{k}$ when $i+1\leq k\leq j-1$.

First we need to observe the two values
$\Delta_{r}(\boldsymbol{x}),\Delta_{r}(\boldsymbol{y})$.

  * •

If $i=1$, i.e., the $(3,1)$-burst starts at the very beginning, then depending
on whether $x_{4}=0$ or $x_{4}=1$, the error pattern is either
$0100\rightarrow 10$ or $0101\rightarrow 11$ and thus
$\Delta_{r}(\boldsymbol{x})$ is $1$ or $3$.

  * •

If $i=n-2$, i.e., the $(3,1)$-burst starts at the end, then depending on
whether $x_{n-3}=0$ or $x_{n-3}=1$, the error pattern is either
$0010\rightarrow 01$ or $1010\rightarrow 11$ and thus
$\Delta_{r}(\boldsymbol{x})$ is $1$ or $3$.

  * •

Otherwise, consider the four different cases for $x_{i-1}$ and $x_{i+3}$. The
error pattern is $00100\rightarrow 010,00101\rightarrow 011,10100\rightarrow
110,10101\rightarrow 111$ and the corresponding value of
$\Delta_{r}(\boldsymbol{x})$ is $0$, $2$, $2$, and $4$.

Based on the observations of
$\Delta_{r}(\boldsymbol{x}),\Delta_{r}(\boldsymbol{y})$ we then break into
several cases and in each case we will derive a contradiction by analyzing
$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})$. Since the whole framework is
similar as the previous lemma, we omit some details and only present the
calculations for $Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})$.

  * •

Case 1: $\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})=1$.

$\boldsymbol{x}=(0,1,0,0,x_{5},\ldots,x_{n-2},0,1),~{}\boldsymbol{y}=(1,0,y_{3},\ldots,y_{n-4},0,0,1,0).$

Then $Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=-2r(\boldsymbol{x})+4\neq
0$, since $r(\boldsymbol{x})\geq 4$.

  * •

Case 2: $\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})=3$.

$\boldsymbol{x}=(0,1,0,1,x_{5},\ldots,x_{n-2},1,1),~{}\boldsymbol{y}=(1,1,y_{3},\ldots,y_{n-4},1,0,1,0).$

This case is a little bit special and deserves to be analyzed in detail. We
can compute that
$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=2n-2r(\boldsymbol{x})-4$. Suppose
it is zero modulo $4n$, then $n=r(\boldsymbol{x})+2$. Since the first symbol
of $\boldsymbol{x}$ is $0$ and the last symbol of $\boldsymbol{x}$ is $1$,
then the number of runs $r(\boldsymbol{x})$ must be even and thereby $n$ must
be even. As $\sum_{k=1}^{n/2}x_{2k-1}=1+\sum_{k=3}^{n/2-1}x_{2k-1}$,
$\sum_{k=1}^{n/2}y_{2k-1}=3+\sum_{k=2}^{n/2-2}y_{2k-1}$ and
$\sum_{k=3}^{n/2-1}x_{2k-1}=\sum_{k=2}^{n/2-2}y_{2k-1}$, we can get
$\sum_{k=1}^{n/2}x_{2k-1}-\sum_{k=1}^{n/2}y_{2k-1}\equiv 2\pmod{4}$ which is a
contradiction to $\sum_{k=1}^{n/2}x_{2k-1}-\sum_{k=1}^{n/2}y_{2k-1}\equiv
0\pmod{4}$. Therefore,
$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=2n-2r(\boldsymbol{x})-4\neq
0\pmod{4n}$.

  * •

Case 3: $\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})=0$ and the
error pattern must be $00100\rightarrow 010$. Hence,

$\begin{split}&\boldsymbol{x}=(\ldots,\overset{a}{0},\overset{a}{0},\overset{a+1}{1},\overset{a+2}{0},\overset{a+2}{0},x_{i+4},\ldots,x_{j},\overset{b}{0},\overset{b+1}{1},\overset{b+2}{0},\ldots),\\\
&\boldsymbol{y}=(\ldots,\underset{a}{0},\underset{a+1}{1},\underset{a+2}{0},y_{i+2},\ldots,y_{j-2},\underset{b}{0},\underset{b}{0},\underset{b+1}{1},\underset{b+2}{0},\underset{b+2}{0},\ldots),\end{split}$

Then $Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=2(a-b)\neq 0\pmod{4n}.$

  * •

Case 4: $\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})=4$ and the
error pattern must be $10101\rightarrow 111$. Hence,

$\begin{split}&\boldsymbol{x}=(\ldots,\overset{a}{1},\overset{a+1}{0},\overset{a+2}{1},\overset{a+3}{0},\overset{a+4}{1},x_{i+4},\ldots,x_{j},\overset{b}{1},\overset{b}{1},\overset{b}{1},\ldots),\\\
&\boldsymbol{y}=(\ldots,\underset{a}{1},\underset{a}{1},\underset{a}{1},y_{i+2},\ldots,y_{j-2},\underset{b-4}{1},\underset{b-3}{0},\underset{b-2}{1},\underset{b-1}{0},\underset{b}{1},\ldots),\end{split}$

Then $Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=2(a-b)+4(j-i)+8.$ Since
$a+4\leq b\leq a+j-i+2$, we have $2(j-i)+4\leq
Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\leq 4(j-i)$, so
$Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\neq 0\pmod{4n}$.

  * •

Case 5: $\Delta_{r}(\boldsymbol{x})=\Delta_{r}(\boldsymbol{y})=2$. his case is
further divided depending on whether each error is $00101\rightarrow 011$ or
$10100\rightarrow 110$. We only present one subcase as an example and the
others can be proved analogously. Consider the subcase when the error pattern
in $\boldsymbol{x}$ is $00101\rightarrow 011$ and the error pattern in
$\boldsymbol{y}$ is $10100\rightarrow 110$. We have

$\begin{split}&\boldsymbol{x}=(\ldots,\overset{a}{0},\overset{a}{0},\overset{a+1}{1},\overset{a+2}{0},\overset{a+3}{1},x_{i+4},\ldots,x_{j},\overset{b}{1},\overset{b}{1},\overset{b+1}{0},\ldots),\\\
&\boldsymbol{y}=(\ldots,\underset{a}{0},\underset{a+1}{1},\underset{a+1}{1},y_{i+2},\ldots,y_{j-2},\underset{b-2}{1},\underset{b-1}{0},\underset{b}{1},\underset{b+1}{0},\underset{b+1}{0},\ldots),\end{split}$

Then $Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})=2(a-b)+2(j-i)$. Suppose it
is zero, then $r_{j}-r_{i}=j-i$. Since the symbols with run index $a$ are $0$s
and symbols with run index $b$ are $1$s, $b-a$ must be odd and thus $j-i$ is
odd. The number of symbols from $x_{i+4}$ to $x_{j}$ is $j-i-3$ and thus is
even. WLOG let $i$ be odd, then similarly as Case 2 we can analyze the sum of
the odd coordinates and derive

$\sum_{k=1}^{n/2}x_{2k-1}-\sum_{k=1}^{n/2}y_{2k-1}\equiv 1-3\equiv 2\pmod{4},$

which is a contradiction to $\sum_{k=1}^{n/2}x_{k}-\sum_{k=1}^{n/2}y_{k}\equiv
0\pmod{4}$. As a consequence, $Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})\neq
0\pmod{4n}$.

To sum up, we have assumed that we have two distinct codewords
$\boldsymbol{x},\boldsymbol{y}\in\mathcal{C}_{3,1}(n;a,b,c,d)$ and
$\boldsymbol{z}\in\mathbb{F}_{2}^{n-2}$ can be derived from both
$\boldsymbol{x}$ and $\boldsymbol{y}$ by a $010\rightarrow 1$ error. However,
in all cases we can deduce that $Rsyn(0\boldsymbol{x})-Rsyn(0\boldsymbol{y})$
is nonzero modulo $4n$, which contradicts to the definition of the code. Thus,
we have proven that $\mathcal{C}_{3,1}$ is an error-correcting code against a
$010\rightarrow 1$ error. ∎

We close this section by summarizing our construction of the code
$\mathcal{C}_{3,1}(n;a,b,c,d)$:

  * •

The decoding process starts with the observations of
$\Delta_{odd}(\boldsymbol{u})$ and $\Delta_{even}(\boldsymbol{u})$.

  * •

If we determine that the error can be seen as a $2$-burst-deletion, then
according to Levenshtein[16] our code is capable of correcting a $2$-burst-
deletion error.

  * •

Otherwise, we can determine the error pattern, which is one out of
$\\{000\rightarrow 1,010\rightarrow 1,111\rightarrow 0,101\rightarrow 0\\}$.

  * •

Whatever the error pattern is, our code can correct this type of error (two
models are proved via Lemmas 6 and 7 and the other two follow a similar idea).

Finally, by the pigeonhole principle, we may find suitable parameters
$a\in\mathbb{Z}_{4n}$, $b,c\in\mathbb{Z}_{4}$, and $d\in\mathbb{Z}_{5}$ and
find a code with size at least $\frac{2^{n}}{4n\cdot 80}$ and thus its
redundancy is at most $\log(320n)<\log n+9$. Note that we have proved that the
lower bound of the redundancy of $(3,1)$-burst correcting codes is $\log n+2$,
so our construction is optimal up to a constant. In sum, in this section we
have proved the following.

###### Theorem 7

There exist choices of $a\in\mathbb{Z}_{4n}$, $b,c\in\mathbb{Z}_{4}$, and
$d\in\mathbb{Z}_{5}$, such that the code $\mathcal{C}_{3,1}(n;a,b,c,d)$ is a
$(3,1)$-burst correcting code with redundancy at most $\log n+9$.

##  VII Conclusion and Future Work

In this paper we study $(t,s)$-burst correcting codes. First we prove the
equivalence between $(t,s)$-burst correcting codes and $(s,t)$-burst
correcting codes. Then we present a sphere-packing type upper bound of
$(t,s)$-burst correcting codes, leading to a lower bound of its optimal
redundancy. We present a construction of $(t,s)$-burst correcting codes for
$t\geq 2s$, with redundancy $\log n+(t-s-1)\log\log n+O(1)$. Comparing our
general construction and the lower bound of redundancy, there is only a
$\log\log n$ gap. We manage to close this gap for $t=3,s=1$ by giving a
construction of $(3,1)$-burst correcting codes with redundancy at most $\log
n+9$.

Here is a brief remark on our general construction for $t\geq 2s$. If we want
to generalize the construction for the range $s\leq t<2s$, then by viewing the
codeword as an array of size $(t-s)\times\frac{n}{t-s}$, each row will suffer
from more than a $(2,1)$-burst. To be more specific, if
$\frac{p-2}{p-1}<\frac{s}{t}\leq\frac{p-1}{p}$, then in the array
representation a row may suffer from a $(p,p-1)$-burst. Therefore, good
constructions for codes against a $(p,p-1)$-burst for $p\geq 3$ will be useful
tools in analyzing the general problem of $(t,s)$-burst correcting codes.

Another interesting question is to construct a code capable of correcting any
$(t,s)$-burst for $t\leq T$ and $s\leq S$, with $T$ and $S$ given. Despite a
trivial solution to intersect all $(t,s)$-burst correcting codes for $t\leq T$
and $s\leq S$, a nontrivial solution is considered for future research.

## References

  * [1] J. Brakensiek, V. Guruswami, and S. Zbarsky, “Efficient low-redundancy codes for correcting multiple deletions,” IEEE Transactions on Information Theory, vol. 64, no. 5, pp. 3403-3410, 2018.
  * [2] R. Bitar, S. K. Hanna, N. Polyanskii, and I. Vorobyev, “Optimal codes correcting localized deletions,” arXiv:2105.02298, 2021\.
  * [3] K. Cai, Y. M. Chee, R. Gabrys, H. M. Kiah, and T. T. Nguyen, “Correcting a single indel/edit for DNA-based cata storage: linear-time encoders and order-optimality,” IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 3438-3451, 2021.
  * [4] L. Cheng, T. G. Swart, H. C. Ferreira, and K. A. S. Abdel-Ghaffar, “Codes for correcting three or more adjacent deletions or insertions,” 2014 IEEE International Symposium on Information Theory(ISIT), pp. 1246-1250, 2014.
  * [5] B. K. Dass, “On a burst-error correcting code,” Journal of Information and Optimization Sciences, vol. 1, no. 3, pp. 291-295, 1980.
  * [6] L. Dolecek and V. Anantharam, “Using ReedMuller RM $(1,m)$ codes over channels with synchronization and substitution errors,” IEEE Transactions on Information Theory, vol. 53, no. 4, pp. 1430-1443, 2007.
  * [7] Y. Dong, F. Sun, Z. Ping, Q. Ouyang, and L. Qian, “DNA storage: research landscape and future prospects,” National Science Review, Volume 7, Issue 6, pp. 1092-1107, 2020.
  * [8] R. Gabrys, V. Guruswami, J. Ribeiro, and K. Wu, “Beyond single-deletion correcting codes: substitutions and transpositions,” arXiv:2112.09971, 2021\.
  * [9] R. Gabrys, E. Yaakobi, and O. Milenkovic, “Codes in the damerau distance for deletion and adjacent transcoordinate correction,” IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2550-2570, 2018.
  * [10] R. Gabrys and F. Sala, “Codes correcting two deletions,” IEEE Transactions on Information Theory, vol. 65, no. 2, pp. 965-974, 2019.
  * [11] V. Guruswami and J. Håstad, “Explicit two-deletion codes with redundancy matching the existential bound,” IEEE Transactions on Information Theory, vol. 67, no. 10, pp. 6384-6394, 2021.
  * [12] S. K. Hanna and S. El Rouayheb, “Guess & check codes for deletions, insertions, and synchronization,” IEEE Transactions on Information Theory, vol. 65, no. 1, pp. 3-15, 2019.
  * [13] K. A. S. Immink, Coding Techniques for Digital Recorders. Englewood Cliffs, NJ, USA: Prentice-Hall, 1991.
  * [14] A. Lenz and N. Polyanskii, “Optimal codes correcting a burst of deletions of variable length,” 2020 IEEE International Symposium on Information Theory (ISIT), pp. 757-762, 2020.
  * [15] 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.
  * [16] V. I. Levenshtein, “Asymptotically optimum binary codes with correction for losses of one or two adjacent bits,” Syst. Theory Res., vol. 19, pp. 298-304, 1970.
  * [17] C. Schoeny, A. Wachter-Zeh, R. Gabrys, and E. Yaakobi, “Codes correcting a burst of deletions or insertions,” IEEE Transactions on Information Theory, vol. 63, no. 4, pp. 1971-1985, 2017.
  * [18] F. Sala, C. Schoeny, N. Bitouz, and L. Dolecek, “Synchronizing files from a large number of insertions and deletions,” IEEE Transactions on Communications, vol. 64, no. 6, pp. 2258-2273, 2016.
  * [19] I. Smagloy, L. Welter, A. Wachter-Zeh, and E. Yaakobi, ”Single-deletion single-substitution correcting codes,” 2020 IEEE International Symposium on Information Theory (ISIT), pp. 775-780, 2020.
  * [20] J. Sima and J. Bruck, “On optimal k-deletion correcting codes,” IEEE Transactions on Information Theory, vol. 67, no. 6, pp. 3360-3375, 2021.
  * [21] J. Sima, R. Gabrys, and J. Bruck, “Optimal systematic t-deletion correcting codes,” 2020 IEEE International Symposium on Information Theory (ISIT), pp. 769-774, 2020.
  * [22] W. Song, K. Cai, and T. T. Nguyen, “List-decodable codes for single-deletion single-substitution with list-size two,” arXiv:2201.02013, 2022.
  * [23] W. Song, N. Polyanskii, K. Cai, and X. He, “On multiple-deletion multiple-substitution correcting codes,” 2021 IEEE International Symposium on Information Theory (ISIT), pp. 2655-2660, 2021.
  * [24] K. Tian, A. Fazeli, and A. Vardy, “Polar coding for deletion channels: theory and implementation,” 2018 IEEE International Symposium on Information Theory (ISIT), pp. 1869-1873, 2018.
  * [25] R. R. Varshamov and G. M. Tenengol’ts, “A code that corrects single unsymmetric errors,” Avtomatika Telemekhanika, vol. 26, no. 2, pp. 288-292, 1965.
  * [26] S. M. H. T. Yazdi, H. M. Kiah, E. Garcia-Ruiz, J. Ma, H. Zhao, and O. Milenkovic, “DNA-Based Storage: Trends and Methods,” IEEE Transactions on Molecular, Biological and Multi-Scale Communications, vol. 1, no. 3, pp. 230-248, 2015.