Networks, Matroids, and Non-Shannon Information Inequalities
Top Cited Papers
- 29 May 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 53 (6), 1949-1969
- https://doi.org/10.1109/tit.2007.896862
Abstract
We define a class of networks, called matroidal networks, which includes as special cases all scalar-linearly solvable networks, and in particular solvable multicast networks. We then present a method for constructing matroidal networks from known matroids. We specifically construct networks that play an important role in proving results in the literature, such as the insufficiency of linear network coding and the unachievability of network coding capacity. We also construct a new network, from the Vamos matroid, which we call the Vamos network, and use it to prove that Shannon-type information inequalities are in general not sufficient for computing network coding capacities. To accomplish this, we obtain a capacity upper bound for the Vamos network using a non-Shannon-type information inequality discovered in 1998 by Zhang and Yeung, and then show that it is smaller than any such bound derived from Shannon-type information inequalities. This is the first application of a non-Shannon-type inequality to network coding. We also compute the exact routing capacity and linear coding capacity of the Vamos network. Finally, using a variation of the Vamos network, we prove that Shannon-type information inequalities are insufficient even for computing network coding capacities of multiple-unicast networks.Keywords
This publication has 22 references indexed in Scilit:
- On the capacity of information networksIEEE Transactions on Information Theory, 2006
- Edge-Cut Bounds on Network Coding RatesJournal of Network and Systems Management, 2006
- Linear network codingIEEE Transactions on Information Theory, 2003
- On a new non-Shannon type information inequalityCommunications in Information and Systems, 2003
- A First Course in Information TheoryPublished by Springer Science and Business Media LLC ,2002
- Inequalities for Shannon Entropy and Kolmogorov ComplexityJournal of Computer and System Sciences, 2000
- On characterization of entropy function via information inequalitiesIEEE Transactions on Information Theory, 1998
- A non-Shannon-type conditional inequality of information quantitiesIEEE Transactions on Information Theory, 1997
- Polymatroidal dependence structure of a set of random variablesInformation and Control, 1978
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948