Technical Program

Paper Detail

Paper IDM.8.5
Paper Title Single-Deletion Single-Substitution Correcting Codes
Authors Ilya Smagloy, Technion, Israel; Lorenz Welter, Antonia Wachter-Zeh, Technical University of Munich, Germany; Eitan Yaakobi, Technion, Israel
Session M.8: Insertion Deletion Substitution Codes II
Presentation Lecture
Track Coding for Storage and Memories
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract Correcting insertions/deletions as well as substitution errors simultaneously plays an important role in DNA-based storage systems as well as in classical communications. This paper deals with the fundamental task of constructing codes that can correct a single insertion or deletion along with a single substitution. A non-asymptotic upper bound on the size of single-deletion single-substitution correcting codes is derived, showing that the redundancy of such a code of length n has to be at least 2 log n. The bound is presented both for binary and non-binary codes while an extension to single deletion and multiple substitutions is presented for binary codes. An explicit construction of single-deletion single-substitution correcting codes with at most 6 log n + 8 redundancy bits is derived. Note that the best known construction for this problem has to use 3-deletion correcting codes whose best known redundancy is roughly 24 log n.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!