Compute-Forward for DMCs: Simultaneous Decoding of Multiple Combinations

Algebraic network information theory is an emerging facet of network information theory, studying the achievable rates of random code ensembles that have algebraic structure, such as random linear codes. A distinguishing feature is that linear combinations of codewords can sometimes be decoded more efficiently than codewords themselves. The present work further develops this framework by studying the simultaneous decoding of multiple messages. Specifically, consider a receiver in a multi-user network that wishes to decode several messages. Simultaneous joint typicality decoding is one of the most powerful techniques for determining the fundamental limits at which reliable decoding is possible. This technique has historically been used in conjunction with random i.i.d. codebooks to establish achievable rate regions for networks. Recently, it has been shown that, in certain scenarios, nested linear codebooks in conjunction with "single-user" or sequential decoding can yield better achievable rates. For instance, the compute-forward problem examines the scenario of recovering L

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

CFMA (Compute-Forward Multiple Access) and its Applications in Network Information Theory

Jingge Zhu

While both fundamental limits and system implementations are well understood for the point-to-point communication system, much less is developed for general communication networks. This thesis contributes towards the design and analysis of advanced coding schemes for multi-user communication networks with structured codes. The first part of the thesis investigates the usefulness of lattice codes in Gaussian networks with a generalized compute-and-forward scheme. As an application, we introduce a novel multiple access technique --- Compute-Forward Multiple Access (CFMA), and show that it achieves the capacity region of the Gaussian multiple access channel (MAC) with low receiver complexities. Similar coding schemes are also devised for other multi-user networks, including the Gaussian MAC with states, the two-way relay channel, the many-to-one interference channel, etc., demonstrating improvements of system performance because of the good interference mitigation property of lattice codes. As a common theme in the thesis, computing the sum of codewords over a Gaussian MAC is of particular theoretical importance. We study this problem with nested linear codes, and improve upon the currently best known results obtained by nested lattice codes. Inspired by the advantages of linear and lattice codes in Gaussian networks, we make a further step towards understanding intrinsic properties of the sum of linear codes. The final part of the thesis introduces the notion of typical sumset and presents asymptotic results on the typical sumset size of linear codes. The results offer new insight to coding schemes with structured codes.

EPFL2016

Applications of Derandomization Theory in Coding

Mahdi Cheraghchi Bashi Astaneh

Randomized techniques play a fundamental role in theoretical computer science and discrete mathematics, in particular for the design of efficient algorithms and construction of combinatorial objects. The basic goal in derandomization theory is to eliminate or reduce the need for randomness in such randomized constructions. Towards this goal, numerous fundamental notions have been developed to provide a unified framework for approaching various derandomization problems and to improve our general understanding of the power of randomness in computation. Two important classes of such tools are pseudorandom generators and randomness extractors. Pseudorandom generators transform a short, purely random, sequence into a much longer sequence that looks random, while extractors transform a weak source of randomness into a perfectly random one (or one with much better qualities, in which case the transformation is called a randomness condenser). In this thesis, we explore some applications of the fundamental notions in derandomization theory to problems outside the core of theoretical computer science, and in particular, certain problems related to coding theory. First, we consider the wiretap channel problem which involves a communication system in which an intruder can eavesdrop a limited portion of the transmissions. We utilize randomness extractors to construct efficient and information-theoretically optimal communication protocols for this model. Then we consider the combinatorial group testing problem. In this classical problem, one aims to determine a set of defective items within a large population by asking a number of queries, where each query reveals whether a defective item is present within a specified group of items. We use randomness condensers to explicitly construct optimal, or nearly optimal, group testing schemes for a setting where the query outcomes can be highly unreliable, as well as the threshold model where a query returns positive if the number of defectives pass a certain threshold. Next, we use randomness condensers and extractors to design ensembles of error-correcting codes that achieve the information-theoretic capacity of a large class of communication channels, and then use the obtained ensembles for construction of explicit capacity achieving codes. Finally, we consider the problem of explicit construction of error-correcting codes on the Gilbert-Varshamov bound and extend the original idea of Nisan and Wigderson to obtain a small ensemble of codes, mostly achieving the bound, under suitable computational hardness assumptions.