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

Information and Electronic Engineering

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

Hong Zhou

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

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.

Related papers

Designing LDPC codes using bit-filling

J. Campello, Dharmendra S. Modha, S. Rajagopalan

Bipartite graphs of bit nodes and parity check nodes arise as Tanner graphs corresponding to low density parity check codes. Given graph parameters such as the number of check nodes, the maximum check-degree, the bit-degree, and the girth, we consider the problem of constructing bipartite graphs with the largest number of bit nodes, that is, the highest rate. We propose a simple-to-implement heuristic bit-filling algorithm for this problem. As a benchmark, our algorithm yields codes better or comparable to those in MacKay (1999).

International Conference on Communications•Nov 13, 2002•70 citations

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

PWG: Progressive Weight-Growth Algorithm for LDPC Codes

Xiangxue Li, Qingji Zheng, Haifeng Qian +2 more

Given specified parameters, the number of check nodes, the expected girth and the variable node degrees, the Progressive Weight-Growth (PWG) algorithm is proposed to generate high rate low-density parity-check (LDPC) codes. Based on the theoretic foundation that is to investigate the girth impact by adding/removing variable nodes and edges of the Tanner graph, the PWG progressively increases column weights of the parity check matrix without violating the constraints defined by the given parameters. The analysis of the computational complexity and the simulation of code performance show that the LDPC codes by the PWG provide better or comparable performance in comparison with LDPC codes by some well-known methods (e.g., Mackay's random constructions, the PEG algorithm, and the bit-filling algorithm).

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2014•0 citations

Extended PEG Algorithm for High Rate LDPC Codes

Zhiheng Zhou, Xiangxue Li, Dong Zheng +2 more

Progressive Edge-Growth(PEG) Algorithm is a good candidate to generate Tanner Graphs with a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner. In this paper, we propose an extended PEG algorithm for constructing Low-Density Parity-Check (LDPC) codes with very high rate when given a lower bound of girth. Simulation results show the bit error rates of constructed LDPC codes with very high rate or large girth.

IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA)•Jan 1, 2009•5 citations

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 novel algorithm of constructing LDPC codes with graph theory

Yan Cui, Xinhui Si, Yanan Shen

There are many algorithms to construct good low-density parity-check (LDPC) code, the most typical algorithms are bit-filling algorithm, randomly construction algorithm, and PEG (progressive edge growth) algorithm. As shown in [1], the error floor of LDPC Code is decreased by using PEG algorithm, but the error correction performance in waterfall region is compromised since a stopping set with small size will form the codeword with small Hamming weight over AWGN [2]. In this paper, we propose a novel algorithm to construct LDPC Codes. In our algorithm, we construct LDPC Code to avoid small girth and small stopping set by detecting the complete associated matrix of check node (defined in this paper) that converted from bipartite graph of LDPC Code based on the graph theory. Simulation shows that the LDPC code constructed by our algorithm has lower error floor than randomly constructed LDPC Code. The performance improvement of our algorithm is 0.1dB at BER of 10-3compared with PEG algorithm.

IEEE Conference on Cybernetics and Intelligent Systems•Sep 1, 2008•2 citations
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.
Bipartite graphs of bit nodes and parity check nodes arise as Tanner graphs corresponding to low density parity check codes. Given graph parameters such as the number of check nodes, the maximum check-degree, the bit-degree, and the girth, we consider the problem of constructing bipartite graphs with the largest number of bit nodes, that is, the highest rate. We propose a simple-to-implement heuristic bit-filling algorithm for this problem. As a benchmark, our algorithm yields codes better or comparable to those in MacKay (1999).
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.
Given specified parameters, the number of check nodes, the expected girth and the variable node degrees, the Progressive Weight-Growth (PWG) algorithm is proposed to generate high rate low-density parity-check (LDPC) codes. Based on the theoretic foundation that is to investigate the girth impact by adding/removing variable nodes and edges of the Tanner graph, the PWG progressively increases column weights of the parity check matrix without violating the constraints defined by the given parameters. The analysis of the computational complexity and the simulation of code performance show that the LDPC codes by the PWG provide better or comparable performance in comparison with LDPC codes by some well-known methods (e.g., Mackay's random constructions, the PEG algorithm, and the bit-filling algorithm).
There are many algorithms to construct good low-density parity-check (LDPC) code, the most typical algorithms are bit-filling algorithm, randomly construction algorithm, and PEG (progressive edge growth) algorithm. As shown in [1], the error floor of LDPC Code is decreased by using PEG algorithm, but the error correction performance in waterfall region is compromised since a stopping set with small size will form the codeword with small Hamming weight over AWGN [2]. In this paper, we propose a novel algorithm to construct LDPC Codes. In our algorithm, we construct LDPC Code to avoid small girth and small stopping set by detecting the complete associated matrix of check node (defined in this paper) that converted from bipartite graph of LDPC Code based on the graph theory. Simulation shows that the LDPC code constructed by our algorithm has lower error floor than randomly constructed LDPC Code. The performance improvement of our algorithm is 0.1dB at BER of 10-3compared with PEG algorithm.