论文标题
Levenshtein的序列重建问题和列表的长度
The Levenshtein's Sequence Reconstruction Problem and the Length of the List
论文作者
论文摘要
在本文中，在每个$ n $通道中最多出现$ t $替换错误的情况下，考虑了Levenshtein的序列重建问题，而解码器输出了一个长度$ \ MATHCAL {l} $的列表。此外，假定从$ e $ eRRECT的代码$ c \（\ subseteq \ {0,1 \}^n）$选择传输单词。以前，当$ t = e+\ ell $和传输单词的长度$ n $足够大时，确定了所需的频道的数量，用于$ \ mathcal {l} = 1，2 \ text {and} \ ell+1 $。在这里，我们确定$ \ Mathcal {l} = 3，4，\ ldots，\ ell $的确切频道数量。此外，在覆盖法规的帮助下，我们还考虑了长度$ n $相当小的情况（改善先前已知的结果）。之后，我们研究了使用列表编码代码时可以减少所需渠道数量的多少。最后，讨论了在概率设置中解码的多数算法。特别是，我们表明，具有基于它的解码器的概率很高，即可以验证解码器的输出单词是传输的。
In the paper, the Levenshtein's sequence reconstruction problem is considered in the case where at most $t$ substitution errors occur in each of the $N$ channels and the decoder outputs a list of length $\mathcal{L}$. Moreover, it is assumed that the transmitted words are chosen from an $e$-error-correcting code $C \ (\subseteq \{0,1\}^n)$. Previously, when $t = e+\ell$ and the length $n$ of the transmitted word is large enough, the numbers of required channels are determined for $\mathcal{L} =1, 2 \text{ and } \ell+1$. Here we determine the exact number of channels in the cases $\mathcal{L} = 3, 4, \ldots, \ell$. Furthermore, with the aid of covering codes, we also consider the list sizes in the cases where the length $n$ is rather small (improving previously known results). After that we study how much we can decrease the number of required channels when we use list-decoding codes. Finally, the majority algorithm is discussed for decoding in a probabilistic set-up; in particular, we show that with high probability a decoder based on it is verifiably successful, i.e., the output word of the decoder can be verified to be the transmitted one.
