Technical Program

Paper Detail

Paper IDS.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

Visit Website!