Chapter 18: Compute-and-Forward

Learning Objectives

• State the Nazer-Gastpar (2011) compute-and-forward model: $K$ users transmit lattice codewords $\mathbf{x}_k$ over a Gaussian MAC $y = \sum_{k=1}^K h_k \mathbf{x}_k + \mathbf{w}$ to a relay, and the relay decodes a linear equation $\sum_k a_k \mathbf{u}_k \bmod \Lambda$ for an integer coefficient vector $\mathbf{a} \in \mathbb{Z}^K$ — not the individual messages
• Prove the Nazer-Gastpar computation rate $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)$ by building a nested Erez-Zamir lattice codebook, applying MMSE scaling $\alpha^* = \text{SNR}\, \mathbf{h}^T \mathbf{a}/(1 + \text{SNR}\|\mathbf{h}\|^2)$, and bounding the effective noise variance
• Apply compute-and-forward to the two-way relay channel and prove Nam-Chung-Lee (2010) constant-gap optimality: CF achieves the capacity region within $1/2$ bit per user, versus $4$ orthogonal slots for routing and $2$ slots for amplify-or-decode-forward
• Recognise physical-layer network coding (Zhang-Liew-Lam 2006) as the integer-coefficient special case $\mathbf{a} = (1, 1)^T$ of the Nazer-Gastpar framework, and explain why PNC's asymmetric-channel failure mode is precisely the integer-coefficient mismatch $\|\mathbf{a}\|^2 \gg (\mathbf{h}^T \mathbf{a})^2$
• Formulate the integer-coefficient search $\mathbf{a}^* = \arg\max_{\mathbf{a} \in \mathbb{Z}^K \setminus \{0\}} R(\mathbf{h}, \mathbf{a})$ as a shortest-vector-problem instance on the $\alpha^*$-scaled channel lattice, and recognise it as NP-hard in general but tractable (LLL, Fincke-Pohst) at moderate $K$
• Extend to the integer-forcing linear receiver (Ordentlich-Erez-Nazer 2014) and the $K$-user Gaussian interference channel: CF gives a within-constant-gap achievability for the symmetric sum-capacity and serves as the natural lattice dual to interference alignment