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

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, Shu Lin, Khaled Abdel-Ghaffar

Published Jul 1, 2004• 29 citations
Publisher

Abstract

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.
DOI
10.1109/lcomm.2004.832776

Related papers

An improved method for counting 6-cycles in low-density parity-check codes

Djamel Slimani, Abdellah Kaddai

Since their rediscovery in the early 1990s, low-density parity-check (LDPC) codes have become the most popular error-correcting codes owing to their excellent performance. An LDPC code is a linear block code that has a sparse parity-check matrix. Cycles in this matrix, particularly short cycles, degrade the performance of such a code. Hence, several methods for counting short cycles in LDPC codes have been proposed, such as Fan?s method to detect 4-cycles, 6- cycles, 8-cycles, and 10-cycles. Unfortunately, this method fails to count all 6- cycles, i.e., ignores numerous 6-cycles, in some given parity-check matrices. In this paper, an improvement of this algorithm is presented that detects all 6-cycles in LDPC codes, as well as in general bipartite graphs. Simulations confirm that the improved method offers the exact number of 6-cycles, and it succeeds in detecting those ignored by Fan?s method.

Serbian Journal of Electrical Engineering•Jan 1, 2023•0 citations

Improved Trellis-Based Algorithm for Locating and Breaking Cycles in Bipartite Graphs with Applications to LDPC Codes

Juane Li, Shu Lin, Khaled Abdel-Ghaffar

LDPC codes are typically decoded using belief propagation decoding algorithms applied to their Tanner graphs. Cycles of short lengths in these graphs, which are bipartite graphs representing parity-check equations of the codes, can negatively impact the performance of the decoder. In this paper, a trellis-based algorithm is presented to locate cycles in bipartite graphs. This algorithm is an improvement in complexity and run-time over the one developed by Lan et al. in 2004. When applied to Tanner graphs of quasi-cyclic LDPC codes, the newly proposed algorithm can exploit the structure of their parity-check matrices to cut the complexity further. Locating cycles in the Tanner graphs of codes allows for eliminating them to increase the girth and thus improve performance.

Information Theory and Applications Workshop (ITA)•Feb 1, 2018•0 citations

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

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

Ivana Djurdjevic, Shu Lin, Khaled Abdel-Ghaffar

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.

IEEE Communications Letters•Apr 1, 2003•12 citations

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

Algorithm for Removal of Short Cycles in Tanner Graphs with Minimum-Hamming-Distance Check

Viktor Ďurček, Michal Kuba, Milan Dado

Two algorithms for removal of short cycles in Tanner graphs of parity-check matrices of binary LDPC codes constructed by Progressive Edge-Growth algorithm are described. These loop-removing algorithms can be used to improve error-correcting performance of existing LDPC codes and achieved results are provided.

ELEKTRO•May 1, 2020•0 citations
Since their rediscovery in the early 1990s, low-density parity-check (LDPC) codes have become the most popular error-correcting codes owing to their excellent performance. An LDPC code is a linear block code that has a sparse parity-check matrix. Cycles in this matrix, particularly short cycles, degrade the performance of such a code. Hence, several methods for counting short cycles in LDPC codes have been proposed, such as Fan?s method to detect 4-cycles, 6- cycles, 8-cycles, and 10-cycles. Unfortunately, this method fails to count all 6- cycles, i.e., ignores numerous 6-cycles, in some given parity-check matrices. In this paper, an improvement of this algorithm is presented that detects all 6-cycles in LDPC codes, as well as in general bipartite graphs. Simulations confirm that the improved method offers the exact number of 6-cycles, and it succeeds in detecting those ignored by Fan?s method.
LDPC codes are typically decoded using belief propagation decoding algorithms applied to their Tanner graphs. Cycles of short lengths in these graphs, which are bipartite graphs representing parity-check equations of the codes, can negatively impact the performance of the decoder. In this paper, a trellis-based algorithm is presented to locate cycles in bipartite graphs. This algorithm is an improvement in complexity and run-time over the one developed by Lan et al. in 2004. When applied to Tanner graphs of quasi-cyclic LDPC codes, the newly proposed algorithm can exploit the structure of their parity-check matrices to cut the complexity further. Locating cycles in the Tanner graphs of codes allows for eliminating them to increase the girth and thus improve performance.
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 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 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.