Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2018 | Submitted
Book Section - Chapter Open

Two Deletion Correcting Codes from Indicator Vectors

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.

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.

Attached Files

Submitted - 1806.09240.pdf

Files

1806.09240.pdf
Files (282.8 kB)
Name Size Download all
md5:a9ab5c91fdc6c5a5f5fc73eb766e2c72
282.8 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 20, 2023