Technical Program

Paper Detail

Paper IDM.8.1
Paper Title Syndrome Compression for Optimal Redundancy 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 We introduce a general technique that we call syndrome compression, for designing low-redundancy error correcting codes. The technique allows us to boost the redundancy efficiency of hash/labeling-based codes by further compressing the labeling. We apply syndrome compression to different types of adversarial deletion channels and present code constructions that correct up to a constant number of errors. Our code constructions achieve the redundancy of twice the Gilbert-Varshamov bound, which improve upon the state of art for these channels. The encoding/decoding complexity of our constructions is of order equal to the size of the corresponding deletion balls, namely, it is polynomial in the code length.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!