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

Cambridge University Press eBooks

Finite-Geometry LDPC Codes

W.E. Ryan, Shu Lin

Published Sep 17, 2009• 1 citation
Publisher

Abstract

Finite geometries, such as Euclidean and projective geometries, are powerful mathematical tools for constructing error-control codes. In the 1960s and 1970s, finite geometries were successfully used to construct many classes of easily implementable majority-logic decodable codes. In 2000, Kou, Lin, and Fossorier [1–3] showed that finite geometries can also be used to construct LDPC codes that perform well and close to the Shannon theoretical limit with iterative decoding based on belief propagation. These codes are called finite-geometry (FG) -LDPC codes. FG-LDPC codes form the first class of LDPC codes that are constructed algebraically. Since 2000, there have been many major developments in construction of LDPC codes based on various structural properties of finite geometries [4–18]. In this chapter, we put together all the major constructions of LDPC codes based on finite geometries under a unified frame. We begin with code constructions based on Euclidean geometries and then go on to discuss those based on projective geometries. Construction of LDPC Codes Based on Lines of Euclidean Geometries This section presents a class of cyclic LDPC codes and a class of quasi-cyclic (QC) LDPC codes constructed using lines of Euclidean geometries. Before we present the constructions of these two classes of Euclidean-geometry (EG)-LDPC codes, we recall some fundamental structural properties of a Euclidean geometry that have been discussed in Chapter 2.

DOI
10.1017/cbo9780511803253.011

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

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

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•49 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 a class of finite geometry low density parity check codes

Shu Lin, Heng Tang, Yu Kou

A new class of geometry LDPC codes is presented which contains the class of Kou-Lin-Fossorier codes (see IEEE International Symposium on Information Theory, p.200, June 2000) as a subclass. If the code construction is based on Euclidean geometry (EG) and projective geometry (PG) over finite fields, we obtain four classes of LDPC codes, namely: (1) type-I EG-LDPC codes; (2) type-II EG-LDPC codes; (3) type-I PG-LDPC codes; and (4) type-II PG-LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Nov 13, 2002•7 citations

Cyclic Partial Geometries and Their Associated LDPC and Constant-Weight Codes

Juane Li, Yi Gong, Xin Wei Xiao +2 more

Partial geometries form an interesting branch in combinatorial mathematics, and recently they have been shown to be very effective in the construction of LDPC codes with distinct geometric and algebraic structures. This paper presents three specific cyclic classes of partial geometries. Based on these three classes of partial geometries, three classes of LDPC codes and three classes of constant-weight codes are constructed. Codes in these two categories are either cyclic or quasi-cyclic. Designs and constructions of these codes are straightforward and flexible without a need for extensive computer search. It is shown that long high-rate LDPC codes constructed based on the three classes of cyclic partial geometries perform well over the additive white Gaussian noise channel (AWGNC) with iterative decoding algorithm based on belief propagation. They can achieve low error-rates without visible error-floor and their decoding converges rapidly. These LDPC codes also perform well over the binary erasure channel (BEC) and are very effective in correcting phased-bursts of erasures. Based on cyclic partial geometries, a special type of constant-weight codes, called balanced codes, can be constructed. The constant-weight codes constructed based on partial geometries are either optimal or nearly optimal.

IEEE Transactions on Information Theory•May 19, 2023•2 citations
Finite geometries, such as Euclidean and projective geometries, are powerful mathematical tools for constructing error-control codes. In the 1960s and 1970s, finite geometries were successfully used to construct many classes of easily implementable majority-logic decodable codes. In 2000, Kou, Lin, and Fossorier [1–3] showed that finite geometries can also be used to construct LDPC codes that perform well and close to the Shannon theoretical limit with iterative decoding based on belief propagation. These codes are called finite-geometry (FG) -LDPC codes. FG-LDPC codes form the first class of LDPC codes that are constructed algebraically. Since 2000, there have been many major developments in construction of LDPC codes based on various structural properties of finite geometries [4–18]. In this chapter, we put together all the major constructions of LDPC codes based on finite geometries under a unified frame. We begin with code constructions based on Euclidean geometries and then go on to discuss those based on projective geometries. Construction of LDPC Codes Based on Lines of Euclidean Geometries This section presents a class of cyclic LDPC codes and a class of quasi-cyclic (QC) LDPC codes constructed using lines of Euclidean geometries. Before we present the constructions of these two classes of Euclidean-geometry (EG)-LDPC codes, we recall some fundamental structural properties of a Euclidean geometry that have been discussed in Chapter 2.
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.
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.
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.
Partial geometries form an interesting branch in combinatorial mathematics, and recently they have been shown to be very effective in the construction of LDPC codes with distinct geometric and algebraic structures. This paper presents three specific cyclic classes of partial geometries. Based on these three classes of partial geometries, three classes of LDPC codes and three classes of constant-weight codes are constructed. Codes in these two categories are either cyclic or quasi-cyclic. Designs and constructions of these codes are straightforward and flexible without a need for extensive computer search. It is shown that long high-rate LDPC codes constructed based on the three classes of cyclic partial geometries perform well over the additive white Gaussian noise channel (AWGNC) with iterative decoding algorithm based on belief propagation. They can achieve low error-rates without visible error-floor and their decoding converges rapidly. These LDPC codes also perform well over the binary erasure channel (BEC) and are very effective in correcting phased-bursts of erasures. Based on cyclic partial geometries, a special type of constant-weight codes, called balanced codes, can be constructed. The constant-weight codes constructed based on partial geometries are either optimal or nearly optimal.