Rank Distribution Analysis for Sparse Random Linear Network Coding

In this paper, the decoding failure probability for sparse random linear network coding in a probabilistic network model is analyzed. The network transfer matrix is modeled by a random matrix consisting of independently and identically distributed elements chosen from a large finite field, and the probability of choosing each nonzero field element tends to zero, as the finite field size tends to infinity. In the case of a constant dimension subspace code over a large finite field with bounded distance decoding, the decoding failure probability is given by the rank distribution of a random transfer matrix. We prove that the latter can be completely characterized by the zero pattern of the matrix, i.e., where the zeros are located in the matrix. This insight allows us to use counting arguments to derive useful upper and lower bounds on the rank distribution and hence the decoding failure probability. Our rank distribution analysis not only sheds some light on how to minimize network resource in a sparse random linear network coding application, but is also of theoretical interest due to its connection with probabilistic combinatorics. © 2011 IEEE