Path Gain Algebraic Formulation for the Scalar Linear Network Coding Problem
| Autor: | Subramanian, Abhay T., Thangaraj, Andrew |
|---|---|
| Rok vydání: | 2008 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1109/TIT.2010.2054270 |
| Popis: | 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. Comment: 12 pages, 6 figures. Accepted for publication in IEEE Transactions on Information Theory (May 2010) |
| Databáze: | arXiv |
| Externí odkaz: |
|