A necessary and sufficient condition for solvability of a 3s/3t sum-network
作者： Sagar Shenvi , Bikash Kumar Dey
DOI: 10.1109/ISIT.2010.5513430
关键词: Conjecture 、 Discrete mathematics 、 Field (mathematics) 、 Mathematics 、 Linear network coding 、 Fountain code 、 Block code 、 Terminal (electronics) 、 Variable-length code 、 Linear code 、 Combinatorics
摘要: We consider a directed acyclic network with three sources and terminals such that each source independently generates one symbol from given field F terminal wants to receive the sum (over F) of symbols. Each link is error-free, delay-free can carry in use. call 3-source 3-terminal (3s/3t) sum-network. give necessary sufficient condition for 3s/3t sum-network be solvable over any field. Some lemmas provide interesting simpler conditions same. show linear codes, most cases XOR are this problem though they known insufficient arbitrary number terminals. also prove recent conjecture capacity either 0, ⅔ or ≥ 1.
sci-hub.se 参考文章(21)
Kenneth Zeger, Rathinakumar Appuswamy, Nikhil Karamchandani, Massimo Franceschetti, Network Coding for Computing Part I : Cut-Set Bounds ,(2009)
Tracey Ho, Desmond Lun, Network Coding: An Introduction ,(2008)
Sagar Shenvi, Bikash Kumar Dey, On the solvability of 3-source 3-terminal sum-networks arXiv: Information Theory. ,(2010)
Brijesh Kumar Rai, Bikash Kumar Dey, Sum-networks: system of polynomial equations, reversibility, insufficiency of linear network coding, unachievability of coding capacity ,(2009)
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
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
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
Michael Langberg, Aditya Ramamoorthy, Communicating the sum of sources in a 3-sources/3-terminals network international symposium on information theory. pp. 2121- 2125 ,(2009) , 10.1109/ISIT.2009.5205758
Dinesh Krithivasan, S. Sandeep Pradhan, An achievable rate region for distributed source coding with reconstruction of an arbitrary function of the sources international symposium on information theory. pp. 56- 60 ,(2008) , 10.1109/ISIT.2008.4594947
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