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. Parallel and Distributed Systems Group Technical Reports, 141. California Institute of Technology , Pasadena, CA. (Unpublished)

[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 7 log(n) + o(log(n) redundant bits to encode an n-bit message, which is near-optimal.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription Report ItemConference Paper ItemJournal Article
Sima, Jin0000-0003-4588-9790
Raviv, Netanel0000-0002-1686-1994
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:The work was presented in part at the IEEE International Symposium on Information Theory, July 2018. The work was supported in part by 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.
Group:Parallel and Distributed Systems Group
Funding AgencyGrant Number
Center for the Mathematics of Information, CaltechUNSPECIFIED
Lester-Deutsch postdoctoral fellowshipUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Series Name:Parallel and Distributed Systems Group Technical Reports
Issue or Number:141
Record Number:CaltechAUTHORS:20180709-102730008
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:87639
Deposited By: George Porter
Deposited On:09 Jul 2018 17:51
Last Modified:09 Apr 2020 18:09

Repository Staff Only: item control page