doi:10.3934/amc.2020062

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

doi: 10.3934/amc.2020062

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

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

More Information

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

摘要

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.
- Algebraic-based QC-LDPC codes /
- girth /
- Tanner graph /
- elementary trapping set /
- edge coloring

HTML全文

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

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

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)

下载: 全尺寸图片幻灯片

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) $

下载: 导出CSV

参考文献(30)

[1]	Amirzade F. Alishahi M. Sadeghi M.-R. 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. 2019 6 129 140
[2]	Amirzade F. Sadeghi M.-R. Lower bounds on the lifting degree of QC-LDPC codes by difference matrices IEEE Access 2018 6 23688 23700 10.1109/ACCESS.2018.2830406 doi: 10.1109/ACCESS.2018.2830406
[3]	Amirzade F. Sadeghi M.-R. 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. 2018 66 2313 2321 10.1109/TCOMM.2018.2805834 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.
[6]	Bocharova I. E. Hug F. Johannesson R. Kudryashov B. D. Satyukov R. V. Searching for voltage graph-based LDPC tailbiting codes with large girth IEEE Trans. Inf. Theory 2012 58 2265 2279 10.1109/TIT.2011.2176717 MR2951330 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]	Diao Q. J. Huang Q. Lin S. Abdel-Ghaffar K. A matrix-theoretic approach for analyzing quasi-cyclic low-density parity-check codes IEEE Trans. Inf. Theory 2012 58 4030 4048 10.1109/TIT.2012.2184834 MR2924422 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.
[11]	Fossorier M. P. C. Quasi-cyclic low-density parity-check codes from circulant permutation matrices IEEE Trans. Inf. Theory 2004 50 1788 1793 10.1109/TIT.2004.831841 MR2096847 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]	Li J. Liu K. Lin S. Abdel-Ghaffar K. Algebraic quasi-cyclic LDPC codes: Construction, low error-floor, large girth and a reduced-complexity decoding scheme IEEE Trans. Commun. 2014 62 2626 2637 10.1109/TCOMM.2014.2339329 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]	Li J. Liu K. Lin S. Abdel-Ghaffar K. A matrix-theoretic approach to the construction of non-binary quasi-cyclic LDPC codes IEEE Trans. Commun. 2015 63 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]	Nguyen D. V. Chilappagari S. K. Marcellin N. W. Vasic B. On the construction of structured LDPC codes free of small trapping sets IEEE Trans. Inf. Theory 2012 58 2280 2302 10.1109/TIT.2011.2173733 MR2951331 doi: 10.1109/TIT.2011.2173733
[18]	O'Sullivan M. E. Algebraic construction of sparse matrices with large girth IEEE Trans. Inf. Theory 2006 52 718 727 10.1109/TIT.2005.862120 MR2236186 doi: 10.1109/TIT.2005.862120
[19]	Sadeghi M.-R. Optimal search for girth-8 quasi cyclic and spatially coupled multiple-edge LDPC codes IEEE Commun. Letters 2019 23 1466 1469 10.1109/LCOMM.2019.2924892 doi: 10.1109/LCOMM.2019.2924892
[20]	Sadeghi M.-R. Amirzade F. Analytical lower bound on the lifting degree of multiple-edge QC-LDPC codes with girth 6 IEEE Commun. Letters 2018 22 1528 1531 10.1109/LCOMM.2018.2841873 doi: 10.1109/LCOMM.2018.2841873
[21]	Sakzad A. Sadeghi M.-R. Panario D. Codes with girth 8 Tanner graph representation Designs, Codes and Cryptography 2010 57 71 81 10.1007/s10623-009-9349-0 MR2669669 doi: 10.1007/s10623-009-9349-0
[22]	Song S. Zhou B. Lin S. Abdel-Ghaffar K. A unified approach to the construction of binary and nonbinary Quasi-cyclic LDPC codes based on finite field IEEE Trans. Commun. 2009 57 84 93
[23]	H Tadayon M. Alireza T. Massino B. Efficient search of compact QC-LDPC and SC-LDPC convolutional codes with large girth IEEE Commun. Letters 2018 22 1156 1159 10.1109/LCOMM.2018.2827959 doi: 10.1109/LCOMM.2018.2827959
[24]	Tao X. F. Li Y. F. Liu Y. H. Hu Z. Q. On the construction of LDPC codes free of small trapping sets by controlling cycles IEEE Commun. Letters 2018 22 9 12 10.1109/LCOMM.2017.2679707 doi: 10.1109/LCOMM.2017.2679707
[25]	Tasdighi A. Banihashemi A. H. Sadeghi M. R. Efficient search of girth-optimal QC-LDPC codes IEEE Trans. Inf. Theory 2016 62 1552 1564 10.1109/TIT.2016.2523979 MR3480065 doi: 10.1109/TIT.2016.2523979
[26]	Wang J. D. Dolecek L. Wesel R. D. The cycle consistency matrix approach to absorbing sets in separable circulant-based LDPC codes IEEE Trans. Inf. Theory 2013 59 2293 2314 10.1109/TIT.2012.2235122 MR3043798 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]	Zhang G. Sun R. Wang X. Explicit construction of girth-eight QC-LDPC codes and its application in CRT methods J. Commun. 2012 33 171 176
[29]	Zhang L. Lin S. Abdel Ghaffar K. Ding Z. Zhou B. Quasi-Cyclic LDPC codes on cyclic subgroups of finite fields IEEE Trans. Commun. 2011 59 2330 2336 10.1109/TCOMM.2011.060911.100208 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.