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

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

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

Published Oct 20, 1999• 86 citations
OpenAlex

Abstract

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.

Related papers

Low density parity check codes: construction based on finite geometries

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

Low density parity check (LDPC) codes with iterative decoding based on belief propagation (IDBP) achieve astonishing error performance close to the Shannon limit. Until now there has been no known method for constructing these Shannon limit approaching codes systematically. Good LDPC codes are largely generated by computer search. As a result, the encoding of long LDPC codes is in general very complex. This paper presents the first algebraic method for constructing LDPC codes systematically based on finite analytic geometries. Four classes of finite geometry LDPC codes with relatively good minimum distances are constructed. These codes are either cyclic or quasi-cyclic and therefore their encoding can be implemented with simple linear feedback shift registers. Long finite geometry LDPC codes have been constructed and they achieve an error performance only a few tenths of a dB away from the Shannon limit. Finite geometry LDPC codes are strong competitors to turbo codes for error control in communication and digital data storage systems.

Globecom•Nov 7, 2002•46 citations

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,281 citations

Iterative decoding of a class of cyclic codes

Li Guo Zhang, Qin Huang, Shu Lin

Among the classes of LDPC codes that have been constructed and designed, the only class of LDPC codes that are cyclic is the class of codes constructed based on the incidence vectors of lines of finite geometries, called finite geometry LDPC codes. Cyclic finite geometry LDPC codes are known to have large minimum distances and can provide good error performance with very low error-floors using iterative decoding based on belief propagation. Their cyclic structure allows them to be efficiently and systematically encoded with simple shift-registers in linear time with linear complexity. An obvious question is whether, besides cyclic finite geometry LDPC codes, there are other cyclic codes with large minimum distances that can be efficiently decoded iteratively using channel soft information. In this paper, we present one such class of cyclic codes. Codes in this class are two-step majority-logic decodable and they are also constructed based on finite geometries. Two iterative decoding algorithms are devised for this class of cyclic codes and they provide significant coding gain over the two-step majority-logic decoding of codes in this class.

Information Theory and Applications Workshop (ITA)•Jan 1, 2010•4 citations

On Algebraic Construction of Gallager and Circulant Low-Density Parity-Check Codes

H. Tang, Jun Xu, Y. Kou +2 more

This correspondence presents three algebraic methods for constructing low-density parity-check (LDPC) codes. These methods are based on the structural properties of finite geometries. The first method gives a class of Gallager codes and a class of complementary Gallager codes. The second method results in two classes of circulant-LDPC codes, one in cyclic form and the other in quasi-cyclic form. The third method is a two-step hybrid method. Codes in these classes have a wide range of rates and minimum distances, and they perform well with iterative decoding.

IEEE Transactions on Information Theory•Jun 1, 2004•108 citations

A Decoding Algorithm for Finite-Geometry LDPC Codes

We develop a new low-complexity algorithm to decode low-density parity-check (LDPC) codes. The developments are oriented specifically toward low cost, yet effective, decoding of (high-rate) finite-geometry LDPC codes. The decoding procedure iteratively updates the hard-decision received vector in search of a valid codeword in the vector space. Only one bit is changed in each iteration, and the bit-selection criterion combines the number of failed checks and the reliability of the received bits. Prior knowledge of the signal amplitude and noise power is not required. An optional mechanism to avoid infinite loops in the search is also proposed. Our studies show that the algorithm achieves an appealing tradeoff between performance and complexity for finite-geometry LDPC codes.

IEEE Transactions on Communications•Feb 1, 2005•2 citations

A Class of Quantum LDPC Codes Constructed From Finite Geometries

Salah A. Aly

