2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | S.2.1 | ||
| Paper Title | Bounds on Permutation Channel Capacity | ||
| Authors | Anuran Makur, Massachusetts Institute of Technology, United States | ||
| Session | S.2: Channel Capacity | ||
| Presentation | Lecture | ||
| Track | Shannon Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | The "permutation channel" model is a convenient representation of certain communication networks, where packets are not indexed and delivered out-of-order, and closely resembles models of DNA based storage systems. It consists of a standard discrete memoryless channel (DMC) followed by an independent random permutation block that permutes the output codewords of the DMC. In this paper, we present some new general bounds on the so called permutation channel capacity of such channels. Specifically, on the achievability front, we derive a lower bound on the permutation channel capacity of any DMC in terms of the rank of the stochastic matrix of the DMC. On the converse front, we illustrate two complementary upper bounds on the permutation channel capacity of any DMC whose stochastic matrix is entry-wise strictly positive. Together, these bounds characterize the permutation channel capacities of entry-wise strictly positive and "full rank" DMCs. Finally, we also demonstrate two related results concerning the well-known degradation preorder. The first constructs a symmetric channel for any DMC such that the DMC is a degraded version of the symmetric channel, and the second demonstrates the monotonicity of permutation channel capacity. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
