Abroshan, MahedVenkataramanan, RamjiGuillén i Fábregas, A. (Albert)2023-02-132023-02-132021Abroshan M, Venkataramanan R, Guillen i Fàbregas A. Multilayer codes for synchronization from deletions and insertions. IEEE Trans Inf Theory. 2021;67(6):3342-59. DOI: 10.1109/TIT.2020.30362840018-9448http://hdl.handle.net/10230/55728Consider 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.application/pdfeng© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. http://dx.doi.org/10.1109/TIT.2020.3036284info:eu-repo/semantics/articlehttp://dx.doi.org/10.1109/TIT.2020.3036284file synchronizationdocument exchangeedit channelVarshomov-Tenengolts (VT) codesinfo:eu-repo/semantics/openAccess