变速率线性广播网络编码的通用全局编码核构造算法

针对单源有向无圈网络中,当信源速率变化时,线性广播网络编码需重新构造链路的全局编码核和非源节点的局部编码核问题.提出通用全局编码核的概念,并给出通用全局编码核的构造算法.利用该算法,以信源最大可行速率构造出各链路的通用全局编码核.当信源速率变化时,各链路的全局编码核可由通用全局编码核进行简单变形而直接导出,且非源节点的局部编码核无需改变.这样既保持了现有算法构造的各非源节点的局部编码核适用于不同速率的优点,又能方便地得到各链路对应于不同速率的全局编码核.最后基于线性信息流理论,对该算法的时间复杂度和记忆复杂度进行了论证,相对于基于递归向量构造全局编码核的编码算法,该算法的时间复杂度和记忆复杂度均大大降低.

Construction algorithm of universal global encoding kernels for variable-rate linear broadcast network coding

In a single-source directed acyclic network, when the source-rate varies, linear broadcast network coding needs to construct local encoding kernel at every non-source node and global encoding kernel for each edge. In this paper, the concept of universal global encoding kernel is put forward, and the construction algorithm of such universal global encoding kernel is proposed. Construct universal global encoding kernels according to the maximum rate with the algorithm, then the global encoding kernels can be acquired through simple deformation to universal global encoding kernels when the source-rate varies, and the local encoding kernel at every non-source node needs not to be changed.In this way,the advantage that the same local encoding kernel at every non-source node which can be used for different transmission rates can be maintained, and the global encoding kernel for each edge corresponding to different rates can be acquired easily. At last,the time complexity and memory complexity of the algorithm are given based on linear information flow theory, and both the complexities reduce greatly compared with that of the algorithm based on reduction vector.