Technical Program

Paper Detail

Paper IDM.8.4
Paper Title Optimal Systematic t-Deletion Correcting Codes
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.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 Systematic deletion correcting codes play an important role in applications of document exchange. Yet despite a series of recent advances made in deletion correcting codes, most of them are non-systematic. To the best of the authors' knowledge, the only known deterministic systematic~$t$-deletion correcting code constructions with rate approaching~$1$ achieve~$O(t\log^2 n)$ bits of redundancy for constant~$t$, where~$n$ is the code length. In this paper, we propose a systematic~$t$-deletion correcting code construction that achieves~$4t\log n+o(\log n)$ bits of redundancy, which is asymptotically within a factor of~$4$ from being optimal. Our encoding and decoding algorithms have complexity~$O(n^{2t+1})$, which is polynomial for constant~$t$.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!