Back to Search
Start Over
Correcting Deletions With Multiple Reads.
- Source :
- IEEE Transactions on Information Theory; Nov2022, Vol. 68 Issue 11, p7141-7158, 18p
- Publication Year :
- 2022
-
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 $\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 (Cai et 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 of higher order constrained shifted VT code 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- ERROR-correcting codes
IMAGE reconstruction algorithms
NOISE measurement
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 68
- Issue :
- 11
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 160651146
- Full Text :
- https://doi.org/10.1109/TIT.2022.3184868