t-Deletion-s-Insertion-Burst Correcting Codes

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 {\it 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\ge 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.

Part of this work (the (t,1)-burst model) was presented at ISIT2022. This full version has been submitted to IEEE-IT in August 2022