The precoding problem for sparse random linear network coding

In the random linear network coding scenario with subspace codes applied, if the number of packets injected into the network is larger than the dimension of the subspace, the packets are not linearly independent. This paper addresses the problem of how to choose these packets to represent the subspaces so as to minimize the decoding failure probability and formulates it as a precoding problem. We propose a precoding method based on the generator matrices of a class of the maximum distance separable codes and show that it can minimize the decoding failure probability for a sparse random transfer matrix over a large enough finite field. Our result is obtained by analyzing the rank distribution of finite field random matrices in the large field size limit. As a consequence, it is applied to shed some light on the tradeoff between the maximum achievable sparsity of the transfer matrix and the rate of the subspace code.