**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# Broadcasting and Multicasting Nested Message Sets

Résumé

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.

Official source

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Concepts associés (33)

Récepteur radio

Un récepteur radio, aussi appelé simplement radio ou poste de radio, est un appareil électronique destiné à capter, sélectionner et décoder les ondes radioélectriques émises par les émetteurs radio.

Réseau sans fil

Un réseau sans fil est un réseau informatique numérique qui connecte différents postes ou systèmes entre eux par ondes radio. Il peut être associé à un réseau de télécommunications pour réaliser des

Code linéaire

En mathématiques, plus précisément en théorie des codes, un code linéaire est un code correcteur ayant une certaine propriété de linéarité.
Plus précisément, un tel code est structuré comme un sous-e

Publications associées (52)

Chargement

Chargement

Chargement

The focus of this thesis is on communication over cooperative information networks. In the first half of the thesis, we consider lossy source coding problems where a relay assists in the communication of a source stream between two terminals. The following two configurations are studied – (1) The Slepian-Wolf problem setup when the two encoding terminals are allowed a certain degree of collaboration in describing the source to the decoder and (2) A cascade communication system where the communication between the source and the destination is enabled through a relay (or a set of relays). We characterize rate-distortion tradeoffs and compute it explicitly for specific cases when the sources are respectively, jointly Gaussian and binary symmetric. In the second half of the thesis, we consider channel coding over orthogonal information networks. In particular, we find bounds to the capacity region of networks of Multiple Access Channels (MACs) and networks of Deterministic Broadcast Channels (DBCs). We propose a two layered achievability scheme for communication over such networks – consisting of a physical layer that involves "cleaning up" the constituent channels in the network to create a point-to-point wired overlay, and a network layer that involves routing over this wired overlay. We also consider two multicast problems over orthogonal networks. The first problem is the multiple-access multicast problem over a network of DBCs. In the second problem, we consider multicasting a common message along with independent "private messages" from a source node to a set of receivers on a wired network and characterize the capacity region when the network satisfies a certain min-cut property.

Suhas Diggavi, Vinod Malathidevi Prabhakaran, Shirin Saeedi Bidokhti

In this paper, we take a deterministic approach to the problem of broadcasting nested message sets. We mainly consider the scenario where a common message and a private message are to be encoded into a signal and transmitted over a broadcast channel 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. 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. We discuss potential future directions that seem promising.

2012The 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.