Investigation of random-structure regular LDPC codes construction based on progressive edge-growth and algorithms for removal of short cycles

Authors

DOI:

https://doi.org/10.15587/1729-4061.2021.225852

Keywords:

LDPC, low-density parity-check, PEG, progressive edge-growth, channel coding, Tanner graphs

Abstract

This paper investigates the construction of random-structure LDPC (low-density parity-check) codes using Progressive Edge-Growth (PEG) algorithm and two proposed algorithms for removing short cycles (CB1 and CB2 algorithm; CB stands for Cycle Break).

Progressive Edge-Growth is an algorithm for computer-based design of random-structure LDPC codes, the role of which is to generate a Tanner graph (a bipartite graph, which represents a parity-check matrix of an error-correcting channel code) with as few short cycles as possible. Short cycles, especially the shortest ones with a length of 4 edges, in Tanner graphs of LDPC codes can degrade the performance of their decoding algorithm, because after certain number of decoding iterations, the information sent through its edges is no longer independent.

The main contribution of this paper is the unique approach to the process of removing short cycles in the form of CB2 algorithm, which erases edges from the code's parity-check matrix without decreasing the minimum Hamming distance of the code. The two cycle-removing algorithms can be used to improve the error-correcting performance of PEG-generated (or any other) LDPC codes and achieved results are provided. All these algorithms were used to create a PEG LDPC code which rivals the best-known PEG-generated LDPC code with similar parameters provided by one of the founders of LDPC codes.

The methods for generating the mentioned error-correcting codes are described along with simulations which compare the error-correcting performance of the original codes generated by the PEG algorithm, the PEG codes processed by either CB1 or CB2 algorithm and also external PEG code published by one of the founders of LDPC codes

Supporting Agency

  • This paper was written as a part of following scientific projects: Slovak Research and Development Agency APVV-17-0631 (Co-existence of photonics sensor systems and networks in the framework of internet of things.)

Author Biographies

Viktor Durcek, University of Zilina

PhD

Department of Multimedia and Information-Communication Technologies

Michal Kuba, University of Zilina

PhD

Department of Multimedia and Information-Communication Technologies

Milan Dado, University of Zilina

Professor, PhD

Department of Multimedia and Information-Communication Technologies

