Ferkans — Interactive Telecom Tutor

From Single-User to Multiuser

So far in this book, we have studied communication between a single transmitter and a single receiver. But real communication systems — cellular uplink, Wi-Fi, satellite return links — involve multiple transmitters sending independent messages to a common receiver. The fundamental question becomes: what is the set of rate pairs $(R_{1}, R_{2})$ that can be simultaneously achieved with vanishing error probability?

The answer is no longer a single number (the capacity $C$ ) but a region in the rate plane. This is the first instance of a pattern that will recur throughout multiuser information theory: the fundamental limit is a convex set of rate tuples, not a scalar.

The multiple access channel (MAC) is the simplest multiuser channel and also the one where the theory is most complete. We will see that:

The capacity region is a pentagon (for two users) determined by three mutual information inequalities.
Every point in this region is achievable — there is no gap between inner and outer bounds.
The result generalizes beautifully to $K$ users, Gaussian channels, MIMO, and fading.

Definition:
Discrete Memoryless Multiple Access Channel (DM-MAC)

A two-user discrete memoryless multiple access channel (DM-MAC) consists of:

Two finite input alphabets $\mathcal{X}_1$ and $\mathcal{X}_2$ ,
A finite output alphabet $\mathcal{Y}$ ,
A conditional PMF $p(y | x_1, x_2)$ for each $(x_1, x_2, y) \in \mathcal{X}_1 \times \mathcal{X}_2 \times \mathcal{Y}$ .

The channel is memoryless: when used $n$ times,

$p(y^n | x_1^n, x_2^n) = \prod_{i=1}^{n} p(y_i | x_{1,i}, x_{2,i}).$

User $k$ ( $k = 1, 2$ ) has a message $W_k$ uniformly distributed over $\{1, 2, \ldots, 2^{nR_{k}}\}$ , independent of the other user's message. User $k$ 's encoder maps $W_k$ to a codeword $x_k^n(W_k) \in \mathcal{X}_k^n$ . The decoder observes $Y^n$ and produces estimates $(\hat{W}_1, \hat{W}_2)$ .

The key feature is independence: the two encoders cannot cooperate. Each encoder knows only its own message. This constraint is what makes the MAC fundamentally different from a single-user channel with a larger input alphabet $\mathcal{X}_1 \times \mathcal{X}_2$ .

Multiple Access Channel (MAC)

A multiuser channel model with two or more independent transmitters sending messages to a single receiver. The capacity region is the closure of all simultaneously achievable rate tuples.

Related: Capacity Region, Time-Sharing

Definition:
Achievable Rate Pair and Capacity Region

A rate pair $(R_{1}, R_{2})$ is achievable for the DM-MAC if there exists a sequence of $(2^{nR_{1}}, 2^{nR_{2}}, n)$ codes such that the average probability of error

$P_e^{(n)} = \Pr(\hat{W}_1 \neq W_1 \text{ or } \hat{W}_2 \neq W_2)$

tends to zero as $n \to \infty$ .

The capacity region $\mathcal{C}$ of the MAC is the closure of the set of all achievable rate pairs.

Notice that we require both messages to be decoded correctly. A single error event — whether user 1's message or user 2's — counts as a decoding failure.

Capacity Region

The closure of all rate tuples $(R_{1}, \ldots, R_{K})$ that are simultaneously achievable with vanishing probability of error. For the MAC, it is a convex region in $\mathbb{R}_+^K$ described by mutual information inequalities.

Theorem: Capacity Region of the Two-User DM-MAC

The capacity region of the two-user DM-MAC $p(y|x_1, x_2)$ is the closure of the convex hull of all rate pairs $(R_{1}, R_{2})$ satisfying

$R_{1} \leq I(X_1; Y | X_2),$ $R_{2} \leq I(X_2; Y | X_1),$ $R_{1} + R_{2} \leq I(X_1, X_2; Y),$

for some product distribution $p(x_1) p(x_2)$ on $\mathcal{X}_1 \times \mathcal{X}_2$ .

The three inequalities have natural interpretations:

The first says: even if user 2's signal is known (i.e., can be subtracted), user 1 cannot exceed the single-user capacity treating user 2's input as side information.
The second is the symmetric statement for user 2.
The third says: the total throughput cannot exceed the mutual information when we view both users as a single "super-user."

The product distribution constraint $p(x_1)p(x_2)$ reflects the independence of the encoders — they cannot coordinate their inputs. The convex hull (over input distributions) is achieved by time-sharing.

