On Network Coding Capacity - Matroidal Networks and Network Capacity Regions

Details On Network Coding Capacity - Matroidal Networks and Network Capacity Regions On Network Coding Capacity - Matroidal Networks and Network Capacity Regions

2011-03-02

arxiv.org/abs/1103.0358v1

Computer Science

Information Theory

Master of Engineering Thesis, MIT, September 2010, 70 pages, 10 figures

Scientific paper

One fundamental problem in the field of network coding is to determine the network coding capacity of networks under various network coding schemes. In this thesis, we address the problem with two approaches: matroidal networks and capacity regions. In our matroidal approach, we prove the converse of the theorem which states that, if a network is scalar-linearly solvable then it is a matroidal network associated with a representable matroid over a finite field. As a consequence, we obtain a correspondence between scalar-linearly solvable networks and representable matroids over finite fields in the framework of matroidal networks. We prove a theorem about the scalar-linear solvability of networks and field characteristics. We provide a method for generating scalar-linearly solvable networks that are potentially different from the networks that we already know are scalar-linearly solvable. In our capacity region approach, we define a multi-dimensional object, called the network capacity region, associated with networks that is analogous to the rate regions in information theory. For the network routing capacity region, we show that the region is a computable rational polytope and provide exact algorithms and approximation heuristics for computing the region. For the network linear coding capacity region, we construct a computable rational polytope, with respect to a given finite field, that inner bounds the linear coding capacity region and provide exact algorithms and approximation heuristics for computing the polytope. The exact algorithms and approximation heuristics we present are not polynomial time schemes and may depend on the output size.

Affiliated with

Also associated with

No associations

Rating

On Network Coding Capacity - Matroidal Networks and Network Capacity Regions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Network Coding Capacity - Matroidal Networks and Network Capacity Regions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Network Coding Capacity - Matroidal Networks and Network Capacity Regions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-473530