Sequence Reconstruction over the Deletion Channel

Abstract

In this paper, we consider the Levenshtein's sequence reconstruction problem in the case where the transmitted codeword is chosen from $\{0,1{\}}^n$ and the channel can delete up to $t$ symbols from the transmitted codeword. We determine the minimum number of channel outputs (assuming that they are distinct) required to reconstruct a list of size $\ell -1$ of candidate sequences, one of which corresponds to the original transmitted sequence. More specifically, we determine the maximum possible size of the intersection of $\ell \ge 3$ deletion balls of radius $t$ centered at $x_1,x_2,\dots ,x_{\ell }$, where $x_i\in \{0,1{\}}^n$ for all $i\in \{1,2,\dots ,\ell \}$ and $x_i\ne x_j$ for $i\ne j$, with $n\ge t+\ell -1$ and $t\ge 1$.

The main mistake has been corrected