Sequence Reconstruction Problem for Deletion Channels: A Complete Asymptotic Solution

Abstract: Transmit a codeword

x

, that belongs to an

(e l l - 1)

-deletion-correcting code of length

n

, over a

t

-deletion channel for some

1 l e e l l l e t < n

. Levenshtein, in 2001, proposed the problem of determining

N (n, e l l, t) + 1

, the minimum number of distinct channel outputs required to uniquely reconstruct

x

. Prior to this work,

N (n, e l l, t)

is known only when

e l l i n 1, 2

. Here, we provide an asymptotically exact solution for all values of

e l l

and

t

. Specifically, we show that

and in the special instance where

e l l = t

, we show that

. We also provide a conjecture on the exact value of

N (n, e l l, t)

for all values of

n

,

e l l

, and

t

.

This page was built for publication: Sequence Reconstruction Problem for Deletion Channels: A Complete Asymptotic Solution