Compute–Forward Multiple Access (CFMA): Practical Implementations

Sula, Erixhen,Zhu, Jingge,Pastore, Adriano,Lim, Sung Hoon,Gastpar, Michael Institute of Electrical and Electronics Engineers 2019 IEEE transactions on communications Vol.67 No.2

<P>We present a practical strategy that aims to attain rate points on the dominant face of the multiple access channel capacity using a standard low complexity decoder. This technique is built upon recent theoretical developments of Zhu and Gastpar on compute–forward multiple access which achieves the capacity of the multiple access channel using a sequential decoder. We illustrate this strategy with off-the-shelf LDPC codes. In the first stage of decoding, the receiver first recovers a linear combination of the transmitted codewords using the sum-product algorithm (SPA). In the second stage, by using the recovered sum-of-codewords as side information, the receiver recovers one of the two codewords using a modified SPA, ultimately recovering both codewords. The main benefit of recovering the sum-of-codewords instead of the codeword itself is that it allows to attain points on the dominant face of the multiple access channel capacity without the need of rate-splitting or time sharing while maintaining a low complexity in the order of a standard point-to-point decoder. This property is also shown to be crucial for some applications, e.g., interference channels. For all the simulations with single-layer binary codes, our proposed practical strategy is shown to be within 1.7 dB of the theoretical limits, without explicit optimization on the off-the-self LDPC codes.</P>

A Joint Typicality Approach to Compute–Forward

Lim, Sung Hoon,Feng, Chen,Pastore, Adriano,Nazer, Bobak,Gastpar, Michael IEEE 2018 IEEE transactions on information theory Vol.64 No.12

<P>This paper presents a joint typicality framework for encoding and decoding nested linear codes in multi-user networks. This framework provides a new perspective on compute–forward within the context of discrete memoryless networks. In particular, it establishes an achievable rate region for computing a linear combination over a discrete memoryless multiple-access channel (MAC). When specialized to the Gaussian MAC, this rate region recovers and improves upon the lattice-based compute–forward rate region of Nazer and Gastpar, thus providing a unified approach for discrete memoryless and Gaussian networks. Furthermore, our framework provides some valuable insights on establishing the optimal decoding rate region for compute–forward by considering joint decoders, progressing beyond most previous works that consider successive cancellation decoding. Specifically, this paper establishes an achievable rate region for simultaneously decoding two linear combinations of nested linear codewords from <TEX>$K$</TEX> senders.</P>

Computation in Multicast Networks: Function Alignment and Converse Theorems

Changho Suh,Goela, Naveen,Gastpar, Michael Institute of Electrical and Electronics Engineers 2016 IEEE Transactions on Information Theory Vol. No.

<P>The classical problem in a network coding theory considers communication over multicast networks. Multiple transmitters send independent messages to multiple receivers that decode the same set of messages. In this paper, computation over multicast networks is considered: each receiver decodes an identical function of the original messages. For a countably infinite class of two-transmitter two-receiver single-hop linear deterministic networks, the computation capacity is characterized for a linear function (modulo-2 sum) of Bernoulli sources. A new upper bound is derived that is tighter than cut-set-based and genie-aided bounds. A matching inner bound is established via the development of a network decomposition theorem, which identifies elementary parallel subnetworks that can constitute an original network without loss of optimality. The decomposition theorem provides a conceptually simple proof of achievability that generalizes to L-transmitter L-receiver networks.</P>

Communication Versus Computation: Duality for Multiple-Access Channels and Source Coding

Zhu, Jingge,Lim, Sung Hoon,Gastpar, Michael IEEE 2019 IEEE transactions on information theory Vol.65 No.1

<P>Computation codes in network information theory are designed for scenarios where the decoder is not interested in recovering the information sources themselves, but only a function thereof. Körner and Marton showed for distributed source coding (DSC) that such function decoding can be achieved more efficiently than decoding the full information sources. Compute–forward has shown that function decoding, in combination with network coding ideas, is a useful building block for end-to-end communication over a network. In both cases, good computation codes are the key component in the coding schemes. Could these same codes simultaneously also enable full message decoding over a sufficiently strong multiple-access channel (MAC)? This work establishes a partial negative answer and converse result. Specifically, for any code that is known to be a good computation code for some MAC, we characterize a class of MACs for which that code cannot enable full message decoding (and vice versa). Finally, an analogous duality result is established for a related DSC problem.</P>

Computation over Gaussian networks with orthogonal components

Jeon, S.-W.,Wang, C.-Y.,Gastpar, M. IEEE 2013 Proceedings Vol.2013 No.3

Interactive Computation of Type-Threshold Functions in Collocated Gaussian Networks

Chien-Yi Wang,Sang-Woon Jeon,Gastpar, Michael IEEE 2015 IEEE transactions on information theory Vol.61 No.9

<P>In wireless sensor networks, various applications involve learning one or multiple functions of the measurements observed by sensors, rather than the measurements themselves. This paper focuses on the class of type-threshold functions, e.g., the maximum and the indicator functions. A simple network model capturing both the broadcast and superposition properties of wireless channels is considered: the collocated Gaussian network. A general multiround coding scheme exploiting superposition and interaction (through broadcast) is developed. Through careful scheduling of concurrent transmissions to reduce redundancy, it is shown that given any independent measurement distribution, all type-threshold functions can be computed reliably with a nonvanishing rate in the collocated Gaussian network, even if the number of sensors tends to infinity.</P>

Information-Theoretic Caching: The Multi-User Case

Sung Hoon Lim,Chien-Yi Wang,Gastpar, Michael IEEE 2017 IEEE transactions on information theory Vol.63 No.11

<P>In this paper, we consider a cache aided network in which each user is assumed to have individual caches, while upon users' requests, an update message is sent through a common link to all users. First, we formulate a general information theoretic setting that represents the database as a discrete memoryless source, and the users' requests as side information that is available everywhere except at the cache encoder. The decoders' objective is to recover a function of the source and the side information. By viewing cache aided networks in terms of a general distributed source coding problem and through information theoretic arguments, we present inner and outer bounds on the fundamental tradeoff of cache memory size and update rate. Then, we specialize our general inner and outer bounds to a specific model of content delivery networks: file selection networks, in which the database is a collection of independent equal-size files and each user requests one of the files independently. For file selection networks, we provide an outer bound and two inner bounds (for centralized and decentralized caching strategies). For the case when the user request information is uniformly distributed, we characterize the rate versus cache size tradeoff to within a multiplicative gap of 4. By further extending our arguments to the framework of Maddah-Ali and Niesen, we also establish a new outer bound and two new inner bounds in which it is shown to recover the centralized and decentralized strategies, previously established by Maddah-Ali and Niesen. Finally, in terms of rate versus cache size tradeoff, we improve the previous multiplicative gap of 72 to 4.7 for the average case with uniform requests.</P>