论文标题
删除通道的最佳重建代码
Optimal Reconstruction Codes for Deletion Channels
论文作者
论文摘要
Levenshtein在2001年引入的序列重建问题考虑了一种通信方案，其中发件人从某些代码簿中传输代码字，并且接收器获得了代码字的多个嘈杂的读数。在现代存储设备的启发下，我们引入了问题的变体，其中噪声读取$ n $的数量是固定的（Kiah等，2020）。重要的是，对于单缺失通道，使用$ \ log_2 \ log_2 n +o（1）$冗余位，我们设计了一个长度$ n $的重建代码，该代码从两个不同的嘈杂读物中重建代码字。 在这项工作中，我们表明$ \ log_2 \ log_2 n -o（1）$冗余位对于此类重建代码中是必需的，从而证明了我们以前的构造的最佳性。此外，我们表明这些重建代码可在$ t $ - 删除通道（带有$ t \ ge 2 $）中使用，以唯一地从$ n^{t-1}+o \ left（n^{t-2} \ right）中重新构造代码字。
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 reconstruction code 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.
