2016/02/22 by Schoeny, Clayton, Wachter-Zeh, Antonia, Gabrys, Ryan +1 · 7 citations
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1602.06820
This paper studies codes that correct bursts of deletions. Namely, a code will be called a b-burst-deletion-correcting code if it can correct a deletion of any b consecutive bits. While the lower bound on the redundancy of such codes was shown by Levenshtein to be asymptotically log(n)+b-1, the redundancy of the best code construction by Cheng et al. is b(log (n/b+1)). In this paper we close on this gap and provide codes with redundancy at most log(n) + (b-1)log(log(n)) +b -log(b). We also derive a non-asymptotic upper bound on the size of b-burst-deletion-correcting codes and extend the burst deletion model to two more cases: 1) A deletion burst of at most b consecutive bits and 2) A deletion burst of size at most b (not necessarily consecutive). We extend our code construction for the first case and study the second case for b=3,4. The equivalent models for insertions are also studied and are shown to be equivalent to correcting the corresponding burst of deletions.