Citation
Gu, WeiHsin (2009) On achievable rate regions for source coding over networks. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd05262009111455
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 errorfree, 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 multihop and multipath 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 longstanding open question: whether a singleletter 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 singleletter characterizations by using linear programming tools. Those examples contain (1) the lossless coded side information problem by Ahlswede and Korner, (2) the WynerZiv ratedistortion 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 twohop and the diamond networks. The twohop 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 multipath 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.
Item Type:  Thesis (Dissertation (Ph.D.)) 

Subject Keywords:  Achievable Rate Regions; Network Coding; Source Coding 
Degree Grantor:  California Institute of Technology 
Division:  Engineering and Applied Science 
Major Option:  Electrical Engineering 
Thesis Availability:  Public (worldwide access) 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  19 August 2008 
Record Number:  CaltechETD:etd05262009111455 
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd05262009111455 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  5265 
Collection:  CaltechTHESIS 
Deposited By:  WeiHsin Gu 
Deposited On:  09 Apr 2010 17:28 
Last Modified:  26 Dec 2012 03:17 
Thesis Files

PDF (Thesis.pdf)
 Final Version
See Usage Policy. 606Kb 
Repository Staff Only: item control page