Characterization of Deletion/Substitution Channel Capacity for Small Deletion and Substitution Probabilities

We consider binary input deletion/substitution channels, which model certain types of synchronization errors encountered in practice. Specifically, we focus on the regime of small deletion and substitution probabilities, and by extending an approach developed for the deletion-only channel, we obtain an asymptotic characterization of the channel capacity for independent and identically distributed (i. i. d. ) deletion/substitution channels. To do so, given a target probability of successful decoding, we first develop an upper bound on the codebook size for arbitrary but fixed numbers of deletions and substitutions, and then extend the result to the case of random deletions and substitutions to obtain a bound on the channel capacity. Our final result is: The i. i. d. deletion/substitution channel capacity is approximately \ (1 - H (pd) - H (pₛ) \), for \ (pd, pₛ 0\), where \ (pd\) and \ (pₛ\) are the deletion and substitution probabilities, respectively.