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 Transactions on Information Theory

LDPC Codes on Partial Geometries: Construction, Trapping Set Structure, and Puncturing

Qiuju Diao, Ying Yu Tai, Shu Lin, Khaled Abdel-Ghaffar

Published Nov 19, 2013• 41 citations
Publisher

Abstract

Many known constructions of LDPC codes can be placed in a general framework using the notion of partial geometries. Based on this notion, the structure of such LDPC codes can be analyzed using a geometric approach that illuminates important properties of their parity-check matrices. In this approach, trapping sets are represented by subgeometries of the geometry used to construct the code. Based on the incidence relations between lines and points in this geometry, the structure of trapping sets is investigated. On the other hand, it is shown that removing a subgeometry corresponding to a trapping set gives a punctured matrix which can be used as a parity-check matrix of an LDPC code. This relates trapping sets, represented by subgeometries, and punctured matrices, represented by the residual geometries. The null spaces of these punctured matrices are LDPC codes which inherit many of the good structural properties of the original code. Hence, new LDPC codes, with various lengths and rates, can be obtained by puncturing an LDPC code constructed based on a partial geometry. Furthermore, these punctured matrices and codes can be used in a two-phase decoding scheme to correct combinations of errors and erasures.

DOI
10.1109/tit.2013.2280640

Related papers

New Classes of Partial Geometries and Their Associated LDPC Codes

Qiuju Diao, Juane Li, Shu Lin +1 more

The use of partial geometries to construct parity-check matrices for binary low-density parity-check (LDPC) codes has resulted in the design of successful codes with a probability of error on the AWGN channel close to the Shannon capacity at bit error rate down to $10^{-15}$ . Such considerations have motivated this further investigation. A new and simple construction of a type of partial geometries with a quasi-cyclic (QC) structure is given and their properties are investigated. Two new classes of this type of partial geometries, one based on prime fields and the other based on cyclic subgroups of prime orders of finite fields, are constructed. QC-LDPC codes with good error performances are constructed based on these two new classes of partial geometries. The trapping sets of the partial geometry codes were previously considered using the geometric aspects of the underlying structure to derive information on the size of allowable trapping sets. This topic is further considered here. Finally, there is a natural relationship between partial geometries and strongly regular graphs. The eigenvalues of the adjacency matrices of such graphs are well known, and it is of interest to determine if any of the Tanner graphs derived from the partial geometries are good expanders for certain parameter sets, since it can be argued that codes with good geometric and expansion properties might perform well on the AWGN channel under message-passing decoding.

arXiv:1503.06900•IEEE Transactions on Information Theory•Dec 17, 2015•40 citations

Error floors and finite geometries

Shu Lin, Qiuju Diao, Ian F. Blake

The structure of certain subgraphs of the Tanner graph of an LDPC code, the trapping sets, has been identified as important for the error floor performance of iterative decoding algorithms. To investigate such sets requires the parity check matrix of the code to be generated with sufficient structure that allows useful information to be obtained while giving good codes. Structures that have been considered include combinatorial designs and classical finite geometries. More recently other finite geometric notions such as partial geometries and generalized d-gons have been considered with some success. This work considers aspects of this approach.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 1, 2014•6 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

Correcting combinations of errors and erasures with Euclidean geometry LDPC codes

Qiuju Diao, Ying Yu Tai, Shu Lin +1 more

It is shown that Euclidean geometry LDPC codes in conjunction with their shortened codes obtained by puncturing their parity-check matrices are effective in correcting combinations of errors and erasures with a two-phase decoding scheme. This is due to the large row redundancies of the parity-check matrices of these codes which are given by the incidence matrices of Euclidean geometries.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•1 citation

Construction of Optimal Puncturing of Low-Density Parity-Check Codes

S. Suresh Kumar, Manju Rajaram

Low-density parity-check with Length-compatible and low error floors (LDPC-LCLEF) on the binary symmetric channel is presented in this paper. These codes can support a wide range of lengths for a given rate and also the Tanner graphs are free of small trapping sets. This can be obtained by applying the schemes of shortening and puncturing to good LDPC codes and the trapping sets are selected using the trapping set ontology based on their relative harmfulness for the given decoding algorithm. The conventional approach does not guarantee to have a good performance as the degree distributions may be wildly varied. In this paper, a modified algorithm is presented to generate LDPC codes of a given rate with almost their degree distributions are same as the mother code degree distribution. Also the relative harmfulness for different trapping sets are evaluated and decoding failures of one trapping set in presence or absence of other trapping sets are analyzed. To facilitate this discussion, a new description of structured LDPC codes with arrays of permutation matrices as parity-check matrices is given. Numerical results show that the LDPC code constructed by this approach performed much better than the conventional approach.

