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.
Xiaolin Li Wai Ho Mow Fai-Lung Tsang
Hong Kong University of Science and Technology Clear Water Bay, Kowloon, Hong Kong
国际会议
2011 International Symposium on Network Coding(2011网络编码国际会议 NETCOD 2011)
北京
英文
1-6
2011-07-25（万方平台首次上网日期，不代表论文的发表时间）