A Caltech Library Service

Two Deletion Correcting Codes from Indicator Vectors

Sima, Jin and Raviv, Netanel and Bruck, Jehoshua (2018) Two Deletion Correcting Codes from Indicator Vectors. In: 2018 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 421-425. ISBN 978-1-5386-4780-6.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Construction of capacity achieving deletion correcting codes has been a baffling challenge for decades. A recent breakthrough by Brakensiek et al., alongside novel applications in DNA storage, have reignited the interest in this longstanding open problem. In spite of recent advances, the amount of redundancy in existing codes is still orders of magnitude away from being optimal. In this paper, a novel approach for constructing binary two-deletion correcting codes is proposed. By this approach, parity symbols are computed from indicator vectors (i.e., vectors that indicate the positions of certain patterns) of the encoded message, rather than from the message itself. Most interestingly, the parity symbols and the proof of correctness are a direct generalization of their counterparts in the Varshamov- Tenengolts construction. Our techniques require 7log(n)+o(log(n) redundant bits to encode an n-bit message, which is near-optimal.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper ItemTechnical Report ItemJournal Article
Sima, Jin0000-0003-4588-9790
Raviv, Netanel0000-0002-1686-1994
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2018 IEEE. The work was supported in part by the NSF grant CCF-1717884. The work of Netanel Raviv was supported in part by the postdoctoral fellowship of the Center for the Mathematics of Information (CMI), Caltech, and in part by the Lester-Deutsch postdoctoral fellowship.
Funding AgencyGrant Number
Center for the Mathematics of Information, CaltechUNSPECIFIED
Lester-Deutsch postdoctoral fellowshipUNSPECIFIED
Record Number:CaltechAUTHORS:20180709-103747373
Persistent URL:
Official Citation:J. Sima, N. Raviv and J. Bruck, "Two Deletion Correcting Codes from Indicator Vectors," 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, 2018, pp. 421-425. doi: 10.1109/ISIT.2018.8437868
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:87641
Deposited By: George Porter
Deposited On:09 Jul 2018 17:49
Last Modified:09 Apr 2020 18:10

Repository Staff Only: item control page