Citation
Bakshi, Mayank (2012) Network Coding and Distributed Compression over Large Networks: Some Basic Principles. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/GWDW-5H78. https://resolver.caltech.edu/CaltechTHESIS:06082012-122324439
Abstract
The fields of Network Coding and Distributed Compression have focused primarily on finding the capacity for families of problems defined by either a broad class of networks topologies (e.g., directed, acyclic networks) under a narrow class of demands (e.g., multicast), or a specific network topology (e.g. three-node networks) under different types of demands (e.g. Slepian-Wolf, Ahlswede-Körner). Given the difficulty of the general problem, it is not surprising that the collection of networks that have been fully solved to date is still very small. This work investigates several new approaches to bounding the achievable rate region for general network source coding problems - reducing a network to an equivalent network or collection of networks, investigating the effect of feedback on achievable rates, and characterizing the role of side information.
We describe two approaches aimed at simplifying the capacity calculations in a large network. First, we prove the optimality of separation between network coding and channel coding for networks of point-to-point channels with a Byzantine adversary. Next, we give a strategy for calculating the capacity of an error-free network by decomposing that network into smaller networks. We show that this strategy is optimal for a large class of networks and give a bound for other cases.
To date, the role of feedback in network source coding has received very little attention. We present several examples of networks that demonstrate that feedback can increases the set of achievable rates in both lossy and lossless network source coding settings. We derive general upper and lower bounds on the rate regions for networks with limited feedback that demonstrate a fundamental tradeoff between the forward rate and the feedback rate. For zero error source coding with limited feedback and decoder side information, we derive the exact tradeoff between the forward rate and the feedback rate for several classes of sources. A surprising result is that even zero rate feedback can reduce the optimal forward rate by an arbitrary factor.
Side information can be used to reduce the rates required for reliable information. We precisely characterize the exact achievable region for multicast networks with side information at the sinks and find upper and lower bounds on the achievable rate region for other demand types.
Item Type: | Thesis (Dissertation (Ph.D.)) | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subject Keywords: | network coding; data compression; information theory; | ||||||||||||
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: | 16 August 2011 | ||||||||||||
Non-Caltech Author Email: | mayank.bakshi (AT) gmail.com | ||||||||||||
Funders: |
| ||||||||||||
Record Number: | CaltechTHESIS:06082012-122324439 | ||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechTHESIS:06082012-122324439 | ||||||||||||
DOI: | 10.7907/GWDW-5H78 | ||||||||||||
Default Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
ID Code: | 7148 | ||||||||||||
Collection: | CaltechTHESIS | ||||||||||||
Deposited By: | Mayank Bakshi | ||||||||||||
Deposited On: | 11 Jun 2012 16:24 | ||||||||||||
Last Modified: | 07 Jun 2023 17:25 |
Thesis Files
|
PDF
- Final Version
See Usage Policy. 1MB |
Repository Staff Only: item control page