Technical Program

Paper Detail

Paper IDM.7.4
Paper Title Optimal Codes for the q-ary Deletion Channel
Authors Jin Sima, California Institute of Technology, United States; Ryan Gabrys, University of California San Diego, United States; Jehoshua Bruck, California Institute of Technology, United States
Session M.7: Insertion Deletion Substitution Codes I
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 The problem of constructing optimal multiple deletion correcting codes has long been open until recent breakthrough for binary cases. Yet comparatively less progress was made in the non-binary counterpart, with the only rate one non-binary deletion codes being Tenengolts' construction that corrects single deletion. In this paper, we present several $q$-ary $t$-deletion correcting codes of length~$n$ that achieve optimal redundancy up to a factor of a constant, based on the value of the alphabet size~$q$. For small~$q$, our constructions have~$O(n^{2t}q^t)$ encoding/decoding complexity. For large~$q$, we take a different approach and the construction has polynomial time complexity.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!