Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
复制标题
DOI：
10.1109/tit.2011.2155618
复制
发表时间：
2010-10
影响因子：
2.5
通讯作者：
M. Gadouleau;Søren Riis
中科院分区：
文献类型：
--
作者：
M. Gadouleau;Søren Riis
在网络编码实例的溶解度上引入了等同于该Digraph的熵的有向图（Digraph）的猜测数（Digraph）。本文在猜测数字上做出了两个贡献。首先，我们在Digraph的所有可能配置上介绍了一个无向图，称为猜测图，该图将依赖的本质封装在配置之间。我们证明，挖掘物的猜测数量等于其猜测图的独立数的对数。因此，网络编码可解决性不再是每个节点进行操作的问题，而是将可以通过网络传输的消息中的问题简化为问题。通过研究给定的挖掘物的猜测图，以及如何组合挖掘者或字母，我们就可以在猜测数量的挖掘数量上得出界限。其次，我们构建具有较高猜测数字的特定挖掘图，从而产生大量信息可以传输的网络编码实例。我们首先提出了基于循环代码的有限参数的挖掘构建，其猜测数量等于发电机多项式的程度。然后，我们构建了一个无限类别的挖掘图，尽管这些挖掘物是任意稀疏的，但线性猜测数和顶点数量之间的比率趋于一个。这些构造产生可解决的网络编码实例，其中相对较少的中间节点已知节点操作并线性，尽管这些实例稀疏，并且源远离其相应的水槽。
The guessing number of a directed graph (digraph), equivalent to the entropy of that digraph, was introduced as a direct criterion on the solvability of a network coding instance. This paper makes two contributions on the guessing number. First, we introduce an undirected graph on all possible configurations of the digraph, referred to as the guessing graph, which encapsulates the essence of dependence amongst configurations. We prove that the guessing number of a digraph is equal to the logarithm of the independence number of its guessing graph. Therefore, network coding solvability is no more a problem on the operations made by each node, but is simplified into a problem on the messages that can transit through the network. By studying the guessing graph of a given digraph, and how to combine digraphs or alphabets, we are thus able to derive bounds on the guessing number of digraphs. Second, we construct specific digraphs with high guessing numbers, yielding network coding instances where a large amount of information can transit. We first propose a construction of digraphs with finite parameters based on cyclic codes, with guessing number equal to the degree of the generator polynomial. We then construct an infinite class of digraphs with arbitrary girth for which the ratio between the linear guessing number and the number of vertices tends to one, despite these digraphs being arbitrarily sparse. These constructions yield solvable network coding instances with a relatively small number of intermediate nodes for which the node operations are known and linear, although these instances are sparse and the sources are arbitrarily far from their corresponding sinks.