Robust transmission over channels with channel uncertainty: An algorithmic perspective

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 are well studied and often closed-form solutions are known. On the other hand, the case of imperfect channel information is much less understood and closed-form solutions remain unknown in general. This paper approaches this question from a fundamental, algorithmic point of view to study whether or not such optimal schemes can be found algorithmically in principle (without putting any constraints on the computational complexity of such algorithms). To this end, the compound channel is considered as a model for channel uncertainty and it is shown that although the compound channel itself is a computable channel, the corresponding capacity is 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 signal processing and coding schemes that achieve the capacity. This is particularly noteworthy as such schemes must exist (since the capacity is known), but they cannot be effectively, i.e., algorithmically, constructed.