Sequence Reconstruction Problem for Deletion Channels: A Complete Asymptotic Solution
Van Long Phuoc Pham, Keshav Goyal, Han Mao Kiah
Abstract
Transmit a codeword x, that belongs to an (ℓ − 1)deletion-correcting code of length n, over a t-deletion channel for some 1 ≤ ℓ ≤ t < n. Levenshtein, in 2001, proposed the problem of determining N(n,ℓ,t) + 1, the minimum number of distinct channel outputs required to uniquely reconstruct x. Prior to this work, N(n,ℓ,t) is known only when ℓ ∈ {1,2}. Here, we provide an asymptotically exact solution for all values of ℓ and t. Specifically, we show that $N(n,\ell ,t) = \binom{{2\ell }}{\ell}/(t - \ell )!{n^{t - \ell }} - O\left( {{n^t}^{ - \ell - 1}} \right)$ and in the special instance where ℓ = t, we show that $N(n,\ell ,\ell ) = \binom{{2\ell }}{\ell}$. We also provide a conjecture on the exact value of N(n,ℓ,t) for all values of n, ℓ, and t.