Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Engineering
Capacity Of Sum-Networks For Different Message Alphabets, Ardhendu Tripathy, Aditya Ramamoorthy
Capacity Of Sum-Networks For Different Message Alphabets, Ardhendu Tripathy, Aditya Ramamoorthy
Ardhendu Tripathy
A sum-network is a directed acyclic network in which all terminal nodes demand the `sum' of the independent information observed at 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. Our main result is that unlike a multiple unicast network, the coding capacity of a sum-network is dependent on the message alphabet. We demonstrate this using a construction procedure and show that the choice of a message alphabet can reduce the coding capacity of a sum-network from 1 to close to 0.
Sum-Networks From Undirected Graphs: Construction And Capacity Analysis View Document, Ardhendu Tripathy, Aditya Ramamoorthy
Sum-Networks From Undirected Graphs: Construction And Capacity Analysis View Document, Ardhendu Tripathy, Aditya Ramamoorthy
Ardhendu Tripathy
We consider a directed acyclic network with multiple sources and multiple terminals where each terminal is interested in decoding the sum of independent sources generated at the source nodes. We describe a procedure whereby a simple undirected graph can be used to construct such a sum-network and demonstrate an upper bound on its computation rate. Furthermore, we show sufficient conditions for the construction of a linear network code that achieves this upper bound. Our procedure allows us to construct sum-networks that have any arbitrary computation rate p/q (where p, q are non-negative integers). Our work significantly generalizes a previous approach …
On Computation Rates For Arithmetic Sum, Ardhendu Tripathy, Aditya Ramamoorthy
On Computation Rates For Arithmetic Sum, Ardhendu Tripathy, Aditya Ramamoorthy
Ardhendu Tripathy
For zero-error function computation over directed acyclic networks, existing upper and lower bounds on the computation capacity are known to be loose. In this work we consider the problem of computing the arithmetic sum over a specific directed acyclic network that is not a tree. We assume the sources to be i.i.d. Bernoulli with parameter 1/2. Even in this simple setting, we demonstrate that upper bounding the computation rate is quite nontrivial. In particular, it requires us to consider variable length network codes and relate the upper bound to equivalently lower bounding the entropy of descriptions observed by the terminal …