Deterministic Codes for Arbitrarily Varying Multiple-Access Channels.

Abstract

The arbitrarily varying multiple-access channel (AVMAC) is a model of a multiple access channel with unknown parameters. In 1981, Jahn characterized the capacity region of the AVMAC, assuming that the region had a nonempty interior; however, he did not address the problem of deciding whether or not the capacity region had a nonempty interior. Using the method of types and an approach completely different from Jahn's, we have partially solved this problem. We begin by introducing the simple but crucial notion of symmetrizability for the two-user AVMAC. We show that if an AVMAC is symmetrizable, then its capacity region has an empty interior. For the two-user AVMAC, 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. In light of these results, it is indeed fortunate that to test a channel for symmetrizability, one simply solves a system of linear equations whose coefficients are the channel transition probabilities. 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 informatzon decoding rule will be effective. We then consider the situation in which a constraint is imposed on the sequence of "states" in which the channel can reside. We extend our approach to show that in the presence of a state constraint, the capacity region can increase dramatically. A striking example of this effect occurs with the adder channel . This channel is symmetrizable, and without a state constraint, neither user can reliably transmit information across the channel. However, if a suitable state constraint is imposed, each user can reliably transmit more than 0.4 bits of information per channel use.