Acta Metallurgica Sinica(English letters) ›› 2013, Vol. 20 ›› Issue (6): 55-61.doi: 10.1016/S1005-8885(13)60109-0

• Networks • Previous Articles     Next Articles

Reduce the decoding complexity: segment linear network coding

Yijun GuoJian-Jun HAO 2   

  1. School of Telecommunication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • Received:2013-06-06 Revised:2013-10-12 Online:2013-12-31 Published:2013-12-27
  • Contact: Yijun Guo E-mail:guo.yijun@hotmail.com
  • Supported by:

    This work was supported by the National Great Science Specific Project of China (2012ZX03001028).

Abstract:

The throughput gain obtained by linear network coding (LNC) grows as the generation size increases, while the decoding complexity also grows exponentially. High decoding complexity makes the decoder to be the bottleneck for high speed and large data transmissions. In order to reduce the decoding complexity of network coding, a segment linear network coding (SLNC) scheme is proposed. SLNC provides a general coding structure for the generation-based network coding. By dividing a generation into several segments and restraining the coding coefficients of the symbols within the same segment, SLNC splits a high-rank matrix inversion into several low-rank matrix inversions, therefore reduces the decoding complexity dramatically. In addition, two coefficient selection strategies are proposed for both centrally controlled networks and distributed networks respectively. The theoretical analysis and simulation results prove that SLNC achieves a fairly low decoding complexity at a cost of rarely few extra transmissions.

Key words:

SLNC, generation-based network coding, random LNC, decoding complexity, extra transmission cost