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 International Symposium on Information Theory (ISIT)

Trapping sets of structured LDPC codes

Qin Huang, Qiuju Diao, Shu Lin, Khaled Abdel-Ghaffar

Published Jul 1, 2011• 15 citations
Publisher

Abstract

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. This paper analyzes trapping set structure of binary regular LDPC codes whose parity-check matrices satisfy the constraint that no two rows (or two columns) have more than one place where they both have non-zero components, which is called row-column (RC) constraint. For a (γ,ρ)-regular LDPC code whose parity-check matrix satisfies the RC-constraint, its Tanner graph contains no (κ, τ) trapping set with size κ ≤ γ and number τ of odd degree check nodes less than γ. For several classes of RC-constrained regular LDPC codes constructed algebraically, we show that their Tanner graphs contain no trapping sets of sizes smaller than their minimum weights.

DOI
10.1109/isit.2011.6033698

Related papers

Cyclic and Quasi-Cyclic LDPC Codes on Row and Column Constrained Parity-Check Matrices and Their Trapping Sets

Qin Huang, Qiuju Diao, Shu Lin +1 more

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly LDPC codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterizations of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite geometry LDPC codes using the results developed in first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping sets of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite geometry and finite field cyclic and quasi-cyclic LDPC codes with large minimum weights are shown to have no harmful trapping sets with size smaller than their minimum weights. Consequently, their performance error-floors are dominated by their minimum weights.

arXiv:1012.3201•Dec 15, 2010•12 citations

Cyclic and Quasi-Cyclic LDPC Codes on Constrained Parity-Check Matrices and Their Trapping Sets

Qin Huang, Qiuju Diao, Shu Lin +1 more

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances.

IEEE Transactions on Information Theory•Jan 31, 2012•108 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

The Systematic Form of a Class of Regular Structured LDPC Codes

Xiuni Wang, Dongqing Xie

In this paper, we propose a systematic form about a class of regular structured LDPC codes. This class of LDPC codes is quasi-cyclic code with variable node degree dv= 2 on the Tanner graph. The defining parity-check matrices are composed of circulant permutation matrices. By columns permutation, we can locate the information bits and parity check bits easily. Furthermore, the values of associated parity check bits can be calculated directly on the Tanner graph.

International Conference on Emerging Intelligent Data and Web Technologies•Sep 1, 2013•0 citations

SP-Construction of Spatially Coupled QC-LDPC Codes

Juane Li, Shu Wen Lin, Khaled Abdel-Ghaffar +2 more

In this chapter, we present an algebraic construction of a special type of LDPC code whose Tanner graph has a very specific structure. For an LDPC code of this type, its Tanner graph is locally connected . Every VN is only connected to the CNs that are confined to a (small) span of ρ col consecutive locations and every CN is only connected to VNs that are confined to a (small) span of ρ row consecutive locations . We call such constraints on the connections between VNs and CNs of a Tanner graph ( ρ col ,ρ row) -span-constraints . With this span-constraint, the Tanner graph of such an LDPC code is actually a chain of small Tanner graphs in which each graph is connected to its adjacent graphs on either side of it, except the first and the last ones. An LDPC code of this type is called a span-constrained LDPC code. The SC-LDPC code investigated in [59, 60, 22, 86] is a type of span-constrained LDPC code. An SC-LDPC code is an LDPC convolutional (LDPC-C) code viewed from a graphical point of view (or a spatial coupling point of view) [49, 104, 66, 67, 92]. An LDPC-C code [49, 104] is specified by a bi-infinite parity-check matrix whose nonzero entries are confined to a diagonal band of a certain width ρ row and a certain depth ρ col. The nonzero entries in every row are confined to a span of ρ row consecutive locations and the nonzero entries in every column are confined to a span of ρ col consecutive locations. With these constraints on the locations of the nonzero entries of the parity-check matrix of an LDPC-C code, every VN in its Tanner graph is only connected to the CNs that are confined to a span of ρ col consecutive locations and every CN is only connected to VNs that are confined to a span of ρ row consecutive locations. These constraints on the locations of the nonzero entries of the parity-check matrix of an LDPC-C code lead to the graphical ( ρ col ,ρ row)-span-constraint as mentioned above. Hence, an LDPC-C code is a span-constrained LDPC code, an SC-LDPC code.

