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

IEEE Communications Letters

QC-LDPC Codes With Large Column Weight and Free of Small Size ETSs

Farzane Amirzade, Mohammad‐Reza Sadeghi, Daniel Panario

Published Dec 27, 2021• 11 citations
Publisher

Abstract

An approach to improve the performance of QC-LDPC codes is the removal of harmful trapping sets by increasing the girth. However, constructing these LDPC codes with large column weights and girth more than 8 is not easy. We are concerned with protograph-based LDPC codes with large column weights and free of small size trapping sets. We use the edge-coloring technique and some concepts from graph theory such as rainbow cycles to show that for large column weights the removal of all 8-cycles but the ones we call$\textit {rainbow 8-cycle}$causes the elimination of several small size trapping sets. We provide a detailed theoretical analysis of these harmful trapping sets. Then, we apply them to array-based LDPC codes to significantly simplify and optimize the necessary and sufficient conditions to eliminate those 8-cycles from the Tanner graph. The given exponent matrices and simulation results show the impact of this simplification and the removal of the above mentioned 8-cycles.

DOI
10.1109/lcomm.2021.3138936

Related papers

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

Construction of Protograph-Based LDPC Codes With Chordless Short Cycles

Farzane Amirzade, Mohammad‐Reza Sadeghi, Daniel Panario

There is a concept in graph theory known as a chord which has not been considered before in relation to trapping sets of Tanner graphs. A chord of a cycle is an edge outside the cycle which connects two vertices of that cycle. It is proved that short cycles with a chord are the root of several trapping sets and eliminating them increases the minimum distance$d_{\min }$of a code. We provide new analytic lower bounds on$d_{\min }$of LDPC codes with girths 6 and 8 and column weight$\gamma $in which the short cycles are all chordless. We prove, analytically, that$d_{\min }\geq 2\gamma $for girth 6 and$d_{\min }\geq \frac {3(\gamma -1)^{2}}{\gamma \ln \gamma -\gamma +1}$for girth 8. Comparing these bounds with the existing bound$\gamma +1$for girth-6 LDPC codes shows the positive and significant influence of eliminating these cycles. A method to construct protograph-based LDPC codes with different girths and free of short cycles with a chord is given which is applicable to any type of protographs, simple and multi-edge, regular and irregular. The conditions to remove small trapping sets from the Tanner graph of a multi-edge QC-LDPC code are given. Numerical results indicate that the application of our method to QC-LDPC codes improves existing results.

arXiv:2008.01322•IEEE Transactions on Information Theory•Aug 22, 2023•15 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

Protograph-based LDPC codes with chordless short cycles and large minimum distance

Farzane Amirzade, Mohammad‐Reza Sadeghi, Daniel Panario

Controlling small size trapping sets and short cycles can result in LDPC codes with large minimum distance$d_{\min}$. We prove that short cycles with a chord are the root of several trapping sets and eliminating these cycles increases$d_{\min}$. We show that the lower bounds on$d_{\min}$of an LDPC code with chordless short cycles, girth 6 and column weights$\gamma$is$2\gamma$. This is a significant improvement compared to the existing bounds$\gamma+1$• Several exponent matrices of protograph-based LDPC codes with chordless short cycles are proposed for any type of pro-tographs, single-edge and multi-edge. These numerical results as well as simulations show that the removal of short cycles with a chord improves previous results in the literature.

Canadian Workshop on Information Theory (CWIT)•Jun 5, 2022•1 citation

A PEG-like LDPC code design avoiding short trapping sets

Madiagne Diouf, David Declercq, Samuel Ouya +1 more

