Capacity and Decoding Rules for Classes of Arbitrarily Varying Channels.

Abstract

We consider the capacity of an arbitrarily varying channel (AVC) for deterministic codes with the average probability of error criterion, and typically subject to a state constraint. First, sufficient conditions are provided that enable (relatively) simple decoding rules such as typicality, maximum mutual information, and minimum distance, to attain capacity. Then the (possibly noisy) OR channels and group adder channels are studied in detail. For the former, the capacity is explicitly determined and shown to be attainable by minimum distance decoding. Next, for a large class of additive AVCs, in addition to providing an intuitively suggestive simplification of the general AVC capacity formula, we prove that capacity can be attained by an universal decoding rule. Finally, the effect of random state selection on capacity is studied, enabling us to comment on the merits and limitations of a previous "mutual information game" approach.