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

Advances in Mathematics of Communications

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

Published Jan 1, 2020• 10 citations
Publisher

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.

DOI
10.3934/amc.2020062

Related papers

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

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

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.

Algebraic structures and their applications•Mar 1, 2019•1 citation

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 LDPC Codes Free of Small Trapping Sets by Controlling Cycles

Xiongfei Tao, Yufei Li, Yonghe Liu +1 more

Low-density parity-check (LDPC) codes exhibit excellent error correcting capability. However, small trapping sets in the Tanner graph are harmful to the iterative decoding algorithm. In this letter, we present a method of constructing (3, n) girth-eight quasi-cyclic LDPC codes with low error floor by removing the small trapping sets from the Tanner graph. To address this issue, we analyze the relationship between eight-cycles and small trapping sets of Tanner graphs based on fully connected base graphs without parallel edges. We find that if some eight-cycles are not found in the Tanner graphs, any elementary trapping set in the range of a ≤ 8 and b ≤ 3 is removed naturally. We also derive a lower bound on the permutation size for the construction of such codes. The experimental simulation shows a favorable error rate performance with lower error floor over additive white Gaussian noise channels.

IEEE Communications Letters•Mar 8, 2017•30 citations

On Characterization of Elementary Trapping Sets of Variable-Regular LDPC Codes

Karimi, Mehdi, Amir H. Banihashemi

In this paper, we study the graphical structure of elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. ETSs are known to be the main cause of error floor in LDPC coding schemes. For the set of LDPC codes with a given variable node degree $d_l$ and girth $g$, we identify all the non-isomorphic structures of an arbitrary class of $(a,b)$ ETSs, where $a$ is the number of variable nodes and $b$ is the number of odd-degree check nodes in the induced subgraph of the ETS. Our study leads to a simple characterization of dominant classes of ETSs (those with relatively small values of $a$ and $b$) based on short cycles in the Tanner graph of the code. For such classes of ETSs, we prove that any set ${\cal S}$ in the class is a layered superset (LSS) of a short cycle, where the term "layered" is used to indicate that there is a nested sequence of ETSs that starts from the cycle and grows, one variable node at a time, to generate ${\cal S}$. This characterization corresponds to a simple search algorithm that starts from the short cycles of the graph and finds all the ETSs with LSS property in a guaranteed fashion. Specific results on the structure of ETSs are presented for $d_l = 3, 4, 5, 6$, $g = 6, 8$ and $a, b \leq 10$ in this paper. The results of this paper can be used for the error floor analysis and for the design of LDPC codes with low error floors.

arXiv:1308.1259•Aug 6, 2013•0 citations

On Characterization of Elementary Trapping Sets of Variable-Regular LDPC Codes

Mehdi Karimi, Amir H. Banihashemi

In this paper, we study the graphical structure of elementary trapping sets (ETSs) of variable-regular low-density parity-check (LDPC) codes. ETSs are known to be the main cause of error floor in LDPC coding schemes. For the set of LDPC codes with a given variable node degree dl and girth g, we identify all the nonisomorphic structures of an arbitrary class of (a, b) ETSs, where a is the number of variable nodes and b is the number of odd-degree check nodes in the induced subgraph of the ETS. This paper leads to a simple characterization of dominant classes of ETSs (those with relatively small values of a and b) based on short cycles in the Tanner graph of the code. For such classes of ETSs, we prove that any set S in the class is a layered superset (LSS) of a short cycle, where the term layered is used to indicate that there is a nested sequence of ETSs that starts from the cycle and grows, one variable node at a time, to generate S. This characterization corresponds to a simple search algorithm that starts from the short cycles of the graph and finds all the ETSs with LSS property in a guaranteed fashion. Specific results on the structure of ETSs are presented for dl= 3, 4, 5, 6, g = 6, 8, and a, b ≤ 10 in this paper. The results of this paper can be used for the error floor analysis and for the design of LDPC codes with low error floors.

