On the role of the message dimension and the characteristic of the finite field in linear network coding

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
We consider a communication problem over a directed acyclic network where information is generated at certain nodes (sources), and certain nodes (terminals) require the information generated at a subset of the sources. If each source generates k symbols belonging to a finite field, and all terminals can retrieve their demands by using the network n times, then the network is said to have an (k,n) linear solution, and a rate k/n is said to be linearly achiev- -able. If rate 1 is linearly achievable, the network is said to have a linear solution.We consider three aspects of linear network coding, viz, dependency on message dimension (value of k) to achieve certain rates, dependency on characteristic of the finite field with varying message dimension to achieve certain rates, and characteristic-dependent linear rank inequalities to find upper-bound on the rates linearly achievable.The first two chapters of the thesis are the literature review and the system model. In the third chapter, we show that for any integer m ≥ 2, there exists a network which has a linear solution if and only if the message dimension is equal to a positive integer multiple of m. We then show that for any positive integer m ≥ 2, there exists a network which has no linear solution if the message dimension is less than m, but has a linear solution for all values of the message dimension greater than or equal to m.In the fourth chapter, we show that by increasing the message dimension just by 1, the size of the set of characteristics of finite fields over which a linear solution exists may increase or decrease. We also show that when the message dimension is fixed to 1, operating over rings can be more beneficial than operating over finite fields in terms of achieving a linear solution over a lesser sized alphabet.In the fifth and the final chapter, we present three new sets of characteristic-dependent linear rank inequalities and show their application in obtaining upper-bounds on the linear coding capacity of networks over a given set of charac- -teristics. For any given set of primes P, the inequalities in the first set hold if the characteristic of the finite field does not belong to P, and the inequalities in the second and the third set hold if the characteristic of the finite field belongs to P.
Supervisor: Brijesh Kumar Rai