QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field

Farzane Amirzade; Mohammad-Reza Sadeghi; Daniel Panario

doi:10.3934/amc.2020062

Article Contents

2020, Volume 14, Issue 3: 397-411. Doi: 10.3934/amc.2020062

This issue Previous Article Preface Next Article A generalized quantum relative entropy

QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field

1.
Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, 1591634312, Iran
2.
School of Mathematics and Statistics, Carleton University, Ottawa, K1S 5B6, Canada

^* Corresponding author: Mohammad-Reza Sadeghi
^* Corresponding author: Mohammad-Reza Sadeghi

Received: November 30, 2018

Revised: July 31, 2019

Early access: January 2020

Published: August 2020

The authors were partially funded by the Natural Sciences and Engineering Research Council (NSERC) of Canada

Abstract Full Text(HTML) Figure(3) / Table(1) Related Papers Cited by

Abstract

Trapping sets significantly influence the performance of low-density parity-check codes. An $ (a, b) $ elementary trapping set (ETS) causes high decoding failure rate and exert a strong influence on the error floor of the code, where $ a $ and $ b $ denote the size and the number of unsatisfied check-nodes in the ETS, respectively. The smallest size of an ETS in $ (3, n) $-regular LDPC codes with girth 6 is 4. In this paper, we provide sufficient conditions to construct fully connected $ (3, n) $-regular algebraic-based QC-LDPC codes with girth 6 whose Tanner graphs are free of $ (a, b) $ ETSs with $ a\leq5 $ and $ b\leq2 $. We apply these sufficient conditions to the exponent matrix of a new algebraic-based QC-LDPC code with girth at least 6. As a result, we obtain the maximum size of a submatrix of the exponent matrix which satisfies the sufficient conditions and yields a Tanner graph free of those ETSs with small size. Some algebraic-based QC-LDPC code constructions with girth 6 in the literature are special cases of our construction. Our experimental results show that removing ETSs with small size contribute to have better performance curves in the error floor region.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Figure 1. A (5, 3) EAS with $\gamma = 4$ and its corresponding variable node graph

Download: Full-size image PowerPoint slide

Figure 2. The variable node graphs of $ (4, 0) $, $ (4, 2) $ and $ (5, 1) $ ETSs with girth 6

Download: Full-size image PowerPoint slide

Figure 3. The comparison of the performance curves of two $(3, 4)$-regular QC-LDPC codes with the same length. The exponent matrices of both codes, $C1$ and $C2$, are submatrices of B in (10)

Download: Full-size image PowerPoint slide

Table 1. Row indices $ (i, j, k);\ i, j, k\in\{0, 1, 2, 3, 4\} $ and column indices $ (c_1, c_2, c_3, c_4);\ c_i\in\{0, 1, \dots, 16\} $ of $ {\mathbf B} $ in (10) to construct non-isomorphic $ (3, 4) $-regular QC-LDPC codes with girth 6 and free of $ (a, b) $ ETSs with $ a\leq5 $ and $ b\leq2 $

