Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Algebraic structures and their applications

An algebraic construction of QC-LDPC codes based on powers of primitive elements in a finite field and free of small ETSs

Farzane Amirzade, Meysam Alishahi, Mohammad‐Reza Sadeghi

Published Mar 1, 2019• 1 citation
Publisher

Abstract

An $(a,b)$ elementary trapping set (ETS), where $a$ and $b$ denote the size and the number of unsatisfied check nodes in the ETS, influences  the performance of  low-density parity-check (LDPC) codes.  The smallest size of an ETS in LDPC codes with column weight 3 and girth 6 is 4. In this paper, we concentrate on a well-known algebraic-based construction of girth-6 QC-LDPC codes based on powers of a primitive element in a finite field $mathbb{F}_q$. For this structure, we provide the sufficient conditions to obtain $3times n$ submatrices of an exponent matrix in constructing girth-6 QC-LDPC codes whose ETSs have the size of at least 5. For structures on finite field $mathbb{F}_q$, where $q$ is a power of 2, all non-isomorphic $3times n$ submatrices of the exponent matrix which yield QC-LDPC codes free of small ETSs  are presented.

DOI
10.29252/as.2019.1394

Related papers

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

Farzane Amirzade, Mohammad‐Reza Sadeghi, Daniel Panario

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.

Advances in Mathematics of Communications•Jan 1, 2020•10 citations

Efficient Search of QC-LDPC Codes with Girths 6 and 8 and Free of Elementary Trapping Sets with Small Size

Farzane Amirzade, Mohammad‐Reza Sadeghi

One of the phenomena that influences significantly the performance of low-density parity-check codes is known as trapping sets. An $(a,b)$ elementary trapping set, or simply an ETS where $a$ is the size and $b$ is the number of degree-one check nodes and $\frac{b}{a}<1$, causes high decoding failure rate and exert a strong influence on the error floor. In this paper, we provide sufficient conditions for exponent matrices to have fully connected $(3,n)$-regular QC-LDPC codes with girths 6 and 8 whose Tanner graphs are free of small ETSs. Applying sufficient conditions on the exponent matrix to remove some 8-cycles results in removing all 4-cycles, 6-cycles as well as some small elementary trapping sets. For each girth we obtain a lower bound on the lifting degree and present exponent matrices with column weight three whose corresponding Tanner graph is free of certain ETSs.

arXiv:1803.08141•Mar 21, 2018•4 citations

Edge Coloring Technique to Remove Small Elementary Trapping Sets from Tanner Graph of QC-LDPC Codes with Column Weight 4

Mohammad‐Reza Sadeghi, Farzane Amirzade

One of the phenomena that causes high decoding failure rates is trapping sets. Characterization of $(a,b)$ elementary trapping sets (ETSs), their graphical properties and the lower bounds on their size in variable regular LDPC codes with column weights 3, 4, 5 and 6, where $a$ is the size of the ETS and $b$ is the number of degree-one check nodes, have been an interesting subject among researchers. Although progressive-edge-growth method (PEG) to construct LDPC codes free of an specific ETS has been proposed in the literature, it is mostly applied to LDPC codes with column weight 3. In this paper, we focus on constructing QC-LDPC codes with column weight 4 whose Tanner graphs are free of small ETSs. Using coloring the edges of the variable node (VN) graph corresponding to an ETS, we provide the sufficient conditions to obtain QC-LDPC codes with column weight 4, girth 6 and free of $(5,b)$ ETSs, where $b\leq4$, and $(6,b)$ ETs, where $b\leq2$. Moreover, for $(4,n)$-regular QC-LDPC codes with girth 8, we present a method to remove $(7,4)$ ETSs from Tanner graphs.

arXiv:1808.05258•Aug 15, 2018•3 citations

On the Construction of QC-LDPC Codes Based on Integer Sequence With Low Error Floor

Xiongfei Tao, Xin Chen, Bifang Wang

