The Levenshtein’s Sequence Reconstruction Problem and the Length of the List

Abstract

<p>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 L . Previously, when t = e + ℓ and the transmitted word is long enough, the numbers of required channels were determined for L = 1, 2 and ℓ+1. Here we determine the exact number of channels in the cases L = 3,4,..., ℓ. This also provides the size of the largest intersection of L balls of radius t (with respect to substitutions) centered at the words with mutual Hamming distances at least 2 e + 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.</p>