Reduce the decoding complexity: segment linear network coding

doi:10.1016/S1005-8885(13)60109-0

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

Reduce the decoding complexity: segment linear network coding

郭一珺,郝建军,乐光新

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 ²

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.

关键词:

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

Abstract:

Key words:

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

Yijun Guo Jian-Jun HAO. Reduce the decoding complexity: segment linear network coding[J]. Acta Metallurgica Sinica(English letters), 2013, 20(6): 55-61.

参考文献

1. Ahlswede R, Cai N, Li S Y, et al. Network information flow. IEEE Transactions on Information Theory, 2000, 46(4): 1204-1216

2. Koetter R, Medard M. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 2003, 11(5): 782-795

3. Li S Y, Yeung R, Cai N. Linear network coding. IEEE Transactions on Information Theory, 2003, 49(2): 371-381

4. Li S Y, Sun Q, Shao Z. Linear network coding: theory and algorithms. Proceedings of the IEEE, 2011, 99(3): 372-387

5. Li B,Niu D. Random network coding in peer-to-peer networks: from theory to practice. Proceedings of the IEEE, 2011, 99(3): 513-523

6. Nistor M, Lucani D, Vinhoza T, et al. On the delay distribution of random linear network coding. IEEE Journal on Selected Areas in Communications, 2011, 29(5): 1084-1093

7. Swapna B T, Eryilmaz A, Shroff N B. Throughput-delay analysis of random linear network coding for wireless broadcasting. Proceedings of the International Symposium on Network Coding (NetCod’10), Jun 9-11, 2010, Toronto, Canada. Los Alamitos, CA, USA: IEEE Computer Society, 2010: 6p

8. Najeem M, Siva Ram Murthy C. On enhancing the random linear network coding. Proceedings of the 17th IEEE International Conference on Networks (ICON’11), Dec 14-16, 2011, Singapore. Piscataway, NJ, USA: IEEE, 2011: 246-251

9. Ho T, Medard M, Koetter R, et al. A random linear network coding approach to multicast. IEEE Transactions on Information Theory, 2006, 52(10): 4413-4430

10. Wu X F, Zhao C M, You X H. Generation-based network coding over networks with delay. Proceedings of the 8th IFIP International Conference on Network and Parallel Computing (NPC’08), Oct 18-21, 2008, Shanghai, China. Piscataway, NJ, USA: IEEE Computer Society, 2008: 365-368

11. Thibault J P, Chan W Y, Yousefi S. Recursive and non-recursive network coding: Performance and complexity. Proceedings of the 2007 International Conference on Signal Processing and Communication Systems (ICSPCS’07), Nov 24-27, 2007, Gold Coast, Australia. Piscataway, NJ, USA: IEEE, 2007: 1223-1226

12. Fiandrotti A, Zezza S, Magli E. Complexity-adaptive random network coding for peer-to-peer video streaming. Proceedings of the 13th International Workshop on Multimedia Signal Processing (MMSP’11), Oct 17-19, 2011, Hangzhou, China. Piscataway, NJ, USA: IEEE, 2011: 6p

13. Yin B,Wu M, Wang G H, et al. Low complexity opportunistic decoder for network coding. Proceedings of the 2012 Conference Record of the 46th Asilomar Conference on Signals, Systems and Computers (ASILOMAR’12), Nov 4-7, 2012, Asilomar, CA, USA. Piscataway, NJ, USA: IEEE, 2012: 1097-1101

Reduce the decoding complexity: segment linear network coding

Reduce the decoding complexity: segment linear network coding

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价