摘要: A directed acyclic network is considered where all the terminals need to recover sum of symbols generated at sources. We call such a sum-network. It shown that there exists solvably (and linear solvably) equivalent sum-network for any multiple-unicast network, and thus communication network. also every set polynomials having integer coefficients, which scalar solvable over finite field F if only have common root in F. For or cofinite prime numbers, constructed has vector solution length characteristic alphabet given set. The insufficiency net- work coding unachievability capacity are proved sum-networks by using similar known results networks. Under fractional coding, its reverse be equivalent. However, under nonlinear it whose not solvable.
harvard.edu
sci-hub.se 参考文章(33)
Kenneth Zeger, Rathinakumar Appuswamy, Nikhil Karamchandani, Massimo Franceschetti, Network Coding for Computing Part I : Cut-Set Bounds ,(2009)
Sagar Shenvi, Bikash Kumar Dey, On the solvability of 3-source 3-terminal sum-networks arXiv: Information Theory. ,(2010)
Sagar Shenvi, Bikash Kumar Dey, A necessary and sufficient condition for solvability of a 3s/3t sum-network international symposium on information theory. pp. 1858- 1862 ,(2010) , 10.1109/ISIT.2010.5513430
April Rasala Lehman, Eric Lehman, Complexity classification of network information flow problems symposium on discrete algorithms. pp. 142- 150 ,(2004) , 10.5555/982792.982814
J. Korner, K. Marton, How to encode the modulo-two sum of binary sources (Corresp.) IEEE Transactions on Information Theory. ,vol. 25, pp. 219- 221 ,(1979) , 10.1109/TIT.1979.1056022
Y. Kanoria, D. Manjunath, On Distributed Computation in Noisy Random Planar Networks international symposium on information theory. pp. 626- 630 ,(2007) , 10.1109/ISIT.2007.4557101
Te Han, K. Kobayashi, A dichotomy of functions F(X, Y) of correlated sources (X, Y) IEEE Transactions on Information Theory. ,vol. 33, pp. 69- 76 ,(1987) , 10.1109/TIT.1987.1057272
T. Ho, M. Medard, R. Koetter, D.R. Karger, M. Effros, J. Shi, B. Leong, A Random Linear Network Coding Approach to Multicast IEEE Transactions on Information Theory. ,vol. 52, pp. 4413- 4430 ,(2006) , 10.1109/TIT.2006.881746
Michael Atiyah, Introduction to Commutative Algebra ,(1969)
R.G. Gallager, Finding parity in a simple broadcast network IEEE Transactions on Information Theory. ,vol. 34, pp. 176- 180 ,(1988) , 10.1109/18.2626