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

arXiv:1503.06900 · IEEE Transactions on Information Theory

New Classes of Partial Geometries and Their Associated LDPC Codes

Qiuju Diao, Juane Li, Shu Lin, Ian F. Blake

Published Dec 17, 2015• 40 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2015.2508455

Related papers

Low-density parity-check codes based on finite geometries: a rediscovery and new results

Y. Kou, Shu Lin, M.P.C. Fossorier

This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding.

IEEE Transactions on Information Theory•Jan 1, 2001•1,303 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

Algebraic Constructions of Quasi-Cyclic LDPC Codes Based on Prime Fields

Rui Zhang, Guixia Kang, Ningbo Zhang +2 more

On dispersing different base matrices combined with masking, different kinds of quasi-cyclic low-density parity check (QC-LDPC) codes are constructed, which may achieve good error performances. Two new algebraic constructions of regular QC-LDPC codes are presented in this paper. The two constructions are based on two base matrices by dispersing and masking. The two base matrices are based on the generators of the cyclic group of a prime field. Results show that the two classes of codes presented in this paper perform well with iterative decoding over AWGN channel and have advantages over MacKay codes in some aspects of code performances. We find that one of the constructed codes converges very fast with iterative decoding, which is a critical property in ultra-high throughput communication systems.

IEEE Vehicular Technology Conference•May 1, 2015•0 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

Low Density Parity Check Codes Based on Finite Geometries: A Rediscovery and More

Yu Kou, Shu Lin, M.P.C. Fossorier

Low density parity check (LDPC) codes with iterative decoding based on belief propagation achieve astonishing error performance close to Shannon limit. No algebraic or geometric method for constructing these codes has been reported and they are largely generated by computer search. As a result, encoding of long LDPC codes is in general very complex. This paper presents two classes of high rate LDPC codes whose constructions are based on finite Euclidean and projective geometries, respectively. These classes of codes a.re cyclic and have good constraint parameters and minimum distances. Cyclic structure adows the use of linear feedback shift registers for encoding. These finite geometry LDPC codes achieve very good error performance with either soft-decision iterative decoding based on belief propagation or Gallager's hard-decision bit flipping algorithm. These codes can be punctured or extended to obtain other good LDPC codes. A generalization of these codes is also presented.

•Oct 20, 1999•89 citations

Design of Quasi-Cyclic Cycle LDPC Codes over GF(q)

HU Shu-kai, Chao Chen, Rong Xia Sun +1 more

Quasi-cyclic (QC) low-density parity-check (LDPC) codes have several appealing properties regarding decoding, storage requirements and encoding aspects. In this paper, we focus on the QC LDPC codes over GF(q) whose parity-check matrices have fixed column weight j=2. By investigating two subgraphs in the Tanner graphs of the corresponding base matrices, we derive two upper bounds on the minimum Hamming distance for this class of codes. In addition, a method is proposed to construct QC LDPC codes over GF(q), which have good Hamming distance distributions. Simulations show that our designed codes have good performance.

IEICE Transactions on Communications•Jan 1, 2012•0 citations
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.
This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding.
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.
On dispersing different base matrices combined with masking, different kinds of quasi-cyclic low-density parity check (QC-LDPC) codes are constructed, which may achieve good error performances. Two new algebraic constructions of regular QC-LDPC codes are presented in this paper. The two constructions are based on two base matrices by dispersing and masking. The two base matrices are based on the generators of the cyclic group of a prime field. Results show that the two classes of codes presented in this paper perform well with iterative decoding over AWGN channel and have advantages over MacKay codes in some aspects of code performances. We find that one of the constructed codes converges very fast with iterative decoding, which is a critical property in ultra-high throughput communication systems.
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.
Low density parity check (LDPC) codes with iterative decoding based on belief propagation achieve astonishing error performance close to Shannon limit. No algebraic or geometric method for constructing these codes has been reported and they are largely generated by computer search. As a result, encoding of long LDPC codes is in general very complex. This paper presents two classes of high rate LDPC codes whose constructions are based on finite Euclidean and projective geometries, respectively. These classes of codes a.re cyclic and have good constraint parameters and minimum distances. Cyclic structure adows the use of linear feedback shift registers for encoding. These finite geometry LDPC codes achieve very good error performance with either soft-decision iterative decoding based on belief propagation or Gallager's hard-decision bit flipping algorithm. These codes can be punctured or extended to obtain other good LDPC codes. A generalization of these codes is also presented.
Quasi-cyclic (QC) low-density parity-check (LDPC) codes have several appealing properties regarding decoding, storage requirements and encoding aspects. In this paper, we focus on the QC LDPC codes over GF(q) whose parity-check matrices have fixed column weight j=2. By investigating two subgraphs in the Tanner graphs of the corresponding base matrices, we derive two upper bounds on the minimum Hamming distance for this class of codes. In addition, a method is proposed to construct QC LDPC codes over GF(q), which have good Hamming distance distributions. Simulations show that our designed codes have good performance.