  Sparse random linear network coding (SRLNC) is an attractive technique
proposed in the literature to reduce the decoding complexity of random linear
network coding. Recognizing the fact that the existing SRLNC schemes are not
efficient in terms of the required reception overhead, we consider the problem
of designing overhead-optimized SRLNC schemes. To this end, we introduce a new
design of SRLNC scheme that enjoys very small reception overhead while
maintaining the main benefit of SRLNC, i.e., its linear encoding/decoding
complexity. We also provide a mathematical framework for the asymptotic
analysis and design of this class of codes based on density evolution (DE)
equations. To the best of our knowledge, this work introduces the first DE
analysis in the context of network coding. Our analysis method then enables us
to design network codes with reception overheads in the order of a few percent.
We also investigate the finite-length performance of the proposed codes and
through numerical examples we show that our proposed codes have significantly
lower reception overheads compared to all existing linear-complexity random
linear network coding schemes.
