t-Deletion-s-Insertion-Burst Correcting Codes

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+2)+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_{t}(1)$
is given, where
$O_{t}(\cdot)$
suppresses factors that depend only on
$t$
. Additionally, we construct a binary (3, 1)-burst correcting code with redundancy at most
$\log n+9$
, which is optimal up to an additive constant.