2016/11/06 by Ardhendu Tripathy, Tripathy, Ardhendu, Aditya Ramamoorthy +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Cooperative Communication and Network Coding #DNA and Biological Computing #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1611.01887
openalex publication_date 2016/11/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A sum-network is an instance of a network coding problem over a directed\nacyclic network in which each terminal node wants to compute the sum over a\nfinite field of the information observed at all the source nodes. Many\ncharacteristics of the well-studied multiple unicast network communication\nproblem also hold for sum-networks due to a known reduction between instances\nof these two problems. In this work, we describe an algorithm to construct\nfamilies of sum-network instances using incidence structures. The computation\ncapacity of several of these sum-network families is characterized. We\ndemonstrate that unlike the multiple unicast problem, the computation capacity\nof sum-networks depends on the characteristic of the finite field over which\nthe sum is computed. This dependence is very strong; we show examples of\nsum-networks that have a rate-1 solution over one characteristic but a rate\nclose to zero over a different characteristic. Additionally, a sum-network can\nhave an arbitrary different number of computation capacities for different\nalphabets. This is contrast to the multiple unicast problem where it is known\nthat the capacity is independent of the network coding alphabet.\n