$ row\ indices $	$ column\ indices $
$ (1, 2, 3) $	$ (1, 2, 7, 10), \ (1, 3, 4, 13), \ (1, 3, 4, 14), \ (1, 3, 13, 14) $
$ (1, 2, 3) $	$ (1, 4, 5, 16), \ (1, 5, 8, 16), \ (1, 5, 10, 16), \ (1, 5, 12, 15) $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	F. Amirzade, M. Alishahi and M.-R. Sadeghi, An algebraic construction of QC-LDPC codes based on powers of primitive elements in a finite field and free of small ETSs, J. Algebraic Struct. The. Appl., 6 (2019), 129-140.
[2]	F. Amirzade and M.-R. Sadeghi, Lower bounds on the lifting degree of QC-LDPC codes by difference matrices, IEEE Access, 6 (2018), 23688-23700. doi: 10.1109/ACCESS.2018.2830406.
[3]	F. Amirzade and M.-R. Sadeghi, Analytical lower bounds on the size of elementary trapping sets of variable-regular LDPC codes with any girth and irregular ones with girth 8, IEEE Trans. Commun., 66 (2018), 2313-2321. doi: 10.1109/TCOMM.2018.2805834.
[4]	F. Amirzade and M.-R. Sadeghi, Efficient search of QC-LDPC codes with girths 6 and 8 and free of small elementary trapping sets with small size, arXiv: 1803.08141.
[5]	M. Battaglioni, A. Tasdighi, M. Baldi, M. H. Tadayon and F. Chiaraluce, Compact QC-LDPC block and SC-LDPC convolutional codes for low-latency communications, 2018 IEEE 29th Ann. Int. Symp. PIMRC, (2018), 1–5. doi: 10.1109/PIMRC.2018.8580758.
[6]	I. E. Bocharova, F. Hug, R. Johannesson, B. D. Kudryashov and R. V. Satyukov, Searching for voltage graph-based LDPC tailbiting codes with large girth, IEEE Trans. Inf. Theory, 58 (2012), 2265-2279. doi: 10.1109/TIT.2011.2176717.
[7]	J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976.
[8]	Q. J. Diao, Q. Huang, S. Lin and K. Abdel-Ghaffar, A matrix-theoretic approach for analyzing quasi-cyclic low-density parity-check codes, IEEE Trans. Inf. Theory, 58 (2012), 4030-4048. doi: 10.1109/TIT.2012.2184834.
[9]	Q. J. Diao, Q. Huang, S. Lin and K. Abdel-Ghaffar, A transform approach for analyzing and constructing quasi-cyclic low-density parity-check codes, IEEE Trans. Inf. Theory Appl. Workshop, San Diego, CA, USA, (2011), 1–8.
[10]	M. Diouf, D. Declercq, S. Ouya and B. Vasic, A PEG-like LDPC code design avoiding short trapping sets, IEEE Int. Symp. Inf. Theory (ISIT), (2015), 1079–1083. doi: 10.1109/ISIT.2015.7282621.
[11]	M. P. C. Fossorier, Quasi-cyclic low-density parity-check codes from circulant permutation matrices, IEEE Trans. Inf. Theory, 50 (2004), 1788-1793. doi: 10.1109/TIT.2004.831841.
[12]	Q. Huang, Q. Diao, S. Lin and K. Abdel-Ghaffar, Trapping sets of structured LDPC codes, 2011 IEEE Int. Symp. Inf. Theory, (2011), 1086–1090.
[13]	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., 62 (2014), 2626-2637. doi: 10.1109/TCOMM.2014.2339329.
[14]	J. Li, K. Liu, S. Lin and K. Abdel-Ghaffar, Quasi-cyclic LDPC codes on two arbitrary sets of a finite field, IEEE Int. Symp. Inf. Theory, (2014), 2454–2458.
[15]	J. Li, K. Liu, S. Lin and K. Abdel-Ghaffar, A matrix-theoretic approach to the construction of non-binary quasi-cyclic LDPC codes, IEEE Trans. Commun., 63 (2015), 1057-1068.
[16]	K. Liu, Q. Huang, S. Lin and K. Abdel-Ghaffar, Quasi-cyclic LDPC codes: Construction and rank analysis of their parity-check matrices, IEEE Inf. Theory and Appl. Workshop, (2012), 227–233.
[17]	D. V. Nguyen, S. K. Chilappagari, N. W. Marcellin and B. Vasic, On the construction of structured LDPC codes free of small trapping sets, IEEE Trans. Inf. Theory, 58 (2012), 2280-2302. doi: 10.1109/TIT.2011.2173733.
[18]	M. E. O'Sullivan, Algebraic construction of sparse matrices with large girth, IEEE Trans. Inf. Theory, 52 (2006), 718-727. doi: 10.1109/TIT.2005.862120.
[19]	M.-R. Sadeghi, Optimal search for girth-8 quasi cyclic and spatially coupled multiple-edge LDPC codes, IEEE Commun. Letters, 23 (2019), 1466-1469. doi: 10.1109/LCOMM.2019.2924892.
[20]	M.-R. Sadeghi and F. Amirzade, Analytical lower bound on the lifting degree of multiple-edge QC-LDPC codes with girth 6, IEEE Commun. Letters, 22 (2018), 1528-1531. doi: 10.1109/LCOMM.2018.2841873.
[21]	A. Sakzad, M.-R. Sadeghi and D. Panario, Codes with girth 8 Tanner graph representation, Designs, Codes and Cryptography, 57 (2010), 71-81. doi: 10.1007/s10623-009-9349-0.
[22]	S. Song, B. Zhou, S. Lin and K. Abdel-Ghaffar, A unified approach to the construction of binary and nonbinary Quasi-cyclic LDPC codes based on finite field, IEEE Trans. Commun., 57 (2009), 84-93.
[23]	M. H Tadayon, T. Alireza and B. Massino, Efficient search of compact QC-LDPC and SC-LDPC convolutional codes with large girth, IEEE Commun. Letters, 22 (2018), 1156-1159. doi: 10.1109/LCOMM.2018.2827959.
[24]	X. F. Tao, Y. F. Li, Y. H. Liu and Z. Q. Hu, On the construction of LDPC codes free of small trapping sets by controlling cycles, IEEE Commun. Letters, 22 (2018), 9-12. doi: 10.1109/LCOMM.2017.2679707.
[25]	A. Tasdighi, A. H. Banihashemi and M. R. Sadeghi, Efficient search of girth-optimal QC-LDPC codes, IEEE Trans. Inf. Theory, 62 (2016), 1552-1564. doi: 10.1109/TIT.2016.2523979.
[26]	J. D. Wang, L. Dolecek and R. D. Wesel, The cycle consistency matrix approach to absorbing sets in separable circulant-based LDPC codes, IEEE Trans. Inf. Theory, 59 (2013), 2293-2314. doi: 10.1109/TIT.2012.2235122.
[27]	Y. G. Wang, J. S. Yedidia and S. C. Draper, Construction of high-girth QC-LDPC codes, 2008 5th Int. Symp. Turbo Codes and related Topics, (2008), 180–185.
[28]	G. Zhang, R. Sun and X. Wang, Explicit construction of girth-eight QC-LDPC codes and its application in CRT methods, J. Commun., 33 (2012), 171-176.
[29]	L. Zhang, S. Lin, K. Abdel Ghaffar, Z. Ding and B. Zhou, Quasi-Cyclic LDPC codes on cyclic subgroups of finite fields, IEEE Trans. Commun., 59 (2011), 2330-2336. doi: 10.1109/TCOMM.2011.060911.100208.
[30]	L. Zhang, S. Lin, K. Abdel Ghaffar and B. Zhou, Circulant arrays: Rank analysis and construction of Quasi-Cyclic LDPC codes, IEEE Int. Symp. Inf. Theory (ISIT), (2010), 814–818. doi: 10.1109/ISIT.2010.5513640.