An Upper Bound on the Outage Probability of Random Linear Network Codes with Known Incidence Matrices

Abstract:
Random linear network coding (RLNC) is a method to maximise the information flow in a network by forming random linear combinations over a finite field Fq of the received information packets at each intermediate node. The network between one source node and one destination node acts as a linear map F(exp n)q ? F(exp N)q , which is represented by the network channel matrix. The connectivity within the network is assumed to be given, i.e. it is considered to be fixed but arbitrary and thus, the incidence matrix of the network is said to be known. The optimal decoding method is equivalent to solving a consistent system of linear equations over the respective finite field, e.g. by means of Gaussian elimination. Therefore, decoding is only successful if the respective square or tall network channel matrix has full column rank. Since the incidence matrix of the network is given, there is one degree of randomness less compared to the usual notion of random matrices. By exploiting similarities of RLNC with Luby transform (LT) coding, a method to establish rateless erasure resilience, which is also based on random matrices over finite fields, we derive an upper bound on the outage probability for RLNC with known incidence matrices.