Constructing multicast networks where vector linear coding outperforms scalar linear coding
Qifu Tyler Sun, Xiaolong Yang, Keping Long, Zongpeng Li · 2015
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). There are classical exemplifying multi-source networks that have simple vector linear solutions but no scalar linear solutions over any field. For (single-source) multicast networks, a popular conjecture characterizes the following benefit of vector LNC over scalar LNC in terms of alphabet size of data units: there exist 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 general method to construct such a network, and subsequently constructs the first examples to affirm the positive answer of this conjecture. Moreover, among these exemplifying networks vector linearly solvable of dimension L over GF(q), there are instances with the additional property that even for some extremely large q' > qL, they are still not scalar linearly solvable over GF(q').