Search

In the paper, the Levenshtein’s sequence reconstruction problem is considered in the case where the transmitted words are chosen from an $e$ -error-correcting code, at most $t$ substitution errors occur in each of the $N$ channels and the decoder outputs a list of length $\mathcal {L}$ . Previously, when $t = e+\ell $ and the transmitted word is long enough, the numbers of required channels were 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 $ . This also provides the size of the largest intersection of $\mathcal {L}$ balls of radius $t$ (with respect to substitutions) centered at the words with mutual Hamming distances at least $2e+1$ . 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 the output word of the decoder can be verified to be the transmitted one with high probability.