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

IEEE Access

The Cycle-Concentrating PEG Algorithm for Protograph Generalized LDPC Codes

Dae-Young Yun, Jae-Won Kim, Hee-Youl Kwak, Jong‐Seon No

Published Jan 1, 2023• 3 citations
Publisher

Abstract

In this paper, we propose the cycle-concentrating progressive edge growth (CC-PEG) algorithm for lifting protograph generalized low-density parity-check (GLDPC) codes. In GLDPC codes,undoped variable nodes(VNs) that are not connected to generalized constraint (GC) nodes are more vulnerable to channel errors thandoped VNsprotected by GC nodes. We observe that among GLDPC codes sharing the same protograph structure, codes with fewer local cycles at undoped VNs have better decoding performances. Inspired by this observation, the CC-PEG algorithm is proposed to concentrate local cycles at doped VNs and avoid local cycles at vulnerable undoped VNs during the lifting process. Specifically, the CC-PEG algorithm first collects edges that result in the maximumundoped girth, defined as the length of the shortest cycle containing undoped VNs. Following this, the CC-PEG algorithm selects the edge with the lowestconcentrated cycle metric. Consequently, the lifted codes exhibit asymmetric cycle distributions concentrated around robust doped VNs. Simulation results for various protographs show that the CC-PEG algorithm achieves a performance gain of up to 20 times lower frame error rate compared to conventional lifting algorithms.

DOI
10.1109/access.2023.3284314

Related papers

The Effect of PEG-Lifting Order on the Performance of Protograph GLDPC Codes

Dae-Young Yun, Jae-Won Kim, Jong‐Seon No

Generalized low density parity check (GLDPC) codes can be constructed by replacing some single parity check (SPC) nodes in LDPC codes with generalized constraint (GC) nodes. GC nodes are defined by component codes whose minimum distance is larger than that of SPC nodes. Therefore, the variable nodes (VNs) connected to GC nodes, which are called doped VNs, are more protected than the undoped VNs. Due to this effect, we observe that the doped VNs are more robust to local cycles. The distribution of local cycles is affected by the processing VN order of the progressive edge growth (PEG) algorithm, where the latter processed (lifted) VNs tend to have more local cycles. Based on the property of doped VNs and the PEG algorithm, we show that a tangible performance gain is achieved by placing the doped VNs in the latter order of the PEG algorithm compared to the former order. The performance gain is shown with a well known GLDPC code in the literature and over both the binary erasure channel and addictive white Gaussian noise channel.

Asia-Pacific Conference on Communications (APCC)•Oct 19, 2022•2 citations

Modified CC-PEG Algorithm for Protograph-Based QC-LDPC Codes Over Non-Uniform Channel

H. Lee, Jae-Won Kim

In this paper, we propose the modified cycle-concentrating progressive-edge-growth (CC-PEG) algorithm for lifting protograph-based quasi-cyclic low-density parity-check (QC-LDPC) codes over the non-uniform additive white Gaussian noise (AWGN) channel. By introducing various selection criteria for shift values based on the non-uniform channel characteristics, we improve the decoding performances of lifted LDPC codes. From numerous simulation results, we demonstrate that each selection criterion is effective for the performance improvement and the modified CC-PEG algorithm outperforms the conventional lifting methods over the non-uniform AWGN channel. Furthermore, we analyze these simulation results based on some metrics such as the girth, number of cycles, and approximate cycle extrinsic message degree (ACE).

IEEE Access•Jan 1, 2024•3 citations

Constructing Large Girth QC Protograph LDPC Codes Based on PSD-PEG Algorithm

Xueqin Jiang, Han Hai, Hui-Ming Wang +1 more

For a given base graph, the lifted graph can be obtained by a copy-and-permute procedure. If the permutation is cyclic, the lifted graph corresponds to a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code. The girth of the QC protograph LDPC code is determined by the girth of the base graph and the permutation shifts. In this paper, we first derive a lower bound on the lifting degree to achieve a large girth lifted graph. Then, motivated by the cycle searching and girth maximizing features of the progressive edge-growth (PEG) algorithm, we introduce the permutation shifts determining (PSD) PEG algorithm, which can construct large girth base graph and determine the optimal permutation shifts, simultaneously. It is shown that the computational complexity of PSD-PEG algorithm is much lower than that of the PEG algorithm and the PEG-QC algorithm for the same codeword length. Furthermore, we show that the PSD-PEG algorithm can also be used to construct nonbinary QC protograph LDPC codes without low weight codes. Simulation results show that the binary and nonbinary QC protograph LDPC codes constructed by the PSD-PEG algorithm have good bit error rate performance and frame error rate performance over the additive white Gaussian noise channel.

IEEE Access•Jan 1, 2017•23 citations