Low-density parity check (LDPC) codes are a significant class of classical codes with many applications. Several good LDPC codes have been constructed using random, algebraic, and finite geometries approaches, with containing cycles of length at least six in their Tanner graphs. However, it is impossible to design a self-orthogonal parity check matrix of an LDPC code without introducing cycles of length four. In this paper, a new class of quantum LDPC codes based on lines and points of finite geometries is constructed. The parity check matrices of these codes are adapted to be self- orthogonal with containing only one cycle of length four in each pair of two rows. Also, the column and row weights, and bounds on the minimum distance of these codes are given. As a consequence, these codes can be encoded using shift-register encoding algorithms and can be decoded using iterative decoding algorithms over various quantum depolarizing channels.

arXiv:0712.4115•Globecom•Jan 1, 2008•54 citations
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.
Low density parity check (LDPC) codes with iterative decoding based on belief propagation (IDBP) achieve astonishing error performance close to the Shannon limit. Until now there has been no known method for constructing these Shannon limit approaching codes systematically. Good LDPC codes are largely generated by computer search. As a result, the encoding of long LDPC codes is in general very complex. This paper presents the first algebraic method for constructing LDPC codes systematically based on finite analytic geometries. Four classes of finite geometry LDPC codes with relatively good minimum distances are constructed. These codes are either cyclic or quasi-cyclic and therefore their encoding can be implemented with simple linear feedback shift registers. Long finite geometry LDPC codes have been constructed and they achieve an error performance only a few tenths of a dB away from the Shannon limit. Finite geometry LDPC codes are strong competitors to turbo codes for error control in communication and digital data storage systems.
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.
Among the classes of LDPC codes that have been constructed and designed, the only class of LDPC codes that are cyclic is the class of codes constructed based on the incidence vectors of lines of finite geometries, called finite geometry LDPC codes. Cyclic finite geometry LDPC codes are known to have large minimum distances and can provide good error performance with very low error-floors using iterative decoding based on belief propagation. Their cyclic structure allows them to be efficiently and systematically encoded with simple shift-registers in linear time with linear complexity. An obvious question is whether, besides cyclic finite geometry LDPC codes, there are other cyclic codes with large minimum distances that can be efficiently decoded iteratively using channel soft information. In this paper, we present one such class of cyclic codes. Codes in this class are two-step majority-logic decodable and they are also constructed based on finite geometries. Two iterative decoding algorithms are devised for this class of cyclic codes and they provide significant coding gain over the two-step majority-logic decoding of codes in this class.
This correspondence presents three algebraic methods for constructing low-density parity-check (LDPC) codes. These methods are based on the structural properties of finite geometries. The first method gives a class of Gallager codes and a class of complementary Gallager codes. The second method results in two classes of circulant-LDPC codes, one in cyclic form and the other in quasi-cyclic form. The third method is a two-step hybrid method. Codes in these classes have a wide range of rates and minimum distances, and they perform well with iterative decoding.
We develop a new low-complexity algorithm to decode low-density parity-check (LDPC) codes. The developments are oriented specifically toward low cost, yet effective, decoding of (high-rate) finite-geometry LDPC codes. The decoding procedure iteratively updates the hard-decision received vector in search of a valid codeword in the vector space. Only one bit is changed in each iteration, and the bit-selection criterion combines the number of failed checks and the reliability of the received bits. Prior knowledge of the signal amplitude and noise power is not required. An optional mechanism to avoid infinite loops in the search is also proposed. Our studies show that the algorithm achieves an appealing tradeoff between performance and complexity for finite-geometry LDPC codes.
Low-density parity check (LDPC) codes are a significant class of classical codes with many applications. Several good LDPC codes have been constructed using random, algebraic, and finite geometries approaches, with containing cycles of length at least six in their Tanner graphs. However, it is impossible to design a self-orthogonal parity check matrix of an LDPC code without introducing cycles of length four. In this paper, a new class of quantum LDPC codes based on lines and points of finite geometries is constructed. The parity check matrices of these codes are adapted to be self- orthogonal with containing only one cycle of length four in each pair of two rows. Also, the column and row weights, and bounds on the minimum distance of these codes are given. As a consequence, these codes can be encoded using shift-register encoding algorithms and can be decoded using iterative decoding algorithms over various quantum depolarizing channels.