Back to Search
Start Over
Multicast Network Coding and Field Sizes.
- Source :
- IEEE Transactions on Information Theory; Nov2015, Vol. 61 Issue 11, p6182-6191, 10p
- Publication Year :
- 2015
-
Abstract
- 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 \omega \geq 3 , there is a multicast network with source outdegree \omega 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 ) and over GF( q^m2 ) is not necessarily linearly solvable over GF( q^{m1 + m2} ); and 4) there exists a class of multicast networks with a set T of receivers such that the minimum field size q_{\mathrm{ min}} for a linear solution over GF( q_{\mathrm{ min}} ) is lower bounded by \Theta (\sqrt <INNOPIPE>T<INNOPIPE>) , but not every larger field than GF( q\mathrm{ min} ) 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 61
- Issue :
- 11
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 110439804
- Full Text :
- https://doi.org/10.1109/TIT.2015.2473863