2013/02/26 by Daniel Cullina, Cullina, Daniel, Negar Kiyavash +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced biosensing and bioanalysis techniques #Algorithms and Data Compression #DNA and Biological Computing #DNA and Nucleic Acid Chemistry #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.DM #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1302.6562
openalex publication_date 2013/02/26 · arxiv created 2013/07/29 · arxiv updated 2013/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.