AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
PDF (1.6 MB)
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Comparison of Parallelization Strategies for Min-Sum Decoding of Irregular LDPC Codes

Hua Xu( )Wei WanWei WangJun WangJiadong YangYun Wen
State Key Laboratory on Intelligent Technology and Systems, Tsinghua National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China
Department of Electronics Engineering, Tsinghua University, Beijing 100084, China
Show Author Information

Abstract

Low-Density Parity-Check (LDPC) codes are powerful error correcting codes. LDPC decoders have been implemented as efficient error correction codes on dedicated VLSI hardware architectures in recent years. This paper describes two strategies to parallelize min-sum decoding of irregular LDPC codes. The first implements min-sum LDPC decoders on multicore platforms using OpenMP, while the other uses the Compute Unified Device Architecture (CUDA) to parallelize LDPC decoding on Graphics Processing Units (GPUs). Empirical studies on data with various scales show that the performance of these decoding processes is improved by these parallel strategies and the GPUs provide more efficient, fast implementation decoder.

References

[1]
B. Chapman, G. Jost, and R. Van Der Pas, Using OpenMP: Portable Shared Memory Parallel Programming, The MIT Press, 2008.
[2]
J. D. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. E. Lefohn, and T. J. Purcell, A survey of general-purpose computation on graphics hardware, Computer Graphics Forum, vol. 26, no. 1, pp. 80-113, Mar. 2007.
[3]
R. G. Gallager, Low-density parity-check codes, IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21-28, 1962.
[4]
D. J. C. MacKay and R. M. Neal, Near shannon limit performance of low density parity check codes, Electronics Letters, vol. 32, no. 18, pp. 1645-1466, 1996.
[5]
C. E. Shannon, A mathematical theory of communication, ACM SIGMOBILE Mobile Computing and Communications Review, vol. 5, no. 1, pp. 3-55, 2001.
[6]
G. Al-Rawi, J. Cioffi, R. Motwani, and M. Horowitz, Optimizing iterative decoding of low-density Parity check codes on programmable pipelined parallel architectures, presented at the IEEE Global Telecommunications Conference, Houston, USA, 2001.
[7]
Z. He, P. Fortier, and S. Roy, A class of irregular LDPC codes with low error floor and low encoding complexity, IEEE Communications Letters, vol. 10, no. 5, pp. 372-374, 2006.
[8]
T. Tian, C. Jones, J. D. Villasenor, and R. D. Wesel, Construction of irregular LDPC codes with low error floors, presented at the 6th IEEE International Conference on Communications, Anchorage, USA, 2003.
[9]
V. D. Kolesnik, Probabilistic decoding of majority codes, Problemy Peredachi Informatsii, vol. 7, no. 3, pp. 3-12, 1971.
[10]
Y. Kou, S. Lin, and M. Fossorier, Low-density parity-check codes based on finite geometries: A rediscovery and new results, IEEE Transactions on Information Theory, vol. 47, no. 7, pp. 2711-2736, 2001.
[11]
Z. Liu and D. A. Pados, Low complexity decoding of finite geometry LDPC codes, presented at the 6th IEEE International Conference on Communications, Anchorage, USA, 2003.
[12]
J. Chen and M. Fossorier, Near optimum universal belief propagation based decoding of low-density parity check codes, IEEE Transactions on Communications, vol. 50, no. 3, pp. 406-414, 2002.
[13]
D. J. C. MacKay, Good error-correcting codes based on very sparse matrices, IEEE Transactions on Information Theory, vol. 45, no. 2, pp. 399-431, 1999.
[14]
F. R. Kschischang, B. J. Frey, and H. A. Loeliger, Factor graphs and the sum-product algorithm, IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 498-519, 2001.
[15]
M. Fossorier, M. Mihaljević, and H. Imai, Reduced complexity iterative decoding of low-density parity check codes based on belief propagation, IEEE Transactions on Communications, vol. 47, no. 5, pp. 673-680, 1999.
[16]
C. Howland and A. Blanksby, Parallel decoding architectures for low density parity check codes, presented at the IEEE International Symposium on Circuits and Systems, Sydney, Australia, 2001.
[17]
K. Shimizu, T. Ishikawa, N. Togawa, T. Ikenaga, and S. Goto, A parallel LSI architecture for LDPC decoder improving message-passing schedule, presented at the IEEE International Symposium on Circuits and Systems, Island of Kos, Greece, 2006.
[18]
G. Falcão, L. Sousa, and V. Silva, Massive parallel LDPC decoding on GPU, presented at the Principles and Practice of Parallel Programming, Salt Lake City, UT, USA, 2008.
[19]
G. Falcão, L. Sousa, V. Silva, and J. Marinho, Parallel LDPC decoding on the Cell/B.E. processor, in High Performance Embedded Architectures and Compilers, 2009, pp. 389-403.
[20]
G. Falcão, L. Sousa, and V. Silva, Massively LDPC decoding on multicore architectures, IEEE Transactions on Parallel and Distributed Systems, vol. 22, no. 2, pp. 309-322, 2011.
[21]
S. Wang, S. Cheng, and Q. Wu, A parallel decoding algorithm of LDPC codes using CUDA, presented at the 42nd Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, 2008.
[22]
R. M. Tanner, A recursive approach to low-complexity codes, IEEE Transactions on Information Theory, vol. 27, no. 5, pp. 533-547, 1981.
[23]
M. Fossorier, Quasi-cyclic low-density parity-check codes from circulant permutation matrices, IEEE Transactions on Information Theory, vol. 50, no. 8, pp. 1788-1793, 2004.
[24]
L. Chen, J. Xu, I. Djurdjevic, and S. Lin, Near-shannon-limit quasi-cyclic low-density parity-check codes, IEEE Transactions on Communications, vol. 52, no. 7, pp. 1038-1042, 2004.
[25]
D. Niu, K. Peng, J. Song, C. Pan, and Z. Yang, Multi-rate LDPC decoder implementation for China digital television terrestrial broadcasting standard, presented at IEEE International Conference on Communications, Circuits and Systems, Guilin, China, 2007.
[26]
J. Song, Z. Yang, L. Yang, K. Gong, C. Pan, J. Wang, and Y. Wu, Technical review on Chinese digital terrestrial television broadcasting standard and measurements on some working modes, IEEE Transactions on Broadcasting, vol. 53, no. 1, pp. 1-7, 2007.
[27]
X. Wang, J. Wang, J. Wang, Y. Li, S. Tang, and J. Song, Embedded transmission of multi-service over DTMB system, IEEE Transactions on Broadcasting, vol. 56, no. 4, pp. 504-513, 2010.
[28]
Q. Hong, J. Wang, and W. Lei, A resource-efficient decoder architecture for LDPC codes, presented at the International Conference on Electrical and Control Engineering (ICECE), Wuhan, China, 2010.
[29]
M. Garland, S. Le Grand, J. Nickolls, J. Anderson, J. Hardwick, S. Morton, E. Phillips, Y. Zhang, and V. Volkov, Parallel computing experiences with CUDA, MicroIEEE, vol. 28, no. 4, pp. 13-27, 2008.
Tsinghua Science and Technology
Pages 577-587
Cite this article:
Xu H, Wan W, Wang W, et al. Comparison of Parallelization Strategies for Min-Sum Decoding of Irregular LDPC Codes. Tsinghua Science and Technology, 2013, 18(6): 577-587. https://doi.org/10.1109/TST.2013.6678903

524

Views

19

Downloads

0

Crossref

N/A

Web of Science

2

Scopus

0

CSCD

Altmetrics

Received: 28 February 2012
Revised: 02 April 2013
Accepted: 06 May 2013
Published: 06 December 2013
© The author(s) 2013
Return