On Vector Linear Solvability of Multicast Networks
Qifu Tyler Sun, Xiaolong Yang, Keping Long, Xunrui Yin, Zongpeng Li · IEEE Transactions on Communications · 2016
Vector linear network coding (LNC) is a generalization of the conventional scalar LNC, such that the data unit transmitted on every edge is an L-dimensional vector of data symbols over a base field GF(q). Vector LNC enriches the choices of coding operations at intermediate nodes, and there is a popular conjecture on the benefit of vector LNC over scalar LNC in terms of alphabet size of data units: there exist (singlesource) multicast networks that are vector linearly solvable of dimension L over GF(q) but not scalar linearly solvable over any field of size q' qL. This paper introduces a systematic way to construct such multicast networks, and subsequently establish explicit instances to affirm the positive answer of this conjecture for infinitely many alphabet sizes pL with respect to an arbitrary prime p. On the other hand, this paper also presents explicit instances with the special property that they do not have a vector linear solution of dimension L over GF(2) but have scalar linear solutions over GF(q') for someq'L, where q' can be odd or even. This discovery also unveils that over a given base field, a multicast network that has a vector linear solution of dimension L does not necessarily have a vector linear solution of dimension L' > L.