Sum-Networks From Incidence Structures: Construction and Capacity Analysis

DOI10.1109/TIT.2017.2765661zbMATH Open1395.94242arXiv1611.01887OpenAlexW2963944130MaRDI QIDQ5375528

Aditya Ramamoorthy, Ardhendu Tripathy

Publication date: 14 September 2018

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: A sum-network is an instance of a network coding 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 instances of these two problems. In this work, 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 characterized. We demonstrate that unlike the 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. Additionally, a sum-network can have an arbitrary different number of computation capacities for different alphabets. This is contrast to the multiple unicast problem where it is known that the capacity is independent of the network coding alphabet.

Full work available at URL: https://arxiv.org/abs/1611.01887

Mathematics Subject Classification ID

Could not fetch data.

Recommendations

• On critical capacity of arcs in a directed network 👍 👎
• On the Shannon capacity of sums and products of graphs 👍 👎
• On general sum-connectivity index 👍 👎
• A note on capacity models for network design 👍 👎
• On the sum-connectivity index 👍 👎
• On the capacity of disjointly shared networks 👍 👎
• Towards a general theory of source networks 👍 👎
• Capacity results for the discrete memoryless network 👍 👎
• Network design with probabilistic capacities 👍 👎
• On Network Coding for Sum-Networks 👍 👎

This page was built for publication: Sum-Networks From Incidence Structures: Construction and Capacity Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5375528)