Exercises

Since $Y_1 = X$, we have $X \to Y_1 \to Y_2$ trivially (knowing $Y_1 = X$ determines the distribution of $Y_2$). The channel is degraded.

With $U \sim \text{Bernoulli}(q)$ and $X = U \oplus V$ where $V \sim \text{Bernoulli}(r)$: $$R_{2} \leq I(U; Y_2) = H(Y_2) - H(Y_2|U)$$ $$R_{1} \leq I(X; Y_1|U) = H(X|U) = h_b(r)$$

Since $Y_1 = X$, user 1 can decode everything. The capacity region is: $$R_{2} \leq 1 - h_b(p), \quad R_{1} + R_{2} \leq 1$$ User 2 is limited by the BSC capacity, and the total rate cannot exceed the noiseless channel capacity of 1 bit.

Sum capacity equals the single-user capacity to the better user: $$C_{\text{sum}} = \frac{1}{2}\log(1 + P/\sigma^2_{1}) = \frac{1}{2}\log(11) \approx 1.73 \text{ bits/use}$$

With power split $\alpha$: $$R_{1} = \frac{1}{2}\log\left(1 + \frac{(1-\alpha)P}{\sigma^2_{1} + \alpha P}\right) = \frac{1}{2}\log\left(\frac{1 + P}{1 + \alpha P}\right) \geq 1$$ This gives $1 + \alpha P \leq (1+P)/4$, so $\alpha \leq (P - 3)/(4P) = 7/40$. With $\alpha = 7/40$: $$R_{2} = \frac{1}{2}\log\left(1 + \frac{\alpha P}{\sigma^2_{2}}\right) = \frac{1}{2}\log(1 + 7/16) \approx 0.27 \text{ bits/use}$$

Let $V_1 = X$ and $V_2 = U$ in Marton's bound (no common message version). Then $I(V_1; V_2) = I(X; U)$.

$R_{1} < I(X; Y_1) \quad \text{(since } V_1 = X\text{)}KATEXPLACEHOLDER0ENDR_{2} < I(U; Y_2)KATEXPLACEHOLDER1ENDR_{1} + R_{2} < I(X; Y_1) + I(U; Y_2) - I(X; U)$$

Since $U \to X \to Y_1$ is Markov (degraded channel), we have $I(X; Y_1) \geq I(U; Y_1) \geq I(U; Y_2)$ by data processing. The sum-rate bound becomes: $$R_{1} + R_{2} < I(X; Y_1) + I(U; Y_2) - I(X; U)$$ $$= I(X; Y_1) - I(X; U) + I(U; Y_2) = I(X; Y_1 | U) + I(U; Y_2)$$ This is the sum of the individual bounds for superposition coding: $R_{1} \leq I(X; Y_1 | U)$ and $R_{2} \leq I(U; Y_2)$. Hence the Marton sum-rate constraint is not tighter than the individual constraints.

The dual MAC sum rate is: $$C_{\text{sum}} = \max_{P_1+P_2 \leq P} \log\det(\mathbf{I} + P_1 \mathbf{h}_1 \mathbf{h}_1^H + P_2 \mathbf{h}_2 \mathbf{h}_2^H)$$ The $2 \times 2$ matrix has eigenvalues that depend on $\theta$. When $\theta = \pi/2$ (orthogonal channels), the eigenvalues are $P_1$ and $P_2$, giving $C_{\text{sum}} = \log(1+P/2)^2 = 2\log(1+P/2)$.

ZF projects $\mathbf{h}_1$ onto the null space of $\mathbf{h}_2$, giving effective gain $|\mathbf{h}_1^H \mathbf{h}_2^{\perp}|^2 = \sin^2\theta$ for user 1 (and similarly for user 2). ZF sum rate: $$R_{\text{ZF}} = \log(1 + P_1 \sin^2\theta) + \log(1 + P_2 \sin^2\theta)$$ When $\theta = \pi/2$: $\sin^2\theta = 1$, matching DPC. When $\theta < \pi/2$: $\sin^2\theta < 1$ and ZF loses power in the projection, making it strictly suboptimal.

