Characterization of the Complexity of Computing the Capacity of Colored Noise Gaussian Channels

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

Research output: Contribution to journalArticlepeer-review

Abstract

This paper explores the computational complexity involved in determining the capacity of the band-limited additive colored Gaussian noise (ACGN) channel and its capacity-achieving power spectral density (p.s.d.). The study reveals that when the noise p.s.d. is a strictly positive computable continuous function, computing the capacity of the band-limited ACGN channel becomes a #P1-complete problem within the set of polynomial time computable noise p.s.d.s. Meaning that it is even more complex than problems that are NP1-complete. Additionally, it is shown that computing the capacity-achieving distribution is also #P1-complete. Furthermore, under the widely accepted assumption that FP1 ≠ #P1, it has two significant implications for the ACGN channel. The first implication is the existence of a polynomial time computable noise p.s.d. for which the computation of its capacity cannot be performed in polynomial time, i.e., the number of computational steps on a Turing Machine grows faster than all polynomials. The second one is the existence of a polynomial time computable noise p.s.d. for which determining its capacity-achieving p.s.d. cannot be done within polynomial time. This implies that either the sequence of achievable rates with guaranteed distance to capacity is not polynomial time computable, or the corresponding blocklength sequence is not polynomial time computable.

Original languageEnglish
Pages (from-to)1
Number of pages1
JournalIEEE Transactions on Communications
DOIs
StateAccepted/In press - 2024

Keywords

  • 6G mobile communication
  • Channel capacity
  • Codes
  • Complexity theory
  • Computational complexity
  • Computational modeling
  • Gaussian noise

Fingerprint

Dive into the research topics of 'Characterization of the Complexity of Computing the Capacity of Colored Noise Gaussian Channels'. Together they form a unique fingerprint.

Cite this