Please use this identifier to cite or link to this item:
Title: Efficient encoding/decoding of irreducible words for codes correcting tandem duplications
Authors: Chee, Yeow Meng
Chrisnata, Johan
Kiah, Han Mao
Nguyen, Tuan Thanh
Keywords: Science::Mathematics
Issue Date: 2018
Source: Chee, Y. M., Chrisnata, J., Kiah, H. M., & Nguyen, T. T. (2018). Efficient encoding/decoding of irreducible words for codes correcting tandem duplications. Proceedings of 2018 IEEE International Symposium on Information Theory (ISIT), 2406-2410. doi:10.1109/ISIT.2018.8437789
Abstract: Tandem duplication is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2017) proposed the study of codes that correct tandem duplications. All code constructions are based on irreducible words. We study efficient encoding/decoding methods for irreducible words. First, we describe an (ell, m) -finite state encoder and show that when m=Θ(1ϵ) and ell=Θ(1ϵ), the encoder has rate that is ϵ away from the optimal. Next, we provide ranking/unranking algorithms for irreducible words and modify the algorithms to reduce the space requirements for the finite state encoder.
ISBN: 9781538647806
DOI: 10.1109/ISIT.2018.8437789
Rights: © 2018 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. The published version is available at:
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Conference Papers

Files in This Item:
File Description SizeFormat 
Efficient Encoding_Decoding of Irreducible Words for Codes Correcting Tandem Duplications.pdf161.49 kBAdobe PDFView/Open

Citations 50

Updated on Jan 28, 2023

Page view(s)

Updated on Jan 29, 2023

Download(s) 50

Updated on Jan 29, 2023

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.