IEEE Transactions on Information Theory•Jul 2, 2014•68 citations
Trapping sets significantly influence the performance of low-density parity-check codes. An (a,b)(a, b)(a,b) elementary trapping set (ETS) causes high decoding failure rate and exert a strong influence on the error floor of the code, where aaa and bbb denote the size and the number of unsatisfied check-nodes in the ETS, respectively. The smallest size of an ETS in (3,n)(3, n)(3,n)-regular LDPC codes with girth 6 is 4. In this paper, we provide sufficient conditions to construct fully connected (3,n)(3, n)(3,n)-regular algebraic-based QC-LDPC codes with girth 6 whose Tanner graphs are free of (a,b)(a, b)(a,b) ETSs with a≤5a\leq5a≤5 and b≤2b\leq2b≤2. 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.
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.
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.
Low-density parity-check (LDPC) codes exhibit excellent error correcting capability. However, small trapping sets in the Tanner graph are harmful to the iterative decoding algorithm. In this letter, we present a method of constructing (3, n) girth-eight quasi-cyclic LDPC codes with low error floor by removing the small trapping sets from the Tanner graph. To address this issue, we analyze the relationship between eight-cycles and small trapping sets of Tanner graphs based on fully connected base graphs without parallel edges. We find that if some eight-cycles are not found in the Tanner graphs, any elementary trapping set in the range of a ≤ 8 and b ≤ 3 is removed naturally. We also derive a lower bound on the permutation size for the construction of such codes. The experimental simulation shows a favorable error rate performance with lower error floor over additive white Gaussian noise channels.
In this paper, we study the graphical structure of elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. ETSs are known to be the main cause of error floor in LDPC coding schemes. For the set of LDPC codes with a given variable node degree dld_ldl​ and girth ggg, we identify all the non-isomorphic structures of an arbitrary class of (a,b)(a,b)(a,b) ETSs, where aaa is the number of variable nodes and bbb is the number of odd-degree check nodes in the induced subgraph of the ETS. Our study leads to a simple characterization of dominant classes of ETSs (those with relatively small values of aaa and bbb) based on short cycles in the Tanner graph of the code. For such classes of ETSs, we prove that any set S{\cal S}S in the class is a layered superset (LSS) of a short cycle, where the term "layered" is used to indicate that there is a nested sequence of ETSs that starts from the cycle and grows, one variable node at a time, to generate S{\cal S}S. This characterization corresponds to a simple search algorithm that starts from the short cycles of the graph and finds all the ETSs with LSS property in a guaranteed fashion. Specific results on the structure of ETSs are presented for dl=3,4,5,6d_l = 3, 4, 5, 6dl​=3,4,5,6, g=6,8g = 6, 8g=6,8 and a,b≤10a, b \leq 10a,b≤10 in this paper. The results of this paper can be used for the error floor analysis and for the design of LDPC codes with low error floors.
In this paper, we study the graphical structure of elementary trapping sets (ETSs) of variable-regular low-density parity-check (LDPC) codes. ETSs are known to be the main cause of error floor in LDPC coding schemes. For the set of LDPC codes with a given variable node degree dl and girth g, we identify all the nonisomorphic structures of an arbitrary class of (a, b) ETSs, where a is the number of variable nodes and b is the number of odd-degree check nodes in the induced subgraph of the ETS. This paper leads to a simple characterization of dominant classes of ETSs (those with relatively small values of a and b) based on short cycles in the Tanner graph of the code. For such classes of ETSs, we prove that any set S in the class is a layered superset (LSS) of a short cycle, where the term layered is used to indicate that there is a nested sequence of ETSs that starts from the cycle and grows, one variable node at a time, to generate S. This characterization corresponds to a simple search algorithm that starts from the short cycles of the graph and finds all the ETSs with LSS property in a guaranteed fashion. Specific results on the structure of ETSs are presented for dl= 3, 4, 5, 6, g = 6, 8, and a, b ≤ 10 in this paper. The results of this paper can be used for the error floor analysis and for the design of LDPC codes with low error floors.