1Design of Multiple-Edge Protographs for QC LDPC Codes Avoiding Short Inevitable Cycles

Hosung Park Seokbeom Hong

There have been lots of efforts on the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with large girth. However, most of them are focused on protographs with single edges and little research has been done for the construction of QC LDPC codes lifted from protographs with multiple edges. Compared to single-edge protographs, multiple-edge protographs have benefits such that QC LDPC codes lifted from them can potentially have larger minimum Hamming distance. In this paper, all subgraph patterns of multiple-edge protographs, which prevent QC LDPC codes from having large girth by inducing inevitable cycles, are fully investigated based on graph-theoretic approach. By using combinatorial designs, a systematic construction method of multiple-edge protographs is proposed for regular QC LDPC codes with girth at least 12 and also other method is proposed for regular QC LDPC codes with girth at least 14. A construction algorithm of QC LDPC codes by lifting multiple-edge protographs is proposed and it is shown that the resulting QC LDPC codes have larger upper bounds on the minimum Hamming distance than those lifted from single-edge protographs. Simulation results are provided to compare the performance of the proposed QC LDPC codes, the progressive edge-growth (PEG) LDPC codes, and the PEG QC LDPC codes.

•Jan 1, 2014•26 citations

Modified PEG algorithm for large girth Quasi-cyclic protograph LDPC codes

Xueqin Jiang, Moon Ho Lee, Hui-Ming Wang +2 more

For a given base graph, the protograph can be obtained by a copy-and-permute procedure. If the permutation is cyclic, the protograph corresponds to a quasi-cyclic (QC) protograph LDPC code. The girth of the QC protograph LDPC code is determined by the girth of the base graph and the permutation shifts. Progressive edge-growth (PEG) construction builds up a Tanner graph, or equivalently a parity-check matrix, for an LDPC code by maximizing the local girth at symbol nodes in a greedy algorithm. In this paper, we introduce a modified version of the PEG algorithm which can construct large girth base graph and determine the optimal permutation shifts, simultaneously, for QC protograph LDPC codes. Simulation results show that the QC protograph LDPC codes constructed by the proposed modified PEG algorithm have good frame error rate (FER) performance over the AWGN channel.

2012 International Conference on Computing, Networking and Communications (ICNC)•Feb 1, 2016•5 citations

Anti-burst PEG Algorithm for P-LDPC Codes with Short-to-Medium Length

Li Juan DENG, Zhiping Shi, Yanxia Li +1 more

Protograph low-density parity-check (P-LDPC) codes are widely researched in communication systems due to the simple encoder structure and high-speed iterative decoding implementation. The key factors to affect the performance of P-LDPC codes are the base matrix and the lifting method. This paper focuses on the lifting method of P-LDPC codes with short-to-medium length over burst-error channels. An improved anti-burst protograph progressive edge-growth (IPPEG) algorithm based on edge constraints is proposed to improve the bit error rate (BER) performance. Simulation results show that the proposed IPPEG has better burst-resistance performance than the traditional PEG based lifting algorithm (PPEG) with or without random interleaver; additionally, on the premising of correctly decoding, more coding gains of IPPEG can be achieved with condition of larger channel transition probability, shorter code length or smaller coding rate.

