Exercises

$R(\mathbf{h}, \mathbf{a}) = \tfrac{1}{2} \log_2^+ \big( 1 / (\|\mathbf{a}\|^2 - \text{SNR}(\mathbf{h}^T \mathbf{a})^2 / (1 + \text{SNR}\|\mathbf{h}\|^2)) \big)$ where $\log_2^+(x) = \max(\log_2 x, 0)$. The truncation is necessary because $\|\mathbf{a}\|^2 - \text{SNR}(\mathbf{h}^T \mathbf{a})^2/(1 + \text{SNR}\|\mathbf{h}\|^2)$ can exceed $1$ (low SNR or strong misalignment), giving $R = 0$.

$\alpha^*(\mathbf{h}, \mathbf{a}) = \text{SNR}\,(\mathbf{h}^T \mathbf{a}) / (1 + \text{SNR}\, \|\mathbf{h}\|^2)$. Scalar; minimises the effective-noise variance $N(\alpha) = \text{SNR}\, \|\alpha \mathbf{h} - \mathbf{a}\|^2 + \alpha^2$. $\blacksquare$

$\|\mathbf{a}\|^2 = 1$; $\mathbf{h}^T \mathbf{a} = h$; $\|\mathbf{h}\|^2 = h^2$. Then $N_{\rm eff} = 1 - \text{SNR} h^2 / (1 + \text{SNR} h^2) = 1/(1 + \text{SNR} h^2)$.

$R = \tfrac{1}{2} \log_2 (1 + \text{SNR} h^2)$ — the single-user AWGN capacity at effective SNR $\text{SNR} h^2$. $\blacksquare$

$\|\mathbf{a}\|^2 = 2$; $\mathbf{h}^T \mathbf{a} = 2$; $\|\mathbf{h}\|^2 = 2$.

$N_{\rm eff} = 2 - 10 \cdot 4 / (1 + 20) = 2 - 40/21 \approx 2 - 1.905 = 0.0952$.

$R = \tfrac{1}{2} \log_2 (1/0.0952) = \tfrac{1}{2} \log_2 (10.5) \approx 1.69$ bits per channel use per user. Compare to Thm. TNam-Chung-Lee: CF Is Within 1/2 Bit of TWRC Capacity: $\tfrac{1}{2} \log_2(1/2 + 10) = \tfrac{1}{2} \log_2(10.5)$ — identical. $\blacksquare$

$\|\mathbf{h}\|^2 = 5$, denominator $1 + 31.6 \cdot 5 = 159$.

$\mathbf{a}^* = (1, 2)^T$ with $R^* \approx 2.52$ bits/user — the vector that exactly matches $\mathbf{h} = (1, 2)^T$. The vector $(2, 1)^T$ has the same norm but much worse alignment: $\mathbf{h}^T \mathbf{a} = 4$ vs. $\mathbf{h}^T \mathbf{a}^* = 5$. $\blacksquare$

$\alpha^* = 10 \cdot 5 / (1 + 10 \cdot 5) = 50/51 \approx 0.980$.

$\partial N / \partial \alpha = 2 \text{SNR} (\alpha \|\mathbf{h}\|^2 - \mathbf{h}^T \mathbf{a}) + 2 \alpha = 10 \cdot 2 (\alpha \cdot 5 - 5) + 2 \alpha = 10 \alpha - 50 + 2\alpha = 12\alpha - 50$. Wait — that gives $\alpha^* = 50/12 \approx 4.17$, NOT $0.98$. Let me recheck: the formula uses $P = \text{SNR}$. With per-dimension variance $P \|\alpha \mathbf{h} - \mathbf{a}\|^2 + \alpha^2$: derivative $= 2 P \mathbf{h}^T (\alpha \mathbf{h} - \mathbf{a}) + 2\alpha = 0$, giving $\alpha (P \|\mathbf{h}\|^2 + 1) = P \mathbf{h}^T \mathbf{a}$, i.e., $\alpha^* = P \mathbf{h}^T \mathbf{a} / (1 + P \|\mathbf{h}\|^2) = 10 \cdot 5 / 51 = 50/51$. $\blacksquare$

