Multiple Access Channel Capacity

Core Idea

The capacity region of a discrete memoryless multiple access channel (MAC) with K users is the set of rate tuples (R_1, ..., R_K) simultaneously achievable with error probability approaching zero. For general MACs, the region is characterized by the union of inner and outer bounds. The achievable region (inner bound) is defined by the rate constraints: sum_{i in S} R_i <= I(X_S; Y | X_{S^c}) for every non-empty subset S of users, where X_S is the input vector for users in S and X_{S^c} is the complement. The region is a polymatroid — a convex set with special combinatorial structure. The converse (outer bound) matches the inner bound for discrete memoryless MACs, fully characterizing capacity. For Gaussian MACs, the sum-capacity is log2(1 + (sum_i P_i)/N) and is achieved by the orthogonal multiple access of users alone or by non-orthogonal access combined with successive interference cancellation (SIC).

Explainer

The multiple access channel is the canonical multi-user uplink: multiple transmitters sending independent information to a single receiver over a shared noisy channel. The fundamental question is: what is the set of rate tuples (R_1, ..., R_K) that all users can simultaneously achieve with arbitrarily low error probability?

For a discrete memoryless MAC with transition probability p(y|x_1, ..., x_K), the capacity region is the set of rate tuples satisfying:

• For each non-empty subset S of users: sum_{i in S} R_i <= I(X_S; Y | X_{S^c})

where X_S denotes the inputs of users in subset S, and X_{S^c} denotes inputs of the other users. This characterization is both achievable (inner bound, by random coding) and optimal (converse, by information-theoretic counting arguments), so it is the exact capacity region.

The achievability uses a clever coding scheme: random coding over all possible (x_1ⁿ, x_2ⁿ, ..., x_Kⁿ) codeword sequences, with joint typicality decoding. The receiver decodes users sequentially (successive interference cancellation): decode user 1 treating all others as noise, subtract user 1's signal from the received signal, then decode user 2, and so on. The rate constraint for user i when decoded with users in set S decoded before i is precisely I(X_i; Y | X_S), hence the polymatroidal structure.

For the Gaussian MAC, where Y = X_1 + X_2 + ... + X_K + Z with Z ~ N(0, N), the capacity region is characterized by:

• sum_{i in S} R_i <= (1/2) log2(1 + (sum_{i in S} P_i) / (N + sum_{i in S^c} P_i))

for all subsets S. The sum-rate (all users transmit) is (1/2) log2(1 + (sum_i P_i) / N). This is significantly larger than orthogonal multiple access (TDMA, FDMA) which achieves sum-rate (1/K) sum_i (1/2) log2(1 + P_i / N), because non-orthogonal schemes allow concurrent transmission with interference resolved at the receiver.

The capacity region is a polymatroid: a convex polytope with special combinatorial properties. It is invariant under certain transformations and has the monotonicity property that if (R_1, ..., R_K) is in the region, then so is any (R_1', ..., R_K') with R_i' <= R_i for all i. The dominant face (where all constraints are tight) traces the Pareto frontier of rates. Different SIC decoding orders yield different corner points on this frontier; time-sharing (randomizing the order) achieves any point on the dominant face.

The MAC capacity region was the first multi-user capacity problem fully solved and remains the gold standard in network information theory. Its complete characterization motivates the field: other multi-user scenarios (broadcast, interference, relay channels) are either incompletely solved or remain open, revealing gaps in our understanding of multi-user communication. Modern wireless systems (5G NOMA, CDMA) are designed based on these information-theoretic principles to approach MAC capacity limits.