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

Advances in Electrical and Computer Engineering

A PEG Construction of LDPC Codes Based on the Betweenness Centrality Metric

I. BHURTAH-SEEWOOSUNGKUR, Pierre Clarel Catherine, K. M. S. Soyjaudah

Published Jan 1, 2016• 2 citations
Publisher

Abstract

Progressive Edge Growth (PEG) constructions are usually based on optimizing the distance metric by using various methods. In this work however, the distance metric is replaced by a different one, namely the betweenness centrality metric, which was shown to enhance routing performance in wireless mesh networks. A new type of PEG construction for Low-Density Parity-Check (LDPC) codes is introduced based on the betweenness centrality metric borrowed from social networks terminology given that the bipartite graph describing the LDPC is analogous to a network of nodes. The algorithm is very efficient in filling edges on the bipartite graph by adding its connections in an edge-by-edge manner. The smallest graph size the new code could construct surpasses those obtained from a modified PEG algorithm - the RandPEG algorithm. To the best of the authors' knowledge, this paper produces the best regular LDPC column-weight two graphs. In addition, the technique proves to be competitive in terms of error-correcting performance. When compared to MacKay, PEG and other recent modified-PEG codes, the algorithm gives better performance over high SNR due to its particular edge and local graph properties.

DOI
10.4316/aece.2016.02012

Related papers

An Improvement of the PEG Algorithm for LDPC Codes in the Waterfall Region

Gerd Richter

There exist many different algorithms to construct good low-density parity-check (LDPC) codes. To maximize the girth of the bipartite graph, which represents the LDPC code, the progressive edge-growth (PEG) algorithm was introduced. This construction methods leads for irregular LDPC codes to a lower error floor, but also to a performance loss in the waterfall region compared with randomly constructed LDPC codes. In this paper, we describe a modification of the PEG algorithm that improves the performance in the waterfall region. Furthermore, this modified PEG algorithm yields codes with lower error floors and a slightly better performance in the waterfall region than randomly constructed LDPC codes

IEEE EUROCON - International Conference on Computer as a Tool (EUROCON)•Jan 1, 2005•9 citations

New PEG algorithm with low error floor for construction of irregular LDPC codes

Feijin Shi, Shuangshuang Han

The progressive-edge-growth (PEG) algorithm for constructing Tanner graphs with large girth by progressively establishing edges/connections between symbol nodes and check nodes in an edge-by-edge way is highly known to construct low-density parity-check (LDPC) codes at short block lengths for achieving good performance. This paper proposed an improved PEG construction for irregular codes, which heuristically selects good codes from random graphs for short block lengths. The simulation results are given to demonstrate that the proposed algorithm gians better BER performance for high signal-to-noise (SNR) ratios without performance loss for low-SNR region, i.e. low error floor.

IEEE International Conference on Computer and Communications (ICCC)•Oct 1, 2015•1 citation

A density-based progressive edge-growth matrix creation technique for LDPC codes

Pierre Clarel Catherine, K. M. S. Soyjaudah

In this work, we propose a method specially suited for creating high rate LDPC codes. The technique employed adds the connections of the bipartite graph on an edge-by-edge basis. Unlike other progressive edge-growth methods however, we favor the use of a density metric over the conventional distance metric for the node selection process. As benchmark, the algorithm yield codes of higher rates than those obtained from bit-filling algorithms. Because of its efficient approach in filling edges on the bipartite graph however, the algorithm may also be used to produce codes (of various rates) that are very competitive in terms of error-correcting performance.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2010•0 citations

Edges metric constrained PEG algorithm for designing LDPC codes

Xin Qin, Yang Chuanchuan, Jiang Xiaotian +3 more

The progressive edge-growth (PEG) algorithm is a general method to construct short low-density parity-check (LDPC) codes and it is a greedy method to place each edge with large girths. In order to improve the performance of LDPC codes, many improved PEG (IPEG) algorithms employ multi metrics to select surviving edges in turn. In this paper, the proposed edges metric (EM) based on message-passing algorithm (MPA) is introduced to PEG algorithm and the proposed EM constrained PEG (EM-PEG) algorithm mainly considers the independence of message passing from different nodes in Tanner graph. The numerical results show that our EM-PEG algorithm brings better bit error rate (BER) performance gains to LDPC codes than the traditional PEG algorithm and the powerful multi-edge multi-metric constrained PEG algorithm (MM-PEGA) proposed recently. In addition, the multi-edge EM constrained PEG (M-EM-PEG) algorithm which adopts multi-edge EM may further improve the BER performance.

China Communications•Oct 1, 2025•1 citation

Investigation of random-structure regular LDPC codes construction based on progressive edge-growth and algorithms for removal of short cycles

Viktor Ďurček, Michal Kuba, Milan Dado

This paper investigates the construction of random-structure LDPC (low-density parity-check) codes using Progressive Edge-Growth (PEG) algorithm and two proposed algorithms for removing short cycles (CB1 and CB2 algorithm; CB stands for Cycle Break). Progressive Edge-Growth is an algorithm for computer-based design of random-structure LDPC codes, the role of which is to generate a Tanner graph (a bipartite graph, which represents a parity-check matrix of an error-correcting channel code) with as few short cycles as possible. Short cycles, especially the shortest ones with a length of 4 edges, in Tanner graphs of LDPC codes can degrade the performance of their decoding algorithm, because after certain number of decoding iterations, the information sent through its edges is no longer independent. The main contribution of this paper is the unique approach to the process of removing short cycles in the form of CB2 algorithm, which erases edges from the code's parity-check matrix without decreasing the minimum Hamming distance of the code. The two cycle-removing algorithms can be used to improve the error-correcting performance of PEG-generated (or any other) LDPC codes and achieved results are provided. All these algorithms were used to create a PEG LDPC code which rivals the best-known PEG-generated LDPC code with similar parameters provided by one of the founders of LDPC codes. The methods for generating the mentioned error-correcting codes are described along with simulations which compare the error-correcting performance of the original codes generated by the PEG algorithm, the PEG codes processed by either CB1 or CB2 algorithm and also external PEG code published by one of the founders of LDPC codes

