The capacity of the M-user binary adder channel, subjected to various restrictions of physical nature, is investigated. The underlying propagation media considered are (i) fiber-optic, with lossless coupling and Poisson statistics, (ii) radio, under Rayleigh fading, and (iii) radio with constant amplitudes and random phases. Whereas the capacity of the unrestricted (ideal) model for the binary adder channel is known to increase without limit with the number of users, it is shown in the present paper that, for each of these cases, the total capacity is upper-bounded by a constant independent of the number of users: in case (i) by 1.7Q/sub T/ bits per channel use, where Q/sub T/ is the parameter of the Poisson process, in case (ii) by 4.33 bits per channel use, and in case (iii) by 4.27 bits per channel use.>

Consider M-Choose-T communications: T users or less, out of M potential users, are chosen at random to simultaneously transmit binary data over a common channel. A method for constructing codes that achieve error-free M-Choose-T communication over the noiseless adder channel (AC), at a nominal rate of 1/T bits per channel symbol per active user, is described and an efficient decoding procedure is presented. The use of such codes is referred to as forward collision resolution (FCR), as it enables correct decoding of collided messages without retransmissions. For any given T a code is available that yields a stable throughput arbitrarily close to 1 message/slot. Furthermore, if the occurrence of collisions is made known to the transmitters, such a throughput can be maintained for arbitrary T,T>

A situation where up to T randomly chosen users, out of M potential ones, simultaneously transmit data over the noiseless adder channel (AC) is considered. These T (or fewer) active users operate independently, and because of unknown time offsets among their clocks and different delays that the various messages incur during transmission, both block and bit synchronism are precluded. Code constructions that ensure error-free asynchronous communication over the adder channel are presented. The information rate of these codes=approaches 1/T bits per user. If exactly T users are active, use of these codes leads to an aggregate rate arbitrarily close to 1 bit per channel use. Furthermore, if the occurrence of simultaneous transmissions of more than T users is made known to the active transmitters, such an aggregate rate can be maintained for arbitrary T, T>

An upper bound on the probability of a sequence drawn from a finite-state source is derived. The bound is given in terms of the number of phrases obtained by parsing the sequence according to the Lempel-Ziv (L-Z) incremental parsing rule, and is universal in the sense that it does not depend on the statistical parameters that characterize the source. This bound is used to derive an upper bound on the redundance of the L-Z universal data compression algorithm applied to finite-state sources, that depends on the length N of the sequence, on the number K of states of the source, and, eventually, on the source entropy. A variation of the L-Z algorithm is presented, and an upper bound on its redundancy is derived for finite-state sources. A method to derive tighter implicit upper bounds on the redundancy of both algorithms is also given, and it is shown that for the proposed variation this bound is smaller than for the original L-Z algorithm, or every value of N and K.>

The multiple-access problem is addressed from the combined standpoint of both coding and scheduling to arrive at a stable, highly efficient access scheme for the binary adder channel. The authors define a system model that includes the channel and the coding mechanism and explain the M-choose-T communication mode which is fundamental to their method. They then address the system's performance and show that high throughput (arbitrarily close to 1) is achieved while the access remains stable. They also investigate the average message delay.>