Computer Science – Information Theory
Scientific paper
2008-07-08
Computer Science
Information Theory
12 pages, 6 figures. Accepted for publication in IEEE Transactions on Information Theory (May 2010)
Scientific paper
In the algebraic view, the solution to a network coding problem is seen as a variety specified by a system of polynomial equations typically derived by using edge-to-edge gains as variables. The output from each sink is equated to its demand to obtain polynomial equations. In this work, we propose a method to derive the polynomial equations using source-to-sink path gains as the variables. In the path gain formulation, we show that linear and quadratic equations suffice; therefore, network coding becomes equivalent to a system of polynomial equations of maximum degree 2. We present algorithms for generating the equations in the path gains and for converting path gain solutions to edge-to-edge gain solutions. Because of the low degree, simplification is readily possible for the system of equations obtained using path gains. Using small-sized network coding problems, we show that the path gain approach results in simpler equations and determines solvability of the problem in certain cases. On a larger network (with 87 nodes and 161 edges), we show how the path gain approach continues to provide deterministic solutions to some network coding problems.
Subramanian Abhay T.
Thangaraj Andrew
No associations
LandOfFree
Path Gain Algebraic Formulation for the Scalar Linear Network Coding Problem 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 Path Gain Algebraic Formulation for the Scalar Linear Network Coding Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Path Gain Algebraic Formulation for the Scalar Linear Network Coding Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-268245