Digital Communications

Compute-and-Forward

Q: How does compute-and-forward differ from decode-and-forward and amplify-and-forward?

Amplify-and-forward simply scales and retransmits the noisy received signal, which also amplifies the noise. Decode-and-forward fully decodes each individual user message, which fails when two strong signals collide at the relay. Compute-and-forward takes a middle path: it uses nested lattice codes so that an integer linear combination of the simultaneously transmitted codewords is itself a valid codeword, and the relay decodes that single combination. Because the channel naturally forms a noisy weighted sum, the relay can pick integer coefficients close to the real channel gains and decode the resulting equation at a higher rate than decode-and-forward would allow under strong interference. The destination collects enough independent equations from multiple relays and solves the linear system over the finite field to recover all messages.

Q: What sets the computation rate in compute-and-forward?

For a relay receiving y = sum of h_l x_l + z with per-symbol power P and noise variance 1, the achievable computation rate for integer coefficient vector a is R(h,a) = 0.5 log2 of ( ( |a|^2 minus P |h dot a|^2 / (1 + P |h|^2) ) to the power minus 1 ), maximized over the integer vector a. The optimal a is the integer vector closest to alpha times h, where alpha is the MMSE scaling factor alpha = P (h dot a) / (1 + P |h|^2). Finding the best a is a shortest-lattice-vector problem solved with LLL reduction or sphere decoding. The rate is highest when the real channel gain vector lies near an integer-scaled lattice point, and it degrades when the gains are far from any low-norm integer combination.

Q: Why are nested lattice codes required for compute-and-forward?

The defining property is that the sum, or any integer linear combination, of two codewords drawn from a lattice code is again a point of the same lattice, so it remains decodable. A nested lattice pair uses a fine lattice for coding gain and a coarse lattice for power shaping; modulo the coarse lattice keeps transmit power bounded. When all users share the same nested lattice codebook, the relay sees a noisy lattice point equal to the integer combination of codewords plus noise and can quantize to the nearest fine-lattice point. Random Gaussian codebooks do not have this closure property, so the sum of two such codewords is generally not a codeword and cannot be decoded directly, which is why compute-and-forward is built on lattices.

/kuhm-PYOOT and FOR-werd/

Introduced by Nazer and Gastpar in 2011, this relaying strategy turns interference into a resource by having a relay decode an integer linear combination of simultaneously transmitted codewords rather than each message on its own. It is a structured form of physical-layer network coding built on nested lattice codes, where the algebraic closure of the lattice guarantees that the weighted sum the wireless medium naturally produces is itself a decodable codeword. The relay selects an integer coefficient vector a close to the real-valued channel gains, decodes the equation a·w over the finite field, and forwards it; a destination that gathers enough independent equations from several relays inverts the linear system to recover every message. The achievable computation rate exceeds decode-and-forward when colliding signals are strong, which makes the scheme attractive for dense relay networks and interference-limited backhaul.

Category: Digital Communications

Origin: Nazer & Gastpar, 2011

Code class: Nested lattice

Turning Interference Into Equations

In a conventional multiple-access setting, two or more users transmitting at once create interference that a relay must either suppress, treat as noise, or decode user by user. Compute-and-forward inverts that logic. Because the wireless channel adds the transmitted signals together with real-valued gains, the relay observes a noisy weighted superposition y = ∑ h_l x_l + z. If every transmitter draws its codeword from the same nested lattice, then any integer linear combination of those codewords is again a lattice point. The relay therefore aims to decode one such combination, indexed by an integer coefficient vector a, instead of fighting to separate the individual streams.

The art of the scheme is choosing a so that the integer combination ∑ a_l x_l sits close to the actual received superposition. The relay applies an MMSE scaling factor α to the received signal so that αy ≈ ∑ a_l x_l, leaving an effective noise term made of channel-mismatch (αh_l − a_l) plus scaled thermal noise. Minimizing the variance of that effective noise over a is a closest-lattice-point search, typically solved with LLL basis reduction or a sphere decoder. When the channel gain vector happens to lie near a low-norm integer-scaled lattice direction, the computation rate is high; when the gains are awkward, the residual mismatch dominates and the rate falls.

