On Vector Linear Solvability of Multicast Networks

Abstract

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 (single-source) multicast networks that are vector linearly solvable of dimension $L$ over GF($q$) but not scalar linearly solvable over any field of size $q^{\prime }\le q^L$. 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 \emph{infinitely many} alphabet sizes $p^L$ with respect to an \emph{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^{\prime }$) for some $q^{\prime }<2^L$, where $q^{\prime }$ 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^{\prime }>L$.

Cited by in corpus (9)

• Circular-shift Linear Network Coding
• Linear Network Coding over Rings, Part II: Vector Codes and Non-Commutative Alphabets
• Circular-shift Linear Network Codes with Arbitrary Odd Block Lengths
• Linear Network Coding over Rings, Part I: Scalar Codes and Commutative Alphabets
• On the Gap between Scalar and Vector Solutions of Generalized Combination Networks
• Linear Network Coding: Effects of Varying the Message Dimension on the Set of Characteristics
• Delay-Complexity Trade-off of Random Linear Network Coding in Wireless Broadcast
• Network-Coding Solutions for Minimal Combination Networks and Their Sub-networks
• On Achievability of an $(r,l)$ Fractional Linear Network Code