Turing Meets Shannon: On the Algorithmic Construction of Channel-Aware Codes

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

Research output: Contribution to journalArticlepeer-review

Abstract

A capacity result involves two parts: achievability and converse. The achievability proof is usually non-constructive and only the existence of capacity-achieving codes is shown invoking probabilistic techniques. Recently, capacity-achieving codes have been found for several channels demonstrating that such codes can actually be constructed algorithmically. To this end, each construction is designed for a pre-specified channel so that the corresponding algorithm is specifically tailored to it. This paper addresses the general question of whether or not it is possible to find algorithms that can construct capacity-achieving codes for a whole class of channels. To do so, 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 that there exists no Turing machine that is able to construct capacity-achieving codes for a whole class of channels, where the channel realization from this class is given as an input to the Turing machine. It is further shown that such an algorithmic construction remains impossible when the optimality condition is dropped and codes only need to achieve a fraction of the capacity. Finally, implications on channel-aware transmission, link adaptation, and cross-layer optimization are discussed.

Original languageEnglish (US)
Pages (from-to)2256-2267
Number of pages12
JournalIEEE Transactions on Communications
Volume70
Issue number4
DOIs
StatePublished - Apr 1 2022
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering

Keywords

  • Algorithmic computability
  • Turing machine
  • code construction
  • communication system

Fingerprint

Dive into the research topics of 'Turing Meets Shannon: On the Algorithmic Construction of Channel-Aware Codes'. Together they form a unique fingerprint.

Cite this