Communication over block fading channels - An algorithmic perspective on optimal transmission schemes

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

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


Wireless channels are considered that change over time but remain constant for a certain (coherence) period. This behavior is perfectly captured by block fading channels and affects the performance of the corresponding wireless communication systems. Desired closed-form characterizations of optimal transmission schemes remain unknown in many cases. This paper approaches this issue from a fundamental, algorithmic point of view by studying whether or not it is in principle possible to construct or find such optimal transmission schemes algorithmically (without putting any constraints on the computational complexity of such algorithms). To this end, the concept of averaged channels is considered as a model for block fading and it is shown that, although the averaged channel itself is computable, the corresponding capacity need not be computable, i.e., there exists no (universal) algorithm that takes the channel as an input and computes the corresponding capacity expression. Subsequently, examples of block fading channels are presented for which it is even impossible to find an algorithm that computes for every blocklength the corresponding optimal transmission scheme.

Original languageEnglish (US)
Pages (from-to)4750-4754
Number of pages5
JournalICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
StatePublished - 2021
Externally publishedYes
Event2021 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2021 - Virtual, Toronto, Canada
Duration: Jun 6 2021Jun 11 2021

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering


  • Block fading
  • Optimal transmission scheme
  • Robust communication
  • Turing computability


Dive into the research topics of 'Communication over block fading channels - An algorithmic perspective on optimal transmission schemes'. Together they form a unique fingerprint.

Cite this