© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:1605.05123 · IEEE Transactions on Communications

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

Xuan He, Liang Zhou, Junyi Du

Published Sep 18, 2017• 7 citations

Abstract

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.

DOI: 10.1109/tcomm.2017.2753805

Related papers

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

PEG-Like Design of Binary QC-LDPC Codes Based on Detecting and Avoiding Generating Small Cycles

Xuan He, Liang Zhou, Junyi Du

In this paper, we propose a new multi-edge metric-constrained quasi-cyclic progressive edge-growth algorithm (MM-QC-PEGA), which is suitable for constructing both single- and multi-weighted (binary) QC low-density parity-check (LDPC) codes with arbitrary lengths, rates, circulant sizes, and variable node (VN)-degree distributions. The MM-QC-PEGA is able to detect all cyclic-edge-set-minimum-virtual cycles (CMVCs), as it accurately computes the metric value of each CMVC with an a posteriori test. In addition, we propose a new greatest-common-divisor (GCD)-approximation for time efficiently approximating the metric value of a CMVC without a posteriori tests, and propose a new GCD-approximated MM-QC-PEGA (G-MM-QC-PEGA) by using the GCD-approximation to replace the a posteriori test involved in the MM-QC-PEGA. As a result, the G-MM-QC-PEGA is faster than the MM-QC-PEGA, and the CMVCs undetectable to the G-MM-QC-PEGA under multi- and single-weighted QC-LDPC code graphs have minimum lengths of eight and ten, respectively. Moreover, we propose a new masking technique that is efficient in masking the parity-check matrix consisting of an array of arbitrary circulants of the same size. Compared with the several existing works, our proposed algorithms could perform better or comparably in terms of avoiding generating small cycles and error performances. Our proposed algorithms somewhat perfect the works of QC-LDPC code construction.

IEEE Transactions on Communications•Dec 29, 2017•30 citations

Progressive edge-growth Tanner graphs

Xiao-Yu Hu, Evangelos S. Eleftheriou, D.-M. Arnold

We propose a general method for constructing Tanner (1981) graphs with large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms or parameters of the graphs. Encoding of LDPC codes based on the PEG principle is also investigated. We show how to exploit the PEG graph construction to obtain LDPC codes that allow linear time encoding. The advantages of PEG Tanner graphs over randomly constructed graphs are demonstrated by extensive simulation results on code performance.

Globecom•Nov 13, 2002•496 citations

A Low Complexity PEG-like Algorithm to Construct Quasi-Cyclic LDPC Codes

Anthony Gómez-Fonseca, Roxana Smarandache, David G. M. Mitchell

In this paper, we introduce a modified version of the Progressive Edge-Growth (PEG) algorithm that is used to construct the Tanner graphs of quasi-cyclic (QC) low-density parity-check (LDPC) codes having large girth. In our algorithms, we replace certain requirements in the original PEG algorithm, namely the expansion of subgraphs from symbol nodes and the identification of a most distant check node before placing a new edge, by the construction of certain minimal sets, called forbidden sets, that contain the problematic quasi-cyclic constraints that do not let us exceed a given girth. We propose some exponent-selection strategies that are shown to increase the chance of obtaining large girth, and reduce the number of short cycles in the Tanner graph.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 4, 2023•4 citations

Low Complexity Progressive Edge-Growth Algorithm Based on Chinese Remainder Theorem

Xueqin Jiang, Papa Ousmance Thiaw Diagne, Moon Ho Lee +1 more

Progressive edge-growth (PEG) algorithm construction builds the Tanner graph for an LDPC code by establishing edges between the symbol nodes and the check nodes in an edge-by-edge manner and maximizing the local girth in a greedy fashion. This approach is simple but the computational complexity of the PEG algorithm scale as O(nm), where n is the number of symbol nodes and m is the number of check nodes. We deal with this problem by first construct a base LDPC code of length n1with the PEG algorithm and then extend this LDPC code into an LDPC code of length n, where n ≥ n1, via the the chinese remainder theorem (CRT). This method increase the code length of an LDPC code generated with the PEG algorithm, without decreasing its girth. Due to the code length reducing in the PEG construction step, the computational complexity of the whole code construction process is reduced. Furthermore, the proposed algorithm have a potential advantage by storing a small parity-check matrix of a base code and extending it “on-the-fly” in hardware.

IEEE Vehicular Technology Conference•Sep 1, 2012•2 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

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 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.

In this paper, we propose a new multi-edge metric-constrained quasi-cyclic progressive edge-growth algorithm (MM-QC-PEGA), which is suitable for constructing both single- and multi-weighted (binary) QC low-density parity-check (LDPC) codes with arbitrary lengths, rates, circulant sizes, and variable node (VN)-degree distributions. The MM-QC-PEGA is able to detect all cyclic-edge-set-minimum-virtual cycles (CMVCs), as it accurately computes the metric value of each CMVC with an a posteriori test. In addition, we propose a new greatest-common-divisor (GCD)-approximation for time efficiently approximating the metric value of a CMVC without a posteriori tests, and propose a new GCD-approximated MM-QC-PEGA (G-MM-QC-PEGA) by using the GCD-approximation to replace the a posteriori test involved in the MM-QC-PEGA. As a result, the G-MM-QC-PEGA is faster than the MM-QC-PEGA, and the CMVCs undetectable to the G-MM-QC-PEGA under multi- and single-weighted QC-LDPC code graphs have minimum lengths of eight and ten, respectively. Moreover, we propose a new masking technique that is efficient in masking the parity-check matrix consisting of an array of arbitrary circulants of the same size. Compared with the several existing works, our proposed algorithms could perform better or comparably in terms of avoiding generating small cycles and error performances. Our proposed algorithms somewhat perfect the works of QC-LDPC code construction.

We propose a general method for constructing Tanner (1981) graphs with large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms or parameters of the graphs. Encoding of LDPC codes based on the PEG principle is also investigated. We show how to exploit the PEG graph construction to obtain LDPC codes that allow linear time encoding. The advantages of PEG Tanner graphs over randomly constructed graphs are demonstrated by extensive simulation results on code performance.

In this paper, we introduce a modified version of the Progressive Edge-Growth (PEG) algorithm that is used to construct the Tanner graphs of quasi-cyclic (QC) low-density parity-check (LDPC) codes having large girth. In our algorithms, we replace certain requirements in the original PEG algorithm, namely the expansion of subgraphs from symbol nodes and the identification of a most distant check node before placing a new edge, by the construction of certain minimal sets, called forbidden sets, that contain the problematic quasi-cyclic constraints that do not let us exceed a given girth. We propose some exponent-selection strategies that are shown to increase the chance of obtaining large girth, and reduce the number of short cycles in the Tanner graph.

Progressive edge-growth (PEG) algorithm construction builds the Tanner graph for an LDPC code by establishing edges between the symbol nodes and the check nodes in an edge-by-edge manner and maximizing the local girth in a greedy fashion. This approach is simple but the computational complexity of the PEG algorithm scale as O(nm), where n is the number of symbol nodes and m is the number of check nodes. We deal with this problem by first construct a base LDPC code of length n1with the PEG algorithm and then extend this LDPC code into an LDPC code of length n, where n ≥ n1, via the the chinese remainder theorem (CRT). This method increase the code length of an LDPC code generated with the PEG algorithm, without decreasing its girth. Due to the code length reducing in the PEG construction step, the computational complexity of the whole code construction process is reduced. Furthermore, the proposed algorithm have a potential advantage by storing a small parity-check matrix of a base code and extending it “on-the-fly” in hardware.