Guess & Check Codes for Deletions, Insertions, and Synchronization

DOI10.1109/TIT.2018.2841936zbMATH Open1431.94004arXiv1705.09569MaRDI QIDQ4611409FDOQ4611409

Authors: Serge Kas Hanna, Salim El Rouayheb 

Publication date: 18 January 2019

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

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.

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

Mathematics Subject Classification ID

Communication theory (94A05)

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)