doi: 10.3934/amc.2020062

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

Received  December 2018 Revised  August 2019 Published  January 2020

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

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.

Citation: Farzane Amirzade, Mohammad-Reza Sadeghi, Daniel Panario. QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field. Advances in Mathematics of Communications, doi: 10.3934/amc.2020062
References:
[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.   Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

References:
[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.   Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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) $
$ 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) $
[1]

Lasse Kliemann, Elmira Shirazi Sheykhdarabadi, Anand Srivastav. Price of anarchy for graph coloring games with concave payoff. Journal of Dynamics & Games, 2017, 4 (1) : 41-58. doi: 10.3934/jdg.2017003

[2]

Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131

[3]

Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233

[4]

Grégory Berhuy. Algebraic space-time codes based on division algebras with a unitary involution. Advances in Mathematics of Communications, 2014, 8 (2) : 167-189. doi: 10.3934/amc.2014.8.167

[5]

Peter Vandendriessche. LDPC codes associated with linear representations of geometries. Advances in Mathematics of Communications, 2010, 4 (3) : 405-417. doi: 10.3934/amc.2010.4.405

[6]

Lars Eirik Danielsen. Graph-based classification of self-dual additive codes over finite fields. Advances in Mathematics of Communications, 2009, 3 (4) : 329-348. doi: 10.3934/amc.2009.3.329

[7]

M. D. König, Stefano Battiston, M. Napoletano, F. Schweitzer. On algebraic graph theory and the dynamics of innovation networks. Networks & Heterogeneous Media, 2008, 3 (2) : 201-219. doi: 10.3934/nhm.2008.3.201

[8]

Javier de la Cruz, Michael Kiermaier, Alfred Wassermann, Wolfgang Willems. Algebraic structures of MRD codes. Advances in Mathematics of Communications, 2016, 10 (3) : 499-510. doi: 10.3934/amc.2016021

[9]

Christine A. Kelley, Deepak Sridhara, Joachim Rosenthal. Zig-zag and replacement product graphs and LDPC codes. Advances in Mathematics of Communications, 2008, 2 (4) : 347-372. doi: 10.3934/amc.2008.2.347

[10]

Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007

[11]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

[12]

Chun-Xiang Guo, Guo Qiang, Jin Mao-Zhu, Zhihan Lv. Dynamic systems based on preference graph and distance. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1139-1154. doi: 10.3934/dcdss.2015.8.1139

[13]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[14]

David Auger, Irène Charon, Iiro Honkala, Olivier Hudry, Antoine Lobstein. Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs. Advances in Mathematics of Communications, 2009, 3 (1) : 97-114. doi: 10.3934/amc.2009.3.97

[15]

Blaine Keetch, Yves van Gennip. A Max-Cut approximation using a graph based MBO scheme. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 6091-6139. doi: 10.3934/dcdsb.2019132

[16]

Seungkook Park. Coherence of sensing matrices coming from algebraic-geometric codes. Advances in Mathematics of Communications, 2016, 10 (2) : 429-436. doi: 10.3934/amc.2016016

[17]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

[18]

Carlos Munuera, Wanderson Tenório, Fernando Torres. Locally recoverable codes from algebraic curves with separated variables. Advances in Mathematics of Communications, 2020, 14 (2) : 265-278. doi: 10.3934/amc.2020019

[19]

Ye Yuan, Yan Ren, Xiaodong Liu, Jing Wang. Approach to image segmentation based on interval neutrosophic set. Numerical Algebra, Control & Optimization, 2020, 10 (1) : 1-11. doi: 10.3934/naco.2019028

[20]

Finley Freibert. The classification of complementary information set codes of lengths $14$ and $16$. Advances in Mathematics of Communications, 2013, 7 (3) : 267-278. doi: 10.3934/amc.2013.7.267

2019 Impact Factor: 0.734

Article outline

Figures and Tables

[Back to Top]