$N(\alpha) = \text{SNR}(\alpha \mathbf{h} - \mathbf{a})^T (\alpha \mathbf{h} - \mathbf{a}) + \alpha^2 = \text{SNR}(\alpha^2 \|\mathbf{h}\|^2 - 2 \alpha \mathbf{h}^T \mathbf{a} + \|\mathbf{a}\|^2) + \alpha^2 = (\text{SNR}\|\mathbf{h}\|^2 + 1) \alpha^2 - 2 \text{SNR}(\mathbf{h}^T \mathbf{a}) \alpha + \text{SNR}\|\mathbf{a}\|^2$.

$N''(\alpha) = 2(\text{SNR} \|\mathbf{h}\|^2 + 1) > 0$ for any $\text{SNR} \ge 0$ and any $\mathbf{h}$. Hence $N$ is strictly convex and has a unique minimiser.

$N'(\alpha) = 2(\text{SNR}\|\mathbf{h}\|^2 + 1)\alpha - 2\text{SNR} (\mathbf{h}^T \mathbf{a}) = 0 \Rightarrow \alpha^* = \text{SNR} (\mathbf{h}^T \mathbf{a}) / (1 + \text{SNR}\|\mathbf{h}\|^2)$. $\blacksquare$

$R_{\rm CF} = \tfrac{1}{2} \log_2 (1/2 + 10) = \tfrac{1}{2} \log_2(10.5) \approx 1.69$ bits per user.

$R_{\rm cut} = \tfrac{1}{2} \log_2(1 + 10) = \tfrac{1}{2} \log_2(11) \approx 1.73$ bits per user.

$\Delta = R_{\rm cut} - R_{\rm CF} = \tfrac{1}{2} (\log_2 11 - \log_2 10.5) = \tfrac{1}{2} \log_2(11/10.5) = \tfrac{1}{2} \log_2(1.0476) \approx 0.034$ bits. Gap $\ll 1/2$. $\blacksquare$

$\Delta(\text{SNR}) = \tfrac{1}{2} \log_2 \big(\tfrac{1 + \text{SNR}} {1/2 + \text{SNR}}\big) = \tfrac{1}{2} \log_2 \big(1 + \tfrac{1/2} {1/2 + \text{SNR}}\big)$.

The argument $1 + 1/(1 + 2\text{SNR})$ is strictly decreasing in $\text{SNR}$: at $\text{SNR} = 0$, it equals $2$; as $\text{SNR} \to \infty$, it tends to $1$.

At $\text{SNR} = 0$: $\Delta = \tfrac{1}{2} \log_2(2) = 1/2$ bit. As $\text{SNR} \to \infty$: $\Delta \to \tfrac{1}{2} \log_2(1) = 0$. Strict monotonicity: $\Delta$ is in $(0, 1/2]$ for all $\text{SNR} > 0$, with $\Delta(0) = 1/2$ attained and $\Delta(\infty) = 0$ asymptotic. $\blacksquare$

$N_{\rm eff}(\mathbf{h}, \mathbf{a}) = \|\mathbf{a}\|^2 - \text{SNR}(\mathbf{h}^T \mathbf{a})^2 / (1 + \text{SNR}\|\mathbf{h}\|^2)$ $= \mathbf{a}^T \big(\mathbf{I} - \tfrac{\text{SNR}\, \mathbf{h} \mathbf{h}^T}{1 + \text{SNR}\|\mathbf{h}\|^2}\big) \mathbf{a}$.

Define $\mathbf{G}_{\rm ch}(\mathbf{h}) = \mathbf{I} - \text{SNR}\, \mathbf{h} \mathbf{h}^T / (1 + \text{SNR}\|\mathbf{h}\|^2)$. Then $N_{\rm eff}(\mathbf{h}, \mathbf{a}) = \mathbf{a}^T \mathbf{G}_{\rm ch} \mathbf{a} = \|\mathbf{a}\|_{\mathbf{G}_ {\rm ch}}^2$. Maximising $R(\mathbf{h}, \mathbf{a})$ is equivalent to minimising $\|\mathbf{a}\|_{\mathbf{G}_{\rm ch}}^2$ over $\mathbf{a} \in \mathbb{Z}^K \setminus \{\mathbf{0}\}$ — the shortest-vector problem (SVP) on the integer lattice $\mathbb{Z}^K$ under the Gram matrix $\mathbf{G}_{\rm ch}$. $\blacksquare$

$\mathbf{G}_{\rm ch} = \mathbf{I} - (\text{SNR}/(1 + 2\text{SNR})) \mathbf{h} \mathbf{h}^T = \mathbf{I} - \kappa \mathbf{h} \mathbf{h}^T$ with $\kappa = \text{SNR}/(1 + 2\text{SNR})$.

$\mathbf{h} \mathbf{h}^T$ has eigenvalues $\{2, 0\}$ with eigenvectors $\{\mathbf{h}/\sqrt{2}, \mathbf{h}^\perp/\sqrt{2}\}$ where $\mathbf{h}^\perp = (1, -1)^T$. Hence $\mathbf{G}_{\rm ch}$ has eigenvalues $\{1 - 2\kappa, 1\}$. At $\text{SNR} = 10$, $\kappa = 10/21$, so eigenvalues are $\{1 - 20/21, 1\} = \{1/21, 1\}$.

The small eigenvalue $1/21$ corresponds to the direction $\mathbf{h}$ — vectors $\mathbf{a}$ nearly parallel to $\mathbf{h}$ have tiny $N_{\rm eff}$ and large $R$. The eigenvalue $1$ corresponds to the perpendicular direction — no lattice-alignment gain. The SVP solution $\mathbf{a}^*$ will be an integer vector in the $\mathbf{h}$-direction, which for $\mathbf{h} = (1, 1)^T$ is exactly $(1, 1)$. $\blacksquare$

Gaussian MAC $\mathbf{y}_R = \mathbf{x}_A + \mathbf{x}_B + \mathbf{w}_R$, per-user power $P = \text{SNR}$, noise $\mathcal{N}(0, 1)$. Joint decoding sum-rate cap: $R_A + R_B \le I(X_A X_B; Y) = \tfrac{1}{2} \log_2(1 + 2\text{SNR})$.

DF splits: $R_A = R_B = R_{\rm DF}$. Sum: $2 R_{\rm DF} \le \tfrac{1}{2} \log_2(1 + 2\text{SNR})$, hence $R_{\rm DF} \le \tfrac{1}{4} \log_2(1 + 2\text{SNR})$.

$R_{\rm CF} = \tfrac{1}{2} \log_2(1/2 + \text{SNR})$ per user.

At high $\text{SNR}$: $R_{\rm DF} \approx \tfrac{1}{4} \log_2(2\text{SNR}) = \tfrac{1}{4} \log_2 \text{SNR} + \tfrac{1}{4}$; $R_{\rm CF} \approx \tfrac{1}{2} \log_2 \text{SNR} - \tfrac{1}{2}$. Ratio $R_{\rm CF} / R_{\rm DF} \to 2$ as $\text{SNR} \to \infty$. DF gets half the CF rate at high SNR because it decodes two messages where CF decodes only one (the sum). $\blacksquare$

$\text{SNR} = 10$, $\sigma_w = 1/\sqrt{10} \approx 0.316$. Decision thresholds at $\pm 1$; mean sum values $\pm 2$ and $0$.

For mean $+2$ (or $-2$): error when $|y_R| < 1$, i.e., noise $> 1$ in magnitude $\Rightarrow$ $p_{e,\pm 2} \approx Q(1/\sigma_w) = Q(3.16) \approx 7.9 \cdot 10^{-4}$. For mean $0$: error when $|y_R| \ge 1$, $p_{e, 0} \approx 2 Q(1/\sigma_w) \approx 1.6 \cdot 10^{-3}$. Averaging: $p_e \approx 0.8 \cdot 10^{-3}$ (dominated by mean-0 case which occurs with probability $1/2$).

