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

China Communications

Edges metric constrained PEG algorithm for designing LDPC codes

Xin Qin, Yang Chuanchuan, Jiang Xiaotian, Hu Jiazhe, Xinyue Wang, Ziyu Wang

Published Oct 1, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.23919/jcc.fa.2021-0045.202510

Related papers

A New Multi-Edge Metric-Constrained PEG Algorithm for Designing Binary LDPC Code With Improved Cycle-Structure

Xuan He, Liang Zhou, Junyi Du

The progressive edge-growth (PEG) algorithm constructs an edge in each stage to maximize the variable node (VN) of interest's local girth in real time. Thus, this VN's local girths, after more than one edge is added to the current tanner graph (TG) setting, may not be maximized relative to that TG setting. To address this problem, we define the multi-edge local girth and edge-trial, and based on these definitions, propose a new multi-edge metric-constrained PEG algorithm (MM-PEGA) to improve the design at each VN. The MM-PEGA constructs an edge in each stage that, relative to the current TG setting, can potentially maximize the VN of interest's local girth after a certain number (up to the edge-trial) of edges are added to the TG setting. We first analyze the properties of the multi-edge local girth, and then propose an algorithm for calculating the multi-edge local girth. We also propose a method for accelerating the MM-PEGA. Moreover, we generalize the MM-PEGA for improving different PEG-like designs. According to the theoretical analysis, increasing the edge-trial of the MM-PEGA is expected to positively affect the cycle-structure and the error performance of resulting low-density parity-check (LDPC) code. This expectation is verified by simulations.

arXiv:1605.05123•IEEE Transactions on Communications•Sep 18, 2017•7 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

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

Efficient Progressive Edge-Growth Algorithm Based on Chinese Remainder Theorem

Xueqin Jiang, Xiang‐Gen Xia, Moon Ho Lee

Progressive edge-growth (PEG) algorithm construction builds a Tanner graph, or equivalently a parity-check matrix, for an LDPC code by establishing edges between the symbol nodes and the check nodes in an edge-by-edge manner and maximizing the girth in a greedy fashion. This approach is simple but the complexity of the PEG algorithm scale is O(nm), where n is the number of symbol nodes and m is the number of check nodes. We deal with this problem by construct a base matrix Hbof size mb× nbwith the PEG algorithm and simultaneously expand this base matrix into a parity-check matrix H of size mx n via the the Chinese remainder theorem (CRT), where m ≫ mband n ≥ nb. The size of the base matrix is expanded without decreasing the girth. For convenience, the PEG and CRT combined algorithm is referred to as the PEG-CRT algorithm in this paper. Since a smaller matrix is constructed with the PEG algorithm and the complexity of the CRT computation is negligible compared to the PEG algorithm, the complexity of the whole code construction process is reduced. Furthermore, the proposed algorithm has a potential advantage of saving storage space by storing a smaller matrix Hband expanding it to H "on-the-fly" in hardware. The expanded matrix H preserves the important properties of base matrix such as large girth, flexible code rate and low density. The complexity analysis shows that the complexity of the PEG-CRT algorithm does not grow with the code length n. Simulation results show that compared with the PEG LDPC codes of length nb, the expanded PEG-CRT LDPC codes have better bit error rate (BER) performance with the iterative decoding. It is also shown that compared with PEG LDPC codes of length n, which constructed with higher complexities, the PEG-CRT codes have similar BER performance.

IEEE Transactions on Communications•Jan 31, 2014•19 citations

Improved progressive edge-growth algorithm for fast encodable LDPC codes

Xueqin Jiang, Moon Ho Lee, Jinpeng Qi

The progressive edge-growth (PEG) algorithm is known to construct low-density parity-check (LDPC) codes at finite code lengths with large girths by establishing edges between symbol and check nodes in an edge-by-edge manner. The linear-encoding PEG (LPEG) algorithm, a simple variation of the PEG algorithm, can be applied to generate linear time encodable LDPC codes whose m parity bits p1, p2, ..., p m are computed recursively in m steps. In this article, we propose modifications of the LPEG algorithm to construct LDPC codes whose number of encoding steps is independent of the code length. The maximum degree of the symbol nodes in the Tanner graph is denoted by ; The m parity bits of the proposed LDPC codes are divided into subgroups and can be computed in only steps. Since , the number of encoding steps can be significantly reduced. It has also been proved that the PEG codes and the codes proposed in this article have similar lower bound on girth. Simulation results showed that the proposed codes perform very well over the AWGN channel with an iterative decoding.

EURASIP Journal on Wireless Communications and Networking•May 21, 2012•7 citations

An improved algorithm for constructing QC-LDPC codes based on the PEG algorithm

Zhiyong Fan, Weibo Zhang, Xingcheng Liu +1 more

