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.

Delay and coding in multiple-user communications

Stéphane Musy

In multiple-user communications, the bursty nature of the packet arrival times cannot be divorced from the analysis of the transmission process. However, in traditional information theory the random arrival times are smoothed out by appropriated source coding and no consideration is made for the end-to-end delay. In this thesis, using tools from network theory, we investigate simple models that consider the end-to-end delay and/or the variability of the packet arrivals as important parameters, while staying in a information theoretic framework. First, we simplify the problem and focus on the transmission of a bursty source over a single-user channel. We introduce a new measure of channel features that enable us to incorporate the possibility to code among several packets in a scheduling problem. In this setup, we look for policies that minimize the average packet delay. Assuming that the packets are independent and sufficiently large to perform capacity achieving coding, we then consider the problem of allocating rates among a finite number of users communicating through a multiple-user channel. Following the previous work in the context of multiple-access channel, we formulate a scheduling problem in which the rate of each user is chosen from the capacity region of the multiple-user channel. Here, the goal is to find a scheduling policy that minimizes the sum of the transmitter queue lengths, such a policy is called delay optimal. In particular settings, for the additive Gaussian multiple-access channel we show the delay optimality of the Longer Queue Higher Rate policy introduced by Yeh. And, when the users communicate through a symmetric broadcast channel, we propose and show the delay optimality of a Best User Highest Possible Rate policy, among a large class of admissible policies. Finally, in the last part of this thesis, we look at the multiple-user channel coding problem from the perspective of the receivers. By measuring the transmission rates at the receivers, we are able to define variable length codes and to characterize the region of achievable rates when the receivers can decode their intended messages at different instants of time. For the two-user degraded broadcast channel and for the two-user multiple-access channel, we show that the gain in using variable length codes essentially comes from the possibility for the receivers to decode the transmitted messages in non-overlapping periods of time.

EPFL2007

Polar codes for channel and source coding

Satish Babu Korada

The two central topics of information theory are the compression and the transmission of data. Shannon, in his seminal work, formalized both these problems and determined their fundamental limits. Since then the main goal of coding theory has been to find practical schemes that approach these limits. Polar codes, recently invented by Arikan, are the first "practical" codes that are known to achieve the capacity for a large class of channels. Their code construction is based on a phenomenon called "channel polarization". The encoding as well as the decoding operation of polar codes can be implemented with O(N log N) complexity, where N is the blocklength of the code. We show that polar codes are suitable not only for channel coding but also achieve optimal performance for several other important problems in information theory. The first problem we consider is lossy source compression. We construct polar codes that asymptotically approach Shannon's rate-distortion bound for a large class of sources. We achieve this performance by designing polar codes according to the "test channel", which naturally appears in Shannon's formulation of the rate-distortion function. The encoding operation combines the successive cancellation algorithm of Arikan with a crucial new ingredient called "randomized rounding". As for channel coding, both the encoding as well as the decoding operation can be implemented with O(N log N) complexity. This is the first known "practical" scheme that approaches the optimal rate-distortion trade-off. We also construct polar codes that achieve the optimal performance for the Wyner-Ziv and the Gelfand-Pinsker problems. Both these problems can be tackled using "nested" codes and polar codes are naturally suited for this purpose. We further show that polar codes achieve the capacity of asymmetric channels, multi-terminal scenarios like multiple access channels, and degraded broadcast channels. For each of these problems, our constructions are the first known "practical" schemes that approach the optimal performance. The original polar codes of Arikan achieve a block error probability decaying exponentially in the square root of the block length. For source coding, the gap between the achieved distortion and the limiting distortion also vanishes exponentially in the square root of the blocklength. We explore other polar-like code constructions with better rates of decay. With this generalization, we show that close to exponential decays can be obtained for both channel and source coding. The new constructions mimic the recursive construction of Arikan and, hence, they inherit the same encoding and decoding complexity. We also propose algorithms based on message-passing to improve the finite length performance of polar codes. In the final two chapters of this thesis we address two important problems in graphical models related to communications. The first problem is in the area of low-density parity-check codes (LDPC). For practical lengths, LDPC codes using message-passing decoding are still the codes to beat. The current analysis, using density evolution, evaluates the performance of these algorithms on a tree. The tree assumption corresponds to using an infinite length code. But in practice, the codes are of finite length. We analyze the message-passing algorithms for this scenario. The absence of tree assumption introduces correlations between various messages. We show that despite this correlation, the prediction of the tree analysis is accurate. The second problem we consider is related to code division multiple access (CDMA) communication using random spreading. The current analysis mainly focuses on the information theoretic limits, i.e., using Gaussian input distribution. However in practice we use modulation schemes like binary phase-shift keying (BPSK), which is far from being Gaussian. The effects of the modulation scheme cannot be analyzed using traditional tools which are based on spectrum of large random matrices. We follow a new approach using tools developed for random spin systems in statistical mechanics. We prove a tight upper bound on the capacity of the system when the user input is BPSK. We also show that the capacity depends only on the power of the spreading sequences and is independent of their exact distribution.

