Algebraic network coding: A new perspective

Algebraic criteria for existence of scalar linear network codes to satisfy a set of connection requirements has been discussed extensively by Koetter and Ḿedard, Solving for a network code is now known to be equivalent to solving a system of polynomial equations obtained by assigning variables to edges in the line graph of the network and computing a suitable transfer function. An alternative formulation for arriving at an equivalent system of polynomial equations is given in this paper based on the decomposition of the original network into trees, which we call "information flow trees". The basic idea is to exploit the graph structure and assign variables suitably. Interestingly, the information flow tree approach results in only linear and degree-2 equations that can be simplified considerably in directed acyclic networks as shown in prior work. In this article, we provide an alternative derivation of the information flow tree approach that results in two further extensions to networks with cycles. The first extension is to flow acyclic solutions on any directed cyclic network. The second extension is to cyclic networks where all strongly connected components are simple cycles. Here the degree of the equations we are left to solve is limited to 4. © 2009 IEEE.