Back to Search
Start Over
Codes Correcting a Burst of Deletions or Insertions.
- Source :
- IEEE Transactions on Information Theory; Apr2017, Vol. 63 Issue 4, p1971-1985, 15p
- Publication Year :
- 2017
-
Abstract
- This paper studies codes that correct a burst of deletions or insertions. Namely, a code will be called a $b$ -burst-deletion/insertion-correcting code if it can correct a burst of deletions/insertions 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 first show that the models of insertions and deletions are equivalent and thus it is enough to study codes correcting a burst of deletions. We then 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$ . [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 63
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 121995097
- Full Text :
- https://doi.org/10.1109/TIT.2017.2661747