Exercises

$Y_1 = X_1 + Z_1$, $Y_2 = X_2 + Z_2$ — two independent AWGN channels. Capacity region: $R_{1} \leq \frac{1}{2}\log(1+P_1)$, $R_{2} \leq \frac{1}{2}\log(1+P_2)$ (rectangle).

$Y_1 = X_1 + X_2 + Z_1$, $Y_2 = X_1 + X_2 + Z_2$ — a MAC at each receiver. Each receiver decodes both messages. The capacity region is the intersection of two MAC regions. With Gaussian inputs: $R_{1} \leq \frac{1}{2}\log(1+P_1)$, $R_{2} \leq \frac{1}{2}\log(1+P_2)$, $R_{1} + R_{2} \leq \frac{1}{2}\log(1+P_1+P_2)$. The sum-rate constraint binds, making the region strictly smaller than the no-interference rectangle.

Each user achieves $R_{k} = \frac{1}{2}\log(1+P/(aP+1))$. At high SNR, $R_{k} \approx \frac{1}{2}\log(1/a)$ (constant, independent of $P$). Sum DoF from TIN: $0$ (no scaling with $\log P$) when $a$ is constant. But this is only correct for $a$ that does not scale with $P$.

With optimal rate splitting (Etkin-Tse-Wang), the sum rate scales as $C_{\text{sum}} \approx \log P + O(1)$. The sum DoF is $\text{DoF}_{\text{sum}} = 1$ for the two-user symmetric IC with fixed $a$ — each user gets $1/2$ DoF. This is achieved by HK with half the power in the common part and half in the private part.

Nodes: $\{S, R_1, R_2, D\}$. Cuts $(\Omega, \Omega^c)$ with $S \in \Omega, D \in \Omega^c$:

1. $\{S\}$ vs. $\{R_1, R_2, D\}$
2. $\{S, R_1\}$ vs. $\{R_2, D\}$
3. $\{S, R_2\}$ vs. $\{R_1, D\}$
4. $\{S, R_1, R_2\}$ vs. $\{D\}$ Four cuts total.

$R \leq \min_{i=1,\ldots,4} I(X_\Omega; Y_{\Omega^c} | X_{\Omega^c})$. Cut 1 bounds the source's total output; cut 4 bounds the total input to the destination. Cuts 2 and 3 bound intermediate links.

If the Zhang-Yeung inequality were a consequence of Shannon-type inequalities, then every vector in the polymatroidal cone $\Gamma_4$ would satisfy it. But there exist vectors $\mathbf{h} \in \Gamma_4$ that violate the Zhang-Yeung inequality (they satisfy all Shannon-type inequalities but not ZY). Therefore ZY is not derivable from Shannon's axioms.

$\Gamma_4^* \subsetneq \Gamma_4$: the true entropy region for four variables is strictly smaller than the polymatroidal region. This means Shannon-type inequalities are insufficient to characterize all entropy relationships for $n \geq 4$ variables.

1. Which capacity? MIMO BC with perfect CSIT (dirty paper coding) or with imperfect/no CSIT?
2. What SNR regime? 95% of capacity at 30 dB is impressive; 95% at 0 dB less so.
3. How is 95% measured? Ratio of rates? Ratio of sum rates? Per-user or sum?
4. Complexity? DPC is the capacity-achieving scheme but has exponential complexity. A practical scheme at 95% with polynomial complexity is highly valuable.
5. Number of users and antennas? The gap between practical schemes and DPC typically grows with $K/M$ (users per antenna).

$R_{k}^{\text{TIN}} = \frac{1}{2}\log(1 + 10/(0.5 \cdot 10 + 1)) = \frac{1}{2}\log(1 + 10/6) = \frac{1}{2}\log(2.67) \approx 0.71$ bits. Sum rate: $2 \times 0.71 = 1.41$ bits.