Once each relay reports a decoded equation a^(k)·w over the finite field, the destination assembles a system of linear equations. As long as the collected coefficient vectors form a full-rank matrix over that field, the destination inverts it to recover all of the original messages. This two-stage flow, local computation at the relays followed by global linear-system inversion at the sink, is what distinguishes compute-and-forward from store-and-forward routing and from classical network coding performed only at the bit level.

Computation Rate and Coefficient Selection

Achievable computation rate (real AWGN, power P, unit noise):
R(h,a) = ½ log₂⁺ ( ( |a|² − P (h·a)² / (1 + P|h|²) )⁻¹ )

Optimal MMSE scaling:
α_opt = P (h·a) / (1 + P|h|²)

Coefficient search (closest lattice point):
a* = arg min_{a ∈ ℤ^L, a ≠ 0} ( |a|² − P (h·a)² / (1 + P|h|²) )

Where h is the L-dimensional channel gain vector, a is the integer coefficient vector, P is the per-symbol transmit power, and the per-symbol noise variance is normalized to 1. The end-to-end message rate is the minimum of the relay computation rates that span a full-rank equation set. Example: with P giving 20 dB SNR (P ≈ 100) and h ≈ [1.0, 0.5], the choice a = [2, 1] is the rate-maximizing integer vector and yields about 2.3 bits per channel use; weaker choices such as [1, 0] or [1, 1] give near 1.1 bits.

Relaying Strategy Comparison

Strategy	What the relay sends	Coding	Behavior under strong interference	Complexity
Amplify-and-forward	Scaled analog copy	None at relay	Amplifies signal and noise together	Lowest
Decode-and-forward	Re-encoded individual messages	Per-user channel code	Breaks down when collisions are strong	Moderate
Compute-and-forward	Integer linear combination a·w	Nested lattice	Rate grows; exploits the collision	High (lattice search)
Compress-and-forward	Quantized observation	Wyner-Ziv source code	Carries side information, noise-limited	High
Bit-level network coding	XOR of decoded packets	Linear over GF(2)	Needs clean per-user decoding first	Low to moderate

Common Questions

Frequently Asked Questions

How does compute-and-forward differ from decode-and-forward and amplify-and-forward?

Amplify-and-forward retransmits a scaled noisy copy, boosting noise along with signal. Decode-and-forward fully decodes each user message and stalls when two strong signals collide. Compute-and-forward sits between them: nested lattice codes make an integer combination ∑ a_l x_l a valid codeword, so the relay decodes that single equation. Picking a close to the channel gains lets it decode at a higher rate than decode-and-forward under strong interference; the destination then solves the collected equations over the finite field.

What sets the computation rate in compute-and-forward?

For y = ∑ h_l x_l + z at power P with unit noise, R(h,a) = ½ log₂⁺( ( |a|² − P(h·a)²/(1 + P|h|²) )⁻¹ ), maximized over the integer vector a. The optimum a is the closest integer vector to αh, with MMSE scaling α = P(h·a)/(1 + P|h|²). Finding it is a shortest-lattice-vector search handled by LLL reduction or sphere decoding; rate peaks when the gains lie near a low-norm integer combination.

Why are nested lattice codes required for compute-and-forward?

Lattices are closed under integer linear combination, so the weighted sum of codewords is still a codeword the relay can quantize to. The nested pair uses a fine lattice for coding gain and a coarse lattice (via modulo reduction) for power shaping. Random Gaussian codebooks lack this closure: the sum of two such codewords is generally not a codeword, so it cannot be decoded directly. That algebraic structure is exactly what lets the relay recover a·w from a noisy superposition.

Related Terms

← Computational Electromagnetics Compute-in-Sensor →