Algorithmic Computability of the Capacity of Additive Colored Gaussian Noise Channels

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Designing capacity-achieving coding schemes for the band-limited additive colored Gaussian noise (ACGN) channel has been and is still a challenge. In this paper, the capacity of the band-limited ACGN channel is studied from a fundamental algorithmic point of view by addressing the question of whether or not the capacity can be algorithmically computed. For this purpose, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It is shown that there are band-limited ACGN channels having a computable continuous spectral density whose capacity is a non-computable number. Moreover, it is demonstrated that for these channels, it is impossible to find a computable sequence of asymptotically sharp upper bounds for their capacity.

Original languageEnglish (US)
Title of host publicationGLOBECOM 2023 - 2023 IEEE Global Communications Conference
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9798350310900
StatePublished - 2023
Externally publishedYes
Event2023 IEEE Global Communications Conference, GLOBECOM 2023 - Kuala Lumpur, Malaysia
Duration: Dec 4 2023Dec 8 2023

Publication series

NameProceedings - IEEE Global Communications Conference, GLOBECOM
ISSN (Print)2334-0983
ISSN (Electronic)2576-6813


Conference2023 IEEE Global Communications Conference, GLOBECOM 2023
CityKuala Lumpur

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Networks and Communications
  • Hardware and Architecture
  • Signal Processing


Dive into the research topics of 'Algorithmic Computability of the Capacity of Additive Colored Gaussian Noise Channels'. Together they form a unique fingerprint.

Cite this