EPFL2009

Approximation for Problems in Multi-User Information Theory

Soheil Mohajerzefreh

The main goal in network information theory is to identify fundamental limits of communication over networks, and design solutions which perform close to such limits. After several decades of effort, many important problems still do not have a characterization of achievable performance in terms of a finite dimensional description. Given this discouraging state of affairs, a natural question to ask is whether there are systematic approaches to make progress on these open questions. Recently, there has been significant progress on several open questions by seeking a (provably) approximate characterization for these open questions. The main goal of approximation in network information theory is to obtain a universal approximation gap between the achievable and the optimal performance. This approach consists of four ingredients: simplify the model, obtain optimal solution for the simplified model, translate this optimal scheme and outer bounds back to the original model, and finally bound the gap between what can be achieved using the obtained technique and the outer bound. Using such an approach, recent progress has been made in several problems such as the Gaussian interference channel, Gaussian relay networks, etc. In this thesis, we demonstrate that this approach is not only successful in problems of transmission over noisy networks, but gives the first approximation for a network data compression problem. We use this methodology to (approximately) resolve problems that have been open for several decades. Not only do we give theoretical characterization, but we also develop new coding schemes that are required to satisfy this approximate optimality property. These ideas could give insights into efficient design of future network communication systems. This thesis is split into two main parts. The first part deals with the approximation in lossy network data compression. Here, a lossy data compression problem is approximated by a lossless counterpart problem, where all the bits in the binary expansion of the source above the required distortion have to be losslessly delivered to the destination. In particular, we study the multiple description (MD) problem, based on the multi-level diversity (MLD) coding problem. The symmetric version of the MLD problem is well-studied, and we can directly use it to approximate the symmetric MD problem. We formulate the asymmetric multi-level diversity problem, and solve it for three-description case. The optimal solution for this problem, which will be later used to approximate the asymmetric multiple description problem, is based on jointly compressing of independent sources. In both symmetric and asymmetric cases, we derive inner and outer bounds for the achievable rate region, which together with the gap analysis, provide an approximate solution for the problem. In particular, we resolve the symmetric Gaussian MD problem, which has been open for three decades, to within 1 bit. In the second part, we initiate a study of a Gaussian relay-interference network, in which relay (helper) nodes are to facilitate competing information flows over a wireless network. We focus on a two-stage relay-interference network where there are weak cross-links, causing the networks to behave like a chain of Z Gaussian channels. For these Gaussian ZZ and ZS networks, we establish an approximate characterization of the rate region. The outer bounds to the capacity region are established using genie-aided techniques that yield bounds sharper than the traditional cut-set outer bounds. For the inner bound of the ZZ network, we propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This technique allows for over-the-air interference removal, without the transmitters having complete access to the interfering signals. We use insights gained from an exact characterization of the corresponding linear deterministic version of the problem, in order to study the Gaussian network. We resolve the Gaussian relay-interference network to within 2 bits. The new interference management technique (interference neutralization) shows the use of structured lattice codes in the problem. We also consider communication from a source to a destination over a wireless network with the help of a set of authenticated relays, and presence of an adversarial jammer who wishes to disturb communication. We focus on a special diamond network, and show that use of interference suppression (nulling) is crucial to approach the capacity of the network. The exact capacity characterization for the deterministic network, along with an approximate characterization (to within 4 bits) for the Gaussian network is provided. The common theme that binds the diverse network communication problems in this thesis is that of approximate characterization, when exact resolutions are difficult. The approach of focusing on the deterministic/lossless problems underlying the noisy/lossy network communication problems has allowed us to develop new techniques to study these questions. These new techniques might be of independent interest in other network information theory problems.

EPFL2010