PaperlayerView exact revision on arXiv

Source-linked AI summary

Compute-and-Forward: Harnessing Interference through Structured Codes

Bobak Nazer, Michael Gastpar

arXiv:0908.2119v3cs.IT

TL;DR

Wireless interference is conventionally avoided, but this can limit network rates and discard the medium’s broadcast and multiple-access structure. Compute-and-forward instead has relays decode channel-matched linear equations using nested lattice codes, enabling destinations to recover messages from enough equations. The framework provides achievable rates and recovery conditions for AWGN networks, with extensions and a distributed-MIMO comparison against classical relaying.

  • Problem

    Interference avoidance converts wireless networks into bit pipes, while classical relaying strategies face interference or accumulated noise as messages traverse networks.

  • Method

    Compute-and-forward uses nested lattice codes so relays decode linear equations of transmitted messages from noisy channel combinations and forward equations toward destinations.

  • Results

    The paper develops achievable equation-delivery rates, sufficient message-recovery conditions, coding extensions, an upper bound, and slow-fading and distributed-MIMO analyses.

  • Takeaways & Limitations

    Compute-and-forward provides a bits-to-equations interface that exploits interference and supports cooperative communication across AWGN networks.

Abstract

from arXiv · show

Interference is usually viewed as an obstacle to communication in wireless networks. This paper proposes a new strategy, compute-and-forward, that exploits interference to obtain significantly higher rates between users in a network. The key idea is that relays should decode linear functions of transmitted messages according to their observed channel coefficients rather than ignoring the interference as noise. After decoding these linear equations, the relays simply send them towards the destinations, which given enough equations, can recover their desired messages. The underlying codes are based on nested lattices whose algebraic structure ensures that integer combinations of codewords can be decoded reliably. Encoders map messages from a finite field to a lattice and decoders recover equations of lattice points which are then mapped back to equations over the finite field. This scheme is applicable even if the transmitters lack channel state information.

I. INTRODUCTION

Compute-and-forward treats wireless interference as a source of structured information: relays decode linear equations of messages, and destinations recover desired messages from enough equations. Nested lattice codes support this interface across AWGN networks, including settings where transmitters lack channel-state information.

  • I. INTRODUCTION: Compute-and-forward lets relays decode linear equations of transmitted messages from noisy channel combinations instead of treating interference solely as noise.Destinations can solve for desired messages after receiving sufficiently many equations.
  • I. INTRODUCTION: Nested lattice codes make integer combinations of codewords themselves codewords, enabling reliable computation and mapping back to finite-field equations.The scheme maps finite-field messages to lattice points and recovers equations over the original field.
  • I. INTRODUCTION: The approach revises the physical-layer interface from bits to equations, preserving a modular network-stack design while exploiting wireless algebraic structure.The paper presents reliable equations as a digital interface for cooperative schemes.
  • I. INTRODUCTION: Compute-and-forward can outperform classical relaying in moderate-SNR distributed-MIMO settings where interference and noise are both significant.The paper contrasts this regime with classical strategies’ stronger performance at either low or high SNR.
  • B. Summary of Paper Results: The paper develops achievable rates, message-recovery conditions, extensions using successive cancellation and superposition coding, upper bounds, and slow-fading and distributed-MIMO evaluations.Theorems 1–6 address equation delivery and nested lattice coding; Theorems 7–14 address recovery, extensions, and bounds.
  • I. INTRODUCTION: The framework applies to linear AWGN relay networks and allows transmitters to remain oblivious to channel coefficients while relays select equations using channel state information.Equations whose coefficients closely approximate the channel coefficients are available at higher rates.

B. Complex-Valued Channels

For complex-valued channels, the paper first relates the model to a real-valued system, then develops a more specialized formulation that preserves the structure of complex symbols. Transmitters send complex codewords over linear superpositions with complex AWGN, while messages and equation coefficients are adapted accordingly.

  • B. Complex-Valued Channels: Each complex transmitter sends a length-n vector subject to a power constraint, and each relay observes a noisy complex linear superposition of the codewords.The channel coefficients are complex-valued and the relay noise is circularly symmetric complex Gaussian.
  • B. Complex-Valued Channels: A complex-valued network can be represented as a real-valued network with 2L transmitters and 2M relays.The paper also presents a more elegant formulation that exploits complex-symbol structure.
  • B. Complex-Valued Channels: Complex messages contain independent finite-field vectors for the real and imaginary channel components, which are combined into each transmitter’s message.The formulation zero-pads these vectors to a common length before encoding.
  • B. Complex-Valued Channels: Relays in the complex formulation recover linear combinations of complex messages using coefficients from the Gaussian-integer structure.The real and imaginary coefficient choices are coupled, reducing the number of decisions relative to a real-valued representation.

