On the Deterministic-Code Capacity of the Multiple-Access Arbitrarily Varying Channel.

Abstract

The capacity region of the multiple-access arbitrarily varying channel (AVC) was characterized by Jahn, assuming that the region had a nonempty interior; however, he did not indicate how one could decide whether or not the capacity region had a nonempty interior. Using the method of types and an approach different from Jahn's, we have partially solved this problem. We begin by considering the notion of symmetrizability for the two-user AVC as an extension of the same notion for the single-user AVC. We show that if a multiple-access AVC is symmetrizable, then its capacity region has an empty interior. For the two-user AVC, this means that at least one (and perhaps both) users cannot reliably transmit information across the channel. More importantly, we show that if the channel is suitably nonsymmetrizable, then the capacity region has a nonempty interior, and both users can reliably transmit information across the channel. Our proofs rely heavily on a rather complicated decoding rule. This leads us to seek conditions under which simpler multiple-message decoding techniques might suffice. In particular, we give conditions under which the universal mazimum mutual information decoding rule will be effective.