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

Resolvable 2-designs for regular low-density parity-check codes

Sarah J. Johnson, S.R. Weller

Published Sep 1, 2003• 53 citations
Publisher

Abstract

This paper extends the class of low-density parity-check (LDPC) codes that can be algebraically constructed. We present regular LDPC codes based on resolvable Steiner 2-designs which have Tanner graphs free of four-cycles. The resulting codes are (3, /spl rho/)-regular or (4, /spl rho/)-regular for any value of /spl rho/ and for a flexible choice of code lengths.

DOI
10.1109/tcomm.2003.816946

Related papers

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

Construction of low-density parity-check codes from Kirkman triple systems

Sarah J. Johnson, Steven R. Weller

Gallager introduced low-density parity-check (LDPC) codes in 1962, presenting a construction method to randomly allocate bits in the parity-check matrix subject to certain structural constraints. Since then improvements have been made to Gallager's construction method and some analytic constructions for LDPC codes have been presented. However analytically constructed LDPC codes comprise only a very small subset of possible codes and as a result LDPC codes are still, for the most part, constructed randomly. This paper extends the class of LDPC codes that can be systematically generated by presenting a construction method for regular LDPC codes based on combinatorial designs known as Kirkman triple systems. That is, we construct (3, /spl rho/)-regular codes whose Tanner (1981) graph is free of 4-cycles for any integer /spl rho/.

Globecom•Nov 13, 2002•59 citations

Regular low-density parity-check codes from combinatorial designs

Sarah J. Johnson, Steven R. Weller

Analytically constructed LDPC codes comprise only a very small subset of possible codes and as a result LDPC codes are still, for the most part, constructed randomly. This paper extends the class of LDPC codes that can be systematically generated by presenting a construction method for regular LDPC codes based on combinatorial designs known as Kirkman triple systems. We construct (3, /spl rho/)-regular codes whose Tanner graph is free of 4-cycles for any integer /spl rho/, and examine girth and minimum distance properties of several classes of LDPC codes obtained from combinatorial designs.

IEEE Information Theory Workshop (ITW)•Nov 13, 2002•78 citations

Regular low-density parity-check codes from oval designs

Steven R. Weller, Sarah J. Johnson

This paper presents a construction of low-density parity-check (LDPC) codes based on the incidence matrices of oval designs. The new LDPC codes have regular parity-check matrices and Tanner graphs free of 4-cycles. Like the finite geometry codes, the codes from oval designs have parity-check matrices with a large proportion of linearly dependent rows and can achieve significantly better minimum distances than equivalent length and rate randomly constructed LDPC codes. Further, by exploiting the resolvability of oval designs, and also by employing column splitting, we are able to produce 4-cycle free LDPC codes for a wide range of code rates and lengths while maintaining code regularity. Copyright © 2003 AEI.

European Transactions on Telecommunications•Jan 1, 2003•22 citations

Information Theory Regular low-density parity-check codes from oval designs

Steven R. Weller, Sarah J. Johnson

This paper presents a construction of low-density parity-check (LDPC) codes based on the incidence matrices of oval designs. The new LDPC codes have regular parity-check matrices and Tanner graphs free of 4-cycles. Like the finite geometry codes, the codes from oval designs have parity-check matrices with a large proportion of linearly dependent rows and can achieve significantly better minimum distances than equivalent length and rate randomly constructed LDPC codes. Further, by exploiting the resolvability of oval designs, and also by employing column splitting, we are able to produce 4-cycle free LDPC codes for a wide range of code rates and lengths while maintaining code regularity. Copyright # 2003 AEI. 1.

•Apr 2, 2008•0 citations

A New Construction of Structured Binary Regular LDPC Codes Based on Steiner Systems with Parameter t>2

Hossein Falsafain, Morteza Esmaeili

