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

International Conference on Software, Telecommunications and Computer Networks (SoftCOM)

Girth conditioning of LDPC codes through modified breadth first search algorithm

Samuele Bandi, Velio Tralli, Andrea Conti, Maddalena Nonato

Published Jan 1, 2007• 0 citations
Publisher

Abstract

This paper proposes a method to improve the performance of a low-density parity-check code, by selectively removing some cycles from the associated bipartite graph. The method is based on a modified version of breadth-first search (BFS) algorithm, that we call modified BFS (MBFS). Throughout the paper we will give a detailed description of the algorithm and analytically study its complexity. Simulation results will show that applying MBFS to a given code leads to significant improvement of its performance.

DOI
10.1109/softcom.2007.4446102

Related papers

On Girth Conditioning for Low-Density Parity-Check Codes

Samuele Bandi, Velio Tralli, Andrea Conti +1 more

Low-density parity-check (LDPC) codes are gaining interest for high data rate applications in both terrestrial and spatial communications. They can be designed and studied through a bipartite graph whose characteristics affect the performance. This paper proposes a low-complexity method to improve the performance of LDPC codes by selectively removing some cycles from the associated bipartite graph. The method is based on a modified version of the breadth first search (BFS) algorithm that we call modified BFS (MBFS), which is applied to find cycles, and a greedy procedure to eliminate them. Throughout the paper we will give a detailed description of the algorithm proposed and analytically study its complexity. Simulation results show that this girth conditioning method applied to some classes of codes, whose structure allows further optimization, can lead to a significative complexity reduction and a performance improvements with respect to other methods.

IEEE Transactions on Communications•Dec 22, 2010•7 citations

An Algorithm for Checking Girth of Low Density Parity Check Codes in Bipartite Graphs

Hong Zhou

The girth is an indication of the quality of Low Density Parity Check(LDPC) Codes. For any given LDPC Codes,quickly checking their girths is of some important significance. An algorithm for quickly checking the girth of LDPC Codes in bipartite graphs is presented. This algorithm can also give out the numbers of the shortest cycles passing through the given check node (or bit node). The testing result of this algorithm implemented in MATLAB shows that,even for large-scale H matrix of LDPC Codes like PEGReg504x1008,it takes only 2.876 s for the algorithm to finish checking.

Information and Electronic Engineering•Jan 1, 2009•0 citations

A Modified Construction Method of Low-Density Parity-Check Codes Based on PEGPC

Jiwei Chen, Zemao Zhao, Jianrong Bao

A modified construction method of LDPC (Low-density Parity-check) codes based on polynomial of cycles of PEG (Progressive-Edge-Growth) is proposed according to reaction on the performance of LDPC codes by polynomial of cycles based on PEG and connectivity of cycles. It can reduce the number of the shortest cycles, increase average local girth and improve connectivity of cycles while deleting short cycles by considering girth of check matrix, number of the shortest cycles and ACE (Approximate Cycle EMD), so that it can improve performance of decoding. At the same time, a construction method of QC-LDPC (quasi-cyclic-LDPC) codes based on ACE and polynomial of cycles of PEG is also proposed to deal with the complexity of implementation on hardware of unstructured codes. Simulation results show that the performance of this code is better than unstructured Mackay code and it is easier for implementation on hardware.

International Conference on Computational and Information Sciences•Oct 1, 2011•1 citation

A modified PEG algorithm for construction of LDPC codes with Polynomial of Cycle

Lei Xiong, Dongping Yao, Yimeng Wu

Progressive Edge-Growth (PEG) algorithm is a novel approach for construction of low-density parity-check (LDPC) codes with large girth. However, PEG algorithm ignores the effect of the number of shortest cycles. In this paper, we propose a modified PEG algorithm with Polynomial of Cycle, which achieves not only large girth, but also minimizes the number of shortest cycles significantly. Simulation results show that our proposed algorithm can improves the performance of LDPC codes.

IEEE International Symposium on Microwave, Antenna, Propagation and EMC Technologies for Wireless Communications•Oct 1, 2009•3 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
This paper proposes a method to improve the performance of a low-density parity-check code, by selectively removing some cycles from the associated bipartite graph. The method is based on a modified version of breadth-first search (BFS) algorithm, that we call modified BFS (MBFS). Throughout the paper we will give a detailed description of the algorithm and analytically study its complexity. Simulation results will show that applying MBFS to a given code leads to significant improvement of its performance.
Low-density parity-check (LDPC) codes are gaining interest for high data rate applications in both terrestrial and spatial communications. They can be designed and studied through a bipartite graph whose characteristics affect the performance. This paper proposes a low-complexity method to improve the performance of LDPC codes by selectively removing some cycles from the associated bipartite graph. The method is based on a modified version of the breadth first search (BFS) algorithm that we call modified BFS (MBFS), which is applied to find cycles, and a greedy procedure to eliminate them. Throughout the paper we will give a detailed description of the algorithm proposed and analytically study its complexity. Simulation results show that this girth conditioning method applied to some classes of codes, whose structure allows further optimization, can lead to a significative complexity reduction and a performance improvements with respect to other methods.
The girth is an indication of the quality of Low Density Parity Check(LDPC) Codes. For any given LDPC Codes,quickly checking their girths is of some important significance. An algorithm for quickly checking the girth of LDPC Codes in bipartite graphs is presented. This algorithm can also give out the numbers of the shortest cycles passing through the given check node (or bit node). The testing result of this algorithm implemented in MATLAB shows that,even for large-scale H matrix of LDPC Codes like PEGReg504x1008,it takes only 2.876 s for the algorithm to finish checking.
A modified construction method of LDPC (Low-density Parity-check) codes based on polynomial of cycles of PEG (Progressive-Edge-Growth) is proposed according to reaction on the performance of LDPC codes by polynomial of cycles based on PEG and connectivity of cycles. It can reduce the number of the shortest cycles, increase average local girth and improve connectivity of cycles while deleting short cycles by considering girth of check matrix, number of the shortest cycles and ACE (Approximate Cycle EMD), so that it can improve performance of decoding. At the same time, a construction method of QC-LDPC (quasi-cyclic-LDPC) codes based on ACE and polynomial of cycles of PEG is also proposed to deal with the complexity of implementation on hardware of unstructured codes. Simulation results show that the performance of this code is better than unstructured Mackay code and it is easier for implementation on hardware.
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.