On Single-Deletion-Correcting Codes

Abstract

This paper gives a brief survey of binary single-deletion-correcting codes. The Varshamov-Tenengolts codes appear to be optimal, but many interesting unsolved problems remain. The connections with shift-register sequences also remain somewhat mysterious.

23 pages, 1 figure. Dedicated to Dijen Ray-Chaudhuri on the occasion of his 65th birthday

Cited by in corpus (13)

• Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound
• Longest Common Subsequences in Sets of Permutations
• Explicit Formulas for the Weight Enumerators of Some Classes of Deletion Correcting Codes
• Private and Resource-Bounded Locally Decodable Codes for Insertions and Deletions
• An Efficiently Generated Family of Binary de Bruijn Sequences
• Tutorial on algebraic deletion correction codes
• Explicit Good Subspace-metric Codes and Subset-metric Codes
• Two Approaches to the Construction of Deletion Correcting Codes: Weight Partitioning and Optimal Colorings
• Perfect Multi Deletion Codes Achieve the Asymptotic Optimality of Code Size
• Error-correcting Codes for Noisy Duplication Channels
• Covering Codes using Insertions or Deletions
• The packing number of the double vertex graph of the path graph
• A combinatorial problem about binary necklaces and attractors of Boolean automata networks