Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author: Mohammad-Reza Sadeghi

    * Corresponding author: Mohammad-Reza Sadeghi 

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
  • 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.

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


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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) $
     | Show Table
    DownLoad: CSV
  • [1] F. AmirzadeM. 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. BocharovaF. HugR. JohannessonB. 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. DiaoQ. HuangS. 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. LiK. LiuS. 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. LiK. LiuS. 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. NguyenS. K. ChilappagariN. 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. SakzadM.-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. SongB. ZhouS. 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 TadayonT. 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. TaoY. F. LiY. 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. TasdighiA. 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. WangL. 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. ZhangR. 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. ZhangS. LinK. Abdel GhaffarZ. 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.
  • 加载中




Article Metrics

HTML views(860) PDF downloads(578) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint