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 non-systematic 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 capacity-achieving 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.