2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | M.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
