Multilayer Codes for Synchronization from Deletions and Insertions


Type
Article
Change log
Abstract

Consider two remote nodes (encoder and decoder), each with a binary sequence. The encoder’s sequence X differs from the decoder’s sequence Y by a small number of edits (deletions and insertions). The goal is to construct a message M, to be sent via a one-way error free link, such that the decoder can reconstruct X using M and Y . In this paper, we devise a coding scheme for this one-way synchronization model. The scheme is based on multiple layers of Varshamov-Tenengolts (VT) codes combined with off-the-shelf linear error-correcting codes, and uses a list decoder. We bound the expected list size of the decoder under certain assumptions, and validate its performance via numerical simulations. We also consider an alternative decoder that uses only the constraints from the VT codes (i.e., does not require a linear code), and has a smaller redundancy at the expense of a slightly larger average list size.

Description
Keywords
Decoding, Synchronization, Redundancy, Complexity theory, Numerical simulation, Linear codes, File synchronization, document exchange, edit channel, Varshomov-Tenengolts (VT) codes
Journal Title
IEEE Transactions on Information Theory
Conference Name
Journal ISSN
0018-9448
1557-9654
Volume Title
67
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Rights
All rights reserved
Sponsorship
European Research Council (725411)
ERC Grant ITUL