Journal of Networks, Vol 6, No 1 (2011), 36-45, Jan 2011

FPGA Implementation of a LDPC Decoder using a Reduced Complexity Message Passing Algorithm

Vikram Arkalgud Chandrasetty, Syed Mahfuzul Aziz


In this paper, a simplified message passing algorithm for decoding Low-Density Parity-Check (LDPC) codes is proposed with a view to reduce the implementation complexity. The algorithm is based on simple hard-decision decoding techniques while utilizing the advantages of soft channel information to improve decoder performance. It has been validated through simulation using LDPC code compliant with Wireless Local Area Network (WLAN – IEEE 802.11n) standard. The results show that theproposed algorithm can achieve significant improvement in bit error rate (BER) performance and average decoding iterations compared to fully hard-decision based decoding algorithms. The proposed algorithm has been implemented and tested on Xilinx Virtex 5 FPGA. With significantly reduced hardware resources, the implemented decoder can achieve an average throughput of ~16.2 Gbps with a BER performance of 10-5 at an Eb/No of 6.25 dB.


Digital communication, error correction coding, logic design, field programmable gate array


[1] R. Gallager, "Low-density parity-check codes," IRE Transactions on Information Theory, vol. 8, no. 1, pp. 21- 28, January 1962.

[2] D.J.C. MacKay and R.M. Neal, "Near Shannon limit performance of low density parity check codes," Electronics Letters, vol. 33, no. 6, pp. 457-458, 13 March 1997.

[3] 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, March 1999.

[4] G.L.L. Nicolas Fau, LDPC (Low Density Parity Check) - A Better Coding Scheme for Wireless PHY Layers Design and Reuse Industry Article, 2008.

[5] IEEE Std. 802.11n, "Wireless LAN medium access control (MAC) and physicallayer (PHY) specifications: enhancementsfor higher throughput", IEEE, September 2009.

[6] IEEE Stdandard 802.l6e, "Air interface for fixed and mobile broadband wireless access systems . Amendment 2: Physical and medium access control layers for combined fixed and mobile operation in licensed bands", IEEE, December 2005.

[7] A. Morello and V. Mignone, "DVB-S2: The Second Generation Standard for Satellite Broad-Band Services," Proceedings of the IEEE, vol. 94, no. 1, pp. 210-227, January 2006.

[8] Tetsuo Nozawa, LDPC Adopted for Use in Comms, Broadcasting, HDDs, Nikkei Electronics Asia, 2005.

[9] C. Winstead, V. Gaudet, A. Rapley, and C. Schlegel, "Stochastic iterative decoders," Proceedings of the IEEE International Symposium on Information Theory, pp. 1116-1120, 4-9 September 2005.

[10] Z. Cui and Z. Wang, "Improved low-complexity lowdensity parity-check decoding," IET Communications, vol. 2, no. 8, pp. 1061-1068, September 2008.

[11] G. Lechner, I. Land, and L. Rasmussen, "Decoding of LDPC codes with binary vector messages and scalable complexity," Proceedings of the International Symposium on Turbo Codes and Related Topics, Lausanne, pp. 350- 355, 1-5 September 2008.

[12] E. Yeo and V. Anantharam, "Capacity Approaching Codes, Iterative Decoding Architectures, and Their Applications," IEEE Communications Magazine, vol. 41, no. 8, pp. 132-140, 2003.

[13] S.M. Aziz and M.D. Pham, "Implementation of Low Density Parity Check Decoders using a New High Level Design Methodology," Journal of Computers, Academy Publisher, vol. 5, no. 1, pp. 81-90, January 2010.

[14] A. Anastasopoulos, "A comparison between the sumproduct and the min-sum iterative detection algorithms based on density evolution," Proceedings of the IEEE Global Telecommunications Conference, San Antonio, TX, pp. 1021-1025, 25-29 November 2001.

[15] J.H. Han and M.H. Sunwoo, "Simplified sum-product algorithm using piecewise linear function approximation for low complexity LDPC decoding," Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication, Suwon, Korea, pp. 302-308, 2009.

[16] S. Papaharalabos, et al., "Modified sum-product algorithms for decoding low-density parity-check codes," IET Communications, vol. 1, no. 3, pp. 294-300, June 2007.

[17] S. Papaharalabos and P.T. Mathiopoulos, "Simplified sum-product algorithm for decoding LDPC codes with optimal performance," Electronics Letters, vol. 45, no. 2, pp. 116-117, 15 January 2009.

[18] N. Miladinovic and M.P.C. Fossorier, "Improved bitflipping decoding of low-density parity-check codes," IEEE Transactions on Information Theory, vol. 51, no. 4, pp. 1594-1606, April 2005.

