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 Communications

Codes for Iterative Decoding From Partial Geometries

Sarah J. Johnson, Steven R. Weller

Published Feb 1, 2004• 72 citations
Publisher

Abstract

This paper develops codes suitable for iterative decoding using the sum-product algorithm. By considering a large class of combinatorial structures, known as partial geometries, we are able to define classes of low-density parity-check (LDPC) codes, which include several previously known families of codes as special cases. The existing range of algebraic LDPC codes is limited, so the new families of codes obtained by generalizing to partial geometries significantly increase the range of choice of available code lengths and rates. We derive bounds on minimum distance, rank, and girth for all the codes from partial geometries, and present constructions and performance results for the classes of partial geometries which have not previously been proposed for use with iterative decoding. We show that these new codes can achieve improved error-correction performance over randomly constructed LDPC codes and, in some cases, achieve this with a significant decrease in decoding complexity.

DOI
10.1109/tcomm.2003.822737

Related papers

Codes for iterative decoding from partial geometries

Sarah J. Johnson, Steven R. Weller

This work develops codes suitable for iterative decoding using the sum-product algorithm. We consider regular low-density parity-check (LDPC) codes derived from partial geometries, a large class of combinatorial structures which include several of the previously proposed algebraic constructions for LDPC codes as special cases. We derive bounds on minimum distance and rank/sub 2/(H) for codes from partial geometries, and present constructions and performance results for two classes of partial geometries which have not previously been proposed for use with iterative decoding.

IEEE International Symposium on Information Theory (ISIT)•Jun 25, 2003•17 citations

Regular LDPC Codes from Strongly Regular (a ,ß )-Geometries

Xiuli Li, Zhengduo Shan

By considering a class of combinatorial structures, known as strongly regular (a, beta) -geometries, we define a class of low-density parity-check (LDPC) codes. We derive bounds on minimum distance, rank and girth for the codes from strongly regular (a, beta) -geometries, which have not previously been proposed for use with iterative decoding. In further, we present performance results for the class of codes.

International Forum on Information Technology and Applications•May 1, 2009•0 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 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

Can cyclic codes be useful low-density parity-check codes?

Sarah J. Johnson, Steven R. Weller

Traditionally, low-density parity-check (LDPC) codes are constructed randomly and it is not clear whether algebraically constructed codes, such as cyclic codes, can compete with the error correction performances of the random codes. We consider in this paper new cyclic low-density parity-check codes decoded with the sum-product algorithm. The cyclic codes we present have sparse parity-check matrices, good minimum distance and girth 6. Using frnite-length analysis and simulation results we show that the most significant benefit of the new codes, in terms of error correction performance, is the linearly dependent rows in their parity-check matrices. Our results suggest that increasing column weight to improve the minimum distance and the minimum stopping set size of the code proves beneficial at low erasure probabilities but adversely affects performance in channels with high erasure probabilities.

•Jan 1, 2003•1 citation

Low-density parity-check codes from combinatorial designs

Sarah J. Johnson

Abstract Recent breakthroughs in forward error correction, in the form of low-density parity-check(LDPC) and turbo codes, have seen the promise of near Shannon limit information trans-mission realised. The deterministic construction of good codes, for LDPC codes in par-ticular, is currently the subject of intense interest in the research and development com-munity. This thesis adds to this field, developing methods and supporting theory for thedesign of algebraic LDPC codes using incidence structures from combinatorial designs.The benefits of this approach are guaranteed code properties, parameter flexibility, easeof implementation and reduced encoding complexity.In the first part of this thesis Steiner 2-designs and partial geometries are used toprovide systematic constructions of regular LDPC codes with Tanner graphs free of 4-cyclesandwithdeterministiccodeproperties. Drawingextensivelyfromexistingincidencestructures we present new families of algebraic LDPC codes with benefits over traditionalrandomly constructed regular codes, particularly where small-to-medium length codes areconcerned. We focus in particular on exploring the effect of different design propertieson the code parameters by deriving the rate, minimum distance, girth, and stopping setdistribution of LDPC codes from designs.In the second part of this thesis resolvable designs are employed to create regularLDPC codes free of 4-cycles with the parameter flexibility and decoding performance ofrandomly constructed regular LDPC codes. Employing resolvability greatly extends theclass of LDPC codes that can be algebraically constructed. These codes can offer sig-nificant implementation advantages due to the deterministic structure of their resolutionclasses and in some cases their simple encoding.A shortcoming of LDPC codes is their potentially high encoding complexity, whichis generally quadratic in the code length. Finding computationally efficient encodersis therefore critical for LDPC codes to be considered as serious contenders for futuregenerations of forward error correction devices. As a result the purpose of the last part ofthis thesis is to design codes which have the graph-based properties necessary to performwell with sum-product decoding but which are also cyclic or quasi-cyclic and so can beencoded simply. The main focus is regular codes but we also extend our constructionof quasi-cyclic codes to produce irregular LDPC codes with simple linear-time encodingcircuits.

