An improvement to levenshtein's upper bound on the cardinality of deletion correcting codes

Daniel Cullina, Negar Kiyavash

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


We consider deletion correcting codes over a q -ary alphabet. It is well known that any code capable of correcting s deletions can also correct any combination of s total insertions and deletions. To obtain asymptotic upper bounds on code size, we apply a packing argument to channels that perform different mixtures of insertions and deletions. Even though the set of codes is identical for all of these channels, the bounds that we obtain vary. Prior to this paper, only the bounds corresponding to the all-insertion case and the all-deletion case were known. We recover these as special cases. The bound from the all-deletion case, due to Levenshtein, has been the best known for more than 45 years. Our generalized bound is better than Levenshtein's bound whenever the number of deletions to be corrected is larger than the alphabet size.

Original languageEnglish (US)
Article number6799187
Pages (from-to)3862-3870
Number of pages9
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - Jul 2014

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this