III. MAIN RESULTS

Compute-and-forward gives relays achievable computation rates for decoding message equations over real and complex AWGN networks. Rates are highest when integer equation coefficients approximate channel coefficients, with MMSE scaling optimizing the computation rate.

  • Relays can often recover a message equation at a higher rate than any individual message or subset of messages.
  • Theorems 1 and 3 establish achievable computation-rate regions for real-valued and complex-valued AWGN networks, respectively.
  • The computation rate is uniquely maximized by the MMSE coefficient in both real- and complex-valued channel models.
  • The complex-valued computation-rate expression is twice the corresponding real-valued expression.
  • Coefficient vectors achieve their maximum computation rate when they exactly match the channel vector in the illustrated multiple-access example.
  • At high SNR, the scheme's degrees of freedom are discontinuous: maximum at rational channel vectors but bounded by a constant at irrational vectors as users increase.

IV. NESTED LATTICE CODES

Nested lattice codes combine a coarse lattice’s Voronoi region with one or more fine lattices, supporting finite-field mappings and reliable AWGN communication. Their geometric and goodness properties provide the structure used by compute-and-forward.

  • Lattice definitions: Nested lattice codes use a fine lattice for coding and a coarse lattice for shaping through its fundamental Voronoi region.The construction is designed for real-valued channels and extends the nested-lattice framework used for AWGN communication.
  • Lattice definitions: Lattices provide addition, negation, nearest-point quantization, and modulo operations that preserve the code construction.The modulo operation maps points to quantization errors relative to the coarse lattice and supports integer and real scaling identities.
  • Lattice definitions: A nested lattice code is the set of fine-lattice points inside the coarse lattice’s fundamental Voronoi region.The coarse lattice is contained in the fine lattice, and the code is L = Λ1 ∩ V.
  • Lattice goodness: The coarse lattice is characterized by geometric quantities including covering radius, effective radius, second moment, and normalized second moment.These quantities describe coverage, Voronoi-region volume, and average squared distance within the region.
  • Lattice goodness: Sequences of lattices can be simultaneously good for covering, quantization, and AWGN reliability.AWGN-good lattices have exponentially decaying probability of leaving the Voronoi region when the volume-to-noise ratio is sufficiently large.

B. Lattice Constructions

The paper constructs multiple nested fine lattices from finite-field generator matrices and a common coarse lattice. Full-rank and shared-matrix structure supports different transmitter rates while preserving nesting and algebraic compatibility.

  • Lattice Constructions: The fine lattices are designed to be AWGN-good, allowing each transmitter to operate at a different rate.A possible scaling uses p growing like n log n and kℓ = ⌊nRℓ(log p)^−1⌋.
  • Lattice Constructions: A coarse lattice with power-normalized second moment is combined with fine lattices generated through a Construction A procedure.The procedure draws finite-field generator matrices, forms codebooks, projects them into the reals, and embeds them relative to the coarse lattice.
  • Lattice Constructions: Using progressively truncated generator matrices produces the desired nesting order Λ ⊆ ΛL ⊆ ··· ⊆ Λ1.Each transmitter’s fine lattice is nested because its generator matrix is formed from columns of a common larger matrix.
  • Lattice Constructions: Full-rank generator matrices ensure that each fine lattice contains pkℓ points in the coarse Voronoi region and supports the intended code rate.The construction chooses p and the dimensions k1, …, kL so the full-rank condition holds with probability approaching one as n grows.
  • Lattice Constructions: Using full-rank submatrices of one finite-field codebook enables linear equations involving messages with different rates.The coarse lattice’s full-rank condition supports movement between lattice equations and finite-field message equations.

C. Integer Combinations of Lattice Points

