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.
Consider a pair of correlated Gaussian sources (X 1,X 2). Two separate encoders observe the two components and communicate compressed versions of their observations to a common decoder. The decoder is interested in reconstructing a linear combination of X 1 and X 2 to within a mean-square distortion of D. We obtain an inner bound to the optimal rate-distortion region for this problem. A portion of this inner bound is achieved by a scheme that reconstructs the linear function directly rather than reconstructing the individual components X 1 and X 2 first. This results in a better rate region for certain parameter values. Our coding scheme relies on lattice coding techniques in contrast to more prevalent random coding arguments used to demonstrate achievable rate regions in information theory. We then consider the case of linear reconstruction of K sources and provide an inner bound to the optimal rate-distortion region. Some parts of the inner bound are achieved using the following coding structure: lattice vector quantization followed by ldquocorrelatedrdquo lattice-structured binning. Network information theory promises high gains over simple point-to-point communication techniques, at the cost of higher complexity. However, lack of structured coding schemes limited the practical application of these concepts so far. One of the basic elements of a network code is the binning scheme. Wyner (1974, 1978) and other researchers proposed various forms of coset codes for efficient binning, yet these schemes were applicable only for lossless source (or noiseless channel) network coding. To extend the algebraic binning approach to lossy source (or noisy channel) network coding, previous work proposed the idea of nested codes, or more specifically, nested parity-check codes for the binary case and nested lattices in the continuous case. These ideas connect network information theory with the rich areas of linear codes and lattice codes, and have strong potential for practical applications. We review these developments and explore their tight relation to concepts such as combined shaping and precoding, coding for memories with defects, and digital watermarking. We also propose a few novel applications adhering to a unified approach. The techniques of the geometry of numbers, especially the Minkowski-Hlawka theorem, are used to modify Shannon's existence proof for optimal channel codes, so that the modified proof applies specifically to lattice codes. The resulting existence proof states that there exist lattice codes which satisfy Shannon's bound to within the factor 4, and hence match the reliability exponent and critical rate bounds which Shannon derived for optimal codes with unspecified structure. Therefore, it is demonstrated that optimal codes need not be random, but rather that some of them have structure, e.g. the structure of a lattice code. > It has been conjectured that lattice codes are good for (almost) everything. As an additional bit of evidence for this claim, we offer a few results showing the utility of lattice codes for the AWGN relay channel. We show that the decode-and-forward rates of the relay channel can be achieved using lattice encoding and decoding. We present an encoding decoding technique that uses a doubly-nested lattice code. Encoding is accomplished using a combination of superposition encoding and block Markov encoding, while decoding is accomplished using a strategy reminiscent of Cover and El Gamal's list decoding. Our technique can be extended to a wide variety of relay topologies, including the half-duplex relay channel and the cooperative multiple-access channel. It is shown that lattice codes can achieve capacity on the additive white Gaussian noise channel. More precisely, for any rate R less than capacity and e>0, there exists a lattice code with rate no less than R and average error probability upper-bounded by e. These lattice codes include all points of the (translated) lattice within the spherical bounding region (not just the ones inside a thin spherical shell). We propose the notion of secrecy gain as a code design criterion for wiretap lattice codes to be used over an additive white Gaussian noise channel. Our analysis relies on the error probabilites of both the legitimate user and the eavesdropper. We focus on geometrical properties of lattices, described by their theta series, to characterize good wiretap codes. Recently, it has been shown that a quantize-map-and-forward scheme approximately achieves (within a constant number of bits) the Gaussian relay network capacity for arbitrary topologies. This was established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we show that the same approximation result can be established by using lattices for transmission and quantization along with structured mappings at the relays. An error in de Buda's (see IEEE J. Select Areas Commun., vol. 7, no. 6, p. 893, 1989) proof on the asymptotic optimality of lattice channel codes is pointed out and corrected using a modification of de Buda's approach. Comments are given on the correct interpretation and the limitations of this result. >  We consider distributed compression of a pair of Gaussian sources in which the goal is to reproduce a linear function of the sources at the decoder. It has recently been noted that lattice codes can provide improved compression rates for this problem compared to conventional, unstructured codes. We show that by including an additional linear binning stage, the state-of-the-art lattice scheme can be improved, in some cases by an arbitrarily large factor. We then describe a lower bound on the optimal sum rate for the case in which the variance of the linear combination exceeds the variance of one of the sources. This lower bound shows that unstructured codes achieve within one bit of the optimal sum rate at any distortion level. We also describe an outer bound on the rate-distortion region that holds in general, which for the special case of communicating the difference of two positively correlated Gaussian sources shows that the unimproved lattice scheme is within one bit of the rate region at any distortion level. This paper shows that structured transmission schemes are a good choice for secret communication over interference networks with an eavesdropper. Structured transmission is shown to exploit channel asymmetries and thus perform better than randomly generated codebooks for such channels. For a class of interference channels, we show that an equivocation sumrate that is within two bits of the maximum possible legitimate communication sum-rate is achievable using lattice codes. Recent results have shown that structured codes can be used to construct good channel codes, source codes and physical layer network codes for Gaussian channels. For Gaussian channels with secrecy constraints, however, efforts to date rely on random codes. In this work, we advocate that structured codes are useful for providing secrecy, and show how to compute the secrecy rate when structured codes are used. In particular, we solve the problem of bounding equivocation rates with one important class of structured codes, i.e., nested lattice codes. Having established this result, we next demonstrate the use of structured codes for secrecy in two-user Gaussian channels. In particular, with structured codes, we prove that a positive secure degree of freedom is achievable for a large class of fully connected Gaussian channels as long as the channel is not degraded. By way of this, for these channels, we establish that structured codes outperform Gaussian random codes at high SNR. This class of channels include the two-user multiple access wiretap channel, the two-user interference channel with confidential messages and the two-user interference wiretap channel. A notable consequence of this result is that, unlike the case with Gaussian random codes, using structured codes for both transmission and cooperative jamming, it is possible to achieve an arbitrary large secrecy rate given enough power. General random coding theorems for lattices are derived from the Minkowski-Hlawka theorem and their close relation to standard averaging arguments for linear codes over finite fields is pointed out. A new version of the Minkowski-Hlawka theorem itself is obtained as the limit, for p spl rarr spl infin , of a simple lemma for linear codes over GF(p) used with p-level amplitude modulation. The relation between the combinatorial packing of solid bodies and the information-theoretic "soft packing" with arbitrarily small, but positive, overlap is illuminated. The "soft-packing" results are new. When specialized to the additive white Gaussian noise channel, they reduce to (a version of) the de Buda-Poltyrev result that spherically shaped lattice codes and a decoder that is unaware of the shaping can achieve the rate 1 2 log sub 2 (P N).  In this paper, we consider a class of single-source multicast relay networks. We assume that all outgoing channels of a node in the network to its neighbors are orthogonal while the incoming signals from its neighbors can interfere with each other. We first focus on Gaussian relay networks with interference and find an achievable rate using a lattice coding scheme. We show that the achievable rate of our scheme is within a constant bit gap from the information theoretic cut-set bound, where the constant depends only on the network topology, but not on the transmit power, noise variance, and channel gains. This is similar to a recent result by Avestimehr, Diggavi, and Tse, who showed an approximate capacity characterization for general Gaussian relay networks. However, our achievability uses a structured code instead of a random one. Using the idea used in the Gaussian case, we also consider a linear finite-field symmetric network with interference and characterize its capacity using a linear coding scheme.