Networks, Matroids, and Non-Shannon Information Inequalities
Networks, Matroids, and Non-Shannon Information Inequalities
复制标题
DOI：
10.1109/tit.2007.896862
复制
发表时间：
2007-06
影响因子：
2.5
通讯作者：
R. Dougherty;C. Freiling;K. Zeger
中科院分区：
文献类型：
--
作者：
R. Dougherty;C. Freiling;K. Zeger
我们定义了一类网络，称为拟阵网络，其中包括作为特殊情况的所有标量线性可解网络，特别是可解组播网络。然后，我们提出了一种方法，从已知拟阵构造拟阵网络。我们具体构建网络，在证明文献中的结果，如线性网络编码的不足和网络编码容量的不可扩展性发挥了重要作用。我们还构造了一个新的网络，从Vamos拟阵，我们称之为Vamos网络，并用它来证明香农型信息不等式一般不足以计算网络编码能力。为了实现这一点，我们得到了一个容量上限的Vamos网络使用非香农型信息不等式发现于1998年由张和杨，然后表明，它是小于任何这样的界来自香农型信息不等式。这是第一个应用非香农型不等式网络编码。我们还计算了Vamos网络的精确路由容量和线性编码容量。最后，使用Vamos网络的变体，我们证明了香农型信息不等式即使对于计算多单播网络的网络编码容量也是不够的。
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.