An Improvement to Levenshtein's Upper Bound on the Cardinality of Deletion Correcting Codes
From MaRDI portal
Publication:2986258
DOI10.1109/TIT.2014.2317698zbMATH Open1360.94453arXiv1302.6562MaRDI QIDQ2986258FDOQ2986258
Daniel Cullina, Negar Kiyavash
Publication date: 16 May 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: 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 work, 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 forty five years. Our generalized bound is better than Levenshtein's bound whenever the number of deletions to be corrected is larger than the alphabet size.
Full work available at URL: https://arxiv.org/abs/1302.6562
Cited In (1)
This page was built for publication: An Improvement to Levenshtein's Upper Bound on the Cardinality of Deletion Correcting Codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986258)