Each receiver decodes both messages (MAC). Sum rate at receiver 1: $\frac{1}{2}\log(1 + P_1 + aP_2) = \frac{1}{2}\log(1 + 10 + 5) = \frac{1}{2}\log(16) = 2.0$ bits. Sum rate at receiver 2 (symmetric): 2.0 bits. Capacity region constraint: sum rate $\leq 2.0$ bits. But individual rates are also constrained: $R_{1} \leq \frac{1}{2}\log(1+P_1) = \frac{1}{2}\log(11) = 1.73$ and $R_{2} \leq \frac{1}{2}\log(1+aP_2/(P_1+1)) = \frac{1}{2}\log(1+5/11) = 0.30$ (treating user 1 as noise for user 2's private rate). Full decoding is better than TIN here but requires both receivers to decode both messages.

The ETW result says the capacity is within 1 bit of the outer bound. The outer bound (genie-aided) gives sum rate $\leq \frac{1}{2}\log(1+P+aP) + \frac{1}{2}\log(1+P/(aP+1)) \approx 2.0 + 0.71 = 2.71$. The ETW inner bound gives sum rate $\geq 2.71 - 1 = 1.71$. So the sum capacity is between 1.71 and 2.71 bits.

Cut 1: $\frac{1}{2}\log(1 + P_S/\sigma^2_{R} + P_S/\sigma^2_{D}) = \frac{1}{2}\log(1+10+10) = \frac{1}{2}\log(21) = 2.18$ bits. Cut 2: $\frac{1}{2}\log(1 + (\sqrt{P_S}+\sqrt{P_R})^2/\sigma^2_{D}) = \frac{1}{2}\log(1+(\sqrt{10}+\sqrt{10})^2) = \frac{1}{2}\log(41) = 2.70$ bits. Cut-set: $\min(2.18, 2.70) = 2.18$ bits.

DF requires the relay to decode: $R_{\text{DF}} = \min(\frac{1}{2}\log(1+P_S/\sigma^2_{R}), \frac{1}{2}\log(1+(\sqrt{P_S}+\sqrt{P_R})^2/\sigma^2_{D}))$ $= \min(\frac{1}{2}\log(11), \frac{1}{2}\log(41)) = \min(1.73, 2.70) = 1.73$ bits.

CF: the relay quantizes $Y_R$ and forwards. The rate is approximately the cut-set bound minus $1/2$ bit: $R_{\text{CF}} \approx 2.18 - 0.5 = 1.68$ bits. In this case, DF ($1.73$) slightly outperforms CF ($1.68$) because the source-relay link is good ($\text{SNR}_{SR} = 10$). The cut-set gap is $2.18 - 1.73 = 0.45$ bits.

For independent variables: $I(X_3;X_4) = 0$, $I(X_1;X_2) = 0$, $I(X_1;X_3,X_4) = 0$, $I(X_3;X_4|X_1) = 0$, $I(X_3;X_4|X_2) = 0$. The inequality becomes $0 \leq 0 + 0 + 0 + 0 = 0$, which holds with equality.

For independent variables, the ZY inequality is trivially satisfied. The inequality becomes non-trivial (strictly constraining) only when the variables have complex dependencies, which is precisely the setting of network coding and multi-terminal problems.

$C_{\text{comm}} = \frac{1}{2}\log(1 + \text{SNR}_{c}) = \frac{1}{2}\log(101) \approx 3.33$ bits.

CRB $= \sigma^2_{s} / (nP_s)$ where $P_s$ is the power allocated to sensing. For CRB $\leq 0.01$ with $\sigma^2_{s} = P/\text{SNR}_{s} = P/10$: $P_s \geq \sigma^2_{s} / (n \cdot 0.01)$. For $n = 100$: $P_s \geq P/(10 \cdot 100 \cdot 0.01) = P/10$.

Communication power: $P_c = P - P_s = 0.9P$. Rate with sensing: $R = \frac{1}{2}\log(1 + 0.9 \cdot \text{SNR}_{c}) = \frac{1}{2}\log(1+90) \approx 3.26$ bits. Rate loss: $\Delta \approx 3.33 - 3.26 = 0.07$ bits. The sensing penalty is modest when the sensing SNR is reasonable and the blocklength is moderate.

Set $P_p = \min(P, 1/a)$, $P_c = P - P_p$. The private message creates interference $aP_p \leq 1$ at the unintended receiver — at most the noise level.

Each receiver decodes the common part of both users (MAC) and then the private part. Private rate: $R_{p} = \frac{1}{2}\log(1 + P_p/(aP_p + 1)) \geq \frac{1}{2}\log(1 + P_p/2)$ (since $aP_p \leq 1$). Common rate: $R_{c} = \frac{1}{2}\log(1 + aP_c/(aP_p + 1))$.

The outer bound (genie-aided, providing the interference to the receiver) gives $R_{k} \leq \frac{1}{2}\log(1 + P + aP)$. The gap is: $\frac{1}{2}\log(1+P+aP) - (R_{c} + R_{p}) \leq \frac{1}{2}\log(2 \cdot \text{const}) \leq 1$ bit. The detailed calculation (bounding each cut) shows the gap is at most 1 bit for all values of $a$ and $P$.

$C = \max_{P_{X_S, X_R}} \min\!\left(I(X_S; Y_R | X_R), I(X_S, X_R; Y_D)\right)$.

The relay fully decodes $W$ from $Y_R^n$ (possible because $Y_R$ is a better version of $Y_D$). It re-encodes and cooperates with the source in the next block using block Markov coding. The destination decodes using backward decoding. The achievable rate is $\min(I(X_S; Y_R | X_R), I(X_S, X_R; Y_D))$.

By degradedness, $I(X_S^n; Y_D^n | X_R^n) \leq I(X_S^n; Y_R^n | X_R^n)$, so the cut-set bound simplifies to $R \leq \min(I(X_S; Y_R | X_R), I(X_S, X_R; Y_D))$ after single-letterization. This matches the DF rate, establishing capacity.

Does the paper contain a converse proof (outer bound) that matches the inner bound? If only an achievability is proved, the result is an inner bound, not the capacity. Look for a section titled "Converse" or "Outer Bound" and verify it uses Fano's inequality or an equivalent tool.

What CSI is assumed at each node? Perfect CSIT, perfect CSIR, no CSI? Is the CSI acquisition cost accounted for? If perfect CSIT is assumed, the result may not apply to systems with realistic CSI acquisition.

If the capacity expression involves a maximization over input distributions, has the paper proven which distribution is optimal? For Gaussian channels, Gaussian input optimality must be established (not assumed). Check for explicit reference to the entropy power inequality, maximum entropy property, or the worst-case noise lemma.

Antenna $m$ at position $x_m = m d$ (with $d = \lambda/2$, $m = -(M-1)/2, \ldots, (M-1)/2$). Distance: $r_m = \sqrt{r^2 + x_m^2 - 2r x_m \sin\theta}$.

$r_m \approx r - x_m \sin\theta + \frac{x_m^2 \cos^2\theta}{2r}$. The first two terms give the far-field (planar wavefront) model. The third term is the quadratic phase correction (spherical wavefront).

The quadratic term is negligible when $\frac{x_{\max}^2}{2r} \ll \lambda$, i.e., $r \gg \frac{(Md/2)^2}{2\lambda} = \frac{M^2\lambda}{8} \cdot \frac{1}{\lambda} = \frac{M^2\lambda}{8}$. More precisely, the Fraunhofer distance is $r_F = \frac{2D^2}{\lambda}$ where $D = (M-1)d \approx M\lambda/2$ is the array aperture. For $r > r_F$, the far-field model (linear phase across the array) is accurate.

Receiver 1 first decodes $W_2$ (the interferer) from $Y_1 = X_1 + \sqrt{a}X_2 + Z_1$. Since $a \geq 1 + P_1$, the SINR for decoding $W_2$ is $\frac{aP_2}{P_1 + 1} \geq P_2$ (at least as good as receiver 2's own channel). After subtracting $\sqrt{a}X_2$, receiver 1 sees $X_1 + Z_1$, achieving rate $\frac{1}{2}\log(1+P_1)$.

By symmetry, receiver 2 decodes $W_1$ first (possible since $b \geq 1 + P_2$) and then sees $X_2 + Z_2$, achieving $\frac{1}{2}\log(1+P_2)$. The capacity region is the rectangle $R_{1} \leq \frac{1}{2}\log(1+P_1)$, $R_{2} \leq \frac{1}{2}\log(1+P_2)$ — the same as no interference.

Each user's rate is bounded by $\frac{1}{2}\log(1+P_k)$ (the interference-free capacity). Since this is achievable, it is the capacity.

In the ADT model, the channel from node $i$ to node $j$ is $Y_j = S^{n-n_{ij}} X_i$ where $S$ is the shift matrix and $n_{ij} = \lfloor \frac{1}{2}\log(\text{SNR}_{ij}) \rfloor$ is the number of signal levels. Operations are over $\mathbb{F}_2$.

The ADT network is equivalent to a wired network with integer-valued edge capacities. By the max-flow min-cut theorem for graphs, the capacity equals the minimum cut value. This is because each "bit pipe" can carry exactly one bit per use, and the linear structure allows network coding (XOR at intermediate nodes) to achieve the min-cut.

The linear deterministic model approximates the Gaussian relay network to within a constant gap (typically $O(1)$ bits per relay). This is the basis for the approximate capacity results for Gaussian relay networks: solve the deterministic problem exactly (via max-flow), then translate back to the Gaussian case with bounded gap.

Is 10 bps/Hz an achievable rate (demonstrated by simulation or a specific scheme) or a theoretical upper bound? If achievable, what is the gap to capacity? The 4×4 i.i.d. Rayleigh MIMO capacity at 20 dB is approximately 10-11 bps/Hz (with equal power allocation), so 10 bps/Hz is plausible but close to the limit.

Is perfect CSIT assumed? With perfect CSIT, water-filling over eigenvalues is optimal. Without CSIT, equal power allocation loses about 1-2 bps/Hz at this SNR. Is perfect CSIR assumed? With imperfect CSIR (pilot-based estimation), training overhead reduces the effective rate.

At 20 dB, the claim is reasonable for a well-designed system. But what is the blocklength? The bandwidth? The mobility? At high mobility, channel estimation degrades and the effective capacity drops. Is this a narrowband or wideband MIMO? The claim needs these context details to be evaluable.

With $N_c$ data subcarriers out of $N$ total: $R = \frac{N_c}{N} \cdot \frac{1}{2}\log(1+\text{SNR})$.

With $N_s$ pilot subcarriers, the CRB for range estimation is: $\text{CRB}_\tau = \frac{1}{8\pi^2 \text{SNR}_{s} \cdot N_s \cdot \Delta f^2 \cdot \sigma_\tau^2}$ where $\Delta f$ is the subcarrier spacing and $\sigma_\tau^2$ is related to the bandwidth. More pilots (larger $N_s$) reduce the CRB.

Maximize $R$ subject to $\text{CRB} \leq D_{\max}$: $N_s^{\min} = \lceil 1/(8\pi^2 \text{SNR}_{s} \Delta f^2 \sigma_\tau^2 D_{\max}) \rceil$. $N_c^* = N - N_s^{\min}$. The optimal split allocates the minimum pilots needed for sensing and gives the rest to communication.

Let $X_S \in \{0,1\}$, $Y_D = X_S \oplus Z_D$ (BSC($p_D$)), and $Y_R = Z_R$ (independent of $X_S$). The relay observes only noise.

The relay is useless (it has no information about $W$). The capacity equals the direct link capacity: $C = 1 - H_{b}(p_D)$.

Cut $\{S, R\}$ vs. $\{D\}$: $I(X_S, X_R; Y_D)$. If $X_R$ is correlated with $X_S$ (cooperative transmission), this can exceed $I(X_S; Y_D) = 1 - H_{b}(p_D)$. For example, if $Y_D = X_S \oplus X_R \oplus Z_D$ and we set $X_R = X_S$ (perfect relay cooperation), then $Y_D = Z_D$ and $I(X_S, X_R; Y_D) = 0$. But if instead $Y_D = f(X_S, X_R, Z_D)$ allows cooperation gain, the cut-set exceeds the capacity because the relay cannot actually cooperate (it has no information about $X_S$). The gap arises because the cut-set bound ignores the relay's causality constraint.