The Capacity of the Arbitrarily Varying Channel Revisited: Positivity, Constraints.

Abstract

A well-know result of Ahlswede asserts that the deterministic code capacity of an arbitrarily varying channel (AVC), under the average error probability criterion, either equals its random code capacity or else is zero. In this paper, we identify a necessary and sufficient condition for deciding between these alternatives, namely, the capacity is zero if and only if the AVC is symmetrizable. We also determine the capacity of the AVC with constraints on the transmitted codewords as well as on the channel state sequences, and demonstrate that it may be positive but less than the corresponding random code capacity. A special case of our results resolves a weakened version of a fundamental problem of coding theory.