Broadcast, relay and feedback in Gaussian channels

Network information theory explores the fundamental data transport limits over communication networks. Broadcasting and relaying are two natural models arising in communication contexts where multiple users share a common communication medium. Number of relay and broadcasting models are considered in this thesis. We first collect the existing methodologies of communication over a discrete memoryless relay channel. A new communication strategy over this channel is also proposed, which achieves the same data-rates as the best known schemes in literature, incurring a lower delay at the same time. We then consider the Gaussian broadcast channel (GBC), and show that its capacity region is enlarged by the availability of feedback, even if the feedback is from only one of the receivers. We further show a low complexity, explicit capacity achieving strategy over a GBC with degraded receivers. A combination of relay and broadcast models, called the relay-broadcast channel (RBC) is analyzed next. Achievable regions are proposed for different RBC scenarios. For the Gaussian version of an RBC, we characterize the complete capacity region when the receivers are degraded with respect to the relay. The final part of this thesis investigates communication over fading channels. We propose upper bounds for non-coherent, as well as lower bounds for coherent communication over a MIMO fading channel.

Broadcasting and Multicasting Nested Message Sets

Shirin Saeedi Bidokhti

Finding theoretical limits on the performance of communication systems and designing schemes to achieve them is one of the fundamental questions in information theory. While the theory of point-to-point communication is well-investigated, most problems have remained unresolved when communication is over a multi-user system. This lack of understanding is unsatisfactory for today’s growing networks. Recently, significant progress has been made on these problems through a deterministic approach which lays out a promising path in developing a better understanding of multi-user communication systems and in devising new communication schemes. In this thesis, we take a deterministic approach to the problem of communicating nested message sets over wireless and wireline networks. This class of problems is motivated by its applications in video streaming services over heterogeneous networks, where users have different quality-of-service demands. This thesis mainly considers the scenario where a common message (e.g., the low resolution information of a video stream) and a private message (e.g., a higher level of resolution) are to be encoded into a signal and transmitted over a shared medium (e.g., mobile networks, the Internet) towards a set of users. A group of the users, called public receivers, demand only the common message and the rest, called private receivers, demand both messages. The focus is on single-hop broadcast channels and multi-hop wireline networks. A Linear deterministic model for broadcast channels assumes that every user receives a linear transformation of the sent signal. This model is mainly motivated by the MIMO Gaussian broadcast problem in the high SNR regime. We start our study with a simple, yet rich, class of such broadcast channels. We address the main challenges in designing optimal encoding schemes and seek new techniques. In particular, we give an exact characterization of the ultimate rates of communication (together with a class of linear codes that achieves them) over channels with three public and any number of private receivers. We show sub-optimality of these schemes for channels with more than three public receivers and propose a block Markov scheme which allows communication at higher rates. Using this technique, we characterize a set of achievable rates of communication. The intuitions and techniques that we develop over this class of channels guide us towards designing optimal codes for (general) linear deterministic channels. We fully characterize the set of all admissible rates of communication for linear deterministic channels with two public and any number of private receivers. We extend this result to also allow communication of three nested message sets. The study of deterministic models is aimed to be instructive for understanding more general channels. In this regard, we consider the problem of broadcasting two nested message sets over general broadcast channels with two public and one private receiver. For such general broadcast channels, the ultimate rates of communications (and consequently optimal communication schemes) are still unknown. We adapt the block Markov encoding scheme, which we developed within the framework of linear deterministic channels, to general broadcast channels and characterize a set of achievable rates. This achievable rate-region turns out to be equal to the best previously known region (over channels with two public and one private receiver). Nonetheless, we argue that it remains possible that our block Markov encoding scheme may strictly outperform the previous schemes over channels with more (public) receivers. We discuss potential future directions that seem promising. When communication takes place over a multi-hop network, devising optimal communication strategies becomes much more challenging as the encoding scheme of the source should be designed jointly together with the encoding schemes of all the intermediate nodes of the network. We explore this problem over wireline networks, assuming two public and one private receiver. First, we ask if one can always devise a simple and rate-optimal strategy to route the private information to the private receiver and on the remaining network multicast the common message to all receivers. We discuss networks for which this strategy is suboptimal and characterize a class of networks for which it is indeed optimal. We also establish close connections of this problem to linear deterministic channels. This connection lets us formulate another strategy for nodes’ operations which achieves higher rates of transmission. Characterizing all admissible rates of communication over this three-receiver network remains open for further investigation.

EPFL2012

From Polar to Reed-Muller Codes

Marco Mondelli