$R_{\rm PNC} = 1 - H_2(p_e) = 1 - H_2(8 \cdot 10^{-4}) \approx 1 - 0.010 = 0.990$ bits per user. Very close to the BPSK cap.

$R_{\rm CF} = \tfrac{1}{2} \log_2(1/2 + 10) \approx 1.69$ bits per user. Lattice-CF wins by $\sim 0.7$ bits.

At $\text{SNR} = 10$ dB, lattice-CF dominates PNC-BPSK by $70\%$ in rate. The advantage grows at higher SNR because PNC is rate-capped at $1$ bit/use while lattice-CF is not. $\blacksquare$

For each row $k = 1, \ldots, K$: apply a row-specific equaliser $\mathbf{b}_k^T \mathbf{y} = \mathbf{b}_k^T \mathbf{H} \mathbf{X} + \mathbf{b}_k^T \mathbf{W}$, then run CF decoding with effective channel $\mathbf{H}^T \mathbf{b}_k$ and integer vector $\mathbf{a}_k$. The decoded row is $\mathbf{v}_k = \sum_j A_{kj} \mathbf{u}_j \bmod \Lambda_s$.

$\mathbf{V} = \mathbf{A} \mathbf{U} \bmod \Lambda_s$; since $\det(\mathbf{A}) \neq 0$, $\mathbf{A}^{-1}$ exists (over $\mathbb{Q}$; the modular inverse exists in $\mathbb{Z} / \Lambda_s$). Then $\mathbf{U} = \mathbf{A}^{-1} \mathbf{V} \bmod \Lambda_s$.

