A Caltech Library Service

Optimal Systematic t-Deletion Correcting Codes

Sima, Jin and Gabrys, Ryan and Bruck, Jehoshua (2020) Optimal Systematic t-Deletion Correcting Codes. In: 2020 IEEE International Symposium on Information Theory (ISIT). IEEE , pp. 769-774. ISBN 9781728164328.

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

Use this Persistent URL to link to this item:


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² 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.

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-144630883
Persistent URL:
Official Citation:J. Sima, R. Gabrys and J. Bruck, "Optimal Systematic t-Deletion Correcting Codes," 2020 IEEE International Symposium on Information Theory (ISIT), Los Angeles, CA, USA, 2020, pp. 769-774, doi: 10.1109/ISIT44484.2020.9173986
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:105181
Deposited By: Tony Diaz
Deposited On:08 Sep 2020 18:50
Last Modified:16 Nov 2021 18:40

Repository Staff Only: item control page