Capacity of Noisy Permutation Channels
| Autor: | Tang, Jennifer, Polyanskiy, Yury |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | in IEEE Transactions on Information Theory, vol. 69, no. 7, pp. 4145-4162, July 2023 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1109/TIT.2023.3247812 |
| Popis: | We establish the capacity of a class of communication channels introduced in [1]. The $n$-letter input from a finite alphabet is passed through a discrete memoryless channel $P_{Z|X}$ and then the output $n$-letter sequence is uniformly permuted. We show that the maximal communication rate (normalized by $\log n$) equals $1/2 (rank(P_{Z|X})-1)$ whenever $P_{Z|X}$ is strictly positive. This is done by establishing a converse bound matching the achievability of [1]. The two main ingredients of our proof are (1) a sharp bound on the entropy of a uniformly sampled vector from a type class and observed through a DMC; and (2) the covering $\epsilon$-net of a probability simplex with Kullback-Leibler divergence as a metric. In addition to strictly positive DMC we also find the noisy permutation capacity for $q$-ary erasure channels, the Z-channel and others. Comment: draft version updated to newer version |
| Databáze: | arXiv |
| Externí odkaz: |
|