Characterization of Deletion/Substitution Channel Capacity for Small Deletion and Substitution Probabilities
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915412161069056 |
|---|---|
| author | Kazemi, Mohammad Duman, Tolga M. |
| author_facet | Kazemi, Mohammad Duman, Tolga M. |
| contents | 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(p_d) - H(p_s)\), for \(p_d, p_s \approx0\), where \(p_d\) and \(p_s\) are the deletion and substitution probabilities, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02545 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Characterization of Deletion/Substitution Channel Capacity for Small Deletion and Substitution Probabilities Kazemi, Mohammad Duman, Tolga M. Information Theory 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(p_d) - H(p_s)\), for \(p_d, p_s \approx0\), where \(p_d\) and \(p_s\) are the deletion and substitution probabilities, respectively. |
| title | Characterization of Deletion/Substitution Channel Capacity for Small Deletion and Substitution Probabilities |
| topic | Information Theory |
| url | https://arxiv.org/abs/2503.02545 |