Each row-$k$ CF rate is independent — the $K$ lattice points $\mathbf{v}_k$ are decoded in parallel. The total rate (summing over $K$ users' message load) is $\sum_k R(\mathbf{H}^T \mathbf{b}_k^*, \mathbf{a}_k)$. The optimisation chooses $(\mathbf{A}^*, \{\mathbf{b}_k^*\})$ jointly to maximise this sum. $\blacksquare$

$\mathbf{H}^T \mathbf{H} = \begin{pmatrix} 1.49 & 0.7 \\ 0.7 & 1 \end{pmatrix}$. Eigenvalues: $\lambda_\pm = \tfrac{1}{2} (2.49 \pm \sqrt{0.49^2 + 1.96}) \approx \{1.96, 0.525\}$. Condition number: $1.96/0.525 \approx 3.73$.

Per-stream SNR: $\text{SNR}/(\mathbf{H}^T \mathbf{H})^{-1}_{kk}$. $(\mathbf{H}^T \mathbf{H})^{-1} \approx \begin{pmatrix} 1.23 & -0.862 \\ -0.862 & 1.833 \end{pmatrix}$. Per-stream SNRs: $31.6/1.23 \approx 25.7$ and $31.6/1.833 \approx 17.2$. Rate: $\tfrac{1}{2} \log_2(1 + 25.7) + \tfrac{1}{2} \log_2(1 + 17.2) \approx 2.37 + 2.11 = 4.48$ bits.

This is identical to ZF (each stream decoded independently). IF sum-rate: $4.48$ bits.

Try $\mathbf{A} = \begin{pmatrix} 1 & 0 \\ -1 & 1 \end{pmatrix}$. Row 1: $\mathbf{a}_1 = (1, 0)$ — CF decodes $\mathbf{u}_1$. Row 2: $\mathbf{a}_2 = (-1, 1)$ — CF decodes $\mathbf{u}_2 - \mathbf{u}_1 \bmod \Lambda_s$. The effective channel is $\mathbf{H}^T \mathbf{a}_2 = (0.7, 1)^T - (1, 0)^T = (-0.3, 1)^T$, $\|\mathbf{H}^T \mathbf{a}_2\|^2 = 0.09 + 1 = 1.09$. CF rate for row 2: $R(\mathbf{H}^T \mathbf{b}_2^*, (-1, 1))$ optimised over $\mathbf{b}_2$. Numerical optimisation gives $R_{\rm row 2} \approx 2.47$ bits. Row 1: $R_{\rm row 1} = \tfrac{1}{2} \log_2(1 + 31.6) \approx 2.51$. IF sum-rate: $2.51 + 2.47 = 4.98$ bits.

IF with LLL-reduced $\mathbf{A}$ beats ZF by $0.50$ bits ($\sim 10\%$). The gain comes from avoiding the noise enhancement of inverting the ill-conditioned $\mathbf{H}^T \mathbf{H}$. $\blacksquare$

$\mathbb{Z}$ modulo $2\mathbb{Z}$ gives cosets $\{0 + 2\mathbb{Z}, 1 + 2\mathbb{Z}\}$; representatives $\{0, 1\}$ (or $\{-1, +1\}$ for the BPSK-symmetric version). Codebook size: $|\mathbb{Z} / 2\mathbb{Z}| = 2$.

$R_{\rm cb} = \tfrac{1}{n} \log_2 |\Lambda_c \cap \mathcal{V} (\Lambda_s)|^n = \log_2 2 = 1$ bit per channel use. The hard-decision decoding rule matches the XOR logic.

With $\mathbf{a} = (1, 1)^T$ and BPSK $\mathbf{x}_k \in \{-1, +1\}$, the relay computes $y_R \bmod 2\mathbb{Z}$ and rounds to the nearest $\mathbb{Z}$ point in $[-1, 1)$ — yielding $(u_A + u_B) \bmod 2 = u_A \oplus u_B$ (for bits $u_k$). This is the Zhang-Liew-Lam XOR rule. The Nazer-Gastpar MMSE scaling $\alpha^* \to 1$ at high SNR matches the "no scaling" assumption of PNC. $\blacksquare$

$R_{\rm sum} = \sum_{k=1}^K R(\mathbf{h}_k, \mathbf{a}_k^*)$ where $\mathbf{h}_k$ is the $k$-th row of the interference-channel coupling matrix $\mathbf{H}$, and $\mathbf{a}_k^* = \arg\max_{\mathbf{a}} R(\mathbf{h}_k, \mathbf{a})$ is the best integer coefficient for receiver $k$.

Ordentlich-Erez-Nazer 2014 proves $\sum_k R(\mathbf{h}_k, \mathbf{a}_k^*) \ge R_{\rm sum, cap} - C(K)$ where $R_{\rm sum, cap}$ is the Etkin-Tse-Wang sum-capacity upper bound and $C(K) = O(K \log K)$ is a constant independent of the channel matrix $\mathbf{H}$ and SNR.

At each receiver $k$, CF decodes a lattice combination $\sum_j (\mathbf{a}_k^*)_j \mathbf{u}_j \bmod \Lambda_s$. Since the combinations are chosen via the integer-coefficient search (SVP on channel Gram), they align with the channel structure and absorb the interference constructively. The constant-gap term reflects the discretisation loss from restricting to integer coefficients. $\blacksquare$

Provides the discrete $2^{nR}$ hypothesis space and the "lattice closure under integer linear combination" property. All $K$ users share the codebook so $\sum_k a_k \mathbf{u}_k \in \Lambda_c$ is automatic.

Minimises the effective-noise variance $N(\alpha) = P\|\alpha \mathbf{h} - \mathbf{a}\|^2 + \alpha^2$. At $\alpha^* = P\mathbf{h}^T \mathbf{a}/(1 + P\|\mathbf{h}\|^2)$, the signal interference $(\alpha \mathbf{h} - \mathbf{a})^T \mathbf{x}$ is traded off against the noise $\alpha^2$, giving the smallest residual.

Reduces the ambient space $\mathbb{R}^n$ to the Voronoi region $\mathcal{V}(\Lambda_s)$, ensuring the decoded lattice point is a legal codeword. Combined with Poltyrev-good $\Lambda_c$, the decoding error probability vanishes whenever the noise variance is below the capacity-achieving threshold.

The combined protocol achieves $R(\mathbf{h}, \mathbf{a}) = \tfrac{1}{2} \log_2(1/N_{\rm eff})$. Each ingredient is inherited from Erez-Zamir Ch. 16; the new flavour is that the $K$ users share the codebook and the relay targets an integer-coefficient combination. $\blacksquare$

Denominator $1 + 15.85 \cdot 2.08 = 33.97$.

$\mathbf{a}^* = (1, 1)^T$ with $R \approx 1.47$ bits per user. Although $(1, 2)$ gives better $\mathbf{h}^T \mathbf{a}/ \|\mathbf{h}\|$ alignment, its $\|\mathbf{a}\|^2 = 5$ penalty dominates. $\blacksquare$

$\|\mathbf{a}\|^2 = \|\mathbf{h}\|^2 = 5$; $\mathbf{h}^T \mathbf{a} = 5$. $N_{\rm eff} = 5 - 10 \cdot 25 / (1 + 50) = 5 - 250/51 \approx 0.098$. $R_{\rm CF} = \tfrac{1}{2} \log_2(1/0.098) \approx 1.68$ bits per user.

Sum-cap: $\tfrac{1}{2} \log_2(1 + 10 \cdot 5) = \tfrac{1}{2} \log_2(51) \approx 2.84$ bits. Per user (symmetric split): $1.42$ bits.

CF at $1.68$ bits/user EXCEEDS the per-user-sum-cap split of $1.42$. This is possible because CF is not bound by the MAC sum-cap: the relay decodes only the sum lattice point, not the individual messages, avoiding the MAC bottleneck.

The within-$1/2$-bit statement of Thm. TNam-Chung-Lee: CF Is Within 1/2 Bit of TWRC Capacity compares to the cut-set bound $\tfrac{1}{2} \log_2(1 + \text{SNR} \|\mathbf{h}\|^2)$, not the MAC sum-split. Cut-set here: $2.84$ bits. Gap: $2.84 - 1.68 = 1.16$ bit per user — larger than $1/2$ bit for this asymmetric case. The $1/2$-bit result only holds for the symmetric TWRC ($h_A = h_B$). $\blacksquare$

The integer-coefficient search is identical to SVP on the integer lattice $\mathbb{Z}^K$ with Gram matrix $\mathbf{G}$: find the shortest non-zero $\mathbf{a} \in \mathbb{Z}^K$ under the norm $\|\mathbf{a}\|_\mathbf{G}^2 = \mathbf{a}^T \mathbf{G} \mathbf{a}$.

Ajtai (1996) proved that SVP is NP-hard under randomised polynomial-time reductions. The proof uses a worst-case-to- average-case connection: solving random SVP instances would imply solving the worst-case Shortest-Vector-with-Gap problem, which is NP-hard.

For a generic $\mathbf{G}$, no polynomial-time algorithm is known to find the exact $\mathbf{a}^*$. LLL reduction gives a $2^{K/2}$-approximation in $O(K^4 \log B)$ time (Lenstra- Lenstra-Lovász 1982); block KZ / BKZ improves this to $O(\gamma^K)$-approximation in exponential time. For the specific Gram matrix $\mathbf{G}_{\rm ch}(\mathbf{h}) = \mathbf{I} - \text{SNR}\, \mathbf{h} \mathbf{h}^T / (1 + \text{SNR}\|\mathbf{h}\|^2)$ arising in CF, the structure (rank-one perturbation of identity) might enable faster specialised algorithms — this is an active research area. $\blacksquare$

$\mathbf{h}_1 = (1.3, 0.3, 0.3)^T$; $\|\mathbf{h}_1\|^2 = 1.69 + 0.09 + 0.09 = 1.87$. $\text{SNR} = 31.6$. Denominator $1 + 31.6 \cdot 1.87 = 60.1$.

Try $\mathbf{a} \in \{(1, 0, 0), (1, 1, 1), (2, 1, 1), (1, 1, 0), (1, 0, 1), (0, 1, 1), (1, -1, 0)\}$: