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

Birkhäuser Basel eBooks

Combinatorially Designed LDPC Codes Using Zech Logarithms and Congruential Sequences

Jing Li

Published Jan 1, 2004• 0 citations
Publisher

Abstract

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.

DOI
10.1007/978-3-0348-7865-4_12

Related papers

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•58 citations

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

Bane V. Vasic, Olgica Milenković

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.

IEEE Transactions on Information Theory•Jun 1, 2004•258 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•73 citations

The Design of Structured Low-Density Parity-Check Codes With Large Girth

Jing Long

This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.

Chinese Journal of Computers•Jan 1, 2007•1 citation

A lattice-based systematic recursive construction of quasi-cyclic LDPC codes

Morteza Esmaeili, Mahdi Tadayon

This paper presents a low-complexity recursive and systematic method to construct good well-structured low-density parity-check (LDPC) codes. The method is based on a recursive application of a partial Kronecker product operation on a given gamma x q, q ges 3 a prime, integer lattice L(gamma x q). The (n - 1)- fold product of L(gamma x q) by itself, denoted Ln(gamma x q), represents a regular quasi-cyclic (QC) LDPC code, denoted (see PDF), of high rate and girth 6. The minimum distance of (see PDF) is equal to that of the core code (see PDF) introduced by L(gamma x q). The support of the minimum weight codewords in (see PDF) are characterized by the support of the same type of codewords in (see PDF). From performance perspective the constructed codes compete with the pseudorandom LDPC codes.

IEEE Transactions on Communications•Oct 1, 2009•10 citations

Performance Analysis and Design of (3,ρ) — Regular Quasi Cyclic LDPC Codes

Xu Xia, Moon Ho Lee, Choi Seung Je +1 more

In this paper we construct a novel family of (3,rho)-regular quasi-cyclic (QC) low-density parity-check (LDPC) codes, derived from permutation theorem for Latin squares, when used over binary input additive white Gaussian noise (BIAWGN) channel. The codes have high code rate, girth absence of 4, good minimum distance, and sparse parity check matrices. They are designed to perform well when iteratively decoding with sum-product decoding algorithm and to allow low complexity encoding

•Dec 10, 2005•0 citations
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.
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/.
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.
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,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.
This paper presents a low-complexity recursive and systematic method to construct good well-structured low-density parity-check (LDPC) codes. The method is based on a recursive application of a partial Kronecker product operation on a given gamma x q, q ges 3 a prime, integer lattice L(gamma x q). The (n - 1)- fold product of L(gamma x q) by itself, denoted Ln(gamma x q), represents a regular quasi-cyclic (QC) LDPC code, denoted (see PDF), of high rate and girth 6. The minimum distance of (see PDF) is equal to that of the core code (see PDF) introduced by L(gamma x q). The support of the minimum weight codewords in (see PDF) are characterized by the support of the same type of codewords in (see PDF). From performance perspective the constructed codes compete with the pseudorandom LDPC codes.