Exponential error bounds achievable by universal coding and decoding are derived for frame-asynchronous discrete memoryless multiple access channels with two senders, via the method of subtypes, a refinement of the method of types. An empirical entropy decoder is employed. A key tool is an improved packing lemma, that overcomes the technical difficulty caused by codeword repetitions via an induction based new argument. The asymptotic form of the bounds admits numerical evaluation. This demonstrates that error exponents achievable by synchronous transmission can be superseded via controlled asynchronism, i.e. a deliberate shift of the codewords.

The following conjectures from previous work of the authors are proven, enhancing the relevance of results there on the subject in the title: (i) The error exponents previously derived assuming that consecutive messages could be encoded using different codebooks, are also achievable with each sender using only one codebook. (ii) In case the senders could be synchronized, controlled asynchronism (a deliberate shift of codewords) may admit to achieve error exponents unachievable by synchronous transmission.

A variant of successive decoding for asynchronous multiple access channel is introduced involving constant composition codebooks and maximal mutual information decoder. This admits to improve known achievability results to universal achievability, complemented by error exponents. A further result is that when synchronization is available, a deliberate shifting of the starting times of codewords (controlled asynchronism) combined with successive decoding offers a substitute for techniques of rate splitting and time sharing.

Csiszár's channel coding theorem for multiple codebooks is generalized allowing the code word lengths differ across codebooks. Also in this case, for each codebook an error exponent can be achieved that equals the random coding exponent for this codebook alone. In addition, when the rate and code word-type of the employed codebook do not admit reliable transmission over the given channel, overload is detected with probability approaching 1. This is proved even for a sender and receiver not knowing the channel beyond the alphabets. A substantial improvement is obtained when the sender knows the channel while the receiver still does not.

Csiszár's channel coding theorem for multiple code-books is generalized allowing the codeword lengths differ across codebooks. Also in this case, for each codebook an error exponent can be achieved that equals the random coding exponent for this codebook alone, in addition, the overload detection failure probability tends to 0. This is proved even for sender and receiver not knowing the channel. As a corollary, a substantial improvement is obtained when the sender knows the channel.

Communication over a discrete memoryless channel is addressed when codewords are transmitted in certain time intervals of arbitrary locations, at other times the channel outputs pure noise. The receiver has to locate and decode the codewords. Exponential error bounds are derived, jointly achievable via a semi-universal or universal decoder. Implications are discussed for the familiar model of communication under strong asynchronism when in exponentially long time only one codeword is transmitted.

Improved exponential error bounds are derived for frame-asynchronous discrete memoryless multiple access channels with two senders. By numerical evaluation for a particular case, it follows that the best error exponent known for synchronous transmission may be beaten if the senders are allowed to transmit with a chosen delay.

A new universal coding/decoding scheme for random access with collision detection is given in case of two senders. The result is used to give achievable joint source-channel coding error exponents for multiple access channel and independent sources. In a modified model admitting zero rate communication between the senders, an improved exponent is derived, of form similar to Csiszár’s joint source-channel exponent for the one-sender case.

Exponential error bounds achievable via universal decoder are derived for frame-asynchronous discrete memoryless multiple access channels with two senders. The exponent is strictly positive inside the capacity region. The method of types and a modified maximal mutual information decoder are used.

A new universal coding/decoding scheme for Random Access with collision detection is given in case of two senders. The result is used to give an achievable source-channel coding error exponent for Multiple-Access channels in case of independent sources.

Frame asynchronous discrete memoryless multiple access channels are analyzed, where some groups of senders are synchronized but the groups are not synchronized with each other. A single-letter characterization of the capacity region is obtained.

Motivated by the importance of asynchronous multiple access channels we give an exact formalization. This formalization admits different distributions on delays. The two classical settings when the delay is uniformly distributed and when it is bounded are discussed as special cases of this model. Our method also allows for the analysis of a so far unexplored class of models, where the known distribution of the delay has a special form, leading to new interesting capacity regions.