t-Deletion-s-Insertion-Burst Correcting Codes

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 = 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(.) 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.

Automated summary

This study focuses on deletion and insertion errors in DNA-based storage and communication systems. An upper bound on the size of binary codes that can correct a (t, s)-burst error is provided, demonstrating the minimum redundancy required for such codes. An explicit construction for binary (t, s)-burst correcting codes for the case where t = 2s is also presented.