Multilayer codes for synchronization from deletions and insertions
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Abroshan, Mahed
- dc.contributor.author Venkataramanan, Ramji
- dc.contributor.author Guillén i Fábregas, A. (Albert)
- dc.date.accessioned 2023-02-13T07:16:33Z
- dc.date.available 2023-02-13T07:16:33Z
- dc.date.issued 2021
- dc.description.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.
- dc.description.sponsorship This work was supported in part by the European Research Council under Grant 725411 and in part by the Spanish Ministry of Economy and Competitiveness under Grant TEC2016-78434-C3-1-R.
- dc.format.mimetype application/pdf
- dc.identifier.citation Abroshan 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.3036284
- dc.identifier.doi http://dx.doi.org/10.1109/TIT.2020.3036284
- dc.identifier.issn 0018-9448
- dc.identifier.uri http://hdl.handle.net/10230/55728
- dc.language.iso eng
- dc.publisher Institute of Electrical and Electronics Engineers (IEEE)
- dc.relation.ispartof IEEE Transactions on Information Theory. 2021;67(6):3342-59.
- dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/725411
- dc.relation.projectID info:eu-repo/grantAgreement/ES/1PE/TEC2016-78434-C3-1-R
- dc.rights © 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.3036284
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.subject.keyword file synchronization
- dc.subject.keyword document exchange
- dc.subject.keyword edit channel
- dc.subject.keyword Varshomov-Tenengolts (VT) codes
- dc.title Multilayer codes for synchronization from deletions and insertions
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/acceptedVersion