Eastern-European Journal of Enterprise Technologies•Aug 31, 2021•1 citation

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
Progressive Edge Growth (PEG) constructions are usually based on optimizing the distance metric by using various methods. In this work however, the distance metric is replaced by a different one, namely the betweenness centrality metric, which was shown to enhance routing performance in wireless mesh networks. A new type of PEG construction for Low-Density Parity-Check (LDPC) codes is introduced based on the betweenness centrality metric borrowed from social networks terminology given that the bipartite graph describing the LDPC is analogous to a network of nodes. The algorithm is very efficient in filling edges on the bipartite graph by adding its connections in an edge-by-edge manner. The smallest graph size the new code could construct surpasses those obtained from a modified PEG algorithm - the RandPEG algorithm. To the best of the authors' knowledge, this paper produces the best regular LDPC column-weight two graphs. In addition, the technique proves to be competitive in terms of error-correcting performance. When compared to MacKay, PEG and other recent modified-PEG codes, the algorithm gives better performance over high SNR due to its particular edge and local graph properties.
There exist many different algorithms to construct good low-density parity-check (LDPC) codes. To maximize the girth of the bipartite graph, which represents the LDPC code, the progressive edge-growth (PEG) algorithm was introduced. This construction methods leads for irregular LDPC codes to a lower error floor, but also to a performance loss in the waterfall region compared with randomly constructed LDPC codes. In this paper, we describe a modification of the PEG algorithm that improves the performance in the waterfall region. Furthermore, this modified PEG algorithm yields codes with lower error floors and a slightly better performance in the waterfall region than randomly constructed LDPC codes
The progressive-edge-growth (PEG) algorithm for constructing Tanner graphs with large girth by progressively establishing edges/connections between symbol nodes and check nodes in an edge-by-edge way is highly known to construct low-density parity-check (LDPC) codes at short block lengths for achieving good performance. This paper proposed an improved PEG construction for irregular codes, which heuristically selects good codes from random graphs for short block lengths. The simulation results are given to demonstrate that the proposed algorithm gians better BER performance for high signal-to-noise (SNR) ratios without performance loss for low-SNR region, i.e. low error floor.
In this work, we propose a method specially suited for creating high rate LDPC codes. The technique employed adds the connections of the bipartite graph on an edge-by-edge basis. Unlike other progressive edge-growth methods however, we favor the use of a density metric over the conventional distance metric for the node selection process. As benchmark, the algorithm yield codes of higher rates than those obtained from bit-filling algorithms. Because of its efficient approach in filling edges on the bipartite graph however, the algorithm may also be used to produce codes (of various rates) that are very competitive in terms of error-correcting performance.
The progressive edge-growth (PEG) algorithm is a general method to construct short low-density parity-check (LDPC) codes and it is a greedy method to place each edge with large girths. In order to improve the performance of LDPC codes, many improved PEG (IPEG) algorithms employ multi metrics to select surviving edges in turn. In this paper, the proposed edges metric (EM) based on message-passing algorithm (MPA) is introduced to PEG algorithm and the proposed EM constrained PEG (EM-PEG) algorithm mainly considers the independence of message passing from different nodes in Tanner graph. The numerical results show that our EM-PEG algorithm brings better bit error rate (BER) performance gains to LDPC codes than the traditional PEG algorithm and the powerful multi-edge multi-metric constrained PEG algorithm (MM-PEGA) proposed recently. In addition, the multi-edge EM constrained PEG (M-EM-PEG) algorithm which adopts multi-edge EM may further improve the BER performance.
This paper investigates the construction of random-structure LDPC (low-density parity-check) codes using Progressive Edge-Growth (PEG) algorithm and two proposed algorithms for removing short cycles (CB1 and CB2 algorithm; CB stands for Cycle Break). Progressive Edge-Growth is an algorithm for computer-based design of random-structure LDPC codes, the role of which is to generate a Tanner graph (a bipartite graph, which represents a parity-check matrix of an error-correcting channel code) with as few short cycles as possible. Short cycles, especially the shortest ones with a length of 4 edges, in Tanner graphs of LDPC codes can degrade the performance of their decoding algorithm, because after certain number of decoding iterations, the information sent through its edges is no longer independent. The main contribution of this paper is the unique approach to the process of removing short cycles in the form of CB2 algorithm, which erases edges from the code's parity-check matrix without decreasing the minimum Hamming distance of the code. The two cycle-removing algorithms can be used to improve the error-correcting performance of PEG-generated (or any other) LDPC codes and achieved results are provided. All these algorithms were used to create a PEG LDPC code which rivals the best-known PEG-generated LDPC code with similar parameters provided by one of the founders of LDPC codes. The methods for generating the mentioned error-correcting codes are described along with simulations which compare the error-correcting performance of the original codes generated by the PEG algorithm, the PEG codes processed by either CB1 or CB2 algorithm and also external PEG code published by one of the founders of LDPC codes
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).