Belief propagation decoding assisted on-the-fly Gaussian elimination for short LT codes

详细信息    查看全文

• 作者：Hoyoung Cheong ; Jonwon Eun ; Hyuncheol Kim ; Kuinam J. Kim
• 关键词：OFG decoding ; Complexity ; Triangularization ; Gaussian elimination
• 刊名：Cluster Computing
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：19
• 期：1
• 页码：309-314
• 全文大小：1,477 KB
• 参考文献：1.Luby, M., Codes, L.T., In: IEEE Symposium on Foundations of Computer Science, pp. 271–280 (2002)
  2.Lu, H., Lu, F., Cai, J., Foh, C.H.: LT-W: Improving LT decoding with Wiedemann solver. IEEE Trans. Inf. Theory 59(12), 7887 (2013)MathSciNet CrossRef
  3.Chang, L.-J., Wang, C.-H., Zao, J.K.: An error-floor reduction technique for short-length LT codes. In: International Symposium on Information Theory and its Applications (ISITA) 2014, Melbourne, Australia, 26–29 Oct 2014
  4.Kim, S., Ko, K., Chung, S.-Y.: Incremental Gaussian elimination decoding of raptor codes over BEC. IEEE Commun. Lett. 12(4), 307–309 (2008)CrossRef
  5.Bioglio, V., Grangetto, M., Gaeta, R., Sereno, M.: On the fly gaussian elimination for LT codes. IEEE Commun. Lett. 13(12), 953–955 (2009)CrossRef
  6.Byers, J., Luby, M., Mitzenmacher, M.: A digital fountain approach to asynchronous reliable multicast. IEEE J. Sel. Areas Commun. 20, 1528–1540 (2002)CrossRef
  7.Anglano, C., Gaeta, R., Grangetto, M.: Exploiting rateless codes in cloud storage systems. IEEE Trans. Parallel Distrib. Syst. 26(5), 1313–1322 (2015)CrossRef
  8.Schotsch, B., Garrammone, G., Vary, P.: Analysis of LT codes over finite fields under optimal erasure decoding. IEEE Commun. Lett. 17(7), 1826–1829 (2013)CrossRef
  9.Bloemer, J., Kalfane, M., Karpinski, M., Karp, R., Luby, M., Zuckerman, D.: An XOR-based erasure-resilient coding scheme. In: ICSI TR-95-048 (1995)
  
• 作者单位：Hoyoung Cheong (1)
  Jonwon Eun (1)
  Hyuncheol Kim (2)
  Kuinam J. Kim (3)
  
  1. Department of Information Communication, Namseoul University, Cheonan, Korea
  2. Department of Computer Science, Namseoul University, Cheonan, 331-707, Korea
  3. Department of Convergence Security, Kyonggi University, Suwon, Korea
  
• 刊物类别：Computer Science
• 刊物主题：Processor Architectures
  Operating Systems
  Computer Communication Networks
  
• 出版者：Springer Netherlands
• ISSN：1573-7543

文摘

Belief propagation (BP) decoding has been widely used for decoding Luby transform (LT) codes which perform very well for a large number of input symbols. However, in reality, small numbers of input symbols are often encountered. In this paper, an efficient BP decoding assisted on-the-fly Gaussian elimination (OFG) decoding process is proposed. Our algorithm exploits XOR operations to get a packet of degree one when the ripple is empty, which gives a small value of overhead. Simulation results show that the proposed algorithm gives a largely improved overhead, about a 0.25 or more, with respect to that of the conventional BP algorithm. The complexity of the proposed algorithm is notably reduced with respect to that of OFG, especially in case of \(k = 150\)–500, while guaranteeing the overhead nearly same as that of OFG.