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

Globecom

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

Sarah J. Johnson, Steven R. Weller

Published Nov 13, 2002• 58 citations
Publisher

Abstract

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/.

DOI
10.1109/glocom.2001.965562

Related papers

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

Design of 4-cycles Free Short-length LDPC Codes Based on the Kirkman Triple Systems

Dongliang Guo, Yuejiao Feng, Congduan Li

Short-length codes may play a crucial role in delay-sensitive scenarios. Low-density parity-check (LDPC) codes, as a class of Shannon limit approaching codes, perform well with long code length. However, the design of short-length LDPC codes with good performance is still challenging. This paper investigates the construction of short-length LDPC codes based on the combinatorial design theory. Specifically, Kirkman triple systems (KTS), as a type of balanced incomplete block design (BIBD) techniques, are used to construct the parity-check matrices of LDPC codes, which are guaranteed to be 4-cycles free. Some other properties of such designed LDPC codes are also investigated. For instance, a lower bound on the girth, the code rate and minimum code distance. The simulation results show that the designed short-length LDPC codes based on KTS outperform that of randomly constructed ones.

IEEE/CIC International Conference on Communications in China (ICCC)•Aug 11, 2022•0 citations

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

Sarah J. Johnson, S.R. Weller

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.

IEEE Transactions on Communications•Sep 1, 2003•53 citations

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

A systematic construction of irregular low-density parity-check codes from combinatorial designs

S. Sankaranarayanan, Bane V. Vasic, Erozan M. Kurtas

In this paper, we propose an algorithm to design an irregular low-density parity-check (LDPC) code, with a given degree distribution pair, from a combinatorially constructed regular LDPC code. Richardson et al., (2001) showed that long LDPC codes from irregular bipartite graphs with carefully chosen degree distribution pair performed very close to the Shannon capacity limit. It is known that the cyclic or quasicyclic property of regular LDPC codes, constructed from combinatorial designs Colbourn, J et al., (1996), helps to simplify their encoding procedure and also facilitates a memory-efficient storage of the codes. The proposed algorithm involves splitting columns and rows of a regular LDPC code systematically in order to achieve an irregular code with a given distribution pair. Also, this algorithm is a useful alternative to random generation of irregular codes because it enables to exploit the structural properties of the regular code in efficiently storing the resultant irregular code.

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2003•5 citations
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.
Short-length codes may play a crucial role in delay-sensitive scenarios. Low-density parity-check (LDPC) codes, as a class of Shannon limit approaching codes, perform well with long code length. However, the design of short-length LDPC codes with good performance is still challenging. This paper investigates the construction of short-length LDPC codes based on the combinatorial design theory. Specifically, Kirkman triple systems (KTS), as a type of balanced incomplete block design (BIBD) techniques, are used to construct the parity-check matrices of LDPC codes, which are guaranteed to be 4-cycles free. Some other properties of such designed LDPC codes are also investigated. For instance, a lower bound on the girth, the code rate and minimum code distance. The simulation results show that the designed short-length LDPC codes based on KTS outperform that of randomly constructed ones.
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.
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.
In this paper, we propose an algorithm to design an irregular low-density parity-check (LDPC) code, with a given degree distribution pair, from a combinatorially constructed regular LDPC code. Richardson et al., (2001) showed that long LDPC codes from irregular bipartite graphs with carefully chosen degree distribution pair performed very close to the Shannon capacity limit. It is known that the cyclic or quasicyclic property of regular LDPC codes, constructed from combinatorial designs Colbourn, J et al., (1996), helps to simplify their encoding procedure and also facilitates a memory-efficient storage of the codes. The proposed algorithm involves splitting columns and rows of a regular LDPC code systematically in order to achieve an irregular code with a given distribution pair. Also, this algorithm is a useful alternative to random generation of irregular codes because it enables to exploit the structural properties of the regular code in efficiently storing the resultant irregular code.