Quasi-cyclic low-density parity-check (QC-LDPC) codes have efficient hardware implementation and excellent correcting performance. However, the existence of trapping sets can affect the decoding performance. In this letter, a novel class of QC-LDPC codes based on integer sequence with column weight 3 and girth at least 8 is proposed. If the numbers in the sequence are different, the QC-LDPC codes free of elementary trapping sets (${a}$,${b}$) with${a} \leq10$and${b} \leq $3 can be constructed. The row weight of the parity check matrix can be arbitrary and we give a lower bound of the circulant permutation matrix (CPM) size. Simulation results show that the generated codes have good performance with low error floor over AWGN channels.

IEEE Communications Letters•Jun 30, 2022•5 citations

Analytical Lower Bounds on the Size of Elementary Trapping Sets of Variable-Regular LDPC Codes With Any Girth and Irregular Ones With Girth 8

Farzane Amirzade, Mohammad‐Reza Sadeghi

In this paper, we give lower bounds on the size of (a, b) elementary trapping sets (ETSs) of variable-regular LDPC codes with any girth, g, and irregular ones with girth 8, where a is the size and b is the number of degree-one check nodes. Our proposed lower bounds are analytical, applicable to all values of g and b, based on graph theories and tighter than the existing ones in the literature. Our results mostly depend on the girth. We also propose results, which are independent of the girth and rely on the variables a, b, y, and the column weight value. We obtain the tightest lower bounds on the size of ETSs of variable-regular LDPC codes with girth eight. These results provide us with a chance to present a method to achieve the minimum size of ETSs of irregular LDPC codes with girth, especially those whose column weight values are a subset of (2, 3, 4, 5, 61 and fulfill the inequality (b/a) <; 1. Moreover, we present a range of numerical results about (a, b) ETSs with girths 8 and 10 to compare the tightness between our proposed lower bounds and the existing bounds in the literature.

arXiv:1706.01703•IEEE Transactions on Communications•Feb 13, 2018•15 citations

Construction of Algebraic-Based Variable-Rate QC-LDPC Codes

Huaan Li, Baoming Bai, Hengzhou Xu +1 more

In this paper, we concentrate on one algebraic-based quasi-cyclic low-density parity-check (QC-LDPC) code constructed from two subsets of a finite field and generalize it to propose a class of variable-rate QC-LDPC (VR-QC-LDPC) codes, whose parity-check matrices are nested horizontally and have constant number of rows. Thus the proposed codes are significant at least in terms of storage complexity and can be simply implemented. The constructed codes also inherit the original algebraic-based QC-LDPC codes and their exponent matrices can be obtained from two subsets of the given finite field. We hereby analyze the structural properties from the isomorphism perspective, and present some rules to significantly prune the size of search space and determine the non-isomorphic exponent matrices. By distinguishing the smaller quantities of non-isomorphic matrices with cycle property metric, we can easily construct a series of nested exponent matrices with better cycle distributions and obtain the VR-QC-LDPC codes. Numerical results demonstrate that the constructed codes have better iterative decoding performance within a range of code rates and decoding iterations.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•2 citations
An (a,b)(a,b)(a,b) elementary trapping set (ETS), where aaa and bbb denote the size and the number of unsatisfied check nodes in the ETS, influences  the performance of  low-density parity-check (LDPC) codes.  The smallest size of an ETS in LDPC codes with column weight 3 and girth 6 is 4. In this paper, we concentrate on a well-known algebraic-based construction of girth-6 QC-LDPC codes based on powers of a primitive element in a finite field mathbbFqmathbb{F}_qmathbbFq​. For this structure, we provide the sufficient conditions to obtain 3timesn3times n3timesn submatrices of an exponent matrix in constructing girth-6 QC-LDPC codes whose ETSs have the size of at least 5. For structures on finite field mathbbFqmathbb{F}_qmathbbFq​, where qqq is a power of 2, all non-isomorphic 3timesn3times n3timesn submatrices of the exponent matrix which yield QC-LDPC codes free of small ETSs  are presented.
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.
One of the phenomena that influences significantly the performance of low-density parity-check codes is known as trapping sets. An (a,b)(a,b)(a,b) elementary trapping set, or simply an ETS where aaa is the size and bbb is the number of degree-one check nodes and ba<1\frac{b}{a}<1ab​<1, causes high decoding failure rate and exert a strong influence on the error floor. In this paper, we provide sufficient conditions for exponent matrices to have fully connected (3,n)(3,n)(3,n)-regular QC-LDPC codes with girths 6 and 8 whose Tanner graphs are free of small ETSs. Applying sufficient conditions on the exponent matrix to remove some 8-cycles results in removing all 4-cycles, 6-cycles as well as some small elementary trapping sets. For each girth we obtain a lower bound on the lifting degree and present exponent matrices with column weight three whose corresponding Tanner graph is free of certain ETSs.
One of the phenomena that causes high decoding failure rates is trapping sets. Characterization of (a,b)(a,b)(a,b) elementary trapping sets (ETSs), their graphical properties and the lower bounds on their size in variable regular LDPC codes with column weights 3, 4, 5 and 6, where aaa is the size of the ETS and bbb is the number of degree-one check nodes, have been an interesting subject among researchers. Although progressive-edge-growth method (PEG) to construct LDPC codes free of an specific ETS has been proposed in the literature, it is mostly applied to LDPC codes with column weight 3. In this paper, we focus on constructing QC-LDPC codes with column weight 4 whose Tanner graphs are free of small ETSs. Using coloring the edges of the variable node (VN) graph corresponding to an ETS, we provide the sufficient conditions to obtain QC-LDPC codes with column weight 4, girth 6 and free of (5,b)(5,b)(5,b) ETSs, where b≤4b\leq4b≤4, and (6,b)(6,b)(6,b) ETs, where b≤2b\leq2b≤2. Moreover, for (4,n)(4,n)(4,n)-regular QC-LDPC codes with girth 8, we present a method to remove (7,4)(7,4)(7,4) ETSs from Tanner graphs.
Quasi-cyclic low-density parity-check (QC-LDPC) codes have efficient hardware implementation and excellent correcting performance. However, the existence of trapping sets can affect the decoding performance. In this letter, a novel class of QC-LDPC codes based on integer sequence with column weight 3 and girth at least 8 is proposed. If the numbers in the sequence are different, the QC-LDPC codes free of elementary trapping sets (a{a}a,b{b}b) witha≤10{a} \leq10a≤10and${b} \leq $3 can be constructed. The row weight of the parity check matrix can be arbitrary and we give a lower bound of the circulant permutation matrix (CPM) size. Simulation results show that the generated codes have good performance with low error floor over AWGN channels.
In this paper, we give lower bounds on the size of (a, b) elementary trapping sets (ETSs) of variable-regular LDPC codes with any girth, g, and irregular ones with girth 8, where a is the size and b is the number of degree-one check nodes. Our proposed lower bounds are analytical, applicable to all values of g and b, based on graph theories and tighter than the existing ones in the literature. Our results mostly depend on the girth. We also propose results, which are independent of the girth and rely on the variables a, b, y, and the column weight value. We obtain the tightest lower bounds on the size of ETSs of variable-regular LDPC codes with girth eight. These results provide us with a chance to present a method to achieve the minimum size of ETSs of irregular LDPC codes with girth, especially those whose column weight values are a subset of (2, 3, 4, 5, 61 and fulfill the inequality (b/a) <; 1. Moreover, we present a range of numerical results about (a, b) ETSs with girths 8 and 10 to compare the tightness between our proposed lower bounds and the existing bounds in the literature.
In this paper, we concentrate on one algebraic-based quasi-cyclic low-density parity-check (QC-LDPC) code constructed from two subsets of a finite field and generalize it to propose a class of variable-rate QC-LDPC (VR-QC-LDPC) codes, whose parity-check matrices are nested horizontally and have constant number of rows. Thus the proposed codes are significant at least in terms of storage complexity and can be simply implemented. The constructed codes also inherit the original algebraic-based QC-LDPC codes and their exponent matrices can be obtained from two subsets of the given finite field. We hereby analyze the structural properties from the isomorphism perspective, and present some rules to significantly prune the size of search space and determine the non-isomorphic exponent matrices. By distinguishing the smaller quantities of non-isomorphic matrices with cycle property metric, we can easily construct a series of nested exponent matrices with better cycle distributions and obtain the VR-QC-LDPC codes. Numerical results demonstrate that the constructed codes have better iterative decoding performance within a range of code rates and decoding iterations.