otter studied certain classes of finite field matrix channels in order to model random linear network coding where exactly t random errors are introduced. The exact capacity of such channels is hard to determine due to the many degrees of freedom involved: the naive formula maximises over a probability distribution on the set of possible input matrices, and this set is exponentially large. In this paper we introduce a generalisation of these matrix channels, that allow the modelling of channels where a variable number of random errors are introduced. 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. One corollary of our result is that the capacity for these channels may be expressed as a maximisation over probability distributions on the set of possible ranks of input matrices: a set of linear rather than exponential size. I. I NTRODUCTION Network coding, first defined in [1], allows intermediate nodes of a network to compute with and modify data, as opposed to the traditional view of nodes as ‘on/off’ switche s. This can increase the rate of information flow through a network. It is shown in [4] that linear network coding is sufficient to maximise information flow in multicast problem s, that is when there is one source node and information is to be transmitted to a set of sink nodes. Moreover, in [2] it is shown that for general multisource multicast problems, random linear network coding achieves capacity with probability exponentially approaching 1 with the code length. In random linear network coding, the source injects packets into the network that can be thought of as vectors of length m with entries in a finite field Fq (where q is a fixed power of a prime). The packets flow through a network of unknown topology to a sink node. Each intermediate node forwards packets that are random linear combinations of the packets it has received. A sink node attempts to reconstruct the message from these packets. In this context, Silva, Kschischang and
['Simon R. Blackburn', 'Jessica Claridge']
Finite field matrix channels for network coding