Please use this identifier to cite or link to this item:
Title: Correcting deletions with multiple reads
Authors: Chrisnata, Johan
Kiah, Han Mao
Yaakobi, Eitan
Keywords: Engineering::Computer science and engineering
Issue Date: 2022
Source: Chrisnata, J., Kiah, H. M. & Yaakobi, E. (2022). Correcting deletions with multiple reads. IEEE Transactions On Information Theory, 68(11), 7141-7158.
Project: MOE-T2EP20121-0007
Journal: IEEE Transactions on Information Theory
Abstract: The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. Motivated by modern storage devices, we introduced a variant of the problem where the number of noisy reads N is fixed. Of significance, for the single-deletion channel, using log2log2 n +O(1) redundant bits, we designed a reconstruction code of length n that reconstructs codewords from two distinct noisy reads (Cai et al., 2021). In this work, we show that log2log2 n -O(1) redundant bits are necessary for such reconstruction codes, thereby, demonstrating the optimality of the construction. Furthermore, we show that these reconstruction codes can be used in t-deletion channels (with t ≥ qslant 2) to uniquely reconstruct codewords from nt-1/(t-1)!}+O ({nt-2) distinct noisy reads. For the two-deletion channel, using higher order VT syndromes and certain runlength constraints, we designed the class of higher order constrained shifted VT code with 2log2 n +o(log2(n)) redundancy bits that can reconstruct any codeword from any N ≥ 5 of its length-(n-2) subsequences.
ISSN: 0018-9448
DOI: 10.1109/TIT.2022.3184868
Rights: © 2022 IEEE. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SPMS Journal Articles

Page view(s)

Updated on Feb 5, 2023

Google ScholarTM




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