References

  1. Ryan, W. E., Lin, S. (2009). Channel Codes: Classical and Modern. Cambridge University Press. doi: https://doi.org/10.1017/cbo9780511803253
  2. Vandendriessche, P. (2009). Some low-density parity-check codes derived from finite geometries. Designs, Codes and Cryptography, 54 (3), 287–297. doi: https://doi.org/10.1007/s10623-009-9324-9
  3. Gallager, R. (1962). Low-density parity-check codes. IEEE Transactions on Information Theory, 8 (1), 21–28. doi: https://doi.org/10.1109/tit.1962.1057683
  4. MacKay, D. J. C., Neal, R. M. (1996). Near Shannon limit performance of low density parity check codes. Electronics Letters, 32 (18), 1645. doi: https://doi.org/10.1049/el:19961141
  5. MacKay, D. J. C. (1997). Good error-correcting codes based on very sparse matrices. Proceedings of IEEE International Symposium on Information Theory. doi: https://doi.org/10.1109/isit.1997.613028
  6. Arora, K., Singh, J., Randhawa, Y. S. (2019). A survey on channel coding techniques for 5G wireless networks. Telecommunication Systems, 73 (4), 637–663. doi: https://doi.org/10.1007/s11235-019-00630-3
  7. Richardson, T., Urbanke, R. (2008). Modern Coding Theory. Cambridge University Press. doi: https://doi.org/10.1017/cbo9780511791338
  8. Blahut, R. E. (2003). Algebraic Codes for Data Transmission. Cambridge University Press. doi: https://doi.org/10.1017/cbo9780511800467
  9. Fan, J., Xiao, Y., Kim, K. (2008). Design LDPC Codes without Cycles of Length 4 and 6. Research Letters in Communications, 2008, 1–5. doi: https://doi.org/10.1155/2008/354137
  10. Liu, X., Zhang, W., Fan, Z. (2009). Construction of Quasi-Cyclic LDPC Codes and the Performance on the PR4-Equalized MRC Channel. IEEE Transactions on Magnetics, 45 (10), 3699–3702. doi: https://doi.org/10.1109/tmag.2009.2023422
  11. Jiang, X.-Q., Lee, M. H., Wang, H.-M., Li, J., Wen, M. (2016). Modified PEG algorithm for large girth Quasi-cyclic protograph LDPC codes. 2016 International Conference on Computing, Networking and Communications (ICNC). doi: https://doi.org/10.1109/iccnc.2016.7440704
  12. Hailes, P., Xu, L., Maunder, R. G., Al-Hashimi, B. M., Hanzo, L. (2016). A Survey of FPGA-Based LDPC Decoders. IEEE Communications Surveys & Tutorials, 18 (2), 1098–1122. doi: https://doi.org/10.1109/comst.2015.2510381
  13. Prompakdee, P., Phakphisut, W., Supnithi, P. (2011). Quasi Cyclic-LDPC codes based on PEG algorithm with maximized girth property. 2011 International Symposium on Intelligent Signal Processing and Communications Systems (ISPACS). doi: https://doi.org/10.1109/ispacs.2011.6146165
  14. Huang, Y., Cheng, Y., Zhang, Y., Han, H. (2010). Construction of non-binary quasi-cyclic LDPC codes based on PEG algorithm. 2010 IEEE 12th International Conference on Communication Technology. doi: https://doi.org/10.1109/icct.2010.5689251
  15. Uchoa, A. G. D., Healy, C., de Lamare, R. C., Souza, R. D. (2012). Generalised Quasi-Cyclic LDPC codes based on Progressive Edge Growth Techniques for block fading channels. 2012 International Symposium on Wireless Communication Systems (ISWCS). doi: https://doi.org/10.1109/iswcs.2012.6328513
  16. Zongwang Li, Vijaya Kumar, B. V. K. (2004). A class of good quasi-cyclic low-density parity check codes based on progressive edge growth graph. Conference Record of the Thirty-Eighth Asilomar Conference on Signals, Systems and Computers. doi: https://doi.org/10.1109/acssc.2004.1399513
  17. Lei, Y., Dong, M. (2017). An Efficient Construction Method for Quasi-Cyclic Low Density Parity Check Codes. IEEE Access, 5, 4606–4610. doi: https://doi.org/10.1109/access.2017.2678515
  18. Jiang, X.-Q., Hai, H., Wang, H.-M., Lee, M. H. (2017). Constructing Large Girth QC Protograph LDPC Codes Based on PSD-PEG Algorithm. IEEE Access, 5, 13489–13500. doi: https://doi.org/10.1109/access.2017.2688701
  19. McGowan, J. A., Williamson, R. C. (2003). Loop removal from LDPC codes. Proceedings 2003 IEEE Information Theory Workshop (Cat. No.03EX674). doi: https://doi.org/10.1109/itw.2003.1216737
  20. Li, B., Wang, G., Yang, H. (2009). A new method of detecting cycles in Tanner graph of LDPC codes. 2009 International Conference on Wireless Communications & Signal Processing. doi: https://doi.org/10.1109/wcsp.2009.5371660
  21. Hu, P., Zhao, H. (2010). Improved method for detecting the short cycles of LDPC codes. 2010 IEEE International Conference on Information Theory and Information Security. doi: https://doi.org/10.1109/icitis.2010.5689706
  22. Karimi, M., Banihashemi, A. H. (2013). Message-Passing Algorithms for Counting Short Cycles in a Graph. IEEE Transactions on Communications, 61 (2), 485–495. doi: https://doi.org/10.1109/tcomm.2012.100912.120503
  23. Li, J., Lin, S., Abdel-Ghaffar, K. (2015). Improved message-passing algorithm for counting short cycles in bipartite graphs. 2015 IEEE International Symposium on Information Theory (ISIT). doi: https://doi.org/10.1109/isit.2015.7282488
  24. Cho, S., Cheun, K., Yang, K. (2018). A Message-Passing Algorithm for Counting Short Cycles in Nonbinary LDPC Codes. 2018 IEEE International Symposium on Information Theory (ISIT). doi: https://doi.org/10.1109/isit.2018.8437844
  25. Karimi, M., Banihashemi, A. H. (2012). Counting Short Cycles of Quasi Cyclic Protograph LDPC Codes. IEEE Communications Letters, 16 (3), 400–403. doi: https://doi.org/10.1109/lcomm.2012.020212.112311
  26. Su, Z., Qiu, Q., Zhou, H. (2016). Analysis and elimination of short cycles in LDPC convolutional codes. 2016 2nd IEEE International Conference on Computer and Communications (ICCC). doi: https://doi.org/10.1109/compcomm.2016.7924880
  27. Hu, X.-Y., Eleftheriou, E., Arnold, D.-M. (2001). Progressive edge-growth Tanner graphs. GLOBECOM’01. IEEE Global Telecommunications Conference (Cat. No.01CH37270). doi: https://doi.org/10.1109/glocom.2001.965567
  28. MacKay, D. J. C. The Inference Group. Available at: http://www.inference.org.uk/is/

Downloads

Published

2021-08-31

How to Cite

Durcek, V., Kuba, M., & Dado, M. (2021). Investigation of random-structure regular LDPC codes construction based on progressive edge-growth and algorithms for removal of short cycles. Eastern-European Journal of Enterprise Technologies, 4(9(112), 46–53. https://doi.org/10.15587/1729-4061.2021.225852

Issue

Vol. 4 No. 9(112) (2021): Information and controlling system

Section

Information and controlling system

License

Copyright (c) 2021 Viktor Durcek, Michal Kuba, Milan Dado

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.