Compute-and-forward maps finite-field messages to nested-lattice codewords so relays can decode integer combinations and convert them back into finite-field equations. Dithering, scaling, quantization, and modulo reduction yield an equivalent channel governed by effective noise and computation rates.

  • Integer Combinations of Lattice Points: The scheme maps messages to nested-lattice codewords, decodes integer combinations at relays, and maps the resulting lattice equations back to message equations.Destinations can recover desired messages when they receive sufficiently many independent linear combinations.
  • Integer Combinations of Lattice Points: A lattice equation is an integer combination of lattice codewords reduced modulo the coarse lattice.Its values lie on the finest lattice participating in the combination.
  • Integer Combinations of Lattice Points: Finite-field messages and nested-lattice codewords are connected by one-to-one maps that preserve linear equations.Full-rank generator matrices make the message-to-codeword map injective, while modulo reduction and equal cardinalities establish the inverse mapping.
  • Integer Combinations of Lattice Points: Dithering separates transmitted codewords from the underlying lattice points, while mismatch between channel and integer coefficients contributes self-noise.The effective noise combines scaled channel noise with the mismatch between αmhmℓ and amℓ.
  • Integer Combinations of Lattice Points: Theorem 5 guarantees reliable decoding of lattice equations for sufficiently large blocklength when the message rates satisfy the computation-rate condition.The achievable rates can approach the computation rates arbitrarily closely by choosing δ sufficiently small.
  • Integer Combinations of Lattice Points: Relays scale their observations, remove dithers, quantize onto the relevant fine lattice, reduce modulo the coarse lattice, and recover finite-field equations.The relevant fine lattice corresponds to the highest-rate message with a nonzero coefficient in the decoded equation.
  • Integer Combinations of Lattice Points: The equivalent modulo-Λ channel lets a relay decode a lattice equation when effective noise remains within the relevant Voronoi region.The error probability is characterized by the probability that equivalent noise exits that region, and AWGN-good lattices make this probability vanish under the stated volume-to-noise condition.

B. Complex-Valued Channel Models

The complex-valued scheme extends compute-and-forward with nested lattice codes and decoders that recover finite-field equations from complex channel observations.

  • Complex-valued lattice coding: Theorem 6 guarantees nested lattice codes enabling relays to decode complex-valued lattice equations with sufficiently small error for large blocklengths.The result applies to arbitrary channel vectors and Gaussian-integer coefficient vectors, subject to suitable rate conditions.
  • Encoding: Each encoder maps finite-field messages to nested-lattice points, applies independent dithers, and transmits the resulting complex channel input.The construction scales the coarse lattice to second moment P/2 and satisfies average power nP over the dithers.
  • Decoding: Each relay scales its observation, separates real and imaginary components, removes dithers, quantizes to the appropriate fine lattice, and reduces modulo the coarse lattice.These operations produce an equation of lattice codewords that is mapped back to an equation of finite-field messages.
  • Performance: The complex-valued decoder has the same effective SNR for both real and imaginary components, namely P/(|α_m|^2+P∥α_mh_m−a_m∥^2).The equality follows because the coarse lattice has second moment P/2, and the remaining proof parallels the real-valued case.

C. Multi-Stage Networks

In multilayer AWGN relay networks, recovered equations become messages for the next relay layer and are repeatedly re-encoded and decoded toward the destination.

  • C. Multi-Stage Networks: The first relay layer passes its recovered equations to the second layer, which decodes new equations using coefficients close to its channel coefficients.The process repeats across layers until the equations reach a destination.
  • C. Multi-Stage Networks: Because the equations remain linear, layered relay operations can be represented as linear equations over the originating messages.This preserves the algebraic structure needed for final message recovery.
  • C. Multi-Stage Networks: A destination can recover desired messages after receiving sufficiently many independent equations generated across the relay layers.The supplied passage frames the layered process as forwarding equations rather than individual decoded messages.

VI. RECOVERING MESSAGES

Message recovery reduces to solving finite-field linear systems formed by equations decoded at relays, with rank conditions determining whether all or selected messages are recoverable.

  • VI. RECOVERING MESSAGES: A real-valued destination recovers all messages if and only if the coefficient matrix of its received equations has rank L.The condition applies when the destination receives M linear combinations over the finite field.
  • VI. RECOVERING MESSAGES: For complex-valued channels, all messages are recoverable if and only if both real and imaginary coefficient matrices have rank L.The received complex equations are represented through separate real and imaginary coefficient matrices.
  • VI. RECOVERING MESSAGES: A destination interested in only one message may need fewer equations when a linear combination of received equations isolates that message.The paper gives separate real- and complex-valued conditions for such selective recovery.
  • VI. RECOVERING MESSAGES: Under bounded equation coefficients and sufficiently large blocklength and field size, L full-rank complex equations suffice to recover all L messages.The coefficient matrix must be full rank over the complex field.
  • VI. RECOVERING MESSAGES: In the Hadamard-network example, compute-and-forward dominates except at very low power, approaches log(1 + P) as P grows, and competing rates vanish as M increases.The comparison concerns decode-and-forward, amplify-and-forward, and compress-and-forward in the stated symmetric-rate setting.

