Correcting Deletions With Multiple Reads
Johan Chrisnata, Han Mao Kiah, Eitan Yaakobi · IEEE Transactions on Information Theory · 2022
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$\log _{2}\log _{2} n +O(1)$redundant bits, we designed a reconstruction code of length$n$that reconstructs codewords from two distinct noisy reads (Caiet al., 2021). In this work, we show that$\log _{2}\log _{2} 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 \geqslant 2$) to uniquely reconstruct codewords from${n^{t-1}}/{(t-1)!}+O\left ({n^{t-2}}\right)$distinct noisy reads. For the two-deletion channel, using higher order VT syndromes and certain runlength constraints, we designed the class ofhigher order constrained shifted VTcode with$2\log _{2} n +o(\log _{2}(n))$redundancy bits that can reconstruct any codeword from any$N \geqslant 5$of its length-$(n-2)$subsequences.