Sparse Random Linear Network Codes
In this paper, the authors presented a randomized approach to linear network coding. In this scheme each intermediate node chooses linear coding coefficients randomly and uniformly from the finite field Fq. This approach can be used in various types of networks. It is shown that the capacity of multicast network is achievable by using this approach. Random linear network coding achieves the capacity in a multicast session. Using Gaussian elimination, the decoding complexity of a transfer matrix is O(n3). In this paper, they want to make the transfer matrix sparse and leverage the sparsity to decrease decoding complexity.