Guess & Check Codes for Deletions, Insertions, and Synchronization

DOI10.1109/TIT.2018.2841936MaRDI QIDQ4611409zbMATH OpenFDO

Authors Serge Kas Hanna, Salim El Rouayheb

Publication date 18 January 2019

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.09569

Mathematics Subject Classification ID

Communication theory (94A05)

Abstract: We consider the problem of constructing codes that can correct $delta$ deletions occurring in an arbitrary binary string of length $n$ bits. Varshamov-Tenengolts (VT) codes, dating back to 1965, are zero-error single deletion $(delta=1)$ correcting codes, and have an asymptotically optimal redundancy. Finding similar codes for $deltageq2$ deletions remains an open problem. In this work, we relax the standard zero-error (i.e., worst-case) decoding requirement by assuming that the positions of the $delta$ deletions (or insertions) are independent of the codeword. Our contribution is a new family of explicit codes, that we call Guess & Check (GC) codes, that can correct with high probability up to a constant number of $delta$ deletions (or insertions). GC codes are systematic; and have deterministic polynomial time encoding and decoding algorithms. We also describe the application of GC codes to file synchronization.

Cited in

(1)

• Efficient Linear and Affine Codes for Correcting Insertions/Deletions

This page was built for publication: Guess & Check Codes for Deletions, Insertions, and Synchronization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4611409)