Capacity Bounds for a Channel with Synchronization Errors

We analyze the problem of computing the capacity of a symmetrical channel with independent streams of symbol insertions, deletions, and replacements. Lower bounds on capacity are derived for a channel without insertions and for a channel without deletions. Using a certain combinatorial conjecture, we derive bounds for a channel with only insertions and for a channel with only deletions, which to a high degree of accuracy coincide with the experimental data of Vvedenskaya and Dobrushin [Probl. Peredachi Inf., 4, No. 3, 92–95 (1968)].