VII. SUCCESSIVE CANCELLATION

Successive cancellation lets relays decode one equation, subtract its contribution, and decode another equation under an achievable rate region.

  • VII. SUCCESSIVE CANCELLATION: The successive-cancellation result characterizes rates for relays that decode an equation with coefficient vector a_m and then one with b_m.The paper states the achievable region for real-valued channels and notes that the construction generalizes beyond two equations.
  • VII. SUCCESSIVE CANCELLATION: After decoding the first equation, a relay subtracts its contribution from the observation and uses the residual to decode a second equation.For a unit-vector first equation, the relay can reproduce and remove the corresponding codeword before decoding the residual equation.
  • VII. SUCCESSIVE CANCELLATION: When the first coefficient vector is not a unit vector, the relay uses the recovered lattice equation within the modified decoding procedure for the second equation.The proof substitutes the effective channel and coefficient terms into the single-equation analysis.
  • VII. SUCCESSIVE CANCELLATION: For h_1 = [10 10 8 8]^T, decoding [1 1 1 1]^T first enables [1 1 −1 −1]^T through τ_1 = 9, whereas direct decoding of the second equation has no positive rate.The example illustrates how cancellation changes the effective channel seen by the later equation.
  • VII. SUCCESSIVE CANCELLATION: Theorem 12 is strictly better than the basic strategy when an equation is recovered piecewise from equations over subsets of messages.The paper identifies this as a more efficient way to construct an equation in some cases.

A. Multiple-Access

Compute-and-forward can recover multiple linear equations using superimposed nested-lattice codebooks, while successive cancellation recovers the Gaussian multiple-access capacity region.

  • Multiple-access capacity: Successive cancellation lets compute-and-forward achieve any point in the Gaussian multiple-access capacity region when the relay wants all messages.Changing the decoding order achieves every corner point, and time-sharing achieves the boundary.
  • Superposition: Multiple equations can be decoded by superimposing lattice codebooks at different levels and applying successive cancellation.Each relay decodes equations over the first level and then the second, with scaling coefficients enforcing the power constraint.
  • Encoding: Each encoder maps separate messages to lattice points, dithers them modulo the coarse lattice, and combines the resulting signals using level-specific scaling.The construction uses nested lattice chains and independently generated dithers.
  • Superposition: The two-level superposition strategy extends to more levels, relay-specific decoding orders, and equations spanning levels.The paper presents these as immediate extensions of the two-level construction.
  • Example: An example with three transmitters shows a relay decoding one level-A equation followed by a level-B equation under the superposition scheme.The coefficient vectors are a1 = [0 0 1]T and b1 = [1 1 1]T.
  • Related result: Nested lattice codes can also approach the capacity region of the standard Gaussian broadcast problem.The paper cites prior work for this related result.

IX. OUTAGE FORMULATION

The outage analysis shows that decoding equations can outperform message decoding in fading channels, but end-to-end success additionally requires full-rank equations. In distributed MIMO, compute-and-forward is strongest at moderate and high transmit powers, while classical strategies retain low-power advantages.

  • IX. OUTAGE FORMULATION: Slow fading creates outage because transmitters use rates before the channel matrix remains fixed for the transmission.The scheme remains applicable without channel state information at the transmitters.
  • IX. OUTAGE FORMULATION: In the three-user relay example, compute-and-forward allows the relay to decode any nonzero linear equation of the messages, unlike classical message decoding.The comparison uses i.i.d. Gaussian channel coefficients known only to the relay and evaluates P = 10, 20, and 30 dB.
  • IX. OUTAGE FORMULATION: Decoding an equation is often easier than decoding a message, but network use requires the end-to-end transformation of desired messages to be full rank.The distributed MIMO case study examines this rank requirement.
  • X. CASE STUDY: DISTRIBUTED MIMO: The distributed MIMO case study uses two sources, two relays, one destination, local relay channel knowledge, and R0-bit-per-use relay-to-destination pipes.The fading coefficients are i.i.d. Rayleigh, and each relay observes only its own channel vector.
  • X. CASE STUDY: DISTRIBUTED MIMO: At low SNR, forcing each relay to choose an equation with a nonzero desired-message coefficient makes the equations more likely to be solvable, at a slight computation-rate cost.The basic best-equation strategy has a high probability of rank failure at low SNR.
  • X. CASE STUDY: DISTRIBUTED MIMO: The case study compares decode-and-forward, compress-and-forward, and compute-and-forward using achievable rates, a cut-set bound, and the distributed MIMO channel model.Decode-and-forward assigns each relay responsibility for one message, while compress-and-forward quantizes relay observations within R0 bits.
  • RMIMO(H), R0: Compute-and-forward with the best equation outperforms the other strategies from approximately 8dB and saturates the destination bit pipes using 5dB less power per transmitter than decode-and-forward.The comparison is for R0 = 2 and outage probability ρ = 1/4.
  • RMIMO(H), R0: Compress-and-forward is favorable at low power, decode-and-forward benefits from joint decoding there, and compute-and-forward is best in the moderate-power regime despite integer-coefficient mismatch noise.At high power, quantization noise limits compress-and-forward, while decode-and-forward becomes less efficient because it treats interference as noise or decodes both messages.

