Contents / Information Theory / Multiple-Access and Broadcast Channels

Chapter 13

Multiple-Access and Broadcast Channels

Many senders into one receiver, and one sender to many receivers: capacity regions rather than a single number.

Introduction

Many senders into one receiver, and one sender to many receivers: capacity regions rather than a single number.

13.1The Multiple-Access Channel and Its Codes

Single-user information theory answers one question: how many bits per channel use can a sender push to a receiver? The answer is a number, the capacity $C$ , and the whole theory organises itself around comparing a rate $R$ with that number. The moment two independent senders share one channel, the question changes shape. There is no longer one rate to report but a pair $(R_1, R_2)$ , and the two rates trade against each other: the channel is a shared resource, and what one user takes the other cannot have. The object that replaces the number $C$ is a subset of the plane.

Definition 13.1 (Discrete memoryless multiple-access channel). A two-user discrete memoryless multiple-access channel (MAC) consists of two input alphabets $\mathcal{X}_1, \mathcal{X}_2$ , an output alphabet $\mathcal{Y}$ , and a transition law $p(y \mid x_1, x_2)$ . Used $n$ times without feedback it acts as

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

The memorylessness assumption is doing real work here: it says the channel does not remember, and that the two users' symbols interact only within a single time slot. Everything downstream — the single-letter form of the capacity region, the converse, the fact that a pentagon rather than some wilder shape appears — traces back to this product form.

Definition 13.2 (Code, error probability, achievability). A $\bigl(2^{nR_1}, 2^{nR_2}, n\bigr)$ code for the MAC consists of

two message sets $\mathcal{W}_1 = \{1,\dots,2^{nR_1}\}$ and $\mathcal{W}_2 = \{1,\dots,2^{nR_2}\}$ ;
two encoders $f_1 : \mathcal{W}_1 \to \mathcal{X}_1^n$ and $f_2 : \mathcal{W}_2 \to \mathcal{X}_2^n$ , each acting on its own message alone;
one decoder $g : \mathcal{Y}^n \to \mathcal{W}_1 \times \mathcal{W}_2$ .

With $(W_1, W_2)$ uniform and independent, the average error probability is

P_e^{(n)} = \Pr\bigl\{ g(Y^n) \neq (W_1, W_2) \bigr\}.

The pair $(R_1,R_2)$ is achievable if there is a sequence of $\bigl(2^{nR_1}, 2^{nR_2}, n\bigr)$ codes with $P_e^{(n)} \to 0$ . The capacity region $\mathscr{C}$ is the closure of the set of achievable pairs.

Two features of this definition are worth pausing on, because they are exactly what makes the problem multi-user rather than two single-user problems stacked together.

First, the encoders are separate. Here $f_1$ sees $W_1$ and nothing else. If the encoders could confer they would form one super-encoder with input alphabet $\mathcal{X}_1 \times \mathcal{X}_2$ , the channel would be an ordinary point-to-point channel, and the total rate would be the single number $\max_{p(x_1,x_2)} I(X_1,X_2;Y)$ . The separation of encoders is what forces independent input distributions into the answer.

Second, the decoder is joint. It is not required — and generally not able — to recover $W_1$ without also pinning down $W_2$ . A decoder that tried to read $W_1$ while ignoring $W_2$ would be solving a harder problem, and would get a smaller region.

Intuition. Two people speak at once to a single listener in a noisy room. Neither speaker hears the other, so neither can adapt what they say — that is the separate encoders. The listener hears one mixed waveform and must reconstruct both sentences — that is the joint decoder. If the listener could somehow be told what the second speaker said, the first speaker's words would be much easier to pick out; that "genie" version is what the bound $R_1 \le I(X_1; Y \mid X_2)$ measures.

Example 13.3 (The binary adder MAC). Let $\mathcal{X}_1 = \mathcal{X}_2 = \{0,1\}$ and let the channel be noiseless with real addition, $Y = X_1 + X_2 \in \{0,1,2\}$ . How much can the two users send together, and what does the decoder's difficulty look like?

Solution. The map is deterministic: $(0,0)\mapsto 0$ , $(0,1)\mapsto 1$ , $(1,0)\mapsto 1$ , $(1,1)\mapsto 2$ . If $Y=0$ the decoder knows the pair is $(0,0)$ ; if $Y=2$ it knows $(1,1)$ . Only the output $1$ is ambiguous, and it is ambiguous in exactly one direction: the decoder learns the sum but not the split.

Take $X_1, X_2$ independent and uniform. Then $Y$ takes the values $0,1,2$ with probabilities $\tfrac14, \tfrac12, \tfrac14$ , so

H(Y) = \tfrac14\log_2 4 + \tfrac12 \log_2 2 + \tfrac14 \log_2 4 = \tfrac12 + \tfrac12 + \tfrac12 = 1.5 \text{ bits}.

Because the channel is deterministic, $H(Y \mid X_1, X_2) = 0$ and therefore

I(X_1,X_2;Y) = H(Y) - H(Y\mid X_1,X_2) = 1.5 \text{ bits per use}.

Meanwhile $I(X_1;Y\mid X_2) = H(Y \mid X_2) - 0 = 1$ bit, since given $X_2$ the output determines $X_1$ and conversely. So the constraints are $R_1 \le 1$ , $R_2 \le 1$ , $R_1 + R_2 \le 1.5$ .

Both numbers are intelligible. The pair together moves $1.5$ bits per use — strictly more than the $1$ bit one binary user alone could carry, so sharing beats handing the channel to one user; and strictly less than the $2$ bits two private noiseless links would give, so sharing is not free. □□

Pitfall. Uniform independent inputs are not automatically the best choice, and $I(X_1,X_2;Y)$ is not automatically maximised where $I(X_1;Y\mid X_2)$ is. The capacity region is a union over all product distributions $p(x_1)p(x_2)$ , and different corners of the region are typically attained at different input distributions. Computing one mutual information at one convenient distribution gives an achievable point, never the region.

Example 13.4 (The Gaussian MAC). Let $Y = X_1 + X_2 + Z$ with $Z \sim \mathcal{N}(0,N)$ independent of the inputs, under average power constraints $\tfrac1n\sum_i x_{ji}^2 \le P_j$ for $j = 1,2$ . Which three mutual informations does a Gaussian input choice produce?

Solution. Take $X_1 \sim \mathcal{N}(0,P_1)$ and $X_2 \sim \mathcal{N}(0,P_2)$ independent. Conditioned on $X_2$ , the channel $Y - X_2 = X_1 + Z$ is an ordinary Gaussian channel of signal power $P_1$ and noise power $N$ , so

I(X_1;Y \mid X_2) = \tfrac12 \log\Bigl(1 + \tfrac{P_1}{N}\Bigr), \qquad I(X_2;Y \mid X_1) = \tfrac12 \log\Bigl(1 + \tfrac{P_2}{N}\Bigr).

Treating the pair as one input, $Y = (X_1 + X_2) + Z$ where $X_1+X_2$ has power $P_1+P_2$ , so

I(X_1,X_2;Y) = \tfrac12 \log\Bigl(1 + \tfrac{P_1+P_2}{N}\Bigr).

That these are the optimal choices is the usual maximum-entropy argument: among all inputs of given power the Gaussian maximises differential entropy, and here $h(Y \mid X_2)$ and $h(Y)$ are the quantities being maximised while $h(Z)$ is fixed. □□

With $P_1 = P_2 = N = 1$ these read $R_1 \le \tfrac12$ , $R_2 \le \tfrac12$ , $R_1 + R_2 \le \tfrac12 \log_2 3 \approx 0.792$ . The sum bound bites — $0.792 < 1$ — so the two users cannot both sit at their individual ceilings. The shape this carves out is the subject of the next section.

Exercises for §13.1 →

13.2The Capacity Region of the Two-User MAC

Theorem 13.5 (Capacity region of the two-user MAC). For a discrete memoryless MAC $p(y\mid x_1,x_2)$ , let $\mathscr{R}(p_1,p_2)$ be the set of non-negative pairs $(R_1,R_2)$ with

R_1 \le I(X_1;Y \mid X_2), \qquad R_2 \le I(X_2;Y\mid X_1), \qquad R_1 + R_2 \le I(X_1,X_2;Y),

the mutual informations computed under $p_1(x_1)p_2(x_2)p(y\mid x_1,x_2)$ . Then the capacity region is

\mathscr{C} = \overline{\operatorname{conv}} \bigcup_{p_1, p_2} \mathscr{R}(p_1,p_2),

the closed convex hull of the union over all product input distributions.

This is the Ahlswede–Liao theorem. Three separate claims are packed into it, and each needs its own argument: that each $\mathscr{R}(p_1,p_2)$ is achievable, that convexification costs nothing, and that nothing outside is achievable. We take them in that order, but first record the shape of a single $\mathscr{R}(p_1,p_2)$ , since the whole geometry of the MAC lives there.

Proposition 13.6 (The pentagon and its corners). Write $a = I(X_1;Y\mid X_2)$ , $b = I(X_2;Y\mid X_1)$ and $s = I(X_1,X_2;Y)$ for a fixed product distribution. Then $a + b \ge s$ , so $\mathscr{R}(p_1,p_2)$ is a pentagon with vertices

(0,0),\quad (a, 0),\quad (a,\, s-a),\quad (s-b,\, b),\quad (0,b),

whose only non-trivial face is the segment of the line $R_1 + R_2 = s$ joining the two corner points $(a,\,s-a)$ and $(s-b,\,b)$ .

Proof. By the chain rule $s = I(X_1,X_2;Y) = I(X_2;Y) + I(X_1;Y\mid X_2)$ , so $s - a = I(X_2;Y)$ . Now compare $b$ with $s-a$ :

b - (s-a) = I(X_2;Y\mid X_1) - I(X_2;Y) = \bigl[H(X_2\mid X_1) - H(X_2 \mid Y, X_1)\bigr] - \bigl[H(X_2) - H(X_2\mid Y)\bigr].

Independence of the inputs gives $H(X_2 \mid X_1) = H(X_2)$ , so the expression collapses to

b - (s-a) = H(X_2\mid Y) - H(X_2 \mid Y, X_1) = I(X_1; X_2 \mid Y) \ \ge\ 0.

Hence $b \ge s-a$ , i.e. $a + b \ge s$ , and symmetrically $a \ge s - b$ . Consequently each individual cap $R_1 \le a$ , $R_2 \le b$ meets the sum line $R_1+R_2=s$ at an interior point of the positive quadrant, producing five vertices rather than the rectangle that $a+b \le s$ would have given.∎

The quantity $I(X_1;X_2\mid Y)$ appearing in that proof is the exact size of the sum-rate "loss": independent inputs become dependent once you condition on the output, because the output constrains them jointly. When the channel is such that $Y$ reveals nothing linking the two inputs, $I(X_1;X_2\mid Y) = 0$ and the pentagon degenerates to a rectangle — the users do not interfere at all.

Figure 13.7. The capacity pentagon of the Gaussian MAC with

P_1=P_2=N=1

. The individual caps are

\tfrac12

each; the sum cap is

\tfrac12\log_2 3 \approx 0.792

. Corner

A

decodes user 2 last, corner

B

decodes user 1 last, and the dominant face between them is swept out by time sharing.

Achievability

The achievability proof rests on one counting lemma, which we state rather than invoke by name.

Lemma 13.8 (Joint typicality lemma for the MAC). Fix a product distribution $p_1(x_1)p_2(x_2)$ and let $A_\epsilon^{(n)}$ be the jointly typical set for $(X_1,X_2,Y)$ under $p_1p_2p$ . Let $(X_1^n, X_2^n, Y^n)$ be drawn from the true joint law. If $\tilde{X}_1^n \sim \prod_i p_1$ is drawn independently of $(X_2^n, Y^n)$ , then

\Pr\bigl\{ (\tilde{X}_1^n, X_2^n, Y^n) \in A_\epsilon^{(n)} \bigr\} \le 2^{-n\left(I(X_1;Y\mid X_2) - 3\epsilon\right)},

and symmetrically with the roles of the two users exchanged. If $\tilde{X}_1^n$ and $\tilde{X}_2^n$ are both drawn independently of $Y^n$ and of each other, then

\Pr\bigl\{ (\tilde{X}_1^n, \tilde{X}_2^n, Y^n) \in A_\epsilon^{(n)} \bigr\} \le 2^{-n\left(I(X_1,X_2;Y) - 4\epsilon\right)}.

Moreover $\Pr\{(X_1^n,X_2^n,Y^n) \in A_\epsilon^{(n)}\} \to 1$ .

Proof. The bounds are the same counting argument run on different variables. For the first, condition on a typical pair $(x_2^n, y^n)$ and count the sequences $\tilde{x}_1^n$ jointly typical with it: there are at most $2^{n(H(X_1\mid X_2,Y)+\epsilon)}$ of them, each of probability at most $2^{-n(H(X_1)-\epsilon)}$ under $\prod_i p_1$ . The product is

2^{-n\left(H(X_1) - H(X_1\mid X_2,Y) - 2\epsilon\right)} = 2^{-n\left(I(X_1;Y,X_2)-2\epsilon\right)},

and independence of $X_1$ and $X_2$ makes $I(X_1;Y,X_2) = I(X_1;X_2) + I(X_1;Y\mid X_2) = I(X_1;Y\mid X_2)$ . Absorbing the probability that $(x_2^n,y^n)$ is itself atypical gives the stated $3\epsilon$ slack. The second bound is the same count with jointly typical pairs $(\tilde{x}_1^n, \tilde{x}_2^n)$ against $y^n$ , of which there are at most $2^{n(H(X_1,X_2\mid Y)+\epsilon)}$ , each of probability at most $2^{-n(H(X_1,X_2)-2\epsilon)}$ . The final claim is the weak law of large numbers applied to the three empirical entropies.∎

Theorem 13.9 (Achievability of the pentagon). Every rate pair in the interior of $\mathscr{R}(p_1,p_2)$ is achievable.

Proof. Codebook. Generate $2^{nR_1}$ codewords $x_1^n(w_1)$ i.i.d. from $\prod_i p_1$ , and independently $2^{nR_2}$ codewords $x_2^n(w_2)$ i.i.d. from $\prod_i p_2$ . Reveal both codebooks to both encoders and the decoder.

Encoding and decoding. To send $(w_1,w_2)$ the encoders transmit $x_1^n(w_1)$ and $x_2^n(w_2)$ . The decoder declares $(\hat w_1,\hat w_2)$ if it is the unique pair with $\bigl(x_1^n(\hat w_1), x_2^n(\hat w_2), y^n\bigr) \in A_\epsilon^{(n)}$ ; otherwise it declares an error.

Error analysis. By the symmetry of the random code construction we may assume $(W_1,W_2)=(1,1)$ was sent. Decompose the error into $E_0$ , the true triple is not jointly typical; $E_1$ , some $w_1 \ne 1$ is jointly typical with the true $x_2^n(1)$ and $y^n$ ; $E_2$ , the same with the users exchanged; and $E_{12}$ , some pair with $w_1 \ne 1$ and $w_2\ne1$ is jointly typical with $y^n$ . The union bound gives

P_e^{(n)} \le \Pr(E_0) + \Pr(E_1) + \Pr(E_2) + \Pr(E_{12}).

Now $\Pr(E_0)\to 0$ by the last clause of Lemma Joint typicality lemma for the MAC. For $E_1$ , each wrong codeword $x_1^n(w_1)$ is independent of $(x_2^n(1), y^n)$ , so the lemma's first bound applies:

\Pr(E_1) \le 2^{nR_1} \, 2^{-n\left(I(X_1;Y\mid X_2) - 3\epsilon\right)} \to 0 \quad\text{whenever } R_1 < I(X_1;Y\mid X_2) - 3\epsilon,

and symmetrically $\Pr(E_2)\to0$ when $R_2 < I(X_2;Y\mid X_1) - 3\epsilon$ . For $E_{12}$ there are fewer than $2^{n(R_1+R_2)}$ candidate pairs, each independent of $y^n$ , so

\Pr(E_{12}) \le 2^{n(R_1+R_2)}\, 2^{-n\left(I(X_1,X_2;Y)-4\epsilon\right)} \to 0 \quad\text{whenever } R_1+R_2 < I(X_1,X_2;Y)-4\epsilon.

The average error probability over the ensemble therefore vanishes, so at least one code in the ensemble has $P_e^{(n)}\to0$ . Letting $\epsilon \downarrow 0$ gives the whole interior.∎

Notice what error event $E_{12}$ is for. The constraints on $R_1$ and $R_2$ come from confusing one user while the other is known; the sum constraint comes from confusing both at once, an event with no single-user counterpart at all. That is the information-theoretic origin of the pentagon's slanted face.

Proof. Take rational $\lambda = k/m$ first. Given codes of block lengths $n$ and $n'$ achieving the two pairs with error probabilities $\epsilon_n$ and $\epsilon_{n'}$ , build a code of block length $mnn'$ that runs the first code on the initial $knn'$ symbols and the second on the remaining $(m-k)nn'$ . Both users switch at the same pre-agreed time, so no coordination beyond the shared codebooks is needed. Each user's message count is the product of the two stages' counts, so its rate per symbol is $\lambda R_j + (1-\lambda)R_j'$ , and the union bound over the two stages gives error probability at most $\epsilon_n + \epsilon_{n'} \to 0$ . Irrational $\lambda$ follows because the achievable set is closed.∎

Remark. Time sharing can equivalently be folded into the single-letter description: $\mathscr{C}$ is also the union over $p(q)p(x_1\mid q)p(x_2\mid q)$ of the pentagons computed with every mutual information conditioned on $Q$ . Because the union of pentagons is a connected compact subset of $\mathbb{R}^2$ , the Fenchel–Bunt strengthening of Carathéodory's theorem says every point of its convex hull is a mixture of at most two points of the set, so a time-sharing alphabet with $|\mathcal{Q}| \le 2$ suffices.

The converse

Lemma 13.11 (Fano's inequality). Let $W$ be uniform on a set of size $M$ and let $\hat W$ be any estimate of $W$ computed from data, with $P_e = \Pr\{\hat W \ne W\}$ . Then

H(W \mid \hat W) \le 1 + P_e \log M.

Proof. Let $E = \mathbb{1}\{\hat W \ne W\}$ . Expanding $H(E,W\mid \hat W)$ in the two orders gives $H(W\mid \hat W) \le H(E) + H(W \mid \hat W, E)$ , since $H(E \mid W,\hat W)=0$ . Now $H(E)\le 1$ because $E$ is binary. For the second term, $H(W\mid \hat W, E=0)=0$ — knowing there was no error and knowing $\hat W$ determines $W$ — while $H(W \mid \hat W, E=1) \le \log(M-1) \le \log M$ , so averaging gives at most $P_e \log M$ .∎

Theorem 13.12 (Converse for the MAC). If $(R_1,R_2)$ is achievable then it lies in $\mathscr{C}$ .

Proof. Take a sequence of codes with $P_e^{(n)}\to0$ . Fano's inequality gives $H(W_1\mid Y^n) \le 1 + P_e^{(n)}nR_1 =: n\epsilon_{1n}$ with $\epsilon_{1n}\to0$ , and similarly for $W_2$ and for the pair; write $\epsilon_n$ for the largest of the three.

First bound. The messages are independent and $X_1^n$ is a function of $W_1$ , so

nR_1 = H(W_1) = H(W_1 \mid W_2) = I(W_1; Y^n \mid W_2) + H(W_1 \mid Y^n, W_2) \le I(X_1^n; Y^n \mid X_2^n) + n\epsilon_n,

using the data processing inequality along $W_1 - X_1^n - Y^n$ given $W_2$ (hence given $X_2^n$ ) for the first term and Fano for the second. Expand the mutual information and use that $Y_i$ depends only on $(X_{1i},X_{2i})$ :

I(X_1^n;Y^n\mid X_2^n) = \sum_{i=1}^n \Bigl[H(Y_i \mid Y^{i-1}, X_2^n) - H(Y_i \mid Y^{i-1}, X_1^n, X_2^n)\Bigr] \le \sum_{i=1}^n \Bigl[H(Y_i \mid X_{2i}) - H(Y_i \mid X_{1i},X_{2i})\Bigr],

since conditioning reduces entropy in the first term while memorylessness makes the second term exactly $H(Y_i\mid X_{1i},X_{2i})$ . The right side is $\sum_i I(X_{1i};Y_i\mid X_{2i})$ .

The other two bounds follow identically: $nR_2 \le \sum_i I(X_{2i};Y_i\mid X_{1i}) + n\epsilon_n$ , and

n(R_1+R_2) = H(W_1,W_2) \le I(X_1^n,X_2^n;Y^n) + n\epsilon_n \le \sum_i I(X_{1i},X_{2i};Y_i) + n\epsilon_n.

Single-letterisation. Let $Q$ be uniform on $\{1,\dots,n\}$ , independent of everything, and set $X_1 = X_{1Q}$ , $X_2 = X_{2Q}$ , $Y = Y_Q$ . Each of the three sums equals $n$ times the corresponding mutual information conditioned on $Q$ , so $(R_1,R_2)$ lies within $\epsilon_n$ of the pentagon computed under $p(q)p(x_1\mid q)p(x_2\mid q)$ — and $X_{1i}$ and $X_{2i}$ are indeed conditionally independent given $Q=i$ , because $W_1$ and $W_2$ are independent and each encoder sees only its own message. By the remark above that region lies in $\mathscr{C}$ ; letting $n\to\infty$ kills $\epsilon_n$ , and closedness of $\mathscr{C}$ finishes the argument.∎

Exercises for §13.2 →

13.3Coding Strategies: Joint Decoding, SIC and Rate Splitting

The achievability proof used a single joint typicality decoder searching over all $2^{n(R_1+R_2)}$ message pairs. That is optimal and computationally hopeless. The practical question is which points of the region a layered decoder — one that handles users one at a time, with an ordinary single-user decoder at each stage — can reach. The answer is clean, and it explains why the pentagon has the corners it has.

Method 13.13 (Successive interference cancellation).

Decode user 1 from $Y^n$ alone, treating $X_2^n$ as part of the noise. This is single-user decoding over the marginal channel $p(y \mid x_1) = \sum_{x_2} p_2(x_2)\,p(y\mid x_1,x_2)$ .
Reconstruct $x_1^n(\hat w_1)$ and remove its contribution from $y^n$ ; on the Gaussian MAC this is literal subtraction.
Decode user 2 from the cleaned observation, which is now the channel $p(y\mid x_1,x_2)$ with $x_1^n$ known at the decoder.

Theorem 13.14 (SIC attains the corner points). Fix a product distribution $p_1p_2$ and write $s = I(X_1,X_2;Y)$ , $b = I(X_2;Y\mid X_1)$ . Successive interference cancellation with user 1 decoded first achieves every pair in the interior of the rectangle

R_1 < I(X_1;Y), \qquad R_2 < I(X_2;Y\mid X_1),

whose corner is exactly the corner point $(s-b,\,b)$ of the pentagon $\mathscr{R}(p_1,p_2)$ . Reversing the decoding order attains the other corner $(a,\,s-a)$ with $a = I(X_1;Y\mid X_2)$ .

Proof. Step 1 is point-to-point coding over the memoryless channel $p(y\mid x_1)$ with input distribution $p_1$ ; by the single-user channel coding theorem any $R_1 < I(X_1;Y)$ is achievable there with error probability tending to $0$ . On the event that $\hat w_1 = w_1$ , step 3 is point-to-point coding over the memoryless channel $p(y\mid x_1,x_2)$ with the sequence $x_1^n$ known at the decoder; its mutual information at input distribution $p_2$ is $I(X_2;Y\mid X_1)$ , so any $R_2 < I(X_2;Y\mid X_1)$ is achievable. The union bound over the two stage-error events keeps the total vanishing.

For the identification, the chain rule gives

s = I(X_1,X_2;Y) = I(X_1;Y) + I(X_2;Y\mid X_1) = I(X_1;Y) + b,

so $I(X_1;Y) = s-b$ . The achieved corner is therefore $(s-b,\,b)$ , which satisfies $R_1+R_2=s$ with equality and so lies on the dominant face, and which is a vertex because the constraint $R_2\le b$ is also met with equality.∎

So the corner points cost nothing in decoder complexity: two single-user decoders in sequence get there. That is the entire practical appeal of SIC, and it is a genuinely surprising fact — a greedy, one-user-at-a-time procedure lands on the boundary of an optimally, jointly decoded region. The chain rule is the reason, and it is worth seeing that the algebra and the engineering are the same statement: "decode user 1 against interference, then user 2 cleanly" is $I(X_1;Y) + I(X_2;Y\mid X_1)$ .

Pitfall. SIC's guarantee is conditional on the first stage being correct. If $\hat w_1 \ne w_1$ , the subtraction in step 2 injects a full-power wrong codeword instead of removing interference, and the second stage typically fails too. The asymptotic analysis absorbs this into a union bound that vanishes; at finite block length it appears as error propagation, which is why deployed receivers verify the first stage with a CRC before cancelling.

Example 13.15 (SIC on a strong/weak Gaussian MAC). Let $P_1 = 10$ , $P_2 = 1$ , $N = 1$ , and decode user 1 first. Find the rate pair and verify it lies on the sum-rate face.

Solution. In step 1, user 1 competes against $X_2$ plus thermal noise, an effective noise power of $P_2 + N = 2$ :

R_1 = \tfrac12 \log_2\Bigl(1 + \tfrac{10}{2}\Bigr) = \tfrac12\log_2 6 \approx 1.2925.

In step 3, $X_1^n$ has been subtracted and user 2 faces thermal noise only:

R_2 = \tfrac12\log_2\Bigl(1+\tfrac{1}{1}\Bigr) = \tfrac12 \log_2 2 = 0.5.

The sum is $\tfrac12\log_2 6 + \tfrac12\log_2 2 = \tfrac12\log_2 12$ , and the sum-rate bound is $\tfrac12\log_2\bigl(1+\tfrac{P_1+P_2}{N}\bigr) = \tfrac12\log_2 12 \approx 1.7925$ . They agree exactly, as Theorem SIC attains the corner points guarantees — the identity $\log 6 + \log 2 = \log 12$ is the chain rule in disguise.

Note the asymmetry: user 1 ends up strictly below its genie-aided cap $\tfrac12\log_2 11 \approx 1.7297$ , while user 2, decoded last, sits exactly at its cap $0.5$ . □□

That asymmetry is general: the user decoded last always achieves its single-user capacity, and every earlier user pays for the interference of everyone decoded after it. Which corner you land on is therefore a scheduling decision, not a physical one — and it is the reason a fairness criterion, not information theory, picks the operating point in a real system.

Orthogonal access is the other classical option. It sounds strictly worse, since no user reuses another's time or band, but with power control one such scheme lands exactly on the sum-rate face.

Proposition 13.16 (TDMA with power control touches the sum-rate face). On the Gaussian MAC with powers $P_1,P_2$ and noise $N$ , let user 1 transmit alone during a fraction $\alpha$ of the time at power $P_1/\alpha$ , and user 2 during the remaining fraction at power $P_2/(1-\alpha)$ , so both meet their average power constraints. Choosing $\alpha = P_1/(P_1+P_2)$ gives

R_1 + R_2 = \tfrac12\log\Bigl(1 + \tfrac{P_1+P_2}{N}\Bigr),

a point on the dominant face of the capacity region.

Proof. During its own slot each user sees a clean single-user Gaussian channel, so

R_1 = \tfrac{\alpha}{2}\log\Bigl(1 + \tfrac{P_1}{\alpha N}\Bigr), \qquad R_2 = \tfrac{1-\alpha}{2}\log\Bigl(1+\tfrac{P_2}{(1-\alpha)N}\Bigr).

With $\alpha = P_1/(P_1+P_2)$ we get $P_1/\alpha = P_1+P_2$ and $P_2/(1-\alpha) = P_1+P_2$ , so both logarithms equal $\log\bigl(1+\tfrac{P_1+P_2}{N}\bigr)$ and

R_1 + R_2 = \Bigl(\tfrac{\alpha}{2} + \tfrac{1-\alpha}{2}\Bigr)\log\Bigl(1+\tfrac{P_1+P_2}{N}\Bigr) = \tfrac12\log\Bigl(1+\tfrac{P_1+P_2}{N}\Bigr).

Since no achievable pair exceeds the sum bound, this point is on the boundary.∎

Remark. The point just constructed is $\bigl(\alpha C_{\text{tot}},\,(1-\alpha)C_{\text{tot}}\bigr)$ with $C_{\text{tot}} = \tfrac12\log(1+(P_1+P_2)/N)$ , and it sits strictly between the two SIC corners unless one power is zero. Every other choice of $\alpha$ , and plain TDMA without power control, lands strictly inside the region. The lesson is not "orthogonal access is bad" but "orthogonal access is optimal at exactly one operating point, and you must power-control to find it".

Remark. A third strategy, rate splitting (Rimoldi–Urbanke), reaches every point of the dominant face — not only the corners — using single-user decoders alone. User 1 splits its message into two independent layers transmitted simultaneously; the receiver runs three SIC stages, decoding layer $1a$ , then user 2, then layer $1b$ . Sliding the power split between the two layers slides the achieved point continuously along the face. We do not prove this here: the argument is Theorem SIC attains the corner points applied to the equivalent three-user MAC, whose corners project onto the whole face of the two-user pentagon.

Exercises for §13.3 →

13.4The Broadcast Channel

Reverse the arrows. One transmitter, several receivers, each seeing its own noisy version of one transmitted signal. The constraint has moved to the encoder: it must produce a single sequence $X^n$ that simultaneously serves receivers whose channels differ.

Definition 13.17 (Discrete memoryless broadcast channel). A two-receiver broadcast channel consists of an input alphabet $\mathcal{X}$ , output alphabets $\mathcal{Y}_1,\mathcal{Y}_2$ , and a transition law $p(y_1,y_2\mid x)$ , used memorylessly. A $\bigl(2^{nR_0},2^{nR_1},2^{nR_2},n\bigr)$ code consists of one encoder $f:\mathcal{W}_0\times\mathcal{W}_1\times\mathcal{W}_2 \to \mathcal{X}^n$ and two decoders $g_i : \mathcal{Y}_i^n \to \mathcal{W}_0\times\mathcal{W}_i$ . Here $W_0$ is a common message wanted by both receivers and $W_i$ is private to receiver $i$ . The error probability is

P_e^{(n)} = \Pr\bigl\{ g_1(Y_1^n)\ne(W_0,W_1) \ \text{ or } \ g_2(Y_2^n) \ne (W_0,W_2) \bigr\},

and the capacity region is the closure of the achievable triples $(R_0,R_1,R_2)$ .

Intuition. A single radio tower serving listeners with different antennas. It cannot send two different waveforms; it sends one, and each listener extracts what their channel lets them. A good scheme therefore does not chop the signal into disjoint pieces — it layers it, so a weak listener recovers a coarse description while a strong listener recovers the coarse description and a refinement hidden underneath it.

The first structural fact is that the joint law $p(y_1,y_2\mid x)$ carries more information than the problem needs.

Proposition 13.18 (The capacity region depends only on the marginals). The capacity region of a broadcast channel depends on $p(y_1,y_2\mid x)$ only through the two marginal conditionals $p(y_1\mid x)$ and $p(y_2\mid x)$ .

Proof. Fix a code. Receiver $i$ 's error event $\{g_i(Y_i^n)\ne (W_0,W_i)\}$ is a function of the messages and of $Y_i^n$ alone, so its probability is determined by the joint law of $\bigl(W_0,W_1,W_2,Y_i^n\bigr)$ . Since $X^n$ is a deterministic function of the messages, that joint law is determined by $p(y_i\mid x)$ alone. The overall error probability satisfies

\max_i \Pr\{\text{receiver } i \text{ errs}\} \ \le\ P_e^{(n)} \ \le\ \sum_i \Pr\{\text{receiver } i \text{ errs}\},

so $P_e^{(n)}\to0$ for one joint law exactly when it does for any other with the same two marginals. The achievable sets, and hence their closures, therefore coincide.∎

That proposition is why "degraded" can be defined in two different ways without changing any answer.

Definition 13.19 (Physically and stochastically degraded). A broadcast channel is physically degraded if $X - Y_1 - Y_2$ is a Markov chain, that is $p(y_1,y_2\mid x) = p(y_1\mid x)\,p(y_2\mid y_1)$ . It is stochastically degraded if there exists a channel $q(y_2\mid y_1)$ with

p(y_2\mid x) = \sum_{y_1} p(y_1\mid x)\, q(y_2\mid y_1) \quad \text{for all } x, y_2,

i.e. if its marginals match those of some physically degraded channel.

Corollary 13.20 (The two notions have the same capacity region). A stochastically degraded broadcast channel has the same capacity region as the physically degraded channel built from its marginals.

Proof. The two channels have identical marginals by construction, and by Proposition The capacity region depends only on the marginals the region sees nothing else.∎

So we may always assume the Markov chain $X - Y_1 - Y_2$ when proving a converse, even when the physical channel correlates the two noises. That freedom is used without comment in most treatments; Proposition The capacity region depends only on the marginals is what licenses it.

Example 13.21 (When is a binary broadcast channel degraded?). Let $Y_1 = X \oplus Z_1$ and $Y_2 = X \oplus Z_2$ with $Z_i \sim \mathrm{Bern}(p_i)$ and $0 \le p_1 \le p_2 \le \tfrac12$ . Show the channel is stochastically degraded and identify the degrading channel.

Solution. We look for a $\mathrm{BSC}(\beta)$ whose cascade with $\mathrm{BSC}(p_1)$ is $\mathrm{BSC}(p_2)$ . Cascading two binary symmetric channels gives crossover probability

p_1 * \beta = p_1(1-\beta) + \beta(1-p_1) = p_1 + \beta - 2p_1\beta,

so we need $p_1 + \beta - 2p_1\beta = p_2$ , that is

\beta = \frac{p_2-p_1}{1-2p_1}.

Since $p_1 \le p_2 \le \tfrac12$ , the numerator is non-negative and satisfies $p_2 - p_1 \le \tfrac12 - p_1 = \tfrac12(1-2p_1)$ , so $\beta \in [0,\tfrac12]$ is a legitimate crossover probability. Hence $Y_2$ has the distribution of a further BSC applied to $Y_1$ : the channel is stochastically degraded with receiver 1 the stronger. For instance $p_1 = 0.1$ and $p_2=0.2$ give $\beta = 0.1/0.8 = 0.125$ . □□

Example 13.22 (Ordering a Gaussian broadcast channel). Let $Y_1 = X + Z_1$ and $Y_2 = X + Z_2$ with $Z_1\sim\mathcal{N}(0,1)$ , $Z_2\sim\mathcal{N}(0,4)$ , under $\mathbb{E}[X^{2}]\le P = 10$ . Which receiver is stronger, and what are the single-user ceilings?

Solution. Since $N_1 = 1 < 4 = N_2$ , write $Z_2 \stackrel{d}{=} Z_1 + Z'$ with $Z'\sim\mathcal{N}(0,N_2-N_1) = \mathcal{N}(0,3)$ independent of $Z_1$ . Then $Y_2 \stackrel{d}{=} Y_1 + Z'$ , which exhibits the degrading channel explicitly: receiver 1 is the stronger. The ceilings are

\tfrac12\log_2\Bigl(1+\tfrac{P}{N_1}\Bigr) = \tfrac12\log_2 11 \approx 1.7297, \qquad \tfrac12\log_2\Bigl(1+\tfrac{P}{N_2}\Bigr) = \tfrac12\log_2 3.5 \approx 0.9037.

A scalar Gaussian broadcast channel is always degraded, because two noise variances are always comparable. That is exactly what fails in the vector (MIMO) case, where noise covariances need not be ordered — which is why the MIMO broadcast channel needed a different tool, dirty-paper coding, rather than the superposition scheme of this chapter. □□

Remark. The general broadcast channel, with no ordering assumption, is open: its capacity region has been unknown since Cover posed the problem in 1972. The best known inner bound is Marton's region and the best known outer bound is the Nair–El Gamal bound. Degraded, less noisy and more capable channels are the classes where a single-letter answer exists, and the degraded case is the one we solve next.

Exercises for §13.4 →

13.5The Capacity Region of the Degraded Broadcast Channel

Throughout this section receiver 1 is the stronger: $X - Y_1 - Y_2$ is a Markov chain. The answer involves an auxiliary random variable $U$ , which is neither transmitted nor observed by anyone. It is a bookkeeping device that names the coarse layer.

Theorem 13.23 (Capacity region of the degraded broadcast channel). For a degraded broadcast channel with $X-Y_1-Y_2$ , the capacity region is the set of non-negative triples $(R_0,R_1,R_2)$ satisfying

R_1 \le I(X;Y_1 \mid U), \qquad R_0 + R_2 \le I(U;Y_2)

for some joint law of the form $p(u)\,p(x\mid u)\,p(y_1,y_2\mid x)$ , where $U$ may be restricted to alphabets with

|\mathcal{U}| \le \min\bigl\{|\mathcal{X}|,\,|\mathcal{Y}_1|,\,|\mathcal{Y}_2|\bigr\} + 1.

The region is convex, and no separate time-sharing variable is needed.

Three things in that statement deserve comment, because each is a place the result is routinely misquoted.

The common message shares the weak user's budget. Only $R_0+R_2 \le I(U;Y_2)$ appears, not a separate $R_2 \le I(U;Y_2)$ beside it — the latter is implied by the former. A common message must be decoded by both receivers, so it is limited by the worse of them; and once it rides in the coarse layer it is indistinguishable from the weak user's own private bits. Setting $R_0=0$ recovers the familiar two-private-message region.

There is no explicit sum constraint. One might expect $R_0+R_1+R_2 \le I(X;Y_1)$ , since receiver 1 ends up decoding everything. It is implied: the chain rule gives $I(X;Y_1) = I(U;Y_1) + I(X;Y_1\mid U)$ , and degradedness gives $I(U;Y_1)\ge I(U;Y_2)$ — proved as Proposition The strong receiver can decode the cloud in the next section — so $R_0+R_2 \le I(U;Y_2)\le I(U;Y_1)$ , and adding $R_1 \le I(X;Y_1\mid U)$ delivers the sum bound for free.

The cardinality bound is what makes the region computable. Without a bound on $|\mathcal{U}|$ the union runs over an unbounded family and the "single-letter" description would not be a description at all. The bound comes from a standard support-lemma (Carathéodory) argument on the set of conditional distributions $p(x\mid u)$ .

Proposition 13.24 (Convexity without time sharing). The region of Theorem Capacity region of the degraded broadcast channel is convex.

Proof. Let $(R_0,R_1,R_2)$ and $(R_0',R_1',R_2')$ be achieved by auxiliary pairs $(U,X)$ and $(U',X')$ . Let $Q$ be a Bernoulli variable with $\Pr\{Q=1\}=\lambda$ , independent of both, and set $\tilde U = (U_Q, Q)$ and $\tilde X = X_Q$ . The chain $\tilde U - \tilde X - Y_1 - Y_2$ still holds. Since conditioning on $\tilde U$ includes conditioning on $Q$ ,

I(\tilde X;Y_1\mid \tilde U) = \lambda\, I(X;Y_1\mid U) + (1-\lambda)\, I(X';Y_1\mid U') = \lambda R_1 + (1-\lambda)R_1'

when both are at their bounds. For the weak user, $I(\tilde U;Y_2) = I(U_Q,Q;Y_2) \ge I(U_Q;Y_2\mid Q) = \lambda I(U;Y_2) + (1-\lambda)I(U';Y_2)$ . Hence the convex combination of the two triples is achieved by the single auxiliary variable $\tilde U$ : the time-sharing variable has been absorbed into $U$ .∎

Proof. Sketch of the converse. This is a sketch, and we name what it rests on rather than hiding the gap. Given a code with vanishing error probability, define for each time $i$

U_i = \bigl(W_0,\,W_2,\,Y_2^{\,i-1}\bigr).

One checks that $U_i - X_i - Y_{1i} - Y_{2i}$ is a Markov chain, a step that uses physical degradedness $X-Y_1-Y_2$ — legitimate by Corollary The two notions have the same capacity region. Lemma Fano's inequality applied at receiver 2 gives $n(R_0+R_2) \le I(W_0,W_2;Y_2^n) + n\epsilon_n$ , and the chain rule together with the definition of $U_i$ turns the right-hand side into $\sum_i I(U_i;Y_{2i}) + n\epsilon_n$ . At receiver 1, Fano gives $nR_1 \le I(W_1;Y_1^n\mid W_0,W_2) + n\epsilon_n$ , and the step that discards the past outputs $Y_1^{i-1}$ in favour of $U_i$ is the one that again requires degradedness. A time-sharing variable is then absorbed exactly as in Proposition Convexity without time sharing, and the support lemma installs the cardinality bound. The two ingredients are Lemma Fano's inequality and the degradedness Markov chain; nothing else enters.∎

For the Gaussian channel the region can be written down explicitly, and this is the form that matters in practice.

Theorem 13.25 (Capacity region of the Gaussian broadcast channel). Let $Y_i = X + Z_i$ with $Z_i\sim\mathcal{N}(0,N_i)$ , $N_1 < N_2$ , and $\mathbb{E}[X^{2}]\le P$ . The private-message capacity region is the set of pairs

R_1 \le \tfrac12\log\Bigl(1 + \tfrac{(1-\alpha)P}{N_1}\Bigr), \qquad R_2 \le \tfrac12 \log\Bigl(1 + \tfrac{\alpha P}{(1-\alpha)P + N_2}\Bigr)

for some $\alpha \in [0,1]$ , where $\alpha P$ is the power devoted to the weak receiver's layer.

Proof. Achievability is Theorem Superposition coding achieves the degraded region of the next section, specialised to a Gaussian auxiliary $U$ and $X = U+V$ ; it is proved there in full, and the two mutual informations are computed in Example Gaussian superposition from the encoder's side.

Sketch of the converse. This half is a sketch, because it is the one place in the chapter needing a genuinely different tool: the entropy power inequality, stated immediately below. One shows that for any $U$ with $U-X-Y_1-Y_2$ , if $I(U;Y_2)$ equals $\tfrac12\log\bigl(1+\tfrac{\alpha P}{(1-\alpha)P+N_2}\bigr)$ for some $\alpha \in [0,1]$ , then necessarily

h(Y_1\mid U) \ \ge\ \tfrac12\log\bigl(2\pi e\left((1-\alpha)P + N_1\right)\bigr),

a lower bound on a conditional differential entropy. Ordinary concavity and maximum-entropy arguments give upper bounds on entropies, never lower ones; the entropy power inequality is what supplies this direction. Combining it with $h(Y_1\mid X) = \tfrac12\log(2\pi e N_1)$ bounds $I(X;Y_1\mid U)$ by the stated expression. This is Bergmans' converse.∎

Theorem 13.26 (Entropy power inequality). Let $X$ and $Z$ be independent $n$ -dimensional random vectors with densities. Then

2^{\frac{2}{n}h(X+Z)} \ \ge\ 2^{\frac{2}{n}h(X)} + 2^{\frac{2}{n}h(Z)},

with equality if and only if $X$ and $Z$ are Gaussian with proportional covariance matrices.

Remark. We state the entropy power inequality without proof: every known proof — Stam's, via de Bruijn's identity and Fisher information, or Lieb's, via Young's inequality with sharp constants — is a substantial piece of analysis well outside this chapter. It is recorded here because Theorem Capacity region of the Gaussian broadcast channel has no honest converse without it, and a result leaned on by name but never stated is precisely the gap this chapter is written to avoid.

Example 13.27 (Splitting power on a Gaussian broadcast channel). Take $N_1 = 1$ , $N_2 = 4$ , $P = 10$ and $\alpha = \tfrac12$ . Compute the rate pair, and compare it with what time sharing delivers at the same $R_1$ .

Solution. The weak receiver decodes only the coarse layer, and sees the fine layer — power $(1-\alpha)P = 5$ — as extra noise:

R_2 = \tfrac12\log_2\Bigl(1 + \tfrac{5}{5+4}\Bigr) = \tfrac12\log_2\tfrac{14}{9} \approx 0.3187.

The strong receiver removes the coarse layer and reads the fine layer against thermal noise alone:

R_1 = \tfrac12\log_2\Bigl(1+\tfrac{5}{1}\Bigr) = \tfrac12\log_2 6 \approx 1.2925.

Now compare with time sharing between the two single-user ceilings $(1.7297,\,0)$ and $(0,\,0.9037)$ . The chord joining them, evaluated at $R_1 = 1.2925$ , gives

R_2^{\text{TS}} = 0.9037\Bigl(1 - \tfrac{1.2925}{1.7297}\Bigr) \approx 0.2284.

Superposition delivers $0.3187$ against time sharing's $0.2284$ at the same $R_1$ — about a $40\%$ improvement for the weak user at no cost to the strong one. The reason is that superposition uses the full power $P$ in every channel use, while time sharing idles one user's power whenever the other transmits. □□

Figure 13.28. The Gaussian broadcast region for

P=10

N_1=1

N_2=4

. The superposition boundary bulges strictly outside the time-sharing chord joining the two single-user ceilings; the marked point is the

\alpha=\tfrac12

split computed in the example.

Exercises for §13.5 →

13.6Superposition Coding

Superposition coding is the construction that proves Theorem Capacity region of the degraded broadcast channel achievable. The picture is of clouds and satellites: the weak receiver's message selects a cloud, the strong receiver's message selects a satellite point inside that cloud, and the transmitted signal is the satellite.

Method 13.29 (Superposition coding).

Fix $p(u)p(x\mid u)$ . Generate $2^{n(R_0+R_2)}$ cloud centres $u^n(w_0,w_2)$ i.i.d. from $\prod_i p(u)$ .
For each cloud centre, generate $2^{nR_1}$ satellites $x^n(w_0,w_2,w_1)$ i.i.d. from $\prod_i p(x\mid u_i(w_0,w_2))$ — conditionally on that cloud centre.
Transmit the satellite $x^n(w_0,w_2,w_1)$ . Nothing else is sent; the coarse layer is present in every symbol.
The weak receiver decodes the cloud index only, treating the satellite's displacement within the cloud as noise.
The strong receiver decodes the cloud index first, then the satellite inside it.

Proposition 13.30 (The strong receiver can decode the cloud). If $U - X - Y_1 - Y_2$ is a Markov chain, then $I(U;Y_1) \ge I(U;Y_2)$ .

Proof. The sub-chain $U - Y_1 - Y_2$ holds, so $I(U;Y_2\mid Y_1) = 0$ . Expanding $I(U;Y_1,Y_2)$ in the two orders,

I(U;Y_1) = I(U;Y_1) + I(U;Y_2\mid Y_1) = I(U;Y_1,Y_2) = I(U;Y_2) + I(U;Y_1\mid Y_2) \ \ge\ I(U;Y_2),

since $I(U;Y_1\mid Y_2)\ge0$ . This is the data processing inequality: passing $Y_1$ through the degrading channel that produces $Y_2$ cannot increase the information carried about $U$ .∎

This is the hinge of the whole construction. Step 5 asks the strong receiver to do something the weak receiver already does — decode the cloud — and Proposition The strong receiver can decode the cloud says that whatever rate the weak receiver can sustain, the strong one can sustain too. Degradedness is not a convenience here; remove it and step 5 is simply false, which is why the general broadcast channel resists this method.

Theorem 13.31 (Superposition coding achieves the degraded region). For a degraded broadcast channel with $X-Y_1-Y_2$ , every triple with $R_1 < I(X;Y_1\mid U)$ and $R_0 + R_2 < I(U;Y_2)$ is achievable.

Proof. Use the codebook of Method Superposition coding, and suppose $(w_0,w_2,w_1)=(1,1,1)$ was sent.

Weak receiver. It seeks the unique $\hat m = (\hat w_0,\hat w_2)$ with $\bigl(u^n(\hat m), y_2^n\bigr)$ jointly typical. The true cloud centre is jointly typical with $y_2^n$ with probability tending to $1$ . A wrong cloud centre was generated independently of $y_2^n$ , so by the counting argument of Lemma Joint typicality lemma for the MAC it is jointly typical with probability at most $2^{-n(I(U;Y_2)-2\epsilon)}$ . With fewer than $2^{n(R_0+R_2)}$ wrong centres the union bound gives vanishing error whenever $R_0+R_2 < I(U;Y_2)-2\epsilon$ .

Strong receiver, stage 1. The identical argument with $Y_1$ in place of $Y_2$ succeeds whenever $R_0+R_2 < I(U;Y_1)-2\epsilon$ . By Proposition The strong receiver can decode the cloud, $I(U;Y_1)\ge I(U;Y_2)$ , so the condition already imposed by the weak receiver suffices: stage 1 adds no new constraint.

Strong receiver, stage 2. Given the correct centre $u^n(1,1)$ , the receiver seeks the unique $\hat w_1$ with $\bigl(u^n(1,1),\,x^n(1,1,\hat w_1),\,y_1^n\bigr)$ jointly typical. A wrong satellite in the correct cloud was generated i.i.d. from $\prod_i p(x\mid u_i)$ independently of $y_1^n$ given $u^n$ , so it is jointly typical with probability at most $2^{-n(I(X;Y_1\mid U)-3\epsilon)}$ . With fewer than $2^{nR_1}$ such satellites the union bound gives vanishing error whenever $R_1 < I(X;Y_1\mid U)-3\epsilon$ .

Summing the three vanishing terms bounds the average error probability over the random ensemble, so a particular code exists with $P_e^{(n)}\to0$ . Letting $\epsilon\downarrow0$ gives every triple in the interior.∎

Intuition. Superposition coding is the exact dual of successive interference cancellation, and the duality is worth stating precisely. On the MAC, two independent codewords are added by the channel and peeled apart by the decoder. On the degraded BC, two dependent layers are added by the encoder and peeled apart by the strong decoder. In both settings the thing decoded last enjoys a clean channel while the thing decoded first must tolerate everything else as noise — which is why the same chain-rule quantity, $I(\text{first};Y) + I(\text{second};Y\mid\text{first})$ , governs both.

Pitfall. Superposition is not time sharing, and it is not "sending the two messages in different slots". At every channel use the transmitted symbol carries both layers. The weak receiver never gets a clean look at its own layer; it simply operates at a rate low enough that the fine layer's interference is tolerable. Confusing the two is the commonest error in this subject, and the numbers of Example Splitting power on a Gaussian broadcast channel show it is no semantic quibble: superposition gave the weak user $0.3187$ where time sharing gave $0.2284$ .

Example 13.32 (Gaussian superposition from the encoder's side). With $N_1 = 1$ , $N_2 = 4$ , $P = 10$ and $\alpha = \tfrac12$ , write the explicit signal construction and verify each receiver's rate from the definitions.

Solution. Let $U \sim \mathcal{N}(0,\alpha P) = \mathcal{N}(0,5)$ and $V \sim \mathcal{N}(0,(1-\alpha)P) = \mathcal{N}(0,5)$ be independent, and set $X = U+V$ . Then $\mathbb{E}[X^{2}] = 5+5 = 10 = P$ , so the power constraint holds with equality. Concretely: draw $2^{nR_2}$ cloud centres i.i.d. $\mathcal{N}(0,5)$ , and around each draw $2^{nR_1}$ satellites by adding independent $\mathcal{N}(0,5)$ vectors.

Weak receiver. Write $Y_2 = U + (V+Z_2)$ , where $V+Z_2$ has variance $5+4 = 9$ and is independent of $U$ . Hence

R_2 = I(U;Y_2) = \tfrac12\log_2\Bigl(1+\tfrac{5}{9}\Bigr) \approx 0.3187.

Strong receiver. Here $Y_1 = U+V+Z_1$ , and conditioning on $U$ removes it exactly, leaving the channel $V + Z_1$ with signal power $5$ and noise power $N_1 = 1$ :

R_1 = I(X;Y_1\mid U) = h(Y_1\mid U) - h(Y_1\mid X) = \tfrac12\log_2\bigl(2\pi e\cdot 6\bigr) - \tfrac12\log_2\bigl(2\pi e \cdot 1\bigr) = \tfrac12\log_2 6 \approx 1.2925.

The hinge, numerically. Receiver 1's cloud SNR is $\tfrac{5}{5+1} = \tfrac56$ and receiver 2's is $\tfrac{5}{5+4} = \tfrac59$ . Since $\tfrac56 > \tfrac59$ , Proposition The strong receiver can decode the cloud is confirmed here concretely: stage 1 of the strong receiver is strictly easier than the weak receiver's only task. □□

Example 13.33 (Recovering the endpoints). Show that sweeping $\alpha$ across $[0,1]$ in the Gaussian construction recovers the two single-user ceilings, and that each rate is monotone in $\alpha$ .

Solution. At $\alpha=0$ all power goes to the fine layer: $R_1 = \tfrac12\log_2(1+P/N_1) = \tfrac12\log_2 11 \approx 1.7297$ and $R_2 = \tfrac12\log_2 1 = 0$ . At $\alpha=1$ all power goes to the coarse layer: $R_1 = 0$ and $R_2 = \tfrac12\log_2(1+P/N_2) = \tfrac12\log_2 3.5 \approx 0.9037$ . Both agree with the ceilings of Example Ordering a Gaussian broadcast channel.

For monotonicity, the weak user's SNR is

f(\alpha) = \frac{\alpha P}{(1-\alpha)P + N_2},

whose numerator increases in $\alpha$ while its denominator decreases, so $f$ is strictly increasing on $[0,1]$ and therefore so is $R_2 = \tfrac12\log_2(1+f(\alpha))$ . Meanwhile $R_1 = \tfrac12\log_2\bigl(1+(1-\alpha)P/N_1\bigr)$ is strictly decreasing. The two trade monotonically, so $\alpha$ is a genuine one-dimensional dial that traces the boundary once, from one ceiling to the other. □□

Summary.

The MAC capacity region is the closed convex hull of the pentagons $\mathscr{R}(p_1,p_2)$ , one per product input distribution; achievability is joint typicality decoding, and the converse is Fano plus memorylessness plus a time-sharing variable.
SIC reaches the pentagon's corners with two single-user decoders, because $I(X_1,X_2;Y) = I(X_1;Y)+I(X_2;Y\mid X_1)$ is the chain rule. Rate splitting reaches the whole dominant face the same way; TDMA with power control touches it at exactly one point.
A broadcast channel's capacity region depends only on the marginals $p(y_i\mid x)$ , so stochastic and physical degradedness are interchangeable.
The degraded BC region is $R_1 \le I(X;Y_1\mid U)$ , $R_0+R_2 \le I(U;Y_2)$ , achieved by superposition coding; the hinge is $I(U;Y_1)\ge I(U;Y_2)$ , an instance of data processing.
Both Gaussian cases are explicit: a pentagon built from $\tfrac12\log(1+P_j/N)$ on the MAC, and a one-parameter power split $\alpha$ on the BC that strictly dominates time sharing except at the endpoints.

Exercises for §13.6 →

Common Mistakes

Thinking the MAC capacity region is always a rectangle: it is a rectangle only when $I(X_1;X_2\mid Y) = 0$ , i.e. when the output never couples the two inputs. Otherwise Proposition *The pentagon and its corners* forces a strict sum-rate face.
Treating the other user as noise everywhere: that is optimal only for the user decoded *first* under SIC, and only at that one corner. Applying it to both users at once gives a strictly smaller set of pairs.
Confusing the MAC with the broadcast channel: MAC is many senders into one receiver, with separate encoders and a joint decoder; BC is one sender to many receivers, with a joint encoder and separate decoders. The constraint moves from the encoders to the decoders.
Believing correlated codewords enlarge the MAC region: for the memoryless MAC without feedback or common information, independent codebooks plus a time-sharing variable are optimal — that is the content of Theorem *Capacity region of the two-user MAC*. Correlation between the users' codewords helps only in the *different* problems of the MAC with feedback (the Cover–Leung region) or with a common message.
Reading a capacity region as a finite-block-length guarantee: every statement here is asymptotic in $n$ . At finite length there is a dispersion penalty, and deployed systems layer HARQ, power control and scheduling on top.
Expecting a single-letter answer for every broadcast channel: only the degraded, less noisy and more capable classes are solved. The general two-receiver BC capacity region has been open since 1972.
**Adding a separate constraint $R_2 \le I(U;Y_2)$ beside $R_0+R_2 \le I(U;Y_2)$ **: the first is implied by the second. Likewise the apparently missing sum constraint $R_0+R_1+R_2 \le I(X;Y_1)$ is implied, via $I(U;Y_1)\ge I(U;Y_2)$ and the chain rule.
**Forgetting the cardinality bound on $U$ **: without $|\mathcal{U}| \le \min\{|\mathcal{X}|,|\mathcal{Y}_1|,|\mathcal{Y}_2|\}+1$ the "single-letter" region is a union over an unbounded family and cannot be evaluated.
Assuming a MIMO broadcast channel is degraded: two noise *covariances* need not be ordered, so the scalar argument of Example *Ordering a Gaussian broadcast channel* fails. The MIMO BC is solved, but by dirty-paper coding rather than superposition.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

← Distributed Source Coding and Side Information Network Coding and Common Randomness →

Helpful?