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. Parallel and Distributed Systems Group Technical Reports, 141. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20180709-102730008

[img] PDF - Submitted Version
See Usage Policy.

355Kb

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

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 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
http://www.paradise.caltech.edu/papers/etr141.pdfAuthorTechnical Report
http://resolver.caltech.edu/CaltechAUTHORS:20180709-103747373Related ItemArticle
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
Funders:
Funding AgencyGrant Number
NSFCCF-1717884
Center for the Mathematics of Information, CaltechUNSPECIFIED
Lester-Deutsch postdoctoral fellowshipUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
PARADISEetr-141
Record Number:CaltechAUTHORS:20180709-102730008
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20180709-102730008
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:87639
Collection:CaltechPARADISE
Deposited By: George Porter
Deposited On:09 Jul 2018 17:51
Last Modified:26 Nov 2018 15:45

Repository Staff Only: item control page