On Achievable Rate Regions for Source Coding Over Networks

Citation

Gu, WeiHsin (2009) On Achievable Rate Regions for Source Coding Over Networks. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/J8JP-R695. https://resolver.caltech.edu/CaltechETD:etd-05262009-111455

Abstract

In the field of source coding over networks, a central goal is to understand the best possible performance for compressing and transmitting dependent data distributed over a network. The achievable rate region for such a network describes all link capacities that suffice to satisfy the reproduction demands. Here all the links in the networks are error-free, the data dependency is given by a joint distribution of the source random variables, and the source sequences are drawn i.i.d. according to the given source distribution. In this thesis, I study the achievable rate regions for general networks, deriving new properties for the rate regions of general network source coding problems, developing approximation algorithms to calculate these regions for particular examples, and deriving bounds on the regions for basic multi-hop and multi-path examples.

In the first part, I define a family of network source coding problems. That family contains all of the example networks in the literature as special cases. For the given family, I investigate abstract properties of the achievable rate regions for general networks. These properties include (1) continuity of the achievable rate regions with respect to both the source distribution and the distortion constraint vector and (2) a strong converse that implies the traditional strong converse. Those properties might be useful for studying a long-standing open question: whether a single-letter characterization of a given achievable rate region always exists.

In the second part, I develop a family of algorithms to approximate the achievable rate regions for some example network source coding problems based on their single-letter characterizations by using linear programming tools. Those examples contain (1) the lossless coded side information problem by Ahlswede and Korner, (2) the Wyner-Ziv rate-distortion function, and (3) the Berger et al. bound for the lossy coded side information problem. The algorithms may apply more widely to other examples.

In the third part, I study two basic networks of different types: the two-hop and the diamond networks. The two-hop network is a basic example of line networks with single relay node on the path from the source to the destination, and the diamond network is a basic example of multi-path networks that has two paths from the source to the destination, where each of the paths contains a relay node. I derive performance bounds for the achievable rate regions for these two networks.

Thesis Files