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 Information Theory

Combinatorial Constructions of Low-Density Parity-Check Codes for Iterative Decoding

Bane V. Vasic, Olgica Milenković

Published Jun 1, 2004• 263 citations
Publisher

Abstract

This paper introduces several new combinatorial constructions of low-density parity-check (LDPC) codes, in contrast to the prevalent practice of using long, random-like codes. The proposed codes are well structured, and unlike random codes can lend themselves to a very low-complexity implementation. Constructions of regular Gallager codes based on cyclic difference families, cycle-invariant difference sets, and affine 1-configurations are introduced. Several constructions of difference families used for code design are presented, as well as bounds on the minimal distance of the codes based on the concept of a generalized Pasch configuration.

DOI
10.1109/tit.2004.828066

Related papers

Combinatorially Designed LDPC Codes Using Zech Logarithms and Congruential Sequences

Jing Li

We investigate a systematic construction of regular low density parity check (LDPC) codes based on (γργ-1, ργ, ρ, γ{0,1}) combinatorial designs. The proposed (γ,ρ) regular LDPC ensemble has rate $${\left( {1 - \tfrac{1}{\rho }} \right)^\gamma }$$ girth ≥2γ+1, and exists for all γ≥2. The codes are a subset of Gallager’s random ensemble, but contains a good combination of structure and (pseudo)randomness. In particular, the simple case of γ=2 results in a class of codes that are high-rate, systematic, quasi-cyclic, linear-time encodable and decodable, and free of length-4 and length-6 cycles. Analysis on distance spectrum shows that they are better than the Gallager ensemble of the same parameters. Simulation of the proposed codes on intersymbol interference channels show that they perform comparably to random LDPC codes. Unlike random codes, the proposed structured LDPC codes can lend themselves to a low-complexity implementation for high-speed applications.

Birkhäuser Basel eBooks•Jan 1, 2004•0 citations

A Class of Improved Low-Density Parity-Check Codes Constructed Based on Gallager's Form

Guangen Wu, Pinyi Ren

Focused on the problem that short cycles degrade the iterative decoding performance of finite length LDPC, a class of improved low density parity check (LDPC) codes constructed based on Gallager's form is designed. On the basis of keeping down the basic form of Gallager's construction, a quasi-cyclic form is used, then the new codes are free of cycles of length 4 and have good minimum distance. Simulation results demonstrated that the improved codes are better than Gallager's codes when block length is small

International Conference on Communications, Circuits and Systems•Jun 1, 2006•0 citations

Combinatorial Construction of Low-Density Parity-Check Codes for Short Block Length and High Rate Applications

Suquan Ding, Zhixing Yang, Jian Song +2 more

This paper presents a method to construct regular low-density parity-check (LDPC) codes of short block length and high rate based on a special type of combinatoric designs, i.e., balanced incomplete block designs (BIBDs) with lambda = 2 whose construction are based on cyclic difference families. Although the Tanner graph of the codes constructed contains some cycles of length 4, simulation results show that they perform well under belief propagation (BP) decoding. Further, these codes are quasi-cyclic (QC) codes and hence can be encoded efficiently

International Conference on Wireless Communications, Networking and Mobile Computing•Sep 1, 2006•1 citation

Quasi-cyclic LDPC codes from difference families

Sarah J. Johnson, Steven R. Weller

Abstract — We consider in this paper regular and nearly regular quasi-cyclic low-density parity-check (LDPC) codes, derived from families of dif-ference sets. The codes have girth at least 6, and sparse parity-check matrices. They are designed to perform well when iteratively decoded with the sum-product decoding algorithm and to allow low complexity encoding. I.

•Jan 1, 2002•16 citations

Construction of Low-density Parity-check Codes Based on Cyclic Difference Sets

Guo Zhi-rong

This paper proposes a method to construct Quasi-Cyclic Low-Density Parity-Check(QC-LDPC) codes based on Cyclic Difference Sets(CDS) of combinatory. The constructed regular QC-LDPC codes are free of 4-cycles and with low complexity shift register encoding. Simulations results show that the constructed LDPC codes perform well under sum-product decoding algorithm.

Jisuanji gongcheng•Jan 1, 2010•0 citations

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 introduces several new combinatorial constructions of low-density parity-check (LDPC) codes, in contrast to the prevalent practice of using long, random-like codes. The proposed codes are well structured, and unlike random codes can lend themselves to a very low-complexity implementation. Constructions of regular Gallager codes based on cyclic difference families, cycle-invariant difference sets, and affine 1-configurations are introduced. Several constructions of difference families used for code design are presented, as well as bounds on the minimal distance of the codes based on the concept of a generalized Pasch configuration.
We investigate a systematic construction of regular low density parity check (LDPC) codes based on (γργ-1, ργ, ρ, γ{0,1}) combinatorial designs. The proposed (γ,ρ) regular LDPC ensemble has rate (1−1ρ)γ{\left( {1 - \tfrac{1}{\rho }} \right)^\gamma }(1−ρ1​)γ girth ≥2γ+1, and exists for all γ≥2. The codes are a subset of Gallager’s random ensemble, but contains a good combination of structure and (pseudo)randomness. In particular, the simple case of γ=2 results in a class of codes that are high-rate, systematic, quasi-cyclic, linear-time encodable and decodable, and free of length-4 and length-6 cycles. Analysis on distance spectrum shows that they are better than the Gallager ensemble of the same parameters. Simulation of the proposed codes on intersymbol interference channels show that they perform comparably to random LDPC codes. Unlike random codes, the proposed structured LDPC codes can lend themselves to a low-complexity implementation for high-speed applications.
Focused on the problem that short cycles degrade the iterative decoding performance of finite length LDPC, a class of improved low density parity check (LDPC) codes constructed based on Gallager's form is designed. On the basis of keeping down the basic form of Gallager's construction, a quasi-cyclic form is used, then the new codes are free of cycles of length 4 and have good minimum distance. Simulation results demonstrated that the improved codes are better than Gallager's codes when block length is small
This paper presents a method to construct regular low-density parity-check (LDPC) codes of short block length and high rate based on a special type of combinatoric designs, i.e., balanced incomplete block designs (BIBDs) with lambda = 2 whose construction are based on cyclic difference families. Although the Tanner graph of the codes constructed contains some cycles of length 4, simulation results show that they perform well under belief propagation (BP) decoding. Further, these codes are quasi-cyclic (QC) codes and hence can be encoded efficiently
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.