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

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.

I. Introduction

To set the stage for the results and discussion presented in this paper, it is instructive to consider the two-sender two-receiver memoryless network illustrated in Figure 1. Specifically, this network consists of two multiple access channels that we allow to be different in general, characterized by their respective conditional probability distributions. The two decoders have different decoding goals: Decoder 1 wishes only to recover a function of the two codewords, where denotes the transmitted codeword from user . By contrast, Decoder 2 is a regular multiple access decoder who wishes to recover both codewords (and equivalently both messages). As illustrated in the figure, the same pair of codes are used to serve two purposes (decoding individual codewords and decoding a function thereof) at the same time. This setup will expose the tension between the codes’ computation and multiple access capabilities. Fig. 1.

A two-sender network with channel distribution . Decoder 1 finds an estimate of the desired function of codewords , while Decoder 2 wishes to recover both codewords separately.