Repository logo
 

Multilayer Codes for Synchronization from Deletions and Insertions

Accepted version
Peer-reviewed

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