Amirzade Farzane, Sadeghi Mohammad-Reza, Panario Daniel. QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field[J]. Rhhz Test. doi: 10.3934/amc.2020062
Citation:
Amirzade Farzane, Sadeghi Mohammad-Reza, Panario Daniel. QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field[J]. Rhhz Test. doi: 10.3934/amc.2020062
Amirzade Farzane, Sadeghi Mohammad-Reza, Panario Daniel. QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field[J]. Rhhz Test. doi: 10.3934/amc.2020062
Citation:
Amirzade Farzane, Sadeghi Mohammad-Reza, Panario Daniel. QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field[J]. Rhhz Test. doi: 10.3934/amc.2020062
QC-LDPC construction free of small size elementary trapping sets based on multiplicative subgroups of a finite field
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.
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 $
AmirzadeF.AlishahiM.SadeghiM.-R.An algebraic construction of QC-LDPC codes based on powers of primitive elements in a finite field and free of small ETSsJ. Algebraic Struct. The. Appl.20196129140
[2]
AmirzadeF.SadeghiM.-R.Lower bounds on the lifting degree of QC-LDPC codes by difference matricesIEEE Access20186236882370010.1109/ACCESS.2018.2830406 doi: 10.1109/ACCESS.2018.2830406
[3]
AmirzadeF.SadeghiM.-R.Analytical lower bounds on the size of elementary trapping sets of variable-regular LDPC codes with any girth and irregular ones with girth 8IEEE Trans. Commun.2018662313232110.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]
BocharovaI. E.HugF.JohannessonR.KudryashovB. D.SatyukovR. V.Searching for voltage graph-based LDPC tailbiting codes with large girthIEEE Trans. Inf. Theory2012582265227910.1109/TIT.2011.2176717MR2951330 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.
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]
FossorierM. P. C.Quasi-cyclic low-density parity-check codes from circulant permutation matricesIEEE Trans. Inf. Theory2004501788179310.1109/TIT.2004.831841MR2096847 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]
LiJ.LiuK.LinS.Abdel-GhaffarK.Algebraic quasi-cyclic LDPC codes: Construction, low error-floor, large girth and a reduced-complexity decoding schemeIEEE Trans. Commun.2014622626263710.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]
LiJ.LiuK.LinS.Abdel-GhaffarK.A matrix-theoretic approach to the construction of non-binary quasi-cyclic LDPC codesIEEE Trans. Commun.20156310571068
[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]
NguyenD. V.ChilappagariS. K.MarcellinN. W.VasicB.On the construction of structured LDPC codes free of small trapping setsIEEE Trans. Inf. Theory2012582280230210.1109/TIT.2011.2173733MR2951331 doi: 10.1109/TIT.2011.2173733
[18]
O'SullivanM. E.Algebraic construction of sparse matrices with large girthIEEE Trans. Inf. Theory20065271872710.1109/TIT.2005.862120MR2236186 doi: 10.1109/TIT.2005.862120
[19]
SadeghiM.-R.Optimal search for girth-8 quasi cyclic and spatially coupled multiple-edge LDPC codesIEEE Commun. Letters2019231466146910.1109/LCOMM.2019.2924892 doi: 10.1109/LCOMM.2019.2924892
[20]
SadeghiM.-R.AmirzadeF.Analytical lower bound on the lifting degree of multiple-edge QC-LDPC codes with girth 6IEEE Commun. Letters2018221528153110.1109/LCOMM.2018.2841873 doi: 10.1109/LCOMM.2018.2841873
[21]
SakzadA.SadeghiM.-R.PanarioD.Codes with girth 8 Tanner graph representationDesigns, Codes and Cryptography201057718110.1007/s10623-009-9349-0MR2669669 doi: 10.1007/s10623-009-9349-0
[22]
SongS.ZhouB.LinS.Abdel-GhaffarK.A unified approach to the construction of binary and nonbinary Quasi-cyclic LDPC codes based on finite fieldIEEE Trans. Commun.2009578493
[23]
H TadayonM.AlirezaT.MassinoB.Efficient search of compact QC-LDPC and SC-LDPC convolutional codes with large girthIEEE Commun. Letters2018221156115910.1109/LCOMM.2018.2827959 doi: 10.1109/LCOMM.2018.2827959
[24]
TaoX. F.LiY. F.LiuY. H.HuZ. Q.On the construction of LDPC codes free of small trapping sets by controlling cyclesIEEE Commun. Letters20182291210.1109/LCOMM.2017.2679707 doi: 10.1109/LCOMM.2017.2679707
WangJ. D.DolecekL.WeselR. D.The cycle consistency matrix approach to absorbing sets in separable circulant-based LDPC codesIEEE Trans. Inf. Theory2013592293231410.1109/TIT.2012.2235122MR3043798 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]
ZhangG.SunR.WangX.Explicit construction of girth-eight QC-LDPC codes and its application in CRT methodsJ. Commun.201233171176
[29]
ZhangL.LinS.Abdel GhaffarK.DingZ.ZhouB.Quasi-Cyclic LDPC codes on cyclic subgroups of finite fieldsIEEE Trans. Commun.2011592330233610.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.