A Caltech Library Service

Syndrome Compression for Optimal Redundancy Codes

Sima, Jin and Gabrys, Ryan and Bruck, Jehoshua (2020) Syndrome Compression for Optimal Redundancy Codes. In: 2020 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 751-756. ISBN 9781728164328.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Sima, Jin0000-0003-4588-9790
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2020 IEEE. This work was supported in part by NSF grants CCF-1816965 and CCF-1717884.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20200831-142617575
Persistent URL:
Official Citation:J. Sima, R. Gabrys and J. Bruck, "Syndrome Compression for Optimal Redundancy Codes," 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA, 2020, pp. 751-756, doi: 10.1109/ISIT44484.2020.9174009
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105179
Deposited By: Tony Diaz
Deposited On:08 Sep 2020 19:08
Last Modified:16 Nov 2021 18:40

Repository Staff Only: item control page