The design of structured LDPC codes with algorithmic graph construction

• Autorzy: Sułek Wojciech

Identyfikatory

DOI

10.24425/bpasts.2022.141592

• Języki publikacji: EN

Abstrakty

EN

Low-Density Parity-Check (LDPC) codes are among the most effective modern error-correcting codes due to their excellent correction performance and highly parallel decoding scheme. Moreover, the nonbinary extension of such codes further increases performance in the short-block regime. In this paper, we review the key elements for the construction of implementation-oriented binary and nonbinary codes. These Quasi-Cyclic LDPC (QC-LDPC) codes additionally feature efficient encoder and decoder implementation frameworks. We then present a versatile algorithm for the construction of both binary and nonbinary QC-LDPC codes that have low encoding complexity and an optimized corresponding graph structure. Our algorithm uses a progressive edge growth algorithm, modified for QC-LDPC graph construction, and then performs an iterative global search for optimized cyclic shift values within the QC-LDPC circulants. Strong error correction performance is achieved by minimizing the number of short cycles, and cycles with low external connectivity, within the code graph. We validate this approach via error rate simulations of a transmission system model featuring an LDPC coder-decoder, digital modulation, and additive white Gaussian noise channels. The obtained numerical results validate the effectiveness of the proposed construction algorithm, with a number of constructed codes exhibiting either similar or superior performance to industry standard binary codes and selected nonbinary codes from the literature.

Słowa kluczowe

EN

channel coding; low density parity check code; LDPC; nonbinary code; quasi-cyclic code

PL

kodowanie kanałowe; LDPC; kodowanie niebinarne; kodowanie quasi-cykliczne; kodowanie korekcyjne

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2022
• Tom: Vol. 70, nr 4
• Strony: art. no. e141592
• Opis fizyczny: Bibliogr. 36 poz., rys., tab.

Twórcy

autor

Sułek Wojciech

• Silesian University of Technology, Gliwice, Poland

• https://orcid.org/0000-0003-3462-0657

Bibliografia