Proof

Converse (outer bound)

We prove that any achievable rate pair must satisfy the three inequalities. Suppose $(R_{1}, R_{2})$ is achievable. By Fano's inequality, for any achievable code:

$nR_{1} = H(W_1) = I(W_1; Y^n) + H(W_1 | Y^n) \leq I(W_1; Y^n) + n\epsilon_n$

where $\epsilon_n \to 0$ . Now we bound $I(W_1; Y^n)$ conditioned on $W_2$ (which determines $X_2^n$ ):

$I(W_1; Y^n | W_2) = \sum_{i=1}^n I(W_1; Y_i | Y^{i-1}, W_2)$ $\leq \sum_{i=1}^n I(W_1, Y^{i-1}; Y_i | W_2) = \sum_{i=1}^n I(X_{1,i}; Y_i | X_{2,i})$

where the last step uses the memoryless property and the fact that $X_{1,i}$ is a function of $W_1$ . Since $W_1$ and $W_2$ are independent, $I(W_1; Y^n) \leq I(W_1; Y^n | W_2)$ . Introducing a time-sharing variable $Q$ uniform on $\{1, \ldots, n\}$ and setting $X_1 = X_{1,Q}$ , $X_2 = X_{2,Q}$ , $Y = Y_Q$ :

$R_{1} \leq I(X_1; Y | X_2, Q) + \epsilon_n.$

The sum-rate bound follows similarly from Fano applied to $(W_1, W_2)$ jointly.

Achievability (sketch)

We defer the full achievability proof to Section 14.2. The key idea is random coding with joint typicality decoding: generate $2^{nR_{1}}$ codewords for user 1 and $2^{nR_{2}}$ codewords for user 2, independently according to their respective input distributions. The decoder looks for a unique pair $(w_1, w_2)$ such that $(x_1^n(w_1), x_2^n(w_2), y^n)$ is jointly typical. The error analysis shows that the three inequalities are sufficient to drive the error probability to zero.

Convex hull and time-sharing

For a fixed product distribution $p(x_1)p(x_2)$ , the achievable region is a pentagon (intersection of three half-planes in $\mathbb{R}_+^2$ ). Different input distributions give different pentagons. The full capacity region is the convex hull of the union of all such pentagons. Time-sharing between different input distributions achieves points in the convex hull.

Formally, if $(R_{1}', R_{2}')$ is achievable with input distribution $p'$ and $(R_{1}'', R_{2}'')$ with $p''$ , then for any $\lambda \in [0,1]$ , $\lambda(R_{1}', R_{2}') + (1-\lambda)(R_{1}'', R_{2}'')$ is achievable by using $p'$ for a fraction $\lambda$ of the time and $p''$ for the rest. $\blacksquare$

,

Definition:
The Pentagonal Region

For a fixed product input distribution $p(x_1)p(x_2)$ , define the rate region $\mathcal{R}(p)$ as the set of all $(R_{1}, R_{2}) \in \mathbb{R}_+^2$ satisfying:

$R_{1} \leq I(X_1; Y | X_2) \triangleq A,$ $R_{2} \leq I(X_2; Y | X_1) \triangleq B,$ $R_{1} + R_{2} \leq I(X_1, X_2; Y) \triangleq C.$

This is the intersection of three half-planes in the first quadrant. When $C < A + B$ (the typical case), the region is a pentagon with five vertices:

$(0, 0), \quad (A, 0), \quad (A, C - A), \quad (C - B, B), \quad (0, B).$

The segment from $(A, C - A)$ to $(C - B, B)$ is the dominant face — it lies on the line $R_{1} + R_{2} = C$ .

When $C \geq A + B$ , the sum-rate constraint is inactive and the region is a rectangle $[0, A] \times [0, B]$ . This happens when the users' inputs provide "complementary" information about the output. In most cases of practical interest, $C < A + B$ and the pentagon is strictly inside the rectangle.

Pentagonal Region

The MAC capacity region for a fixed input distribution, shaped as a pentagon in the $(R_{1}, R_{2})$ plane. The five vertices arise from the intersection of three half-plane constraints: individual rate bounds and a sum-rate bound.

Related: Capacity Region, Dominant Face

Dominant Face

The segment of the MAC capacity region boundary where the sum-rate constraint $R_{1} + R_{2} = I(X_1, X_2; Y)$ is active. Points on the dominant face achieve the maximum sum rate.

