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
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (1.6 MB)
Cite
EndNote(RIS) BibTeX
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 Wan, Wei Wang, Jun Wang, Jiadong Yang, Yun 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.

Keywords

Low-Density Parity-Check (LDPC) codesmulticoreOpenMPGraphic Processor Unit (GPU)Compute Unified Device Architecture (CUDA)

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.
Crossref Google Scholar
[3]
R. G. Gallager, Low-density parity-check codes, IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21-28, 1962.
Crossref Google Scholar
[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.
Crossref Google Scholar
[5]
C. E. Shannon, A mathematical theory of communication, ACM SIGMOBILE Mobile Computing and Communications Review, vol. 5, no. 1, pp. 3-55, 2001.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref
[9]
V. D. Kolesnik, Probabilistic decoding of majority codes, Problemy Peredachi Informatsii, vol. 7, no. 3, pp. 3-12, 1971.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref
[22]
R. M. Tanner, A recursive approach to low-complexity codes, IEEE Transactions on Information Theory, vol. 27, no. 5, pp. 533-547, 1981.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[30]
CUDA homepage, http://developer.nvidia.com/object/cuda.html, 2013.
Tsinghua Science and Technology
Volume 18 Issue 6,
December 2013
Pages 577-587
DOI: 10.1109/TST.2013.6678903
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

599

Views

20

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