American Institute of Mathematical Sciences

August  2020, 14(3): 397-411. 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

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, 2020, 14 (3) : 397-411. doi: 10.3934/amc.2020062
References:

show all references

References:
A (5, 3) EAS with $\gamma = 4$ and its corresponding variable node graph
The variable node graphs of $(4, 0)$, $(4, 2)$ and $(5, 1)$ ETSs with girth 6
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)
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] 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 [17] 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 [18] 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 [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