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

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.