中国邮电高校学报(英文) ›› 2013, Vol. 20 ›› Issue (6): 55-61.doi: 10.1016/S1005-8885(13)60109-0

• Networks • 上一篇    下一篇

Reduce the decoding complexity: segment linear network coding

郭一珺,郝建军,乐光新   

  1. School of Telecommunication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • 收稿日期:2013-06-06 修回日期:2013-10-12 出版日期:2013-12-31 发布日期:2013-12-27
  • 通讯作者: 郭一珺 E-mail:guo.yijun@hotmail.com
  • 基金资助:

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

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).

摘要:

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.

关键词:

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

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