The Progressive edge-growth (PEG) algorithm was proven to be a simple and effective approach in designing Low-density parity-check (LDPC) codes. However, the Tanner graph constructed with the PEG algorithm is non-structured, which leads to random distributions of the positions of 1's in the corresponding parity-check matrix. In this paper, an improved algorithm based on the PEG algorithm for constructing quasi-cyclic (QC) LDPC codes is proposed. The proposed algorithm can eliminate short cycles efficiently and gain low error-floors. What is more important, the proposed QC-LDPC codes construction method is hardware-friendly because of its quasi-cyclic structure. Our simulation results demonstrate that the codes constructed with the proposed algorithm has better performance than the PEG algorithm over the additive white Gaussian noise (AWGN) channel and Rayleigh flat fading channel.

International Conference on Communications and Networking in China (ChinaCom)•Aug 1, 2009•5 citations
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.
The progressive edge-growth (PEG) algorithm constructs an edge in each stage to maximize the variable node (VN) of interest's local girth in real time. Thus, this VN's local girths, after more than one edge is added to the current tanner graph (TG) setting, may not be maximized relative to that TG setting. To address this problem, we define the multi-edge local girth and edge-trial, and based on these definitions, propose a new multi-edge metric-constrained PEG algorithm (MM-PEGA) to improve the design at each VN. The MM-PEGA constructs an edge in each stage that, relative to the current TG setting, can potentially maximize the VN of interest's local girth after a certain number (up to the edge-trial) of edges are added to the TG setting. We first analyze the properties of the multi-edge local girth, and then propose an algorithm for calculating the multi-edge local girth. We also propose a method for accelerating the MM-PEGA. Moreover, we generalize the MM-PEGA for improving different PEG-like designs. According to the theoretical analysis, increasing the edge-trial of the MM-PEGA is expected to positively affect the cycle-structure and the error performance of resulting low-density parity-check (LDPC) code. This expectation is verified by simulations.
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.
Progressive edge-growth (PEG) algorithm construction builds a Tanner graph, or equivalently a parity-check matrix, for an LDPC code by establishing edges between the symbol nodes and the check nodes in an edge-by-edge manner and maximizing the girth in a greedy fashion. This approach is simple but the complexity of the PEG algorithm scale is O(nm), where n is the number of symbol nodes and m is the number of check nodes. We deal with this problem by construct a base matrix Hbof size mb× nbwith the PEG algorithm and simultaneously expand this base matrix into a parity-check matrix H of size mx n via the the Chinese remainder theorem (CRT), where m ≫ mband n ≥ nb. The size of the base matrix is expanded without decreasing the girth. For convenience, the PEG and CRT combined algorithm is referred to as the PEG-CRT algorithm in this paper. Since a smaller matrix is constructed with the PEG algorithm and the complexity of the CRT computation is negligible compared to the PEG algorithm, the complexity of the whole code construction process is reduced. Furthermore, the proposed algorithm has a potential advantage of saving storage space by storing a smaller matrix Hband expanding it to H "on-the-fly" in hardware. The expanded matrix H preserves the important properties of base matrix such as large girth, flexible code rate and low density. The complexity analysis shows that the complexity of the PEG-CRT algorithm does not grow with the code length n. Simulation results show that compared with the PEG LDPC codes of length nb, the expanded PEG-CRT LDPC codes have better bit error rate (BER) performance with the iterative decoding. It is also shown that compared with PEG LDPC codes of length n, which constructed with higher complexities, the PEG-CRT codes have similar BER performance.
The progressive edge-growth (PEG) algorithm is known to construct low-density parity-check (LDPC) codes at finite code lengths with large girths by establishing edges between symbol and check nodes in an edge-by-edge manner. The linear-encoding PEG (LPEG) algorithm, a simple variation of the PEG algorithm, can be applied to generate linear time encodable LDPC codes whose m parity bits p1, p2, ..., p m are computed recursively in m steps. In this article, we propose modifications of the LPEG algorithm to construct LDPC codes whose number of encoding steps is independent of the code length. The maximum degree of the symbol nodes in the Tanner graph is denoted by ; The m parity bits of the proposed LDPC codes are divided into subgroups and can be computed in only steps. Since , the number of encoding steps can be significantly reduced. It has also been proved that the PEG codes and the codes proposed in this article have similar lower bound on girth. Simulation results showed that the proposed codes perform very well over the AWGN channel with an iterative decoding.
The Progressive edge-growth (PEG) algorithm was proven to be a simple and effective approach in designing Low-density parity-check (LDPC) codes. However, the Tanner graph constructed with the PEG algorithm is non-structured, which leads to random distributions of the positions of 1's in the corresponding parity-check matrix. In this paper, an improved algorithm based on the PEG algorithm for constructing quasi-cyclic (QC) LDPC codes is proposed. The proposed algorithm can eliminate short cycles efficiently and gain low error-floors. What is more important, the proposed QC-LDPC codes construction method is hardware-friendly because of its quasi-cyclic structure. Our simulation results demonstrate that the codes constructed with the proposed algorithm has better performance than the PEG algorithm over the additive white Gaussian noise (AWGN) channel and Rayleigh flat fading channel.