2014/01/31 by Qifu, Qifu Tyler Sun, Sun +3 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced MIMO Systems Optimization #Bounded function #Cooperative Communication and Network Coding #Field size #Finite field #Interconnection Networks and Systems #Linear network coding #Multicast #Multiplicative function #cs.IT #math.IT
paper · pdf · doi:10.1109/tit.2015.2473863
arxiv created 2015/02/13 · openalex publication_date 2015/08/27 · arxiv updated 2016/09/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In an acyclic multicast network, it is well known that a linear network coding solution over GF(q) exists when q is sufficiently large. In particular, for each prime power q no smaller than the number of receivers, a linear solution over GF(q) can be efficiently constructed. In this paper, we reveal that a linear solution over a given finite field does not necessarily imply the existence of a linear solution over all larger finite fields. In particular, we prove by construction that: 1) for every ω ≥ 3, there is a multicast network with source outdegree ω linearly solvable over GF(7) but not over GF(8), and another multicast network linearly solvable over GF(16) but not over GF(17); 2) there is a multicast network linearly solvable over GF(5) but not over such GF(q) that q > 5 is a Mersenne prime plus 1, which can be extremely large; 3) a multicast network linearly solvable over GF(qm1) and over GF(qm2) is not necessarily linearly solvable over GF(qm1+m2); and 4) there exists a class of multicast networks with a set T of receivers such that the minimum field size qminfor a linear solution over GF(qmin) is lower bounded by O(√|T|), but not every larger field than GF(qmin) suffices to yield a linear solution. The insight brought from this paper is that not only the field size but also the order of subgroups in the multiplicative group of a finite field affects the linear solvability of a multicast network.