Broadcasting Nested Message Sets

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.