DPC does not waste power projecting away interference — it pre-cancels it. The gap is largest when $\theta$ is small (channels nearly aligned), because ZF must project onto a nearly null direction, wasting most of the power.

With time fractions $\tau_1 + \tau_2 = 1$: $$R_{k}^{\text{TDMA}} = \tau_k \cdot \frac{1}{2}\log(1 + P/\sigma^2_{k})$$ The TDMA region is a straight line connecting $(0, \frac{1}{2}\log(1+P/\sigma^2_{2}))$ and $(\frac{1}{2}\log(1+P/\sigma^2_{1}), 0)$.

The superposition region (degraded BC capacity) is the set of $(R_{1}, R_{2})$ with: $$R_{1} = \frac{1}{2}\log\left(\frac{1+P/\sigma^2_{1}}{1+\alpha P/\sigma^2_{1}}\right), \quad R_{2} = \frac{1}{2}\log(1+\alpha P/\sigma^2_{2})$$ for $\alpha \in [0,1]$. This is a curve, not a line.

The superposition region is convex and contains the TDMA line (TDMA corresponds to $\alpha = 0$ and $\alpha = 1$). For $\sigma^2_{1} \neq \sigma^2_{2}$, the curve strictly lies outside the line for $\alpha \in (0,1)$, by the strict concavity of $\log$. The sum rate gain of superposition over TDMA is especially large when the noise variances differ significantly.

For independently generated $V_1^n(l_1) \sim P_{V_1}^n$ and $V_2^n(l_2) \sim P_{V_2}^n$: $$\Pr((V_1^n(l_1), V_2^n(l_2)) \in \mathcal{T}_\epsilon^{(n)}) \doteq 2^{-nI(V_1; V_2)}$$

The total number of $(l_1, l_2)$ pairs is $2^{n\tilde{R}_1} \cdot 2^{n\tilde{R}_2}$. Expected number of jointly typical pairs: $$\mathbb{E}[N_{\text{typical}}] \doteq 2^{n(\tilde{R}_1 + \tilde{R}_2 - I(V_1; V_2))}$$

When $\tilde{R}_1 + \tilde{R}_2 > I(V_1; V_2) + \delta(\epsilon)$, the expected number of jointly typical pairs grows exponentially. By a second-moment argument (showing $\text{Var}[N_{\text{typical}}] = o(\mathbb{E}[N_{\text{typical}}]^2)$), the probability that at least one jointly typical pair exists approaches 1.

