Compute-and-Forward: Harnessing Interference through Structured Codes Bobak Nazer, Member, IEEE and Michael Gastpar, Member, IEEE Abstract—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. Index Terms—Relaying, cooperative communication, structured codes, nested lattice codes, reliable computation, AWGN networks, interference. ### I. INTRODUCTION In a wireless network, a transmission from a single node is heard not only by the intended receiver, but also by all other nearby nodes; by analogy, any receiver not only captures the signal from its designated transmitter, but from all other nearby transmitters. The resulting interference is usually viewed as highly undesirable and clever algorithms and protocols have been devised to avoid interference between transmitters. Collectively, these strategies transform the physical layer into a set of reliable bit pipes, i.e. each link can accommodate a certain number of bits per time unit. These bit pipes can then be used seamlessly by higher layers in the protocol stack. Since wireless terminals must compete for the same fixed chunk of spectrum, interference avoidance results in diminishing rates as the network size increases. Recent work on cooperative communication has shown that this penalty can be overcome by adopting new strategies at the physical layer. The key idea is that users should help relay each other's messages by exploiting the broadcast and multiple-access properties of the wireless medium; properties that are usually viewed as a hindrance and are not captured by a bit pipe interface. To date, most proposed cooperative schemes have relied on one of the following three core relaying strategies: - Decode-and-Forward: The relay decodes at least some part of the transmitted messages. The recovered bits are then re-encoded for collaborative transmission to the next relay. Although this strategy offers significant advantages, the relay is ultimately interference-limited as the number of transmitted messages increases. - Compress-and-Forward: The signal observed at the relay is vector quantized and this information is passed towards the destination. If the destination receives information from multiple relays, it can treat the network as a multiple-input multiple-output (MIMO) channel. Unfortunately, since no decoding is performed at intermediate nodes, noise builds up as messages traverse the network. -Compute-and-Forward: Harnessing Interference through Structured Codes Bobak Nazer, Member, IEEE and Michael Gastpar, Member, IEEE Abstract—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. Index Terms—Relaying, cooperative communication, structured codes, nested lattice codes, reliable computation, AWGN networks, interference. ### I. INTRODUCTION In a wireless network, a transmission from a single node is heard not only by the intended receiver, but also by all other nearby nodes; by analogy, any receiver not only captures the signal from its designated transmitter, but from all other nearby transmitters. The resulting interference is usually viewed as highly undesirable and clever algorithms and protocols have been devised to avoid interference between transmitters. Collectively, these strategies transform the physical layer into a set of reliable bit pipes, i.e. each link can accommodate a certain number of bits per time unit. These bit pipes can then be used seamlessly by higher layers in the protocol stack. Since wireless terminals must compete for the same fixed chunk of spectrum, interference avoidance results in diminishing rates as the network size increases. Recent work on cooperative communication has shown that this penalty can be overcome by adopting new strategies at the physical layer. The key idea is that users should help relay each other's messages by exploiting the broadcast and multiple-access properties of the wireless medium; properties that are usually viewed as a hindrance and are not captured by a bit pipe interface. To date, most proposed cooperative schemes have relied on one of the following three core relaying strategies: - Decode-and-Forward: The relay decodes at least some part of the transmitted messages. The recovered bits are then re-encoded for collaborative transmission to the next relay. Although this strategy offers significant advantages, the relay is ultimately interference-limited as the number of transmitted messages increases. - Compress-and-Forward: The signal observed at the relay is vector quantized and this information is passed towards the destination. If the destination receives information from multiple relays, it can treat the network as a multiple-input multiple-output (MIMO) channel. Unfortunately, since no decoding is performed at intermediate nodes, noise builds up as messages traverse the network. -