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 Communications Letters

Graph-theoretic construction of low-density parity-check codes

Ivana Djurdjevic, Shu Lin, Khaled Abdel-Ghaffar

Published Apr 1, 2003• 12 citations
Publisher

Abstract

This article presents a graph-theoretic method for constructing low-density parity-check (LDPC) codes from connected graphs without the requirement of large girth. This method is based on finding a set of paths in a connected graph, which satisfies the constraint that any two paths in the set are either disjoint or cross each other at one and only one vertex. Two trellis-based algorithms for finding these paths are devised. Good LDPC codes of practical lengths are constructed and they perform well with iterative decoding.

DOI
10.1109/lcomm.2003.809990

Related papers

Graph-theoretic construction of low-density parity-check codes

Ivana Djurdjevic, Shu Hwa Lin, Khaled Abdel-Ghaffar

This paper presents a novel graph-theoretic method for constructing low-density parity-check (LDPC) codes from connected graphs-without the requirement of large girth. The method is based on finding a set of paths in a connected graph, which satisfies the constraint that any two paths in the set are either disjoint or cross each other at one and only one vertex. Two trellis-based algorithms for finding these paths are devised. Good LDPC codes of practical lengths are constructed and they perform well with iterative decoding.

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2003•1 citation

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

Construction of Low-Density Parity-Check Codes by Superposition

J. Xu, Lei Chen, Lingqi Zeng +2 more

This paper presents a superposition method for constructing low-density parity-check (LDPC) codes. Several classes of structured LDPC codes are constructed. Codes in these classes perform well with iterative decoding, and their Tanner graphs have girth at least six.

IEEE Transactions on Communications•Feb 1, 2005•88 citations

A Trellis-Based Method for Removing Cycles From Bipartite Graphs and Construction of Low Density Parity Check Codes

Longwen Lan, Y.Y. Tai, Lei Chen +2 more

This letter presents a trellis-based iterative method for removing short cycles from bipartite graphs. This method can be used to improve the performance of low density parity check (LDPC) codes or to construct new LDPC codes.

IEEE Communications Letters•Jul 1, 2004•29 citations

A random construction of LDPC codes using a sub-optimal search algorithm

Seif Shebl, Nawal Ahmed El-Fishawy, Atef Abou Elazm +1 more

In this paper, a method for constructing Low-Density Parity-Check (LDPC) codes of good performance in terms of Bit Error Rate (BER) using a computer search algorithm is presented. First, LDPC codes and encoding along with its Tanner graph representation is described. Then, a detailed description of the proposed construction algorithm is given. A Modified Shortest-Path (MSP) Algorithm of lower complexity is applied to obtain a code graph of the desired structure. The proposed algorithm works directly on the parity-check matrix of the LDPC code. The parity-check matrix of the code is constructed column by column subject to the bit-degree and girth constraints. Using the proposed algorithm, both regular and irregular LDPC codes have been constructed. Furthermore, not only have the girth been improved but also the rate of LDPC codes. Finally, by simulation results the constructed codes were shown to perform well over an additive white Gaussian noise (AWGN) channel.

National Radio Science Conference•Jan 1, 2009•1 citation

A new random construction for low-density parity-check codes

Zhonghu Huang, Shen Lianfeng, Zhihui Ye

This paper gives a new random construction for LDPC codes, which uses an iterative algorithm to avoid short cycles in the Tanner graph. The construction method has low complexity and great flexible choice in LDPC code parameters including code length, code rate, least girth of the graph, and the weight of column and row in the parity-check matrix. The method can be applied to the irregular LDPC codes and strict regular LDPC codes. Simulations show that the method performs well with iterative decoding.

International Conference on Communications, Circuits and Systems•Aug 16, 2005•0 citations
This article presents a graph-theoretic method for constructing low-density parity-check (LDPC) codes from connected graphs without the requirement of large girth. This method is based on finding a set of paths in a connected graph, which satisfies the constraint that any two paths in the set are either disjoint or cross each other at one and only one vertex. Two trellis-based algorithms for finding these paths are devised. Good LDPC codes of practical lengths are constructed and they perform well with iterative decoding.
This paper presents a novel graph-theoretic method for constructing low-density parity-check (LDPC) codes from connected graphs-without the requirement of large girth. The method is based on finding a set of paths in a connected graph, which satisfies the constraint that any two paths in the set are either disjoint or cross each other at one and only one vertex. Two trellis-based algorithms for finding these paths are devised. Good LDPC codes of practical lengths are constructed and they perform well with iterative decoding.
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.
In this paper, a method for constructing Low-Density Parity-Check (LDPC) codes of good performance in terms of Bit Error Rate (BER) using a computer search algorithm is presented. First, LDPC codes and encoding along with its Tanner graph representation is described. Then, a detailed description of the proposed construction algorithm is given. A Modified Shortest-Path (MSP) Algorithm of lower complexity is applied to obtain a code graph of the desired structure. The proposed algorithm works directly on the parity-check matrix of the LDPC code. The parity-check matrix of the code is constructed column by column subject to the bit-degree and girth constraints. Using the proposed algorithm, both regular and irregular LDPC codes have been constructed. Furthermore, not only have the girth been improved but also the rate of LDPC codes. Finally, by simulation results the constructed codes were shown to perform well over an additive white Gaussian noise (AWGN) channel.
This paper gives a new random construction for LDPC codes, which uses an iterative algorithm to avoid short cycles in the Tanner graph. The construction method has low complexity and great flexible choice in LDPC code parameters including code length, code rate, least girth of the graph, and the weight of column and row in the parity-check matrix. The method can be applied to the irregular LDPC codes and strict regular LDPC codes. Simulations show that the method performs well with iterative decoding.