New algorithm for variable-rate linear broadcast network coding

Abstract

To adjust the variance of source rate in linear broadcast networks, global encoding kernels should have corresponding dimensions to instruct the decoding process. The algorithm of constructing such global encoding kernels is to adjust heterogeneous network to possible link failures. Linear algebra, graph theory and group theory are applied to construct one series of global encoding kernels which are applicable to all source rates. The effectiveness and existence of such global encoding kernels are proved. Based on information flow, the algorithm of construction is explicitly given within polynomial time O(|E|·|T|·ω_max²), and the memory complexity of algorithm is O(|E|). Both time and memory complexity of this algorithm proposed can be O(ω_max) less than those of algorithms in related works.

Keywords

network coding / variable-rate / linear broadcast / heterogeneous network / code construction algorithm