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 <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula>-deletion-<inline-formula> <tex-math notation="LaTeX">$s$ </tex-math></inline-formula>-insertion-burst (<inline-formula> <tex-math notation="LaTeX">$(t,s)$ </tex-math></inline-formula>-burst for short) which is a generalization of the (2, 1)-burst error proposed by Schoeny et al. Such an error deletes <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula> consecutive symbols and inserts an arbitrary sequence of length <inline-formula> <tex-math notation="LaTeX">$s$ </tex-math></inline-formula> at the same coordinate. We provide a sphere-packing upper bound on the size of binary codes that can correct a <inline-formula> <tex-math notation="LaTeX">$(t,s)$ </tex-math></inline-formula>-burst error, showing that the redundancy of such codes is at least <inline-formula> <tex-math notation="LaTeX">$\log (n-t+2)+t-1$ </tex-math></inline-formula>. For <inline-formula> <tex-math notation="LaTeX">$t\geq 2s$ </tex-math></inline-formula>, an explicit construction of binary <inline-formula> <tex-math notation="LaTeX">$(t,s)$ </tex-math></inline-formula>-burst correcting codes with redundancy <inline-formula> <tex-math notation="LaTeX">$\log n+(t-s-1)\log \log n+O_{t}(1)$ </tex-math></inline-formula> is given, where <inline-formula> <tex-math notation="LaTeX">$O_{t}(\cdot)$ </tex-math></inline-formula> suppresses factors that depend only on <inline-formula> <tex-math notation="LaTeX">$t$ </tex-math></inline-formula>. Additionally, we construct a binary (3, 1)-burst correcting code with redundancy at most <inline-formula> <tex-math notation="LaTeX">$\log n+9$ </tex-math></inline-formula>, which is optimal up to an additive constant.