On computation rates for arithmetic sum
作者： Ardhendu Tripathy , Aditya Ramamoorthy
DOI: 10.1109/ISIT.2016.7541720
关键词: Binary entropy function 、 Discrete mathematics 、 Bounding overwatch 、 Maximum entropy probability distribution 、 Entropy (information theory) 、 Combinatorics 、 Mathematics 、 Computation 、 Entropy encoding 、 Upper and lower bounds 、 Arithmetic progression
摘要: For zero-error function computation over directed acyclic networks, existing upper and lower bounds on the capacity are known to be loose. In this work we consider problem of computing arithmetic sum a specific network that is not tree. We assume sources i.i.d. Bernoulli with parameter 1/2. Even in simple setting, demonstrate bounding rate quite nontrivial. particular, it requires us variable length codes relate bound equivalently entropy descriptions observed by terminal conditioned value. This obtained further so-called clumpy distribution. also an achievable scheme uses in-network compression.
harvard.edu
sci-hub.se 参考文章(12)
Cupjin Huang, Zihan Tan, Shenghao Yang, Upper bound on function computation in directed acyclic networks information theory workshop. pp. 1- 5 ,(2015) , 10.1109/ITW.2015.7133086
Ardhendu Tripathy, Aditya Ramamoorthy, Capacity of sum-networks for different message alphabets international symposium on information theory. pp. 606- 610 ,(2015) , 10.1109/ISIT.2015.7282526
Hemant Kowshik, P. R. Kumar, Optimal Function Computation in Directed and Undirected Graphs IEEE Transactions on Information Theory. ,vol. 58, pp. 3407- 3418 ,(2012) , 10.1109/TIT.2012.2188883
Brijesh Kumar Rai, Bikash Kumar Dey, On Network Coding for Sum-Networks IEEE Transactions on Information Theory. ,vol. 58, pp. 50- 63 ,(2012) , 10.1109/TIT.2011.2169532
Ardhendu Tripathy, Aditya Ramamoorthy, Sum-networks from undirected graphs: Construction and capacity analysis allerton conference on communication, control, and computing. pp. 651- 658 ,(2014) , 10.1109/ALLERTON.2014.7028517
Thomas M. Cover, Joy A. Thomas, Elements of information theory ,(1991)
R. Ahlswede, Ning Cai, S.-Y.R. Li, R.W. Yeung, Network information flow IEEE Transactions on Information Theory. ,vol. 46, pp. 1204- 1216 ,(2000) , 10.1109/18.850663
A. Giridhar, P.R. Kumar, Computing and communicating functions over sensor networks IEEE Journal on Selected Areas in Communications. ,vol. 23, pp. 755- 764 ,(2005) , 10.1109/JSAC.2005.843543
K Zeger, R Appuswamy, N Karamchandani, M Franceschetti, Network Coding for Computing: Cut-Set Bounds IEEE Transactions on Information Theory. ,vol. 57, pp. 1015- 1030 ,(2011) , 10.1109/TIT.2010.2095070
Aditya Ramamoorthy, Michael Langberg, Communicating the Sum of Sources Over a Network IEEE Journal on Selected Areas in Communications. ,vol. 31, pp. 655- 665 ,(2013) , 10.1109/JSAC.2013.130404