XI. UPPER BOUND

The upper-bound analysis derives a genie-aided rate bound for sending specified equations. The paper concludes that compute-and-forward provides useful network building blocks, while algebraic structure may require stronger outer bounds.

  • Upper bound: A genie-aided argument gives an upper bound on each message rate based on the mutual information available at relays whose target equations use that message.The bound takes the minimum over relays with nonzero corresponding equation coefficients.
  • Limitation: The paper notes that the genie-aided bound does not generally match the achievable strategy and may be tightened by modeling channel-function mismatch.This identifies a scope boundary of the presented outer bound.
  • Upper bound: The bound applies to general memoryless channels and specializes to real- and complex-valued Gaussian models with integer or Gaussian-integer coefficient vectors.The paper states the real and complex channel specializations separately.
  • Proof idea: The proof supplies every other message as genie-aided side information, reducing the problem to multicasting each message to the relevant relays.The multicast rate is limited by the lowest-rate link, and Gaussian inputs maximize the mutual-information expressions in the Gaussian case.
  • Conclusion: The framework is presented as a coding building block for AWGN networks, with distributed MIMO as one application and possible uses in sensor-network gossiping and low-complexity MIMO receivers.The conclusion attributes these uses to exploiting algebraic and statistical wireless-network structure.
  • Conclusion: Structured codes motivate new outer bounds that account for algebraic as well as statistical structure because usual cut-set bounds do not capture the observed behavior.The paper frames this as broader evidence from multi-user information theory.

APPENDIX A UPPER BOUND ON NOISE DENSITIES

The appendices establish that the effective noise is controlled by Gaussian density bounds and that nested lattice ensembles can be simultaneously good for AWGN. Fixed dithers preserve the desired error behavior with arbitrarily small rate loss.

  • Noise-density bound: The effective noise density is upper bounded by the density of an i.i.d. Gaussian vector.The proof uses convolution of independent component densities and an upper bound applied repeatedly across dimensions.
  • Noise-density bound: The density comparison depends on the coarse lattice’s covering and quantization properties and on geometric quantities including effective radius and normalized ball moments.The appendix uses the fact that a ball has the smallest second moment for a given volume.
  • AWGN-good lattices: Fine lattices are good for AWGN with probability tending to one as blocklength grows, provided the volume-to-noise ratio exceeds 2πe.The resulting error probability decreases exponentially with blocklength under the Poltyrev exponent.
  • AWGN-good lattices: The fine lattices’ pairwise independence and uniform marginal distributions suffice for a union-bound argument matching the relevant i.i.d. random-code error exponent.All L fine lattices are simultaneously good for AWGN with high probability as n →∞.
  • Fixed dithers: Fixed dithers can satisfy the power constraint because the covering-radius choice contains every transmission in the coarse lattice’s Voronoi region.The construction sets the covering radius to √nP.
  • Fixed dithers: The additional rate loss from replacing the coarse lattice’s second moment with the covering-radius construction is log(1 + δ) bits and can be made arbitrarily small.The argument applies for sufficiently large blocklength and any δ > 0.
  • Fixed dithers: Because error probability decays exponentially after averaging over dithers and noise, at least one fixed dither set achieves the desired error probability for sufficiently large n.This converts the randomized dither argument into an existence result for fixed dithers.
Loading 0908.2119v3…