Campus Units
Electrical and Computer Engineering
Document Type
Article
Publication Version
Submitted Manuscript
Publication Date
2016
Journal or Book Title
arXiv
First Page
1601.07228
Abstract
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 conditioned on the function value. This lower bound is obtained by further lower bounding the entropy of a so-called \textit{clumpy distribution}. We also demonstrate an achievable scheme that uses variable length network codes and in-network compression.
Copyright Owner
The authors
Copyright Date
2016
Language
en
File Format
application/pdf
Recommended Citation
Tripathy, Ardhendu and Ramamoorthy, Aditya, "On Computation Rates for Arithmetic Sum" (2016). Electrical and Computer Engineering Publications. 105.
https://lib.dr.iastate.edu/ece_pubs/105
Comments
This preprint is from arXiv:1601.07228 [cs.IT]. Posted with permission.