We examine the benefits of user cooperation under compute-and-forward. Much like in network coding, receivers in a compute-and-forward network recover finite-field linear combinations of transmitters' messages. Recovery is enabled by linear codes: transmitters map messages to a linear codebook, and receivers attempt to decode the incoming superposition of signals to an integer combination of codewords. However, the achievable computation rates are low if channel gains do not correspond to a suitable linear combination. In response to this challenge, we propose a cooperative approach to compute-and-forward. We devise a lattice-coding approach to block Markov encoding with which we construct a decode-and-forward style computation strategy. Transmitters broadcast lattice codewords, decode each other's messages, and then cooperatively transmit resolution information to aid receivers in decoding the integer combinations. Using our strategy, we show that cooperation offers a significant improvement both in the achievable computation rate and in the diversity-multiplexing tradeoff.
Compute-and-forward can be viewed as one of several wireless instantiations of network coding. Network coding was introduced in @cite_55 , where it was shown that network coding achieves the multicast capacity of wireline networks. It was later shown that (random) linear network codes are sufficient for multicast @cite_51 @cite_42 @cite_45 , and although linear codes are provably insufficient for general wireline networks @cite_14 they remain popular due to their simplicity and effectiveness. Network coding has been applied to wireless networks by several means. Two information-theoretic techniques are the quantize-map-and-forward of @cite_20 and the noisy'' network coding of @cite_27 , in which relays compress and re-encode the incoming superposition of signals. These approaches generalize the discrete-valued, noiseless combinations of wireline network coding to continuous-valued, noisy combinations over wireless links. For multicast networks, they come to within a constant gap of capacity. Finally, lattice techniques similar to compute-and-forward have been used for the two-way and multi-way relay channels, again achieving rates within a constant gap of capacity @cite_48 @cite_26 @cite_29 @cite_39 .
@cite_14 @cite_26 @cite_48 @cite_55 @cite_42 @cite_29 @cite_39 @cite_27 @cite_45 @cite_51 @cite_20
2132100261 2400872280 2153077717 2069554030
A noisy network coding scheme for communicating messages between multiple sources and destinations over a general noisy network is presented. For multi-message multicast networks, the scheme naturally generalizes network coding over noiseless networks by Ahlswede, Cai, Li, and Yeung, and compress-forward coding for the relay channel by Cover and El Gamal to discrete memoryless and Gaussian networks. The scheme also extends the results on coding for wireless relay networks and deterministic networks by Avestimehr, Diggavi, and Tse, and coding for wireless erasure networks by Dana, Gowaikar, Palanki, Hassibi, and Effros. The scheme involves lossy compression by the relay as in the compress-forward coding scheme for the relay channel. However, unlike previous compress-forward schemes in which independent messages are sent over multiple blocks, the same message is sent multiple times using independent codebooks as in the network coding scheme for cyclic networks. Furthermore, the relays do not use Wyner-Ziv binning as in previous compress-forward schemes, and each decoder performs simultaneous decoding of the received signals from all the blocks without uniquely decoding the compression indices. A consequence of this new scheme is that achievability is proved simply and more generally without resorting to time expansion to extend results for acyclic networks to networks with cycles. The noisy network coding scheme is then extended to general multi-message networks by combining it with decoding techniques for the interference channel. For the Gaussian multicast network, noisy network coding improves the previously established gap to the cutset bound. We also demonstrate through two popular Gaussian network examples that noisy network coding can outperform conventional compress-forward, amplify-forward, and hash-forward coding schemes. Lattice codes used under the Compute-and-Forward paradigm suggest an alternative strategy for the standard Gaussian multiple-access channel (MAC): The receiver successively decodes integer linear combinations of the messages until it can invert and recover all messages. In this paper, this strategy is developed and analyzed. For the two-user MAC, it is shown that without time-sharing, the entire capacity region can be attained with a single-user decoder as soon as the signal-to-noise ratios are above @math . A partial analysis is given for more than two users. Lastly the strategy is extended to the so-called dirty MAC where two interfering signals are known non-causally to the two transmitters in a distributed fashion. Our scheme extends the previously known results and gives new achievable rate regions. A wireless network with fading and a single source-destination pair is considered. The information reaches the destination via multiple hops through a sequence of layers of single-antenna relays. At high signal-to-noise ratio (SNR), the simple amplify-and-forward strategy is shown to be optimal in terms of degrees of freedom, because it achieves the degrees of freedom equal to a point-to-point multiple-input multiple-output (MIMO) system. Hence, the lack of coordination in relay nodes does not reduce the achievable degrees of freedom. The performance of this amplify-and-forward strategy degrades with increasing network size. This phenomenon is analyzed by finding the tradeoffs between network size, rate, and diversity. A lower bound on the diversity-multiplexing tradeoff for concatenation of multiple random Gaussian matrices is obtained. Also, it is shown that achievable network size in the outage formulation (short codes) is a lot smaller than the ergodic formulation (long codes). Consider several source nodes communicating across a wireless network to a destination node with the help of several layers of relay nodes. Recent work by Avestimehr has approximated the capacity of this network up to an additive gap. The communication scheme achieving this capacity approximation is based on compress-and-forward, resulting in noise accumulation as the messages traverse the network. As a consequence, the approximation gap increases linearly with the network depth. This paper develops a computation alignment strategy that can approach the capacity of a class of layered, time-varying wireless relay networks up to an approximation gap that is independent of the network depth. This strategy is based on the compute-and-forward framework, which enables relays to decode deterministic functions of the transmitted messages. Alone, compute-and-forward is insufficient to approach the capacity as it incurs a penalty for approximating the wireless channel with complex-valued coefficients by a channel with integer coefficients. Here, this penalty is circumvented by carefully matching channel realizations across time slots to create integer-valued effective channels that are well suited to compute-and-forward. Unlike prior constant gap results, the approximation gap obtained in this paper also depends closely on the fading statistics, which are assumed to be i.i.d. Rayleigh.