Ferkans — Interactive Telecom Tutor

The MAC: Where Multiple Users Meet One Receiver

The multiple access channel (MAC) is the simplest multiuser channel: $K$ independent transmitters send messages to a single receiver. This models the uplink of both cellular (Chapter 24) and Wi-Fi (Chapter 25) systems. Unlike the single-user channel, whose capacity is a single number, the MAC capacity is a region in $\mathbb{R}^K_+$ — a set of simultaneously achievable rate tuples $(R_1, \ldots, R_K)$ . The shape of this region reveals fundamental trade-offs: one user can increase its rate only at the expense of others, but time-sharing and successive decoding allow all users to operate simultaneously without loss. The MAC capacity region is one of the crown jewels of network information theory — it is one of the few multiuser channels for which the capacity region is known exactly.

MAC Capacity Region Pentagon — Capacity region of the 2-user Gaussian MAC. The pentagon is bounded by individual rate constraints $R_1 \leq C(P_1/N)$ and $R_2 \leq C(P_2/N)$ , and the sum-rate constraint $R_1 + R_2 \leq C((P_1+P_2)/N)$ . The SIC corner points A and B are achievable by successive interference cancellation.

Definition:
Gaussian Multiple Access Channel

The two-user Gaussian MAC is defined by:

$Y = X_1 + X_2 + Z, \quad Z \sim \mathcal{N}(0, N)$

where $X_k$ is the signal from user $k$ with power constraint $E[X_k^2] \leq P_k$ , $k = 1, 2$ . The signals $X_1, X_2$ are independent (no cooperation between transmitters).

The $K$ -user Gaussian MAC generalises to:

$Y = \sum_{k=1}^{K} X_k + Z$

The receiver observes the superposition of all transmitted signals plus noise and must decode all $K$ messages.

The Gaussian MAC differs from the single-user AWGN channel (Chapter 11) only in that the receiver must contend with interference from other users. The key question is how much total rate the channel can support and how it can be divided among users.

,

Theorem: Capacity Region of the Two-User Gaussian MAC

The capacity region of the two-user Gaussian MAC with power constraints $P_1, P_2$ and noise variance $N$ is the set of rate pairs $(R_1, R_2)$ satisfying:

$R_1 \leq \frac{1}{2}\log_2\!\left(1 + \frac{P_1}{N}\right)$

$R_2 \leq \frac{1}{2}\log_2\!\left(1 + \frac{P_2}{N}\right)$

$R_1 + R_2 \leq \frac{1}{2}\log_2\!\left(1 + \frac{P_1 + P_2}{N}\right)$

This region is a pentagon in the $(R_1, R_2)$ plane. The two corner points are:

Corner A (decode user 1 first, then user 2): $R_1 = \frac{1}{2}\log_2\!\left(1 + \frac{P_1}{P_2 + N}\right)$ , $R_2 = \frac{1}{2}\log_2\!\left(1 + \frac{P_2}{N}\right)$
Corner B (decode user 2 first, then user 1): $R_1 = \frac{1}{2}\log_2\!\left(1 + \frac{P_1}{N}\right)$ , $R_2 = \frac{1}{2}\log_2\!\left(1 + \frac{P_2}{P_1 + N}\right)$

The entire dominant face (line segment AB) is achievable by time-sharing between the two SIC decoding orders, and the sum rate $R_1 + R_2 = \frac{1}{2}\log_2(1 + (P_1 + P_2)/N)$ is achieved at every point on this face.