User 1 is encoded first (sees interference from user 2): $$R_{1} = \log\left(\frac{1 + \mathbf{h}_1^H(\mathbf{K}_1 + \mathbf{K}_2)\mathbf{h}_1}{1 + \mathbf{h}_1^H \mathbf{K}_2 \mathbf{h}_1}\right)$$ User 2 is encoded second (DPC removes user 1's interference): $$R_{2} = \log(1 + \mathbf{h}_2^H \mathbf{K}_2 \mathbf{h}_2)$$

In the MAC, decode user 2 first (treating user 1 as noise): $$R_{2} = \log\left(\frac{1 + P_1' |\mathbf{h}_1|^2 + P_2' |\mathbf{h}_2|^2}{1 + P_1' |\mathbf{h}_1|^2}\right)$$ Then decode user 1 (interference-free): $$R_{1} = \log(1 + P_1' |\mathbf{h}_1|^2)$$

Set $P_1'$ such that $\log(1 + P_1' |\mathbf{h}_1|^2) = R_{1}^{\text{BC}}$, and $P_2'$ such that $R_{2}^{\text{MAC}} = R_{2}^{\text{BC}}$. Verify that $P_1' + P_2' = \text{tr}(\mathbf{K}_1) + \text{tr}(\mathbf{K}_2) \leq P$. This requires algebraic manipulation using the matrix inversion lemma and the identity $\det(\mathbf{I} + \mathbf{A}\mathbf{B}) = \det(\mathbf{I} + \mathbf{B}\mathbf{A})$.

With $\mathbf{h}_k = \mathbf{e}_k$, user $k$ receives $y_k = x_k + z_k$. There is no cross-interference, so DPC is unnecessary. Allocate power $P_k$ to user $k$: $$R_{k} = \frac{1}{2}\log(1 + P_k), \quad P_k = 2^{2R_{k}} - 1$$

$\sum_k P_k \leq P \iff \sum_k (2^{2R_{k}} - 1) \leq P \iff \sum_k 2^{2R_{k}} \leq K + P$$Wait — since$\sigma^2 = 1$and each sub-channel has unit noise,$R_{k} = \frac{1}{2}\log(1+P_k)$gives$P_k = 2^{2R_{k}} - 1$. The power constraint becomes$\sum_k 2^{2R_{k}} \leq P + K$. For the convention with$K = n_t$ and noise power 1, this simplifies to the stated region.

For each iteration and each user $k$:

1. Compute $\Phi_k = \mathbf{I} + \mathbf{H}_{\bar{k}}^H \mathbf{K}_{\bar{k}} \mathbf{H}_{\bar{k}}$
2. SVD of $\Phi_k^{-1/2} \mathbf{H}_{k}^{H} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^H$
3. Water-fill: $P_{k,i} = [\mu - \sigma_i^{-2}]_+$ with $\mu$ chosen so $\sum_i P_{k,i} = P/2$
4. Update $\mathbf{K}_k = \mathbf{V} \text{diag}(P_{k,1}, \ldots) \mathbf{V}^H$

Run until the sum rate changes by less than $10^{-6}$ between iterations. Typical convergence: 10-30 iterations. The result is the MAC sum capacity, which by duality equals the BC DPC sum rate.

With random channels at $\text{SNR} = 20$ dB, the sum capacity is typically 12-15 bits/channel use for $n_t = 4, n_r = 2$. The reader should verify that different initializations converge to the same value (global optimum).

If $X \to Y_1 \to Y_2$ is Markov, then for any $U \to X$: $U \to X \to Y_1 \to Y_2$ is also Markov. By the data processing inequality: $I(U; Y_1) \geq I(U; Y_2)$. Hence $Y_1$ is less noisy.

Consider $Y_1 = X \oplus Z_1$ (BSC$(0.1)$) and $Y_2$ obtained by erasing $X$ with probability 0.3 (BEC$(0.3)$). For this channel, $I(U; Y_1) \geq I(U; Y_2)$ for all auxiliary $U$ (since the BSC capacity $1 - h_b(0.1) \approx 0.531$ exceeds the BEC capacity $0.7$, and this ordering persists for all input distributions). However, $Y_2$ cannot be obtained by processing $Y_1$ — the BEC output contains erasure symbols that have no counterpart in the BSC output. Hence the channel is not degraded.

The Lagrangian for the BC sum-rate problem includes a power constraint multiplier $\mu$ and the KKT stationarity condition relates $\mathbf{K}_k$ to the channel matrices and noise covariances.

Choose $\tilde{\mathbf{N}}_k$ to make the KKT conditions of the enhanced (degraded) channel identical to those of the original. This is always possible because reducing noise can only increase capacity, and the specific reduction is chosen to preserve the optimal operating point.

The enhanced channel is degraded, so superposition coding is optimal. The capacity region of the enhanced channel is at least as large as the original (less noise). But the optimal DPC point is preserved, so the enhanced channel converse matches the DPC achievable rate.

The sum rate is maximized by giving all power to user 1: $$R_{\text{sum}} = \frac{1}{2}\log(1 + P/\sigma^2_{1}) = \frac{1}{2}\log(21) \approx 2.19 \text{ bits/use}$$

With power fractions $\alpha_3 + \alpha_2 + \alpha_1 = 1$: $$R_{3} = \frac{1}{2}\log(1 + \alpha_3 P/\sigma^2_{3})$$ $$R_{2} = \frac{1}{2}\log\left(\frac{1 + (\alpha_2+\alpha_3)P/\sigma^2_{2}}{1 + \alpha_3 P/\sigma^2_{2}}\right)$$ $$R_{1} = \frac{1}{2}\log\left(\frac{1 + P/\sigma^2_{1}}{1 + (\alpha_2+\alpha_3)P/\sigma^2_{1}}\right)$$

The capacity region depends on $P_{Y_1, Y_2 | X}$, not just the marginals. Even with $p_1 < p_2$, if $Z_1$ and $Z_2$ are correlated, the channel may or may not be degraded.

If $Z_2 = Z_1 \oplus Z'$ where $Z' \sim \text{Bernoulli}(q)$ is independent, then $Y_2 = Y_1 \oplus Z'$ and the channel is degraded with $p_2 = p_1 * q$. Superposition is optimal.

If $Z_1 = Z_2$ (perfectly correlated noise), then $Y_1 \neq Y_2$ only when the noise flips differently — but with identical noise, $Y_1 = Y_2$ whenever $Z_1 = Z_2 = 0$ and $Y_1 \neq Y_2$ requires $Z_1 \neq Z_2$. With $Z_1 = Z_2$ always, $Y_1 = Y_2$, which is a degenerate case. For intermediate correlations, the channel may be non-degraded, and Marton's bound may strictly improve on superposition.

The null space of $\mathbf{h}_2^H$ is spanned by $\{[1, 1, 0]^T - [1,0,1]^T \cdot \langle \mathbf{h}_2, [1,1,0]^T\rangle / \|\mathbf{h}_2\|^2 \cdot \mathbf{h}_2, \ldots\}$. More directly: $\mathbf{w}_1$ must satisfy $\mathbf{h}_2^H \mathbf{w}_1 = 0$ and maximize $|\mathbf{h}_1^H \mathbf{w}_1|^2$. Using projection: $\mathbf{w}_1 = (\mathbf{I} - \mathbf{h}_2 \mathbf{h}_2^H / \|\mathbf{h}_2\|^2) \mathbf{h}_1$, normalized.

$\mathbf{h}_1^H \mathbf{h}_2 = (1 + 0 + 0)/2 = 1/2$, so $|\mathbf{h}_1^H \mathbf{h}_2|^2 / (\|\mathbf{h}_1\|^2 \|\mathbf{h}_2\|^2) = 1/4$. Effective gain: $g_k = \|\mathbf{h}_k\|^2 (1 - |\mathbf{h}_1^H \mathbf{h}_2|^2 / (\|\mathbf{h}_1\|^2 \|\mathbf{h}_2\|^2)) = 1 \cdot (1 - 1/4) = 3/4$.

With equal power $P/2 = 5$ per user: $$R_{\text{ZF}} = \log(1 + 5 \cdot 3/4) + \log(1 + 5 \cdot 3/4) = 2\log(19/4) \approx 4.50 \text{ bits/use}$$

For encoding order $(1, 2)$ with covariances $\mathbf{K}_1, \mathbf{K}_2$: $$R_{1} = \log\frac{1 + \mathbf{h}_1^H(\mathbf{K}_1+\mathbf{K}_2)\mathbf{h}_1/\sigma^2_{1}}{1 + \mathbf{h}_1^H \mathbf{K}_2 \mathbf{h}_1/\sigma^2_{1}}$$ $$R_{2} = \log(1 + \mathbf{h}_2^H \mathbf{K}_2 \mathbf{h}_2/\sigma^2_{2})$$

Choose $\tilde{\sigma^2}_1 \leq \sigma^2_{1}$ and $\tilde{\sigma^2}_2 \leq \sigma^2_{2}$ such that the enhanced MISO BC is equivalent to a degraded scalar BC in the space spanned by $\mathbf{h}_1$ and $\mathbf{h}_2$. The enhancement parameters are determined by the KKT conditions of the original optimization.

The degraded enhanced channel's converse (superposition is optimal) gives an outer bound that matches the DPC inner bound of the original channel, establishing $C_{\text{BC}} = \mathcal{R}_{\text{DPC}}$.