In this paper, we propose a predictive method to construct regular column-weight-three LDPC codes with girth g = 8 so that their Tanner graphs contain a minimum number of small trapping sets. Our construction is based on improvements of the Progressive Edge-Growth (PEG) algorithm. We first show how to detect the smallest trapping sets (5; 3) and (6; 4) in the computation tree spread from variable nodes during the edge assignment. A precise and rigorous characterization of trapping sets (5; 3) and (6; 4) are given, and we then derive a modification of the Randomized Progressive Edge-Growth (RandPEG) algorithm [1] to take into account a new cost function that allows to build regular column-weight dv= 3, girth 8 LDPC codes free of (5,3) and with a minimization of (6,4). We present the construction and the performance results in the context of quasi-cyclic LDPC (QC-LDPC) codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2015•28 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
An approach to improve the performance of QC-LDPC codes is the removal of harmful trapping sets by increasing the girth. However, constructing these LDPC codes with large column weights and girth more than 8 is not easy. We are concerned with protograph-based LDPC codes with large column weights and free of small size trapping sets. We use the edge-coloring technique and some concepts from graph theory such as rainbow cycles to show that for large column weights the removal of all 8-cycles but the ones we callrainbow 8-cycle\textit {rainbow 8-cycle}rainbow 8-cyclecauses the elimination of several small size trapping sets. We provide a detailed theoretical analysis of these harmful trapping sets. Then, we apply them to array-based LDPC codes to significantly simplify and optimize the necessary and sufficient conditions to eliminate those 8-cycles from the Tanner graph. The given exponent matrices and simulation results show the impact of this simplification and the removal of the above mentioned 8-cycles.
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.
There is a concept in graph theory known as a chord which has not been considered before in relation to trapping sets of Tanner graphs. A chord of a cycle is an edge outside the cycle which connects two vertices of that cycle. It is proved that short cycles with a chord are the root of several trapping sets and eliminating them increases the minimum distancedmin⁡d_{\min }dmin​of a code. We provide new analytic lower bounds ondmin⁡d_{\min }dmin​of LDPC codes with girths 6 and 8 and column weight$\gamma inwhichtheshortcyclesareallchordless.Weprove,analytically,thatin which the short cycles are all chordless. We prove, analytically, thatinwhichtheshortcyclesareallchordless.Weprove,analytically,thatd_{\min }\geq 2\gamma forgirth6andfor girth 6 andforgirth6andd_{\min }\geq \frac {3(\gamma -1)^{2}}{\gamma \ln \gamma -\gamma +1}forgirth8.Comparingtheseboundswiththeexistingboundfor girth 8. Comparing these bounds with the existing boundforgirth8.Comparingtheseboundswiththeexistingbound\gamma +1$for girth-6 LDPC codes shows the positive and significant influence of eliminating these cycles. A method to construct protograph-based LDPC codes with different girths and free of short cycles with a chord is given which is applicable to any type of protographs, simple and multi-edge, regular and irregular. The conditions to remove small trapping sets from the Tanner graph of a multi-edge QC-LDPC code are given. Numerical results indicate that the application of our method to QC-LDPC codes improves existing results.
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.
Controlling small size trapping sets and short cycles can result in LDPC codes with large minimum distancedmin⁡d_{\min}dmin​. We prove that short cycles with a chord are the root of several trapping sets and eliminating these cycles increasesdmin⁡d_{\min}dmin​. We show that the lower bounds ondmin⁡d_{\min}dmin​of an LDPC code with chordless short cycles, girth 6 and column weightsγ\gammaγis2γ2\gamma2γ. This is a significant improvement compared to the existing boundsγ+1\gamma+1γ+1• Several exponent matrices of protograph-based LDPC codes with chordless short cycles are proposed for any type of pro-tographs, single-edge and multi-edge. These numerical results as well as simulations show that the removal of short cycles with a chord improves previous results in the literature.
In this paper, we propose a predictive method to construct regular column-weight-three LDPC codes with girth g = 8 so that their Tanner graphs contain a minimum number of small trapping sets. Our construction is based on improvements of the Progressive Edge-Growth (PEG) algorithm. We first show how to detect the smallest trapping sets (5; 3) and (6; 4) in the computation tree spread from variable nodes during the edge assignment. A precise and rigorous characterization of trapping sets (5; 3) and (6; 4) are given, and we then derive a modification of the Randomized Progressive Edge-Growth (RandPEG) algorithm [1] to take into account a new cost function that allows to build regular column-weight dv= 3, girth 8 LDPC codes free of (5,3) and with a minimization of (6,4). We present the construction and the performance results in the context of quasi-cyclic LDPC (QC-LDPC) codes.
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.