Abstract
In 2000, Ahlswede, Cai and Li introduced network coding, a technique used to improve the efficiency of information flow through networks by allowing inter mediate nodes to compute with and modify data. In practice random linear network coding is used, where the nodes transmit random linear combinations of their incoming packets. This thesis is concerned with several mathematical problems motivated by network coding.
We first consider partial decoding in random linear network coding. By noting the equivalence to an enumeration problem in linear algebra, we com pute the exact probability of a receiver decoding a fraction of the source message. We investigate the consequences when using both systematic and nonsystematic network coding.
We then consider mathematical models for network coding. Silva, Kschis chang and K ̈otter studied certain classes of finite field matrix channels in order to model random linear network coding where exactly t random errors are introduced. We introduce a generalisation of these channels that allow the modelling of channels where a variable number of random errors are in troduced. For special cases of our channel we improve on previous analysis of the channel capacity.
For the general case we show that a capacityachieving input distribution can always be taken to have a very restricted form (the distribution should be uniform given the rank of the input matrix). Nobrega, Silva and Uchoa Filho proved a similar result for a class of matrix channels that model network coding with link erasures. Our result leads to an expression for the capacity of these channels as a maximisation over probability distributions on the set of possible ranks of input matrices (rather than the set of all input matrices): a set of linear rather than exponential size. Thus we give an efficient method to find optimal input distributions and compute the exact capacity for any channel parameters.
We first consider partial decoding in random linear network coding. By noting the equivalence to an enumeration problem in linear algebra, we com pute the exact probability of a receiver decoding a fraction of the source message. We investigate the consequences when using both systematic and nonsystematic network coding.
We then consider mathematical models for network coding. Silva, Kschis chang and K ̈otter studied certain classes of finite field matrix channels in order to model random linear network coding where exactly t random errors are introduced. We introduce a generalisation of these channels that allow the modelling of channels where a variable number of random errors are in troduced. For special cases of our channel we improve on previous analysis of the channel capacity.
For the general case we show that a capacityachieving input distribution can always be taken to have a very restricted form (the distribution should be uniform given the rank of the input matrix). Nobrega, Silva and Uchoa Filho proved a similar result for a class of matrix channels that model network coding with link erasures. Our result leads to an expression for the capacity of these channels as a maximisation over probability distributions on the set of possible ranks of input matrices (rather than the set of all input matrices): a set of linear rather than exponential size. Thus we give an efficient method to find optimal input distributions and compute the exact capacity for any channel parameters.
Original language  English 

Qualification  Ph.D. 
Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  1 Apr 2017 
Publication status  Unpublished  2017 
Keywords
 random linear network coding
 finite fields
 matrix channels
 channel capacity
 vector spaces
 partial decoding