Summary
2020
Session Number:B06
Session:
Number:B06-2
Optimal Reconstruction Codes for Deletion Channels
Johan Chrisnata, Han Mao Kiah, Eitan Yaakobi,
pp.279-283
Publication Date:2020/10/18
Online ISSN:2188-5079
PDF download
Summary:
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 (Kiah et al. 2020).
Of significance, for the single-deletion channel,
using \(\log_2\log_2 n +O(1)\) redundant bits, we designed a codebook of length \(n\) that reconstructs codewords from two distinct noisy reads.
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 our previous construction.
Furthermore, we show that these reconstruction codes can be used in \(t\)-deletion channels (with \(t\ge 2\)) to uniquely reconstruct codewords from \(n^{t-1}+O\left(n^{t-2}\right)\) distinct noisy reads.