Cambridge University Press eBooks•Dec 1, 2016•0 citations

Structure of non-binary regular ldpc cycle codes

Jie Huang, Shengli Zhou, Peter Willett

In this paper, we study non-binary regular LDPC cycle codes whose parity check matrix has fixed column weight 2 and fixed row weight d. We prove that the parity check matrix of any regular cycle code can be put into a concatenation form of row-permuted block-diagonal matrices after row and column permutations if d is even, or, if d is odd and the code's associated graph contains at least one spanning subgraph that consists of disjoint edges. Utilizing this structure enables parallel processing in linear-time encoding, and parallel processing in sequential belief-propagation decoding, which increases the throughput without compromising performance or complexity. Numerical results are presented to compare the code performance and the decoding complexity.

IEEE International Conference on Acoustics Speech and Signal Processing•Mar 1, 2008•4 citations
THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. This paper analyzes trapping set structure of binary regular LDPC codes whose parity-check matrices satisfy the constraint that no two rows (or two columns) have more than one place where they both have non-zero components, which is called row-column (RC) constraint. For a (γ,ρ)-regular LDPC code whose parity-check matrix satisfies the RC-constraint, its Tanner graph contains no (κ, τ) trapping set with size κ ≤ γ and number τ of odd degree check nodes less than γ. For several classes of RC-constrained regular LDPC codes constructed algebraically, we show that their Tanner graphs contain no trapping sets of sizes smaller than their minimum weights.
This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly LDPC codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterizations of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite geometry LDPC codes using the results developed in first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping sets of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite geometry and finite field cyclic and quasi-cyclic LDPC codes with large minimum weights are shown to have no harmful trapping sets with size smaller than their minimum weights. Consequently, their performance error-floors are dominated by their minimum weights.
This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances.
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.
In this chapter, we present an algebraic construction of a special type of LDPC code whose Tanner graph has a very specific structure. For an LDPC code of this type, its Tanner graph is locally connected . Every VN is only connected to the CNs that are confined to a (small) span of ρ col consecutive locations and every CN is only connected to VNs that are confined to a (small) span of ρ row consecutive locations . We call such constraints on the connections between VNs and CNs of a Tanner graph ( ρ col ,ρ row) -span-constraints . With this span-constraint, the Tanner graph of such an LDPC code is actually a chain of small Tanner graphs in which each graph is connected to its adjacent graphs on either side of it, except the first and the last ones. An LDPC code of this type is called a span-constrained LDPC code. The SC-LDPC code investigated in [59, 60, 22, 86] is a type of span-constrained LDPC code. An SC-LDPC code is an LDPC convolutional (LDPC-C) code viewed from a graphical point of view (or a spatial coupling point of view) [49, 104, 66, 67, 92]. An LDPC-C code [49, 104] is specified by a bi-infinite parity-check matrix whose nonzero entries are confined to a diagonal band of a certain width ρ row and a certain depth ρ col. The nonzero entries in every row are confined to a span of ρ row consecutive locations and the nonzero entries in every column are confined to a span of ρ col consecutive locations. With these constraints on the locations of the nonzero entries of the parity-check matrix of an LDPC-C code, every VN in its Tanner graph is only connected to the CNs that are confined to a span of ρ col consecutive locations and every CN is only connected to VNs that are confined to a span of ρ row consecutive locations. These constraints on the locations of the nonzero entries of the parity-check matrix of an LDPC-C code lead to the graphical ( ρ col ,ρ row)-span-constraint as mentioned above. Hence, an LDPC-C code is a span-constrained LDPC code, an SC-LDPC code.
In this paper, we study non-binary regular LDPC cycle codes whose parity check matrix has fixed column weight 2 and fixed row weight d. We prove that the parity check matrix of any regular cycle code can be put into a concatenation form of row-permuted block-diagonal matrices after row and column permutations if d is even, or, if d is odd and the code's associated graph contains at least one spanning subgraph that consists of disjoint edges. Utilizing this structure enables parallel processing in linear-time encoding, and parallel processing in sequential belief-propagation decoding, which increases the throughput without compromising performance or complexity. Numerical results are presented to compare the code performance and the decoding complexity.