Communication under channel uncertainty: An algorithmic perspective and effective construction

The availability and quality of channel state information heavily influences the performance of wireless communication systems. For perfect channel knowledge, optimal signal processing and coding schemes have been well studied and often closed-form solutions are known. On the other hand, the case of imperfect channel information is less understood and closed-form characterizations of optimal schemes remain unknown in many cases. This paper approaches this question from a fundamental, algorithmic point of view by studying whether or not such optimal schemes can be constructed algorithmically in principle (without putting any constraints on the computational complexity of such algorithms). To this end, the concepts of compound channels and averaged channels are considered as models for channel uncertainty and block fading and it is shown that, although the compound channel and averaged channel themselves are computable channels, the corresponding capacities are not computable in general, i.e., there exists no algorithm (or Turing machine) that takes the channel as an input and computes the corresponding capacity. As an implication of this, it is then shown that for such compound channels, there are no effectively constructible optimal (i.e., capacity-achieving) signal processing and coding schemes possible. This is particularly noteworthy as such schemes must exist (since the capacity is known), but they cannot be effectively, i.e., algorithmically, constructed. Thus, there is a crucial difference between the existence of optimal schemes and their algorithmic constructability. In addition, it is shown that there is no search algorithm that can find the maximal number of messages that can be reliably transmitted for a fixed blocklength. Finally, the case of partial channel knowledge is studied in which either the transmitter or the receiver have perfect channel knowledge while the other part remains uncertain. It is shown that also in the cases of an informed encoder and informed decoder, the capacity remains non-computable in general and, accordingly, optimal signal processing and coding schemes are not effectively constructible.