Algorithmic Computability and Approximability of Capacity-Achieving Input Distributions

Holger Boche, Rafael F. Schaefer, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

The capacity of a channel can usually be characterized as a maximization of certain entropic quantities. From a practical point of view it is of primary interest to not only compute the capacity value, but also to find the corresponding optimizer, i.e., the capacity-achieving input distribution. This paper addresses the general question of whether or not it is possible to find algorithms that can compute the optimal input distribution depending on the channel. For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers and therewith fully specifies which tasks are algorithmically feasible in principle. It is shown for discrete memoryless channels that it is impossible to algorithmically compute the capacity-achieving input distribution, where the channel is given as an input to the algorithm (or Turing machine). Finally, it is further shown that it is even impossible to algorithmically approximate these input distributions.

Original languageEnglish (US)
Pages (from-to)5449-5462
Number of pages14
JournalIEEE Transactions on Information Theory
Volume69
Issue number9
DOIs
StatePublished - Sep 1 2023
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • Capacity-achieving input distribution
  • approximability
  • computability
  • turing machine

Fingerprint

Dive into the research topics of 'Algorithmic Computability and Approximability of Capacity-Achieving Input Distributions'. Together they form a unique fingerprint.

Cite this