• [1] D.J.C. MacKay, “Good Error-Correcting Codes Based on Very Sparse Matrices,” IEEE Trans. Inf. Theory, vol. 45, no. 3, pp. 399–431, 1999.
• [2] J. Pawelec, “Shannon theory. Myths and reality,” Bull. Pol. Acad. Sci. Tech. Sci., vol. 56, no. 3, pp. 247–251, 2008.
• [3] M.C. Davey and D. MacKay, “Low-Density Parity Check Codes over GF(q),” IEEE Commun. Lett., vol. 2, no. 6, pp. 165–167, 1998.
• [4] D. Declercq and M. Fossorier, “Decoding Algorithms for Nonbinary LDPC Codes Over GF(q),” IEEE Trans. Commun., vol. 55, no. 4, pp. 633–643, 2007.
• [5] I.E. Bocharova, B. Kudryashov, and R. Johannesson, “Searching for Binary and Nonbinary Block and Convolutional LDPC Codes,” IEEE Trans. Inf. Theory, vol. 62, no. 1, pp. 163–183, 2016.
• [6] W. Sulek, “Protograph Based Low-Density Parity-Check Codes Design with Mixed Integer Linear Programming,” IEEE Access, vol. 7, pp. 1424–1438, 2019.
• [7] W. Sulek, “Non-binary LDPC Decoders Design for Maximizing Throughput of an FPGA Implementation,” Circuits Syst. Sig. Process., vol. 35, no. 11, pp. 4060–4080, 2016.
• [8] V.Wijekoon, E. Viterbo, Y. Hong, R. Micheloni, and A. Marelli, “A Novel Graph Expansion and a Decoding Algorithm for NBLDPC Codes,” IEEE Trans. Commun., vol. 68, no. 3, pp. 1358–1369, 2020.
• [9] T.X. Pham, T.N. Tan, and H. Lee, “Minimal-Set Trellis Min-Max Decoder Architecture for Nonbinary LDPC Codes,” IEEE Trans. Circuits Syst. II, vol. 68, no. 1, pp. 216–220, 2021.
• [10] M.P.C. Fossorier, “Quasi-Cyclic Low-Density Parity-Check Codes from Circulant Permutation Matrices,” IEEE Trans. Inf. Theory, vol. 50, no. 8, pp. 1788–1793, 2004.
• [11] S. Myung, K. Yang, and J. Kim, “Quasi-Cyclic LDPC Codes for Fast Encoding,” IEEE Trans. Inf. Theory, vol. 51, no. 8, pp. 2894–2901, 2005.
• [12] W. Sulek, “Pipeline processing in low-density parity-check codes hardware decoder,” Bull. Pol. Acad Sci. Tech. Sci., vol. 59, no. 2, pp. 149–155, 2011.
• [13] H. Cui, F. Ghaffari, K. Le, D. Declercq, J. Lin, and Z. Wang, “Design of High-Performance and Area-Efficient Decoder for 5G LDPC Codes,” IEEE Trans. Circuits Syst. I, vol. 68, no. 2, pp. 879–891, 2021.
• [14] T.T. Nguyen-Ly, V. Savin, D. Declercq, F. Ghaffari, and O. Boncalo, “Analysis and Design of Cost-Effective, High-Throughput LDPC Decoders,” IEEE Trans.VLSI Syst., vol. 26, no. 3, pp. 508–521, 2018.
• [15] M. Li, V. Derudder, K. Bertrand, C. Desset, and A. Bourdoux, “High-Speed LDPC Decoders Towards 1 Tb/s,” IEEE Trans. Circuits Syst. I, vol. 68, no. 5, pp. 2224–2233, 2021.
• [16] G. Zhang, R. Sun, and X. Wang, “New Quasi-Cyclic LDPC Codes with Girth at Least Eight based on Sidon Sequences,” in 7th International Symposium on Turbo Codes and Iterative Information Processing, Gothenburg, Sweden, August 2012, pp. 31–35.
• [17] J. Li, K. Liu, S. Lin, and K. Abdel-Ghaffar, “Algebraic Quasi-Cyclic LDPC Codes: Construction, Low Error-Floor, Large Girth and a Reduced-Complexity Decoding Scheme,” IEEE Trans. Commun., vol. 62, no. 8, pp. 2626–2637, 2014.
• [18] X.Y. Hu, E. Eleftheriou, and D.M. Arnold, “Regular and Irregular Progressive Edge-Growth Tanner Graphs,” IEEE Trans. Inf. Theory, vol. 51, no. 1, pp. 386–398, 2005.
• [19] D. Vukobratovic and V. Senk, “Generalized ACE Constrained Progressive Edge-Growth LDPC Code Design,” IEEE Commun. Lett., vol. 12, no. 1, pp. 32–34, 2008.
• [20] X. He, L. Zhou, and J. Du, “PEG-Like Design of Binary QCLDPC Codes Based on Detecting and Avoiding Generating Small Cycles,” IEEE Trans. Commun., vol. 66, no. 5, pp. 1845–1858, 2018.
• [21] J. Huang, L. Liu,W. Zhou, and S. Zhou, “Large-Girth Nonbinary QC-LDPC Codes of Various Lengths,” IEEE Trans. Commun., vol. 58, no. 12, pp. 3436–3447, 2010.
• [22] A. Tasdighi, A.H. Banihashemi, and M.-R. Sadeghi, “Efficient Search of Girth-Optimal QC-LDPC Codes,” IEEE Trans. Inf. Theory, vol. 62, no. 4, pp. 1552–1564, 2016.
• [23] T.J. Richardson and R.L. Urbanke, “Efficient Encoding of Low-Density Parity-Check Codes,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 638–656, 2001.
• [24] T. Tian, C. Jones, J.D. Villasenor, and R.D. Wesel, “Selective Avoidance of Cycles in Irregular LDPC Code Construction,” IEEE Trans. Commun., vol. 52, no. 8, pp. 1242–1247, 2004.
• [25] X. Zheng, F.C.M. Lau, and C.K. Tse, “Constructing Short-Length Irregular LDPC Codes with Low Error Floor,” IEEE Trans. Commun., vol. 58, no. 10, pp. 2823–2834, 2010.
• [26] W. Sulek, “Nonbinary Quasi-Regular QC-LDPC Codes Derived From Cycle Codes,” IEEE Commun. Lett., vol. 20, no. 9, pp. 1705–1708, 2016.
• [27] Local and metropolitan area networks – Specific requirements – Part 11:Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications Amendment 5: Enhancements for Higher Throughput, IEEE Std. 802.11n, 2009.
• [28] Local and Metropolitan Area Networks Part 16: Air Interface for Broadband Wireless Access Systems, IEEE Std. 802.16, 2012.
• [29] 5G; NR; Multiplexing and channel coding (3GPP TS 38.212 version 15.2.0 Release 15), ETSI Std. TS 138 212 V15.2.0, 2018.
• [30] T.J. Richardson, M.A. Shokrollahi, and R.L. Urbanke, “Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes,” IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 619–637, 2001.
• [31] G. Li, I.J. Fair, and W.A. Krzymien, “Density Evolution for Nonbinary LDPC Codes Under Gaussian Approximation,” IEEE Trans. Inf. Theory, vol. 55, no. 3, pp. 997–1015, 2009.
• [32] B. Rong, T. Jiang, X. Li, and M. R. Soleymani, “Combine LDPC Codes Over GF(q) With q-ary Modulations for Bandwidth Efficient Transmission,” IEEE Trans. Broadcast., vol. 54, no. 1, pp. 78–84, 2008.
• [33] W. Sulek and M. Kucharczyk, “Column Weights Optimization for Semi-Regular Nonbinary LDPC Codes,” in Proc. (IEEE) 38th International Conference on Telecommunications and Signal Processing (TSP), Prague, Czech Republic, July 9-11 2015, pp. 172–176.
• [34] R. Diestel, Graph Theory. Berlin: Springer-Verlag, 2006.
• [35] G. Han, Y.L. Guan, and L. Kong, “Construction of Irregular QCLDPC Codes via Masking with ACE Optimization,” IEEE Commun. Lett., vol. 18, no. 2, pp. 348–351, 2014.
• [36] C. Poulliat, M. Fossorier, and D. Declercq, “Design of Regular (2,dc)-LDPC Codes over GF(q) Using Their Binary Images,” IEEE Trans. Commun., vol. 56, pp. 1626–1635, October 2008.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).