Related: Pentagonal Region

The Corner Points and Decoding Order

The two corner points of the dominant face have a beautiful operational interpretation:

Corner point A: $(R_{1}, R_{2}) = (A, C - A) = (I(X_1; Y|X_2),\; I(X_2; Y))$ . Here user 2 is decoded first (treating user 1 as noise), achieving rate $I(X_2; Y)$ . Then user 2's signal is subtracted, and user 1 is decoded interference-free at rate $I(X_1; Y|X_2)$ .

Corner point B: $(R_{1}, R_{2}) = (C - B, B) = (I(X_1; Y),\; I(X_2; Y|X_1))$ . Now user 1 is decoded first (treating user 2 as noise), and then user 2 is decoded interference-free.

The point is that successive cancellation decoding (decode one user, subtract, decode the other) naturally achieves the corner points. The entire dominant face is then achieved by time-sharing between the two decoding orders. We will make this precise in Section 14.2.

Example: The Binary Adder MAC

Consider the binary adder MAC where $\mathcal{X}_1 = \mathcal{X}_2 = \{0, 1\}$ , $\mathcal{Y} = \{0, 1, 2\}$ , and $Y = X_1 + X_2$ (integer addition, no noise). Find the capacity region.

Solution

Compute the mutual information quantities

Let $X_1 \sim \text{Bernoulli}(p_1)$ and $X_2 \sim \text{Bernoulli}(p_2)$ independently. Since the channel is noiseless ( $Y$ is a deterministic function of $(X_1, X_2)$ ), we have $H(Y | X_1, X_2) = 0$ , so

$I(X_1, X_2; Y) = H(Y).$

Evaluate $\ntn{entropy}(Y)$

The output $Y$ takes values $\\{0, 1, 2\\}$ with probabilities:

$\Pr(Y=0) = (1-p_1)(1-p_2), \quad \Pr(Y=1) = p_1(1-p_2) + (1-p_1)p_2, \quad \Pr(Y=2) = p_1 p_2.$

The maximum of $H(Y)$ over $(p_1, p_2)$ is achieved at $p_1 = p_2 = 1/2$ , giving $H(Y) = \log 3 \approx 1.585$ bits.

Describe the capacity region

For $p_1 = p_2 = 1/2$ : $A = B = 1$ bit and $C = \log 3$ bits. The pentagon has corner points $(1, \log 3 - 1) \approx (1, 0.585)$ and $(\log 3 - 1, 1) \approx (0.585, 1)$ .

The capacity region is the convex hull over all $(p_1, p_2)$ . Since the pentagon for $p_1 = p_2 = 1/2$ already contains the pentagons for all other input distributions (by concavity of entropy), the capacity region is exactly this pentagon:

$R_{1} \leq 1, \quad R_{2} \leq 1, \quad R_{1} + R_{2} \leq \log 3.$

The sum rate $\log 3 \approx 1.585$ bits is strictly less than $1 + 1 = 2$ bits. Intuitively, the "collision" when both users send 1 creates ambiguity — the output 1 does not reveal which user sent 1.

MAC Capacity Region Pentagon

Explore the pentagonal capacity region of the two-user DM-MAC. Adjust the three mutual information quantities $A = I(X_1; Y|X_2)$ , $B = I(X_2; Y|X_1)$ , and $C = I(X_1, X_2; Y)$ to see how the shape of the pentagon changes. The corner points of the dominant face and the sum-rate line are highlighted.

Parameters

A = I(X_1; Y|X_2)

1

User 1 single-user rate (with user 2 known)

B = I(X_2; Y|X_1)

1

User 2 single-user rate (with user 1 known)

C = I(X_1, X_2; Y)

1.5

Sum mutual information

Quick Check

For a two-user MAC with $I(X_1; Y|X_2) = 2$ , $I(X_2; Y|X_1) = 1$ , and $I(X_1, X_2; Y) = 2.5$ , what is the maximum achievable sum rate $R_{1} + R_{2}$ ?

$3$ bits per channel use

$2.5$ bits per channel use

$2$ bits per channel use

$1.5$ bits per channel use

Correction:

2.5

bits per channel use

The sum rate is bounded by $I(X_1, X_2; Y) = 2.5$ , which is less than $A + B = 3$ . The sum-rate constraint is active.

Quick Check

Why does the MAC capacity region theorem require a product distribution $p(x_1)p(x_2)$ rather than an arbitrary joint distribution $p(x_1, x_2)$ ?