This paper presents a novel method for constructing structured regular low-density parity-check (LDPC) codes based on a special type of combinatorial designs, known as Steiner systems. This code design approach can be considered as a generalization of the well-known method which uses the point-block incidence matrix of a Steiner 2-design for the code construction. Though the given method can be applied on any Steiner system S(t, k, v), in this paper we focus only on Steiner systems with t ≥ 3. Furthermore, we show that not only a Steiner system (X,B) itself, but also its residual design with respect to an arbitrary point x ∈ X can be employed for code construction. We also present a technique for constructing binary and non-binary QC-LDPC codes from Steiner systems. The Tanner graph of the constructed codes is free of 4-cycles and hence the codes have girth at least six. Simulation results show that the so constructed codes perform well over the AWGN channel with iterative message-passing decoding.

IEEE Transactions on Communications•Oct 17, 2011•11 citations
This paper extends the class of low-density parity-check (LDPC) codes that can be algebraically constructed. We present regular LDPC codes based on resolvable Steiner 2-designs which have Tanner graphs free of four-cycles. The resulting codes are (3, /spl rho/)-regular or (4, /spl rho/)-regular for any value of /spl rho/ and for a flexible choice of code lengths.
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.
Gallager introduced low-density parity-check (LDPC) codes in 1962, presenting a construction method to randomly allocate bits in the parity-check matrix subject to certain structural constraints. Since then improvements have been made to Gallager's construction method and some analytic constructions for LDPC codes have been presented. However analytically constructed LDPC codes comprise only a very small subset of possible codes and as a result LDPC codes are still, for the most part, constructed randomly. This paper extends the class of LDPC codes that can be systematically generated by presenting a construction method for regular LDPC codes based on combinatorial designs known as Kirkman triple systems. That is, we construct (3, /spl rho/)-regular codes whose Tanner (1981) graph is free of 4-cycles for any integer /spl rho/.
Analytically constructed LDPC codes comprise only a very small subset of possible codes and as a result LDPC codes are still, for the most part, constructed randomly. This paper extends the class of LDPC codes that can be systematically generated by presenting a construction method for regular LDPC codes based on combinatorial designs known as Kirkman triple systems. We construct (3, /spl rho/)-regular codes whose Tanner graph is free of 4-cycles for any integer /spl rho/, and examine girth and minimum distance properties of several classes of LDPC codes obtained from combinatorial designs.
This paper presents a construction of low-density parity-check (LDPC) codes based on the incidence matrices of oval designs. The new LDPC codes have regular parity-check matrices and Tanner graphs free of 4-cycles. Like the finite geometry codes, the codes from oval designs have parity-check matrices with a large proportion of linearly dependent rows and can achieve significantly better minimum distances than equivalent length and rate randomly constructed LDPC codes. Further, by exploiting the resolvability of oval designs, and also by employing column splitting, we are able to produce 4-cycle free LDPC codes for a wide range of code rates and lengths while maintaining code regularity. Copyright © 2003 AEI.
This paper presents a construction of low-density parity-check (LDPC) codes based on the incidence matrices of oval designs. The new LDPC codes have regular parity-check matrices and Tanner graphs free of 4-cycles. Like the finite geometry codes, the codes from oval designs have parity-check matrices with a large proportion of linearly dependent rows and can achieve significantly better minimum distances than equivalent length and rate randomly constructed LDPC codes. Further, by exploiting the resolvability of oval designs, and also by employing column splitting, we are able to produce 4-cycle free LDPC codes for a wide range of code rates and lengths while maintaining code regularity. Copyright # 2003 AEI. 1.
This paper presents a novel method for constructing structured regular low-density parity-check (LDPC) codes based on a special type of combinatorial designs, known as Steiner systems. This code design approach can be considered as a generalization of the well-known method which uses the point-block incidence matrix of a Steiner 2-design for the code construction. Though the given method can be applied on any Steiner system S(t, k, v), in this paper we focus only on Steiner systems with t ≥ 3. Furthermore, we show that not only a Steiner system (X,B) itself, but also its residual design with respect to an arbitrary point x ∈ X can be employed for code construction. We also present a technique for constructing binary and non-binary QC-LDPC codes from Steiner systems. The Tanner graph of the constructed codes is free of 4-cycles and hence the codes have girth at least six. Simulation results show that the so constructed codes perform well over the AWGN channel with iterative message-passing decoding.