On The Solvability And Network Coding Capacity Of Sum-networks

In this thesis, we consider a communication problem over a directed acyclic network of unit capacity links having m sources and n terminals, where each terminal requires the sum of symbols generated at all sources. We assume that each source generates one i. i. d. random process with uniform distribution over a finite alphabet have an abelian group structure, and the different source processes are independent. We also assume that each node in the network is capable of implementing network coding. We call such a directed acyclic network as a sum-network.We mainly consider the network coding capacity of sum-networks over a finite field. However, our results also hold over finite alphabets having more general algebraic structures, such as a module over a ring. The network coding capacity of a sum-network is proved to be upper bounded by the min-cut bound, which is the minimum of min-cut capacities of all source-terminal pairs over any alphabet. With the definition of min-cut to the network computing problem, we achieve the same bound by a different method. We present a lower bound for sum-networks with min{m,n}=2 under fractional network coding. Then we also give a lower bound on scalar linear network coding capacity of sum-networks with min{m,n}=2. For sum-networks with min{m, n}≥3, we obtain a lower bound by coding by time-sharing scheme, which is shown to be tight in some cases. Using the lower bound of network coding capacity of sum-networks with min{m, n}=2, we study the problem of computing the arithmetic sum of sources messages in directed acyclic networks with two sources, which shows that the achievable computing rate depends on the network coding capacity of sum-networks. Finally we consider the problem of rate 1 linear network code solutions over finite fields in some special classes of sum-networks having m sources and n terminals and prove that these classes of sum-networks are solvable.