The year 2016, in which I am writing these words, marks the centenary of Claude Shannon, the father of information theory. In his landmark 1948 paper "A Mathematical Theory of Communication", Shannon established the largest rate at which reliable communication is possible, and he referred to it as the channel capacity. Since then, researchers have focused on the design of practical coding schemes that could approach such a limit. The road to channel capacity has been almost 70 years long and, after many ideas, occasional detours, and some rediscoveries, it has culminated in the description of low-complexity and provably capacity-achieving coding schemes, namely, polar codes and iterative codes based on sparse graphs. However, next-generation communication systems require an unprecedented performance improvement and the number of transmission settings relevant in applications is rapidly increasing. Hence, although Shannon's limit seems finally close at hand, new challenges are just around the corner. In this thesis, we trace a road that goes from polar to Reed-Muller codes and, by doing so, we investigate three main topics: unified scaling, non-standard channels, and capacity via symmetry. First, we consider unified scaling. A coding scheme is capacity-achieving when, for any rate smaller than capacity, the error probability tends to 0 as the block length becomes increasingly larger. However, the practitioner is often interested in more specific questions such as, "How much do we need to increase the block length in order to halve the gap between rate and capacity?". We focus our analysis on polar codes and develop a unified framework to rigorously analyze the scaling of the main parameters, i.e., block length, rate, error probability, and channel quality. Furthermore, in light of the recent success of a list decoding algorithm for polar codes, we provide scaling results on the performance of list decoders. Next, we deal with non-standard channels. When we say that a coding scheme achieves capacity, we typically consider binary memoryless symmetric channels. However, practical transmission scenarios often involve more complicated settings. For example, the downlink of a cellular system is modeled as a broadcast channel, and the communication on fiber links is inherently asymmetric. We propose provably optimal low-complexity solutions for these settings. In particular, we present a polar coding scheme that achieves the best known rate region for the broadcast channel, and we describe three paradigms to achieve the capacity of asymmetric channels. To do so, we develop general coding "primitives", such as the chaining construction that has already proved to be useful in a variety of communication problems. Finally, we show how to achieve capacity via symmetry. In the early days of coding theory, a popular paradigm consisted in exploiting the structure of algebraic codes to devise practical decoding algorithms. However, proving the optimality of such coding schemes remained an elusive goal. In particular, the conjecture that Reed-Muller codes achieve capacity dates back to the 1960s. We solve this open problem by showing that Reed-Muller codes and, in general, codes with sufficient symmetry are capacity-achieving over erasure channels under optimal MAP decoding. As the proof does not rely on the precise structure of the codes, we are able to show that symmetry alone guarantees optimal performance.

EPFL2016

Bits through Time

Elie Najm

In any communication system, there exist two dimensions through which the information at the source becomes distorted before reaching the destination: the noisy channel and time. Messages transmitted through a noisy channel are susceptible to modification in their content, due to the action of the noise of the channel. Claude E. Shannon, in his seminal paper of 1948 "A Mathematical Theory of Communication", introduces the bit as a unit of measure of information, and he lays down the theoretical foundations needed to understand the problem of sending bits reliably through a noisy channel. The distortion measure, which he used to quantify reliability, is the error probability. In his paper, Shannon shows that any channel is characterized by a number that he calls capacity: It represents the highest transmission rate that can be used to communicate information with, through this same channel, while guaranteeing a negligible error probability. Whereas, even if the messages are sent through a perfect channel, the time they take to reach their destination causes the receiver to acquire a distorted view of the status of the source that generated these messages. For instance, take the case of a monitor interested in the status of a distant process. A sender observes this process and, to keep the monitor up-to-date, sends updates to it. However, if, at any time t, the last received update at the monitor was generated at time u(t), then the information at the receiver reflects the status of the process at time u(t), not at time t. Hence, the monitor has a distorted version of reality. In fact, it has an obsolete version with an age of t-u(t). The concept of age as a distortion measure in communication systems was first used in 2011 by Kaul et al., in order to assess the performance of a given vehicular network. The aim of the authors was to come up with a transmission scheme that would minimize an age-related metric: the average age. Since then, a growing body of works has used this metric to evaluate the performance of multiple communication systems. The drive behind this interest lies in the importance that status-update applications are gaining in today's life (in vehicular networks, warehouse and environment surveillance, news feed,etc.). In this thesis, we choose age as a distortion measure and derive expressions for the average age and the average peak-age (another age-related metric) for different communication systems. Therefore, we divide this dissertation into two parts: In the first part, we assume that the the updates are transmitted through a noiseless channel that has a random service time. In the second part, we consider a special category of noisy channels, namely the erasure channel. In the first part of this thesis, in order to compute the age-related metrics, we employ queue-theoretic concepts. We study and compare the performance of various transmission schemes under different settings.We show that the optimal transmission scheme when the monitor is interested in a single source loses its optimality when another source of higher priority shares the system. In the second part of this thesis, we introduce, in our age calculations, the distortion caused by the erasure channel on the transmitted updates. In order to combat the erasures of the channel, we first consider two flavors of the hybrid automatic repeat request (HARQ). Finally, we focus on the optimal average age that could be achieved over an erasure channel.

EPFL2019