Conditional Entropies of k-Deletion/Insertion Channels
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915318814736384 |
|---|---|
| author | Singhvi, Shubhransh Sabary, Omer Bar-Lev, Daniella Yaakobi, Eitan |
| author_facet | Singhvi, Shubhransh Sabary, Omer Bar-Lev, Daniella Yaakobi, Eitan |
| contents | The channel output entropy of a transmitted sequence is the entropy of the possible channel outputs and similarly the channel input entropy of a received sequence is the entropy of all possible transmitted sequences. The goal of this work is to study these entropy values for the k-deletion, k-insertion channels, where exactly k symbols are deleted, inserted in the transmitted sequence, respectively. If all possible sequences are transmitted with the same probability then studying the input and output entropies is equivalent. For both the 1-deletion and 1-insertion channels, it is proved that among all sequences with a fixed number of runs, the input entropy is minimized for sequences with a skewed distribution of their run lengths and it is maximized for sequences with a balanced distribution of their run lengths. Among our results, we establish a conjecture by Atashpendar et al. which claims that for the 1-deletion channel, the input entropy is maximized by the alternating sequences over all binary sequences. This conjecture is also verified for the 2-deletion channel, where it is proved that constant sequences with a single run minimize the input entropy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_10026 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Conditional Entropies of k-Deletion/Insertion Channels Singhvi, Shubhransh Sabary, Omer Bar-Lev, Daniella Yaakobi, Eitan Information Theory The channel output entropy of a transmitted sequence is the entropy of the possible channel outputs and similarly the channel input entropy of a received sequence is the entropy of all possible transmitted sequences. The goal of this work is to study these entropy values for the k-deletion, k-insertion channels, where exactly k symbols are deleted, inserted in the transmitted sequence, respectively. If all possible sequences are transmitted with the same probability then studying the input and output entropies is equivalent. For both the 1-deletion and 1-insertion channels, it is proved that among all sequences with a fixed number of runs, the input entropy is minimized for sequences with a skewed distribution of their run lengths and it is maximized for sequences with a balanced distribution of their run lengths. Among our results, we establish a conjecture by Atashpendar et al. which claims that for the 1-deletion channel, the input entropy is maximized by the alternating sequences over all binary sequences. This conjecture is also verified for the 2-deletion channel, where it is proved that constant sequences with a single run minimize the input entropy. |
| title | Conditional Entropies of k-Deletion/Insertion Channels |
| topic | Information Theory |
| url | https://arxiv.org/abs/2407.10026 |