Product distributions are easier to analyze mathematically

The encoders operate independently and cannot coordinate their inputs

Joint distributions would make the capacity region larger than achievable

Product distributions maximize mutual information

Correction:

The encoders operate independently and cannot coordinate their inputs

Each encoder knows only its own message and has no knowledge of the other encoder's message or input. Therefore, the inputs are necessarily independent: $p(x_1^n, x_2^n) = p(x_1^n) p(x_2^n)$ , which for i.i.d. codebooks gives a product distribution per symbol.

Historical Note: Ahlswede and Liao: The MAC Capacity Region

1971

The capacity region of the multiple access channel was independently determined by Rudolf Ahlswede (1971) and Henry Liao (1972). Ahlswede's proof was for the two-user DM-MAC, while Liao's PhD thesis (under the supervision of Andrew Viterbi at UCLA) treated the general case.

The result was remarkable for its time: it showed that for the MAC, random coding arguments could be extended to multiuser settings, and the resulting capacity region was a convex polytope determined by mutual information quantities. The proof that time-sharing suffices to convexify the region (rather than more sophisticated coding techniques) was established by careful analysis of error events in joint typicality decoding.

Interestingly, the MAC capacity region was determined about a decade before the broadcast channel capacity region for general channels remained open (and is still open today for general non-degraded broadcast channels). The MAC is "easier" because the independent encoding constraint naturally leads to a product distribution, while the broadcast channel requires the more subtle technique of superposition coding.

Common Mistake: The MAC Is Not a Point-to-Point Channel with Larger Input

Mistake:

Treating the MAC as a single-user channel with input alphabet $\mathcal{X}_1 \times \mathcal{X}_2$ and computing $C = \max_{p(x_1, x_2)} I(X_1, X_2; Y)$ .

Correction:

The MAC has independent encoders, so only product distributions $p(x_1)p(x_2)$ are feasible. The capacity is not a single number but a region of rate pairs. The maximum sum rate is $\max_{p(x_1)p(x_2)} I(X_1, X_2; Y)$ , which may be strictly less than $\max_{p(x_1,x_2)} I(X_1, X_2; Y)$ .

Common Mistake: Sum Rate Does Not Characterize the Capacity Region

Mistake:

Describing the MAC capacity by its maximum sum rate alone, e.g., "the MAC capacity is $I(X_1, X_2; Y)$ ."

Correction:

The sum rate is only one of three constraints. The individual rate constraints $R_{1} \leq I(X_1; Y|X_2)$ and $R_{2} \leq I(X_2; Y|X_1)$ also limit the region. Two MACs with the same sum rate can have very different capacity regions (e.g., one symmetric, one highly asymmetric).

Key Takeaway

The MAC capacity region is a convex pentagon in the rate plane, described by three mutual information inequalities (individual rates plus sum rate). The corner points of the dominant face correspond to successive cancellation decoding with different user orderings. Every point in the region is achievable — there is no gap between achievability and converse.

Building the MAC Capacity Pentagon

Step-by-step construction of the MAC capacity region: first the individual rate constraints, then the sum-rate bound that creates the dominant face, and finally the SIC corner points where successive cancellation achieves the boundary.

Channel Model and Capacity Region

From Single-User to Multiuser

Definition: Discrete Memoryless Multiple Access Channel (DM-MAC)

Multiple Access Channel (MAC)

Definition: Achievable Rate Pair and Capacity Region

Capacity Region

Theorem: Capacity Region of the Two-User DM-MAC

Converse (outer bound)

Achievability (sketch)

Convex hull and time-sharing

Definition: The Pentagonal Region

Pentagonal Region

Dominant Face

The Corner Points and Decoding Order

Definition: Time-Sharing

Time-Sharing

Example: The Binary Adder MAC

Compute the mutual information quantities

Evaluate $\ntn{entropy}(Y)$

Describe the capacity region

MAC Capacity Region Pentagon

Parameters

Quick Check

Quick Check

Historical Note: Ahlswede and Liao: The MAC Capacity Region

Common Mistake: The MAC Is Not a Point-to-Point Channel with Larger Input

Common Mistake: Sum Rate Does Not Characterize the Capacity Region

Key Takeaway

Building the MAC Capacity Pentagon

Definition:
Discrete Memoryless Multiple Access Channel (DM-MAC)

Definition:
Achievable Rate Pair and Capacity Region

Definition:
The Pentagonal Region

Definition:
Time-Sharing