Author: Sinem Unal

Publisher:

Published: 2016

Total Pages: 366

ISBN-13:

We consider data dissemination from a single transmitter to multiple receivers with side information, which is possibly due to prior transmissions. Side information at receivers can be utilized to reduce the broadcasting rate at the transmitter. How to accomplish this is the main focus of this dissertation. We address this problem in three parts from an information theoretic point of view. First we model the source as uniform vector of bits and each side information is an arbitrary subset of the source. Known as index coding problem [1], we approach this problem as a special case of rate-distortion with multiple receivers, each with side information. Specifically, using techniques developed for the rate-distortion problem, we provide two upper bounds and one lower bound on the optimal index coding rate. The upper bounds are based on specific choices of the auxiliary random variables in the best existing scheme for the ratedistortion problem [2], which is shown invalid for the general rate-distortion problem and improved in our work [3] later. The lower bound is based on a new lower bound for the general rate-distortion problem. The bounds are shown to coincide for a number of (groupcast) index coding instances, including all instances for which the number of decoders does not exceed three. Then we consider rate-distortion with two decoders, each with distinct side information. This problem is well understood when the side information at the various decoders satisfies a certain degradedness condition. We consider cases in which this degradedness condition is violated but the source and the side information consist of jointly Gaussian vectors. We provide a hierarchy of four lower bounds on the optimal rate. These bounds are then used to determine the optimal rate for several classes of instances. Lastly, we consider a rate distortion problem with side information at multiple decoders. We provide an upper bound for general instances of this problem by utilizing random binning and simultaneous decoding techniques [4] and compare it with the existing bounds. Also, we provide a lower bound for the general problem, which was inspired by a linear-programming lower bound for index coding, and show that it subsumes most of the lower bounds in literature including the ones we used for the index coding and rate distortion with two decoders problems. Using these upper and lower bounds, we explicitly characterize the rate distortion function of a problem which can be seen as a Gaussian analogue of the \odd-cycle\" index coding problem."