Performance analysis of complexity reduction BP decoding of rateless codes by deleting low reliable symbols

doi:10.1016/S1005-8885(16)60054-7

中国邮电高校学报(英文) ›› 2016, Vol. 23 ›› Issue (5): 26-31.doi: 10.1016/S1005-8885(16)60054-7

Performance analysis of complexity reduction BP decoding of rateless codes by deleting low reliable symbols

雷维嘉,陈胜男

重庆邮电大学

收稿日期:2016-04-29 修回日期:2016-09-25 出版日期:2016-10-30 发布日期:2016-10-26
通讯作者: 雷维嘉 E-mail:leiwj@cqupt.edu.cn
基金资助:
the National Natural Science Foundation of China (61471076), the Program for Changjiang Scholars ， Innovative Research Team in University (IRT1299), the Special Fund of Chongqing Key Laboratory (CSTC)

Performance analysis of complexity reduction BP decoding of rateless codes by deleting low reliable symbols

Lei Weijia, Chen Shengnan

Received:2016-04-29 Revised:2016-09-25 Online:2016-10-30 Published:2016-10-26
Contact: Wei-Jia LEI E-mail:leiwj@cqupt.edu.cn
Supported by:
the National Natural Science Foundation of China (61471076), the Program for Changjiang Scholars ， Innovative Research Team in University (IRT1299), the Special Fund of Chongqing Key Laboratory (CSTC)

摘要/Abstract

摘要： This paper investigates the performance of the method used to reduce the decoding complexity of rateless codes through the deletion of the received symbols with low reliability. In the decoder, the received symbols whose absolute value of logarithm likelihood ratio (LLR) is lower than the threshold are removed, together with their corresponding edges, and thus not involved in the decoding process. The relationship between the deletion probability and the likelihood ratio deletion threshold is derived. The average mutual information per received symbol is analyzed in the case of deletion. The required number of symbols for the decoder to keep the same performance as regular decoding decreases since the average mutual information per symbol increases with the deletion, thus reducing the decoding complexity. This paper analyzes the reduction of decoding computations and the consequent transmission efficiency loss from the perspective of mutual information. The simulation results of decoding performance are consistent with those of the theoretical analysis, which show that the method can effectively reduce the decoding complexity at the cost of a slight loss of transmission efficiency.

关键词: rateless codes, symbols deletion, logarithm likelihood ratio, average mutual information, decoding complexity

Abstract: This paper investigates the performance of the method used to reduce the decoding complexity of rateless codes through the deletion of the received symbols with low reliability. In the decoder, the received symbols whose absolute value of logarithm likelihood ratio (LLR) is lower than the threshold are removed, together with their corresponding edges, and thus not involved in the decoding process. The relationship between the deletion probability and the likelihood ratio deletion threshold is derived. The average mutual information per received symbol is analyzed in the case of deletion. The required number of symbols for the decoder to keep the same performance as regular decoding decreases since the average mutual information per symbol increases with the deletion, thus reducing the decoding complexity. This paper analyzes the reduction of decoding computations and the consequent transmission efficiency loss from the perspective of mutual information. The simulation results of decoding performance are consistent with those of the theoretical analysis, which show that the method can effectively reduce the decoding complexity at the cost of a slight loss of transmission efficiency.

Key words: rateless codes, symbols deletion, logarithm likelihood ratio, average mutual information, decoding complexity

中图分类号:

TN911.22

参考文献

1. Byers J W, Luby M, Mitzenmacher M. A digital fountain approach to asynchronous reliable multicast. IEEE Journal on Selected Areas in Communications, 2002, 20(8): 1528-1540

2. Luby M. LT codes. Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS’03), Oct 11-14, 2003, Cambridge, MA, USA. Piscataway, NJ, USA: IEEE, 2002: 271-280

3. Palanki R, Yedidia J S. Rateless codes on noisy channels. Proceedings of the 2004 International Symposium on Information Theory (ISIT’04), Jun 27-Jnl 2, 2004, Chicago, IL, USA. Piscataway, NJ, USA: IEEE, 2004: 37

4. Shokrollahi A. Raptor codes. IEEE Transactions on Information Theory, 2006, 52(6): 2551-2567

5. Jenka? H, Mayer T, Stockhammer T, et al. Soft decoding of LT-codes for wireless broadcast. Proceedings of the 14th IST Mobile and Communicationa Summit, Jun 19-23, 2005, Dresden, Germany. 2005: 19-23

6. Yao C M, Zhang Z Y, Tu K. Design of complexity-optimized raptor codes for BI-AWGN channel. Proceedings of the IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC’12), Sept 8-11, 2013, London, UK. Piscataway, NJ, USA: IEEE, 2013: 824-829

7. Hussian I, Land I, Chan T H, et al. A new design framework for LT codes over noisy channels. Proceedings of the 2014 IEEE International Symposium on Information Theory (ISIT’14), Jun 29-Jul 4, 2014, Honolulu, HI, USA. Piscataway, NJ, USA: IEEE, 2014: 2162-2166

8. Dohyung P, Chung S Y. Performance-complexity tradeoffs of rateless codes. Proceedings of the IEEE International Symposium on Information Theory (ISIT’08), Jul. 6-11, 2008, Toronto, Canada. Piscataway, NJ, USA: IEEE, 2008: 2056-2060

9. Hussian I, Xiao M, Rasmussen L K. Reduced-complexity decoding of LT codes over noisy channels. Proceedings of the 2013 IEEE Wireless Communication and Networking Conference (WCNC’13), Apr 7-10, 2013, Shanghai, China. Piscataway, NJ, USA: IEEE, 2013: 3856-3860

10. Chen S L, Zhang Z Y, Zhang L, et al. Belief propagation with gradual edge removal for raptor codes over AWGN channel. Proceedings of the IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC’13), Sept 8-11, 2013, London, UK. Piscataway, NJ, USA: IEEE, 2013: 380-385

[1]	Li Xiaohui, Liu Shuaishuai, Fan Tao, Fang Kun. Dual-CRC polar codes and dual-SCFlip decoding algorithm for cell search in 5G system [J]. 中国邮电高校学报(英文版), 2021, 28(6): 82-90.
[2]	Liu Zhenzhen, Niu Kai, Dong Chao, Lin Jiaru. Convergence analysis and performance optimization of parallel concatenated systematic polar code[J]. 中国邮电高校学报(英文版), 2018, 25(2): 1-9.
[3]	Zheng Hao, Zhang Shuyi, Li Lintao, Gao Yuan, Shao Liwei. Probability stopping criterion for analog decoding of LDPC codes[J]. 中国邮电高校学报(英文版), 2017, 24(1): 35-39.
[4]	王帅 HONG Wei-jun PENG Biao 李书芳. Novel error resilient tag estimation for RFID system in interference scenarios [J]. Acta Metallurgica Sinica(English letters), 2013, 20(4): 116-121.
[5]	唐永生朱士信. Chinese product of constacyclic and cyclic codes over finite rings[J]. Acta Metallurgica Sinica(English letters), 2013, 20(3): 109-113.
[6]	杨洋黄建忠童胜王新梅. Replica horizontal-shuffled iterative decoding of low-density parity-check codes[J]. Acta Metallurgica Sinica(English letters), 2010, 17(6): 32-40.
[7]	张磊袁婷婷张欣杨大成. Combined simplified maximum likelihood and sphere decoding algorithm for MIMO system[J]. Acta Metallurgica Sinica(English letters), 2008, 15(2): 56-59.

Performance analysis of complexity reduction BP decoding of rateless codes by deleting low reliable symbols

Performance analysis of complexity reduction BP decoding of rateless codes by deleting low reliable symbols

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价