[19] Q. Dajun, J. Ming, Z. Chunming, and W. Xiaofu, "A Modification to Weighted Bit-Flipping Decoding Algorithm for LDPC Codes Based on Reliability Adjustment," Proceedings of the IEEE International Conference on Communications, Beijing, pp. 1161-1165, 19-23 May 2008.

[20] F. Guo and L. Hanzo, "Reliability ratio based weighted bit-flipping decoding for low-density parity-check codes," Electronics Letters, vol. 40, no. 21, pp. 1356-1358, 14 October 2004.

[21] C.H. Lee and W. Wolf, "Implementation-efficient reliability ratio based weighted bit-flipping decoding for LDPC codes," Electronics Letters, vol. 41, no. 13, pp. 755-757, 23 June 2005.

[22] V.A. Chandrasetty and S.M. Aziz, "A reduced complexity message passing algorithm with improved performance for LDPC decoding," Proceedings of the 12th International Conference on Computers and Information Technology, Dhaka, pp. 19-24, 21-23 December 2009.

[23] D. Costello Jr, A. Pusane, S. Bates, and K. Zigangirov, "A comparison between LDPC block and convolutional codes," Proceedings of the Information Theory and Applications Workshop, San Diego, USA, February 2006.

[24] S.J. Johnson, Introducing Low-Density Parity-Check Codes, University of Newcastle, Australia, 2006.

[25] J.C. Moreira, Essentials of error-control coding, West Sussex, England: John Wiley & Sons, 2006.

[26] T.J. Richardson and R.L. Urbanke, "The capacity of lowdensity parity-check codes under message-passing decoding," IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 599-618, February 2001.

[27] M.G. Luby, M. Amin Shokrolloahi, M. Mizenmacher, and D.A. Spielman, "Improved low-density parity-check codes using irregular graphs and belief propagation," Proceedings of the IEEE International Symposium on Information Theory, pp. 117.

[28] M. Singh and I.J. Wassell, "Comparison between soft and hard decision decoding using quaternary convolutional encoders and the decomposed CPM model," Proceedings of the IEEE VTS 53rd Vehicular Technology Conference, Rhodes, pp. 1347-1351, 06-09 May 2001.

[29] S. Sharifi Tehrani, S. Mannor, and W.J. Gross, "Fully Parallel Stochastic LDPC Decoders," IEEE Transactions on Signal Processing, vol. 56, no. 11, pp. 5692-5703, November 2008.

[30] N. Mobini, A.H. Banihashemi, and S. Hemati, "A Differential Binary Message-Passing LDPC Decoder," Proceedings of the IEEE Global Telecommunications Conference, Washington, DC, pp. 1561-1565, 26-30 November 2007.

[31] C. Chao-Yu, H. Qin, K. Jingyu, Z. Li, and L. Shu, "A binary message-passing decoding algorithm for LDPC codes," Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing Monticello, IL, pp. 424-430, Sept. 30 2009-Oct. 2 2009.

[32] H. Qin, K. Jingyu, Z. Li, L. Shu, and K. Abdel-Ghaffar, "Two reliability-based iterative majority-logic decoding algorithms for LDPC codes," IEEE Transactions on Communications, vol. 57, no. 12, pp. 3597-3606, December 2009.

[33] G. Lechner, T. Pedersen, and G. Kramer, "EXIT Chart Analysis of Binary Message-Passing Decoders," Proceedings of the IEEE International Symposium on Information Theory, Nice, pp. 871-875, 24-29 June 2007.

[34] X.Y. Hu, Software to Construct PEG LDPC code, 2008, [cited on May 2009]; Available from: tml.

[35] J.G. Proakis, Digital communications, 5th ed, New York: McGraw-Hill, 2008.

[36] V.A. Chandrasetty and S.R. Laddha, "A novel dual processing architecture for implementation of motion estimation unit of H.264 AVC on FPGA," Proceedings of the IEEE Symposium on Industrial Electronics & Applications, Kuala Lumpur, pp. 62-67, 4-6 October 2009.

[37] V.A. Chandrasetty and S.M. Aziz, "FPGA Implementation of High Performance LDPC Decoder Using Modified 2-Bit Min-Sum Algorithm," Proceedings of the 2nd International Conference on Computer Research and Development, Kuala Lumpur, pp. 881-885, 7-10 May 2010.

[38] R. Zarubica, S.G. Wilson, and E. Hall, "Multi-Gbps FPGA-Based Low Density Parity Check (LDPC) Decoder Design," Proceedings of the IEEE Global Telecommunications Conference, Washington, DC, pp. 548-552, 26-30 November 2007.

Full Text: PDF

Journal of Networks (JNW, ISSN 1796-2056)

Copyright @ 2006-2014 by ACADEMY PUBLISHER – All rights reserved.