At corner A, user 2 is decoded last (after cancelling user 1's signal) and thus sees an interference-free channel, achieving its single-user capacity. User 1 is decoded first, treating user 2 as noise, and gets a lower rate. The sum rate equals the capacity of a single user with power $P_1 + P_2$ — there is no loss from sharing when SIC is used. This is remarkable: the MAC sum capacity equals the single-user capacity with the total power.

Proof

Achievability: Random coding with SIC

Codebook generation: For each user $k \in \{1,2\}$ , generate $2^{nR_k}$ codewords independently from $\mathcal{N}(0, P_k)$ i.i.d. across $n$ channel uses.

Encoding: User $k$ transmits codeword $\mathbf{x}_k(w_k)$ corresponding to message $w_k$ .

Decoding (SIC, decode user 1 first):

Treat user 2's signal as noise. Decode user 1's message $\hat{w}_1$ from $\mathbf{y} = \mathbf{x}_1(w_1) + \mathbf{x}_2(w_2) + \mathbf{z}$ using joint typicality. Reliable if: $R_1 < \frac{1}{2}\log_2(1 + P_1/(P_2 + N))$
Subtract $\mathbf{x}_1(\hat{w}_1)$ from $\mathbf{y}$ . Decode user 2 from $\mathbf{y} - \mathbf{x}_1(\hat{w}_1) = \mathbf{x}_2(w_2) + \mathbf{z}$ . Reliable if: $R_2 < \frac{1}{2}\log_2(1 + P_2/N)$

This achieves corner point A. Reversing the decoding order achieves corner point B. Time-sharing (fraction $\lambda$ at corner A, fraction $1-\lambda$ at corner B) achieves the entire dominant face.

Converse: Fano inequality

By Fano's inequality, for any sequence of $(2^{nR_1}, 2^{nR_2}, n)$ codes with $P_e^{(n)} \to 0$ :

$nR_1 \leq I(X_1^n; Y^n | X_2^n) + n\epsilon_n$

Since $(X_1, X_2)$ are independent and $Y = X_1 + X_2 + Z$ : $I(X_1^n; Y^n | X_2^n) = h(Y^n | X_2^n) - h(Z^n)$ $= h(X_1^n + Z^n) - h(Z^n) \leq \frac{n}{2}\log_2(2\pi e(P_1 + N)) - \frac{n}{2}\log_2(2\pi e N)$ $= \frac{n}{2}\log_2\!\left(1 + \frac{P_1}{N}\right)$

where the inequality uses the maximum entropy property of the Gaussian. Similarly for $R_2$ .

For the sum rate: $n(R_1 + R_2) \leq I(X_1^n, X_2^n; Y^n) + n\epsilon_n$ $= h(Y^n) - h(Z^n) \leq \frac{n}{2}\log_2\!\left(1 + \frac{P_1 + P_2}{N}\right)$

since $h(Y^n) \leq \frac{n}{2}\log_2(2\pi e(P_1 + P_2 + N))$ by the Gaussian maximum entropy property. $\blacksquare$

Polymatroidal structure

The Gaussian MAC capacity region has a polymatroidal structure: for any subset $\mathcal{S} \subseteq \{1, \ldots, K\}$ ,

$\sum_{k \in \mathcal{S}} R_k \leq \frac{1}{2}\log_2\!\left(1 + \frac{\sum_{k \in \mathcal{S}} P_k}{N}\right)$

This gives $2^K - 1$ constraints. The capacity region is a contra-polymatroid, and its vertices correspond to the $K!$ possible SIC decoding orders. Each vertex achieves the maximum sum rate.

,

Definition:
Fading MAC and Ergodic Capacity

For the fading MAC with channel coefficients $h_1, h_2$ :

$Y = h_1 X_1 + h_2 X_2 + Z$

the ergodic sum capacity with CSI at receivers only is:

$C_{\mathrm{sum}} = E\left[\frac{1}{2}\log_2\!\left(1 + \frac{|h_1|^2 P_1 + |h_2|^2 P_2}{N}\right)\right]$

With CSI at transmitters and receiver (CSIT), the optimal strategy is multi-user water-filling: allocate power to the user with the best instantaneous channel, achieving the multi-user diversity gain. As $K \to \infty$ , the sum capacity scales as $\frac{1}{2}\log_2(\log K)$ (from extreme value theory).

Multi-user diversity in the fading MAC is the information-theoretic foundation for opportunistic scheduling in cellular systems (Chapter 20). The $\log\log K$ scaling was first observed by Knopp and Humblet (1995).

MAC Capacity Region Pentagon

Animated construction of the two-user Gaussian MAC capacity region. The pentagon is drawn constraint by constraint, the two SIC corner points are highlighted, and a sweep along the dominant face shows that the sum rate remains constant for all time-sharing parameters.

The MAC capacity region is a pentagon. The dominant face (line segment connecting the two SIC corners) achieves the sum capacity

\frac{1}{2}\log_2(1 + (P_1 + P_2)/N)

at every point.

Gaussian MAC Capacity Region

Visualise the capacity region of the two-user Gaussian MAC. The pentagon-shaped region shows all achievable rate pairs $(R_1, R_2)$ . The dominant face connects the two corner points corresponding to the two SIC decoding orders. Adjust the power levels $P_1$ , $P_2$ and noise variance $N$ to see how the region changes. Observe that the sum rate (the slope- $(-1)$ tangent line) remains the same along the entire dominant face.

Parameters

User 1 power

P_1

10

User 2 power

P_2

5

Noise variance

N

1

MAC Time-Sharing Animation

Animate the time-sharing between the two SIC decoding orders on the dominant face of the MAC capacity region. As the time-sharing parameter $\lambda$ varies from 0 to 1, the operating point moves from corner A to corner B along the dominant face. The animation shows the corresponding SIC decoding order and the effective rate pair at each frame.

Parameters

User 1 power

P_1

10

User 2 power

P_2

5

Animation frames20

Example: Two-User MAC Capacity Region Computation

Compute the capacity region for a two-user Gaussian MAC with $P_1 = 10$ , $P_2 = 5$ , $N = 1$ .

(a) Find the three rate constraints. (b) Compute the two corner points. (c) Verify that the sum rate is the same at both corners. (d) Compare the sum capacity to TDMA and FDMA.

Solution

Rate constraints

(a) $R_1 \leq \frac{1}{2}\log_2(1 + 10) = 1.73$ bits/c.u. $R_2 \leq \frac{1}{2}\log_2(1 + 5) = 1.29$ bits/c.u. $R_1 + R_2 \leq \frac{1}{2}\log_2(1 + 15) = 2.00$ bits/c.u.

Corner points

(b) Corner A (decode 1 first): $R_1 = \frac{1}{2}\log_2(1 + 10/6) = 0.71$ , $R_2 = \frac{1}{2}\log_2(1 + 5) = 1.29$ .

Corner B (decode 2 first): $R_1 = \frac{1}{2}\log_2(1 + 10) = 1.73$ , $R_2 = \frac{1}{2}\log_2(1 + 5/11) = 0.27$ .

Sum rate verification

(c) Corner A: $0.71 + 1.29 = 2.00$ . Corner B: $1.73 + 0.27 = 2.00$ . Both corners achieve the sum capacity.

Comparison with orthogonal access

(d) TDMA with fraction $\alpha$ for user 1: $R_1 = \frac{\alpha}{2}\log_2(1 + P_1/(\alpha N))$ , $R_2 = \frac{1-\alpha}{2}\log_2(1 + P_2/((1-\alpha)N))$ .

Sum rate (optimised over $\alpha$ ): For $\alpha = 2/3$ : $R_1 = 1.13$ , $R_2 = 0.86$ , sum $= 1.99$ (close to 2.00 but strictly less).

The MAC sum capacity always exceeds TDMA/FDMA: $\frac{1}{2}\log_2(1 + \frac{P_1 + P_2}{N}) \geq \frac{1}{2}\log_2(1 + \frac{P_1}{N}) \cdot \alpha + \ldots$

by the concavity of $\log$ . The gap is small at low SNR and grows at high SNR. $\blacksquare$

Quick Check

In the two-user Gaussian MAC, what is the sum capacity compared to the capacity of a single user with power $P_1 + P_2$ ?

The sum capacity is strictly less due to multiuser interference

The sum capacity equals the single-user capacity with power $P_1 + P_2$

The sum capacity exceeds the single-user capacity due to diversity

The relationship depends on the ratio $P_1/P_2$

Correction:

The sum capacity equals the single-user capacity with power

P_1 + P_2

The sum capacity of the Gaussian MAC is $\frac{1}{2}\log_2(1 + (P_1 + P_2)/N)$ , which is exactly the capacity of a single-user AWGN channel with power $P_1 + P_2$ . This is achieved by successive interference cancellation: after decoding one user and subtracting its signal, the other user sees a clean channel. There is no sum-rate loss from multiple access when optimal decoding is used.

Common Mistake: Assuming Orthogonal Access Is Optimal for the MAC

Mistake:

Assuming that TDMA or FDMA is optimal because it avoids interference — i.e., believing that "each user should have its own slot."

Correction:

The MAC sum capacity $\frac{1}{2}\log_2(1 + (P_1 + P_2)/N)$ strictly exceeds the TDMA/FDMA sum rate for any power split. The gain comes from SIC: after decoding one user and subtracting its signal, the other user sees a clean channel. Orthogonal access wastes multiplexing gain because $\log$ is concave — it is always better to let users transmit simultaneously and use SIC decoding than to time-share.

Historical Note: Discovery of the MAC Capacity Region

1971-1974

The MAC capacity region was established in the early 1970s through the independent work of Ahlswede (1971) and Liao (1972). They showed that random coding with joint typicality decoding achieves the full rate region, while the converse follows from Fano's inequality applied to each subset of users. The Gaussian MAC capacity was determined by Cover and Wyner (1974), completing the picture for the most important special case. The MAC was the first multiuser channel whose capacity region was fully characterised, and it remains a cornerstone of network information theory.

Why This Matters: MAC Capacity and Network Information Theory

The MAC capacity region is the starting point for the full treatment of network information theory in the ITA book. The ITA book develops the $K$ -user MAC capacity region with arbitrary input distributions, the connection to polymatroidal optimization, and the extension to fading channels with CSI. It also covers the MAC-BC duality in full generality, the multiple-access rate region for the MIMO MAC, and the connections to multiuser detection theory.

⚠️Engineering Note

SIC Implementation in Cellular Uplink

The MAC capacity theorem assumes perfect SIC — decode one user exactly, subtract, then decode the next. In practice:

Error propagation: Imperfect decoding of the first user leaves residual interference that degrades subsequent users. 5G NR mitigates this by using powerful LDPC codes per user and selecting the SIC decoding order based on instantaneous received power (strongest first).
Complexity: SIC requires $K$ sequential decoding stages, each involving full LDPC decoding. For $K = 4$ uplink layers at 100 MHz bandwidth, the decoding pipeline must sustain $> 4$ Gbps aggregate throughput. Hardware implementations use parallel Turbo/LDPC decoders with interleaved scheduling.
NOMA (Non-Orthogonal Multiple Access): Power-domain NOMA in the downlink is the BC analogue of SIC in the uplink — the strong user decodes and subtracts the weak user's signal before decoding its own. 3GPP studied NOMA for Release 17 but deferred standardization due to marginal gains over OFDMA in practical multi-cell scenarios.
Grant-free uplink: For mMTC with thousands of devices, grant-free NOMA with SIC is studied as an alternative to scheduled access, but the required SIC complexity scales with the number of active devices.

Practical Constraints

•
SIC decoding order must be determined from received power estimates
•
Residual interference from imperfect cancellation limits practical gains to 10-20% over orthogonal access

📋 Ref: 3GPP TR 38.812 (Study on NOMA)

MAC Capacity Region

The set of all rate tuples $(R_1, \ldots, R_K)$ that can be simultaneously achieved with arbitrarily small error probability on the multiple access channel. For the Gaussian MAC, it is a polymatroid defined by $2^K - 1$ sum-rate constraints.

Successive Interference Cancellation (SIC)

A decoding strategy where users are decoded sequentially: after decoding one user's message, its signal is reconstructed and subtracted from the received signal before decoding the next user. SIC achieves the corner points of the MAC capacity region.

Related: MAC Capacity Region

Polymatroid

A polytope defined by submodular set function constraints. The Gaussian MAC capacity region is a contra-polymatroid: the sum-rate function $f(\mathcal{S}) = \frac{1}{2}\log(1 + \sum_{k \in \mathcal{S}} P_k/N)$ is submodular in $\mathcal{S}$ .

Related: MAC Capacity Region

Multiple Access Channel Capacity

The MAC: Where Multiple Users Meet One Receiver

MAC Capacity Region Pentagon

Definition: Gaussian Multiple Access Channel

Theorem: Capacity Region of the Two-User Gaussian MAC

Achievability: Random coding with SIC

Converse: Fano inequality

Polymatroidal structure

Definition: Fading MAC and Ergodic Capacity

MAC Capacity Region Pentagon

Gaussian MAC Capacity Region

Parameters

MAC Time-Sharing Animation

Parameters

Example: Two-User MAC Capacity Region Computation

Rate constraints

Corner points

Sum rate verification

Comparison with orthogonal access

Quick Check

Common Mistake: Assuming Orthogonal Access Is Optimal for the MAC

Historical Note: Discovery of the MAC Capacity Region

Why This Matters: MAC Capacity and Network Information Theory

SIC Implementation in Cellular Uplink

MAC Capacity Region

Successive Interference Cancellation (SIC)

Polymatroid

Definition:
Gaussian Multiple Access Channel

Definition:
Fading MAC and Ergodic Capacity