CaltechAUTHORS
  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. http://resolver.caltech.edu/CaltechAUTHORS:20180709-103747373

[img] PDF - Submitted Version
See Usage Policy.

276Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20180709-103747373

Abstract

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
https://doi.org/10.1109/ISIT.2018.8437868DOIArticle
https://arxiv.org/abs/1806.09240arXivDiscussion Paper
http://resolver.caltech.edu/CaltechAUTHORS:20180709-102730008Related ItemTechnical Report
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.
Funders:
Funding AgencyGrant Number
NSFCCF-1717884
Center for the Mathematics of Information, CaltechUNSPECIFIED
Lester-Deutsch postdoctoral fellowshipUNSPECIFIED
Record Number:CaltechAUTHORS:20180709-103747373
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20180709-103747373
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
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:09 Jul 2018 17:49
Last Modified:26 Nov 2018 17:26

Repository Staff Only: item control page