CiiT international journal of fuzzy systems•Jan 1, 2014•0 citations

Trapping set structure of LDPC codes on finite geometries

Qiuju Diao, Ying Yu Tai, Shu Lin +1 more

The trapping set structure of LDPC codes constructed based on finite geometries, called finite geometry (FG) LDPC codes, is analyzed using a geometric approach. In this approach, trapping sets in the Tanner graph of an FG-LDPC code are represented by subgeometries of the geometry based on which the code is constructed. Using this geometrical representation, bounds and configurations of trapping sets of an FG-LDPC code can be derived and analyzed.

Information Theory and Applications Workshop (ITA)•Feb 1, 2013•9 citations
Many known constructions of LDPC codes can be placed in a general framework using the notion of partial geometries. Based on this notion, the structure of such LDPC codes can be analyzed using a geometric approach that illuminates important properties of their parity-check matrices. In this approach, trapping sets are represented by subgeometries of the geometry used to construct the code. Based on the incidence relations between lines and points in this geometry, the structure of trapping sets is investigated. On the other hand, it is shown that removing a subgeometry corresponding to a trapping set gives a punctured matrix which can be used as a parity-check matrix of an LDPC code. This relates trapping sets, represented by subgeometries, and punctured matrices, represented by the residual geometries. The null spaces of these punctured matrices are LDPC codes which inherit many of the good structural properties of the original code. Hence, new LDPC codes, with various lengths and rates, can be obtained by puncturing an LDPC code constructed based on a partial geometry. Furthermore, these punctured matrices and codes can be used in a two-phase decoding scheme to correct combinations of errors and erasures.
The use of partial geometries to construct parity-check matrices for binary low-density parity-check (LDPC) codes has resulted in the design of successful codes with a probability of error on the AWGN channel close to the Shannon capacity at bit error rate down to 10−1510^{-15}10−15 . Such considerations have motivated this further investigation. A new and simple construction of a type of partial geometries with a quasi-cyclic (QC) structure is given and their properties are investigated. Two new classes of this type of partial geometries, one based on prime fields and the other based on cyclic subgroups of prime orders of finite fields, are constructed. QC-LDPC codes with good error performances are constructed based on these two new classes of partial geometries. The trapping sets of the partial geometry codes were previously considered using the geometric aspects of the underlying structure to derive information on the size of allowable trapping sets. This topic is further considered here. Finally, there is a natural relationship between partial geometries and strongly regular graphs. The eigenvalues of the adjacency matrices of such graphs are well known, and it is of interest to determine if any of the Tanner graphs derived from the partial geometries are good expanders for certain parameter sets, since it can be argued that codes with good geometric and expansion properties might perform well on the AWGN channel under message-passing decoding.
The structure of certain subgraphs of the Tanner graph of an LDPC code, the trapping sets, has been identified as important for the error floor performance of iterative decoding algorithms. To investigate such sets requires the parity check matrix of the code to be generated with sufficient structure that allows useful information to be obtained while giving good codes. Structures that have been considered include combinatorial designs and classical finite geometries. More recently other finite geometric notions such as partial geometries and generalized d-gons have been considered with some success. This work considers aspects of this approach.
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.
Low-density parity-check with Length-compatible and low error floors (LDPC-LCLEF) on the binary symmetric channel is presented in this paper. These codes can support a wide range of lengths for a given rate and also the Tanner graphs are free of small trapping sets. This can be obtained by applying the schemes of shortening and puncturing to good LDPC codes and the trapping sets are selected using the trapping set ontology based on their relative harmfulness for the given decoding algorithm. The conventional approach does not guarantee to have a good performance as the degree distributions may be wildly varied. In this paper, a modified algorithm is presented to generate LDPC codes of a given rate with almost their degree distributions are same as the mother code degree distribution. Also the relative harmfulness for different trapping sets are evaluated and decoding failures of one trapping set in presence or absence of other trapping sets are analyzed. To facilitate this discussion, a new description of structured LDPC codes with arrays of permutation matrices as parity-check matrices is given. Numerical results show that the LDPC code constructed by this approach performed much better than the conventional approach.