t-Deletion-1-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-$1$-insertion-burst ($(t,1)$-burst for short) proposed by Schoeny {\it et. al}, which deletes $t$ consecutive symbols and inserts an arbitrary symbol at the same coordinate. We provide a sphere-packing upper bound on the size of binary codes that can correct $(t,1)$-burst errors, showing that the redundancy of such codes is at least $\log n+t-1$. An explicit construction of a binary $(t,1)$-burst correcting code with redundancy $\log n+(t-2)\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.