Papers › Codes Correcting a Burst of Deletions or Insertions
Codes Correcting a Burst of Deletions or Insertions
Clayton Schoeny, Antonia Wachter-Zeh, Ryan Gabrys, Eitan Yaakobi
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections