Exercises

$C_{1} = 1 - h_b(0.01) = 1 - (-0.01\log 0.01 - 0.99\log 0.99) = 1 - 0.0808 = 0.919$ bits.

$C_{2} = 1 - h_b(0.1) = 1 - (-0.1\log 0.1 - 0.9\log 0.9) = 1 - 0.469 = 0.531$ bits.

$R_{1} = 0.6 \times 0.919 = 0.551$ bits.

$R_{2} = 0.4 \times 0.531 = 0.212$ bits.

$\alpha = 0$: $R_{1} = \frac{1}{2}\log(1 + 20/2) = \frac{1}{2}\log(11) = 1.73$ bits, $R_{2} = 0$.

$\alpha = 1$: $R_{1} = 0$, $R_{2} = \frac{1}{2}\log(1 + 20/8) = \frac{1}{2}\log(3.5) = 0.90$ bits.

$R_{1} = \frac{1}{2}\log(1 + 10/2) = \frac{1}{2}\log(6) = 1.29$ bits.

$R_{2} = \frac{1}{2}\log(1 + 10/(10+8)) = \frac{1}{2}\log(1 + 10/18) = \frac{1}{2}\log(1.556) = 0.32$ bits.

Let $\tilde{Y}_2 = Y_1 + Z_3$ where $Z_3 \sim \mathcal{N}(0, N_2 - N_1)$, independent of everything. Then $\tilde{Y}_2 = X + Z_1 + Z_3$.

Since $Z_1 + Z_3 \sim \mathcal{N}(0, N_2)$, we have $\tilde{Y}_2 | X \sim \mathcal{N}(X, N_2)$, which matches the marginal of $Y_2 | X$. Therefore $X \to Y_1 \to \tilde{Y}_2$ is Markov, and the channel is stochastically degraded.

$p_2 = 0.05 \times 0.92 + 0.95 \times 0.08 = 0.046 + 0.076 = 0.122$.

(Values are approximate; use numerical binary entropy computation.) The boundary is a convex curve above the TDMA line from $(0.714, 0)$ to $(0, 0.470)$.

$S(\alpha) = \frac{1}{2}\log\!\left(1 + \frac{(1-\alpha)P}{N_1}\right) + \frac{1}{2}\log\!\left(1 + \frac{\alpha P}{(1-\alpha)P + N_2}\right).$$

$S(\alpha) = \frac{1}{2}\log\!\left(\frac{P+N_1}{N_1}\right) + \frac{1}{2}\log\!\left(\frac{(1-\alpha)P+N_2}{(1-\alpha)P+N_2}\right)$$Actually, let us rewrite more carefully. At$\alpha = 0$:$S(0) = \frac{1}{2}\log(1 + P/N_1)$. At$\alpha = 1$:$S(1) = \frac{1}{2}\log(1 + P/N_2)$. Since$N_1 < N_2$, we have$S(0) > S(1)$. The maximum sum rate is$\frac{1}{2}\log(1 + P/N_1)$, achieved by giving everything to the strong user.

We can verify that $S'(\alpha) < 0$ for all $\alpha \in (0,1)$ when $N_1 < N_2$. Computing the derivative and simplifying:

$$\frac{dS}{d\alpha} = \frac{-P/2}{(1-\alpha)P + N_1} + \frac{P N_2 / 2}{((1-\alpha)P + N_2)(\alpha P + N_2)} \cdot \frac{1}{\ln 2}.$$

The first term is always larger in magnitude (because $N_1 < N_2$), so $S'(\alpha) < 0$. The sum rate is strictly decreasing in $\alpha$, maximized at $\alpha = 0$.

Set $\frac{1}{2}\log(1 + (1-\alpha)\cdot 10) = \frac{1}{2}\log(1 + 10\alpha / ((1-\alpha)\cdot 10 + 4))$.

This gives $1 + 10 - 10\alpha = 1 + 10\alpha/(14 - 10\alpha)$, which simplifies to $10 - 10\alpha = 10\alpha/(14-10\alpha)$.

Let $u = 10\alpha$. Then $(10-u)(14-u) = 10u$, giving $140 - 10u - 14u + u^2 = 10u$, so $u^2 - 34u + 140 = 0$.

$u = (34 \pm \sqrt{1156 - 560})/2 = (34 \pm \sqrt{596})/2 = (34 \pm 24.41)/2$.

Taking the smaller root: $u = 4.80$, so $\alpha = 0.480$.

$R = \frac{1}{2}\log(1 + 5.20) = \frac{1}{2}\log(6.20) = 1.31$ bits.

$R = \frac{1}{2} \cdot \min(C_{1}, C_{2}) = \frac{1}{2} \cdot C_{2} = \frac{1}{2} \cdot \frac{1}{2}\log(1 + 10/4) = 0.46$ bits.

Wait — with equal time fractions, $R_{1} = \frac{1}{2}C_{1} = 0.87$ and $R_{2} = \frac{1}{2}C_{2} = 0.46$. The equal rate is $\min(0.87, 0.46) = 0.46$ bits.

$R^{\text{SC}} / R^{\text{TDMA}} = 1.31/0.46 = 2.85$.

Superposition coding achieves nearly 3 times the equal rate compared to equal-time TDMA.

Since $U \to X \to Y_1 \to Y_2$ is a Markov chain, the sub-chain $U \to Y_1 \to Y_2$ is also Markov. By the data processing inequality:

$$I(U; Y_2) \leq I(U; Y_1).$$

This is the key property that guarantees the strong user can decode the weak user's cloud center: if the cloud is decodable at rate $R_{2} \leq I(U; Y_2) \leq I(U; Y_1)$, then receiver 1 can certainly decode it.

Given $Y_1$ from BEC($\epsilon_1$), apply a further erasure channel: if $Y_1 = e$, set $Y_2 = e$; if $Y_1 \in \{0,1\}$, erase with probability $p_3 = (\epsilon_2 - \epsilon_1)/(1-\epsilon_1)$.

Then $\Pr(Y_2 = e) = \epsilon_1 + (1-\epsilon_1)p_3 = \epsilon_2$, and $\Pr(Y_2 = x | X = x) = (1-\epsilon_1)(1-p_3) = 1-\epsilon_2$. So $X \to Y_1 \to Y_2$ is Markov.

For the BEC, let $U \sim \text{Bernoulli}(\beta)$ and $X = U \oplus V$ with $V \sim \text{Bernoulli}(\gamma)$ independent. The capacity region is:

$$R_{2} \leq (1-\epsilon_2) \cdot [1 - h_b(\gamma)],$$ $$R_{1} \leq (1-\epsilon_1) \cdot h_b(\gamma),$$

for $\gamma \in [0, 1/2]$. This traces a boundary parameterized by $\gamma$, analogous to $\alpha$ in the Gaussian case.

Actually, for the BEC the capacity region takes a simpler form. The BEC$(\epsilon)$ capacity is $1-\epsilon$. By the degraded BC theorem: $R_{2} \leq (1-\epsilon_2)I(U; X)$ and $R_{1} \leq (1-\epsilon_1)(1 - I(U; X))$.

Setting $r = I(U; X) \in [0,1]$: $R_{2} \leq (1-\epsilon_2)r$ and $R_{1} \leq (1-\epsilon_1)(1-r)$.

The boundary is a straight line! The BEC broadcast channel achieves no gain from superposition over time-sharing.

From $R_{2} = \frac{1}{2}\log(1 + \alpha P / ((1-\alpha)P + N_2))$:

$$2^{2R_{2}} = \frac{P + N_2}{(1-\alpha)P + N_2},$$

so $(1-\alpha)P + N_2 = (P + N_2) \cdot 2^{-2R_{2}}$, giving $(1-\alpha)P = (P+N_2)2^{-2R_{2}} - N_2$.

$R_{1} = \frac{1}{2}\log\!\left(1 + \frac{(P+N_2)2^{-2R_{2}} - N_2}{N_1}\right) = \frac{1}{2}\log\!\left(\frac{(P+N_2)2^{-2R_{2}} - N_2 + N_1}{N_1}\right).$$Since the argument of$\log$is a convex-decreasing function of$R_{2}$(exponential decay plus constants), and$\log$is concave, the composition$R_{1}(R_{2})$ is concave. This confirms the boundary is a convex curve.

User 3 (weakest): decodes only its own layer, treating layers 1 and 2 as noise: $$R_{3} \leq \frac{1}{2}\log\!\left(1 + \frac{\alpha_3 P}{(\alpha_1+\alpha_2)P + N_3}\right).$$

User 2: decodes layer 3 first (SIC), then decodes its own layer treating layer 1 as noise: $$R_{2} \leq \frac{1}{2}\log\!\left(1 + \frac{\alpha_2 P}{\alpha_1 P + N_2}\right).$$

User 1 (strongest): decodes layers 3, 2 by SIC, then its own: $$R_{1} \leq \frac{1}{2}\log\!\left(1 + \frac{\alpha_1 P}{N_1}\right).$$

The capacity region is the set of all $(R_{1}, R_{2}, R_{3})$ satisfying these bounds for some $\alpha_1 + \alpha_2 + \alpha_3 = 1$, $\alpha_k \geq 0$.

Let $(w_1, w_2)$ be the sent message pair. Define:

• $E_0$: $(u^n(w_2), y_2^n) \notin \mathcal{T}_\epsilon^{(n)}$ (true cloud atypical at weak Rx).
• $E_1$: $\exists \tilde{w}_2 \neq w_2$ with $(u^n(\tilde{w}_2), y_2^n) \in \mathcal{T}_\epsilon^{(n)}$ (wrong cloud typical at weak Rx).
• $E_2$: $(u^n(w_2), x^n(w_1, w_2), y_1^n) \notin \mathcal{T}_\epsilon^{(n)}$ (true pair atypical at strong Rx).
• $E_3$: $\exists (\tilde{w}_1, \tilde{w}_2) \neq (w_1, w_2)$ with $(u^n(\tilde{w}_2), x^n(\tilde{w}_1, \tilde{w}_2), y_1^n) \in \mathcal{T}_\epsilon^{(n)}$.

$\Pr(E_0) \to 0$ by the joint AEP.

$\Pr(E_1) \leq 2^{nR_{2}} \cdot 2^{-n(I(U;Y_2) - 3\epsilon)} \to 0$ if $R_{2} < I(U; Y_2) - 3\epsilon$ (packing lemma for the weak user).

$\Pr(E_2) \to 0$ by the conditional AEP.

For $E_3$, we split into three sub-events:

• Wrong cloud, any satellite: probability $\leq 2^{n(R_{1}+R_{2})} \cdot 2^{-n(I(U,X;Y_1)-3\epsilon)} \to 0$ if $R_{1} + R_{2} < I(X; Y_1)$.
• Right cloud, wrong satellite: probability $\leq 2^{nR_{1}} \cdot 2^{-n(I(X;Y_1|U)-3\epsilon)} \to 0$ if $R_{1} < I(X; Y_1 | U)$.

The binding constraints are $R_{2} < I(U; Y_2)$ and $R_{1} < I(X; Y_1 | U)$ (the sum-rate constraint is implied since $I(U;Y_2) \leq I(U;Y_1)$).

By the union bound, $P_e^{(n)} \leq \Pr(E_0) + \Pr(E_1) + \Pr(E_2) + \Pr(E_3) \to 0$ for rates in the interior of the stated region. Time-sharing and taking the closure completes the achievability.

With $\alpha = 1$: $R_{2} = \frac{1}{2}\log(1 + P/N_2)$ and $R_{1} = \frac{1}{2}\log(1 + 0) = 0$.

This is exactly the capacity of the AWGN channel $Y_2 = X + Z_2$ with power $P$ and noise $N_2$.

When $\alpha = 1$, the entire transmitted signal carries the weak user's message — there is no satellite layer. The strong user simply gets no data. The broadcast channel reduces to a point-to-point channel for user 2.

The deeper point: the presence of user 1 in the system design does not inherently degrade user 2's maximum rate. The constraint is only on the total power, not on some shared resource that would be degraded by having two users. This is fundamentally different from the MAC, where adding a user creates interference.

$\frac{dR_{1}}{d\alpha} = \frac{-P}{2\ln 2 \cdot ((1-\alpha)P + N_1)},KATEXPLACEHOLDER0END\frac{dR_{2}}{d\alpha} = \frac{P \cdot N_2}{2\ln 2 \cdot ((1-\alpha)P + N_2)(\alpha P + N_2)} \cdot \frac{P+N_2}{P+N_2}...$$More carefully:$R_{2} = \frac{1}{2}\log\frac{P+N_2}{(1-\alpha)P+N_2}$, so$\frac{dR_{2}}{d\alpha} = \frac{P}{2\ln 2 \cdot ((1-\alpha)P+N_2)}$.

$\frac{dR_{1}^*}{dR_{2}} = \frac{dR_{1}/d\alpha}{dR_{2}/d\alpha} = \frac{-P/((1-\alpha)P+N_1)}{P/((1-\alpha)P+N_2)} = -\frac{(1-\alpha)P+N_2}{(1-\alpha)P+N_1}.$$

The slope is always negative (transferring power from user 1 to user 2 decreases $R_{1}$ and increases $R_{2}$).

At $\alpha = 0$: slope $= -(P+N_2)/(P+N_1)$, which is close to $-1$ for large $P$. At $\alpha = 1$: slope $= -N_2/N_1$, which can be very steep if $N_2 \gg N_1$.

The slope magnitude increases with $\alpha$: near the weak user's corner point, each unit of $R_{2}$ gained costs many units of $R_{1}$ — the tradeoff becomes increasingly unfavorable for the weak user.

For any $U \to X \to (Y_1, Y_2)$:

$$I(U; Y_1) - I(U; Y_2) = [I(X; Y_1) - I(X; Y_1 | U)] - [I(X; Y_2) - I(X; Y_2 | U)]$$

$$= [I(X; Y_1) - I(X; Y_2)] + [I(X; Y_2 | U) - I(X; Y_1 | U)].$$

For the more capable condition, this requires a more delicate argument. The result of El Gamal and Van der Meulen shows that "more capable" implies $I(U; Y_1) \geq I(U; Y_2)$, which is exactly what the achievability proof needs.

The converse uses Fano's inequality and single-letterization. The more capable condition ensures the converse bounds match the achievability region. The capacity region is:

$$R_{2} \leq I(U; Y_2), \quad R_{1} \leq I(X; Y_1 | U),$$

the same as for the degraded BC. Hence superposition coding achieves the capacity region for more capable channels.

BC at $\alpha = 0$: $(R_{1}, R_{2}) = (\frac{1}{2}\log(1+P/N_1), 0)$.

BC at $\alpha = 1$: $(R_{1}, R_{2}) = (0, \frac{1}{2}\log(1+P/N_2))$.

In the dual MAC with noise variance 1 (after normalization), user $k$ has power $\tilde{P}_k$. The MAC corner where user 2 is decoded first: $R_{1} = \frac{1}{2}\log(1 + \tilde{P}_1)$ and $R_{2} = \frac{1}{2}\log(1 + \tilde{P}_2/(1 + \tilde{P}_1))$.

Setting $\tilde{P}_1 = (1-\alpha)P/N_1$ and $\tilde{P}_2 = \alpha P/N_2 \cdot N_2/(N_1)$... the mapping requires careful normalization. The key result is that the two regions coincide under the transformation $\tilde{P}_k = P_k^{\text{BC}} / N_k$ with the sum-power constraint.

The duality means that computing the BC capacity (hard, EPI needed) can be replaced by computing the MAC capacity (easier). This extends to the MIMO case and is the basis for practical algorithms that optimize MIMO broadcast channel beamforming via the dual MAC formulation.

Let $\sigma^2 = \text{Var}(X | U) = \mathbb{E}[\text{Var}(X | U)]$ and $\alpha = 1 - \sigma^2/P$, so $\sigma^2 = (1-\alpha)P$.

$I(U; Y_2) = h(Y_2) - h(Y_2 | U)$.

Upper bound: $h(Y_2) \leq \frac{1}{2}\log(2\pi e(P + N_2))$ (max entropy).

Lower bound on $h(Y_2 | U)$: Given $U = u$, $Y_2 = X + Z_2$ with $\text{Var}(X|U=u) = \sigma_u^2$. By the EPI:

$$e^{2h(Y_2|U=u)} = e^{2h(X+Z_2|U=u)} \geq e^{2h(X|U=u)} + 2\pi e N_2.$$

Since $e^{2h(X|U=u)} \geq 2\pi e \sigma_u^2$ (any distribution's entropy power is at least its variance under the max-entropy property), we get $e^{2h(Y_2|U=u)} \geq 2\pi e(\sigma_u^2 + N_2)$.

Taking expectations and using Jensen's inequality on the concave function $\log$: $h(Y_2|U) \geq \frac{1}{2}\log(2\pi e(\sigma^2 + N_2))$.

Therefore: $I(U; Y_2) \leq \frac{1}{2}\log\frac{P+N_2}{\sigma^2+N_2} = \frac{1}{2}\log(1 + \frac{\alpha P}{(1-\alpha)P+N_2})$.

$I(X; Y_1 | U) = h(Y_1 | U) - h(Z_1)$.

$h(Y_1 | U) \leq \frac{1}{2}\log(2\pi e(\sigma^2 + N_1))$ (Gaussian maximizes entropy).

So $I(X; Y_1 | U) \leq \frac{1}{2}\log\frac{\sigma^2+N_1}{N_1} = \frac{1}{2}\log(1 + \frac{(1-\alpha)P}{N_1})$.

Both bounds match the Gaussian superposition rates. Since the bounds hold for any $(U, X)$, the Gaussian choice is optimal, and the capacity region is exactly as stated.

Define $K-1$ auxiliary variables forming a Markov chain: $U_{K-1} \to U_{K-2} \to \cdots \to U_1 \to X$.

Set $U_{K-1} = X_K$ (outermost cloud), $U_{K-2} = X_K + X_{K-1}$, ..., $U_1 = \sum_{k=2}^K X_k$, and $X = \sum_{k=1}^K X_k$, with $X_k \sim \mathcal{N}(0, \alpha_k P)$ independent.

User $k$'s rate: $R_{k} \leq I(U_{k-1}; Y_k | U_k)$ (with conventions $U_0 = X$, $U_K = \text{const}$).

For Gaussian inputs: $$I(U_{k-1}; Y_k | U_k) = \frac{1}{2}\log\!\left(1 + \frac{\alpha_k P}{\sum_{j<k}\alpha_j P + N_k}\right).$$

User $k$ sees layers $1, \ldots, k-1$ plus noise as interference, totaling $\sum_{j<k}\alpha_j P + N_k$.

The converse extends the two-user argument by applying Fano's inequality to each user and using the EPI recursively to establish Gaussian optimality at each layer. The details follow Bergmans' original argument, generalized to $K$ layers.

Time-sharing with fraction $\theta$ corresponds to a time-sharing auxiliary variable $Q$ with $\Pr(Q=1) = \theta$. When $Q = 1$, transmit for user 1 at power $P$; when $Q = 2$, transmit for user 2.

This is a special case of superposition coding where $U = (Q, W_2)$ and the codebook has a particular product structure. The achievable rates are $R_{1} = \theta C_{1}$ and $R_{2} = (1-\theta)C_{2}$, which traces the time-sharing line.

Since the superposition coding region optimizes over all $p(u, x)$ including this special case, it contains the time-sharing region.

$W(\alpha) = \mu \cdot \frac{1}{2}\log\!\left(1 + \frac{(1-\alpha) \cdot 15}{0.5}\right) + \frac{1}{2}\log\!\left(1 + \frac{15\alpha}{(1-\alpha)\cdot 15 + 8}\right).$$

Setting $W'(\alpha) = 0$:

$$\frac{-\mu \cdot 15}{2\ln 2 \cdot ((1-\alpha)\cdot 15 + 0.5)} + \frac{15 \cdot 8}{2\ln 2 \cdot ((1-\alpha)\cdot 15 + 8)^2} \cdot \frac{1}{1} = 0.$$

Simplifying (after clearing denominators), this gives a quadratic in $\alpha$ that can be solved numerically for each $\mu$.

For $\mu = 0.5$: $\alpha^* \approx 0.72$, favoring the weak user.

For $\mu = 1$: $\alpha^* \approx 0.45$, balanced.

For $\mu = 2$: $\alpha^* \approx 0.15$, favoring the strong user.

The weighted sum rate optimization traces the Pareto boundary of the capacity region. Different weights $\mu$ select different operating points.

Set $U = \text{const}$ (deterministic). Then:

• $R_{1} \leq I(X; Y_1 | U) = I(X; Y_1)$. Maximizing over $p(x)$: $R_{1} \leq C_{1}$.
• $R_{2} \leq I(U; Y_2) = 0$.