Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Efficient Approximation of Channel Capacities


T. Sutter, D. Sutter, P. Mohajerin Esfahani, J. Lygeros

IEEE Transactions on Information Theory, vol. 61, no. 4, (arXiv:1407.7629)

We propose an iterative method for approximately computing the capacity of discrete memoryless channels, possibly under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. The presented method requires O(M^2 N (log N)^(1/2) / epsilon) to provide an estimate of the capacity to within epsilon, where N and M denote the input and output alphabet size; a single iteration has a complexity O(MN). We also show how to approximately compute the capacity of memoryless channels having a bounded continuous input alphabet and a countable output alphabet under some mild assumptions on the decay rate of the channel's tail. It is shown that discrete-time Poisson channels fall into this problem class. As an example, we compute sharp upper and lower bounds for the capacity of a discrete-time Poisson channel with a peak-power input constraint.

Further Information

Type of Publication:


File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Article { SutEtal:2015:IFA_4816,
    author={T. Sutter and D. Sutter and P. Mohajerin Esfahani and J. Lygeros},
    title={{Efficient Approximation of Channel Capacities}},
    journal={IEEE Transactions on Information Theory},
Permanent link