•Jan 1, 2004•14 citations
This paper develops codes suitable for iterative decoding using the sum-product algorithm. By considering a large class of combinatorial structures, known as partial geometries, we are able to define classes of low-density parity-check (LDPC) codes, which include several previously known families of codes as special cases. The existing range of algebraic LDPC codes is limited, so the new families of codes obtained by generalizing to partial geometries significantly increase the range of choice of available code lengths and rates. We derive bounds on minimum distance, rank, and girth for all the codes from partial geometries, and present constructions and performance results for the classes of partial geometries which have not previously been proposed for use with iterative decoding. We show that these new codes can achieve improved error-correction performance over randomly constructed LDPC codes and, in some cases, achieve this with a significant decrease in decoding complexity.
This work develops codes suitable for iterative decoding using the sum-product algorithm. We consider regular low-density parity-check (LDPC) codes derived from partial geometries, a large class of combinatorial structures which include several of the previously proposed algebraic constructions for LDPC codes as special cases. We derive bounds on minimum distance and rank/sub 2/(H) for codes from partial geometries, and present constructions and performance results for two classes of partial geometries which have not previously been proposed for use 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.
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.
Traditionally, low-density parity-check (LDPC) codes are constructed randomly and it is not clear whether algebraically constructed codes, such as cyclic codes, can compete with the error correction performances of the random codes. We consider in this paper new cyclic low-density parity-check codes decoded with the sum-product algorithm. The cyclic codes we present have sparse parity-check matrices, good minimum distance and girth 6. Using frnite-length analysis and simulation results we show that the most significant benefit of the new codes, in terms of error correction performance, is the linearly dependent rows in their parity-check matrices. Our results suggest that increasing column weight to improve the minimum distance and the minimum stopping set size of the code proves beneficial at low erasure probabilities but adversely affects performance in channels with high erasure probabilities.
Abstract Recent breakthroughs in forward error correction, in the form of low-density parity-check(LDPC) and turbo codes, have seen the promise of near Shannon limit information trans-mission realised. The deterministic construction of good codes, for LDPC codes in par-ticular, is currently the subject of intense interest in the research and development com-munity. This thesis adds to this field, developing methods and supporting theory for thedesign of algebraic LDPC codes using incidence structures from combinatorial designs.The benefits of this approach are guaranteed code properties, parameter flexibility, easeof implementation and reduced encoding complexity.In the first part of this thesis Steiner 2-designs and partial geometries are used toprovide systematic constructions of regular LDPC codes with Tanner graphs free of 4-cyclesandwithdeterministiccodeproperties. Drawingextensivelyfromexistingincidencestructures we present new families of algebraic LDPC codes with benefits over traditionalrandomly constructed regular codes, particularly where small-to-medium length codes areconcerned. We focus in particular on exploring the effect of different design propertieson the code parameters by deriving the rate, minimum distance, girth, and stopping setdistribution of LDPC codes from designs.In the second part of this thesis resolvable designs are employed to create regularLDPC codes free of 4-cycles with the parameter flexibility and decoding performance ofrandomly constructed regular LDPC codes. Employing resolvability greatly extends theclass of LDPC codes that can be algebraically constructed. These codes can offer sig-nificant implementation advantages due to the deterministic structure of their resolutionclasses and in some cases their simple encoding.A shortcoming of LDPC codes is their potentially high encoding complexity, whichis generally quadratic in the code length. Finding computationally efficient encodersis therefore critical for LDPC codes to be considered as serious contenders for futuregenerations of forward error correction devices. As a result the purpose of the last part ofthis thesis is to design codes which have the graph-based properties necessary to performwell with sum-product decoding but which are also cyclic or quasi-cyclic and so can beencoded simply. The main focus is regular codes but we also extend our constructionof quasi-cyclic codes to produce irregular LDPC codes with simple linear-time encodingcircuits.