Codes Correcting a Burst of Deletions or Insertions

DOI10.1109/TIT.2017.2661747MaRDI QIDQ5280879zbMATH OpenFDO

Authors Clayton Schoeny, Antonia Wachter-Zeh, Ryan Gabrys, Eitan Yaakobi

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.06820

Mathematics Subject Classification ID

Burst-correcting codes (94B20)

Abstract: 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.

Cited in

(11)

• Duplication-correcting codes
• The Modular Subset-Sum Problem and the size of deletion correcting codes
• Deletion correcting codes meet the Littlewood-Offord problem
• scientific article; zbMATH DE number 5302391 (Why is no real title available?)
• scientific article; zbMATH DE number 605666 (Why is no real title available?)
• Balanced reconstruction codes for single edits
• Explicit construction of codes correcting a single reverse-complement duplication of arbitrary length
• Optimal insdel codes from almost MDS codes
• On the coding capacity of reverse-complement and palindromic duplication-correcting codes
• A new path to code-based signatures via identification schemes with restricted errors
• On the decoding error weight of one or two deletion channels

This page was built for publication: Codes Correcting a Burst of Deletions or Insertions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5280879)