Vector versus Scalar Linear Codes for Multicast Network Coding

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 do not have a scalar linear solution over any field.

For (single-source) multicast networks, it has been conjectured and partially proved by Ebrahimi and Fragouli that vector LNC has the following benefits over scalar LNC in terms of alphabet size of data units:

i)A multicast network scalar linearly solvable over GF(q^L1) and GF(q^L2) may not be scalar linearly solvable over GF(q^L1+L2), but a multicast network vector linearly solvable of dimensions L₁ and L₂ over GF(q) must be vector linearly solvable of dimension L₁ + L₂ over GF(q);

ii) There exists a multicast network that is vector linearly solvable of dimension L over GF(q) but not scalar linearly solvable over any field of size q¢£ q^L.

In this talk, we affirm the above two conjectures to be correct by explicit exemplifying networks, which are constructed by a general method to be introduced. 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 q¢ > q^L, they are still not scalar linearly solvable over GF(q¢).

On the other hand, we also demonstrate a few multicast networks where scalar LNC outperforms vector LNC in the sense that they do not have a vector linear solution of dimension L over GF(2) but have a scalar linear solution over GF(q¢) for some q¢ < 2^L.