Sum-Networks from Incidence Structures: Construction and Capacity Analysis
A sum-network is an instance of a function computation problem over a directed acyclic network, in which each terminal node wants to compute the sum over a finite field of the information observed at all the source nodes. Many characteristics of the well-studied multiple unicast network communication problem also hold for sum-networks, due to a known reduction between the two problems. In this paper, we describe an algorithm to construct families of sum-network instances using incidence structures. The computation capacity of several of these sum-network families is evaluated. Unlike the coding capacity of a multiple unicast problem, the computation capacity of sum-networks depends on the characteristic of the finite field over which the sum is computed. This dependence is very strong; we show examples of sum-networks that have a rate-1 solution over one characteristic but a rate close to zero over a different characteristic. In addition, a sum-network can have arbitrarily different computation capacities for different alphabets.
A. S. Tripathy and A. Ramamoorthy, "Sum-Networks from Incidence Structures: Construction and Capacity Analysis," IEEE Transactions on Information Theory, vol. 64, no. 5, pp. 3461-3480, Institute of Electrical and Electronics Engineers (IEEE), May 2018.
The definitive version is available at https://doi.org/10.1109/TIT.2017.2765661
Keywords and Phrases
Characteristic; Function Computation; Incidence Structures; Network Coding; Sum-Networks
International Standard Serial Number (ISSN)
Article - Journal
© 2018 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
01 May 2018