IEEE International Conference on Communication Technology (ICCT)•Oct 1, 2018•1 citation
In this paper, we propose the cycle-concentrating progressive edge growth (CC-PEG) algorithm for lifting protograph generalized low-density parity-check (GLDPC) codes. In GLDPC codes,undoped variable nodes(VNs) that are not connected to generalized constraint (GC) nodes are more vulnerable to channel errors thandoped VNsprotected by GC nodes. We observe that among GLDPC codes sharing the same protograph structure, codes with fewer local cycles at undoped VNs have better decoding performances. Inspired by this observation, the CC-PEG algorithm is proposed to concentrate local cycles at doped VNs and avoid local cycles at vulnerable undoped VNs during the lifting process. Specifically, the CC-PEG algorithm first collects edges that result in the maximumundoped girth, defined as the length of the shortest cycle containing undoped VNs. Following this, the CC-PEG algorithm selects the edge with the lowestconcentrated cycle metric. Consequently, the lifted codes exhibit asymmetric cycle distributions concentrated around robust doped VNs. Simulation results for various protographs show that the CC-PEG algorithm achieves a performance gain of up to 20 times lower frame error rate compared to conventional lifting algorithms.
Generalized low density parity check (GLDPC) codes can be constructed by replacing some single parity check (SPC) nodes in LDPC codes with generalized constraint (GC) nodes. GC nodes are defined by component codes whose minimum distance is larger than that of SPC nodes. Therefore, the variable nodes (VNs) connected to GC nodes, which are called doped VNs, are more protected than the undoped VNs. Due to this effect, we observe that the doped VNs are more robust to local cycles. The distribution of local cycles is affected by the processing VN order of the progressive edge growth (PEG) algorithm, where the latter processed (lifted) VNs tend to have more local cycles. Based on the property of doped VNs and the PEG algorithm, we show that a tangible performance gain is achieved by placing the doped VNs in the latter order of the PEG algorithm compared to the former order. The performance gain is shown with a well known GLDPC code in the literature and over both the binary erasure channel and addictive white Gaussian noise channel.
In this paper, we propose the modified cycle-concentrating progressive-edge-growth (CC-PEG) algorithm for lifting protograph-based quasi-cyclic low-density parity-check (QC-LDPC) codes over the non-uniform additive white Gaussian noise (AWGN) channel. By introducing various selection criteria for shift values based on the non-uniform channel characteristics, we improve the decoding performances of lifted LDPC codes. From numerous simulation results, we demonstrate that each selection criterion is effective for the performance improvement and the modified CC-PEG algorithm outperforms the conventional lifting methods over the non-uniform AWGN channel. Furthermore, we analyze these simulation results based on some metrics such as the girth, number of cycles, and approximate cycle extrinsic message degree (ACE).
For a given base graph, the lifted graph can be obtained by a copy-and-permute procedure. If the permutation is cyclic, the lifted graph corresponds to a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code. The girth of the QC protograph LDPC code is determined by the girth of the base graph and the permutation shifts. In this paper, we first derive a lower bound on the lifting degree to achieve a large girth lifted graph. Then, motivated by the cycle searching and girth maximizing features of the progressive edge-growth (PEG) algorithm, we introduce the permutation shifts determining (PSD) PEG algorithm, which can construct large girth base graph and determine the optimal permutation shifts, simultaneously. It is shown that the computational complexity of PSD-PEG algorithm is much lower than that of the PEG algorithm and the PEG-QC algorithm for the same codeword length. Furthermore, we show that the PSD-PEG algorithm can also be used to construct nonbinary QC protograph LDPC codes without low weight codes. Simulation results show that the binary and nonbinary QC protograph LDPC codes constructed by the PSD-PEG algorithm have good bit error rate performance and frame error rate performance over the additive white Gaussian noise channel.
There have been lots of efforts on the construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes with large girth. However, most of them are focused on protographs with single edges and little research has been done for the construction of QC LDPC codes lifted from protographs with multiple edges. Compared to single-edge protographs, multiple-edge protographs have benefits such that QC LDPC codes lifted from them can potentially have larger minimum Hamming distance. In this paper, all subgraph patterns of multiple-edge protographs, which prevent QC LDPC codes from having large girth by inducing inevitable cycles, are fully investigated based on graph-theoretic approach. By using combinatorial designs, a systematic construction method of multiple-edge protographs is proposed for regular QC LDPC codes with girth at least 12 and also other method is proposed for regular QC LDPC codes with girth at least 14. A construction algorithm of QC LDPC codes by lifting multiple-edge protographs is proposed and it is shown that the resulting QC LDPC codes have larger upper bounds on the minimum Hamming distance than those lifted from single-edge protographs. Simulation results are provided to compare the performance of the proposed QC LDPC codes, the progressive edge-growth (PEG) LDPC codes, and the PEG QC LDPC codes.
For a given base graph, the protograph can be obtained by a copy-and-permute procedure. If the permutation is cyclic, the protograph corresponds to a quasi-cyclic (QC) protograph LDPC code. The girth of the QC protograph LDPC code is determined by the girth of the base graph and the permutation shifts. Progressive edge-growth (PEG) construction builds up a Tanner graph, or equivalently a parity-check matrix, for an LDPC code by maximizing the local girth at symbol nodes in a greedy algorithm. In this paper, we introduce a modified version of the PEG algorithm which can construct large girth base graph and determine the optimal permutation shifts, simultaneously, for QC protograph LDPC codes. Simulation results show that the QC protograph LDPC codes constructed by the proposed modified PEG algorithm have good frame error rate (FER) performance over the AWGN channel.
Protograph low-density parity-check (P-LDPC) codes are widely researched in communication systems due to the simple encoder structure and high-speed iterative decoding implementation. The key factors to affect the performance of P-LDPC codes are the base matrix and the lifting method. This paper focuses on the lifting method of P-LDPC codes with short-to-medium length over burst-error channels. An improved anti-burst protograph progressive edge-growth (IPPEG) algorithm based on edge constraints is proposed to improve the bit error rate (BER) performance. Simulation results show that the proposed IPPEG has better burst-resistance performance than the traditional PEG based lifting algorithm (PPEG) with or without random interleaver; additionally, on the premising of correctly decoding, more coding gains of IPPEG can be achieved with condition of larger channel transition probability, shorter code length or smaller coding rate.