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

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

Xueqin Jiang, Han Hai, Hui-Ming Wang, Moon Ho Lee

Published Jan 1, 2017• 23 citations
Publisher

Abstract

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.

DOI
10.1109/access.2017.2688701

Related papers

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

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

Improved PEG construction of large girth QC-LDPC codes

Madiagne Diouf, David Declercq, M.P.C. Fossorier +2 more

In this paper, we present an improvement of the PEG algorithm for constructing quasi-cyclic low-density parity-check (QC-LDPC) codes with large girth. We introduce the concept of PEG-undetectable cycles on the computation tree in the PEG algorithm for QC-LDPC codes and give a predictive method to avoid these undetected cycles. The aim is to select only the candidates that ensure the maximization of local girth for a code of girth g ≥ 10 and thus avoid a posteriori verification after the creation of a new edge i.e. keep the predictive philosophy of the PEG algorithm. The proposed method is applicable to both regular and irregular codes and also protograph type-I codes. Simulation results are presented to demonstrate the efficiency of our method in terms of minimum circulant permutation matrix pminand error performance.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2016•20 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

On the Construction of Multitype Quasi-Cyclic Low-Density Parity-Check Codes With Different Girth and Length

Farzaneh Abedi, Mohammad Gholami

Multitype quasi-cyclic (QC) low-density parity-check (LDPC) codes are a class of protograph LDPC codes lifted cyclically from protographs with multiple edges, represented by two weight and slope matrices. For a given weight-matrix, an approach is proposed to find the maximum-achievable girth$g_{\max }$of the corresponding multitype QC-LDPC codes by some inevitable chains having less complexity than the existing methods. This advantage leads to some new patterns of the weight matrices such that the corresponding codes have some improvements in terms of the maximum-achievable girths or the minimum-distance upper-bounds. In continue, for a given weight-matrix with maximum-achievable girth$g_{\max }$, some slope-matrices are constructed by a depth-first search algorithm for which the corresponding multitype QC-LDPC codes with even girth$g$,$g\le g_{\max }$, have smaller lengths, higher rates, or larger minimum-distances than the state-of-the-art achievements. Simulation results show that the constructed codes have some error-rate advantages than PEG, random-like, CCSDS, and 802.11n/ac IEEE standard LDPC codes.

IEEE Access•Jan 1, 2021•2 citations

Optimized Construction of Short and High Rate Protograph QC-LDPC Codes

Jianrong Bao, Xiaorong Xu, Chao Liu +2 more

To obtain efficient and pragmatic channel codes high signal-to-noise ratios (SNRs), an optimized construction of short and high rate protograph quasi-cyclic (QC) low-density parity-check (LDPC) codes is presented. Based on an optimized protograph template, the code framework is firstly produced by the extensions of the variable nodes. By enlarging the dimension of the sub-matrices related to the protograph framework, the base quasi-cyclic (QC) matrix is generated with required code rate and length. Then, the elements in the base matrix are split with even smaller square sub-matrices of the same row and column weights. In this procedure, a progressive edge growth (PEG) algorithm is employed to find the optimized positions of the QC submatrices, which brings larger girth for better code performance. Also the circulant offsets in all QC sub-matrices are optimally searched by a QC improved approximated cycle extrinsic message degree (QCI-ACE) algorithm, which improves the relationship of the unavoidable loops in the code's Tanner graph and thus it improves the error floor. Simulation results show that the codes produced by the proposed method demonstrate quite good bit error rate (BER) performance. In addition, they exhibit good properties of high spectrum efficiency by the high code rate, as well as the low complexity by the short code length. Therefore, the proposed code construction can be efficiently applied in the design of short and high rate protograph QC-LDPC codes with high rate and rational complexity.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 20, 2021•1 citation
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.
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.
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.
In this paper, we present an improvement of the PEG algorithm for constructing quasi-cyclic low-density parity-check (QC-LDPC) codes with large girth. We introduce the concept of PEG-undetectable cycles on the computation tree in the PEG algorithm for QC-LDPC codes and give a predictive method to avoid these undetected cycles. The aim is to select only the candidates that ensure the maximization of local girth for a code of girth g ≥ 10 and thus avoid a posteriori verification after the creation of a new edge i.e. keep the predictive philosophy of the PEG algorithm. The proposed method is applicable to both regular and irregular codes and also protograph type-I codes. Simulation results are presented to demonstrate the efficiency of our method in terms of minimum circulant permutation matrix pminand error performance.
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).
Multitype quasi-cyclic (QC) low-density parity-check (LDPC) codes are a class of protograph LDPC codes lifted cyclically from protographs with multiple edges, represented by two weight and slope matrices. For a given weight-matrix, an approach is proposed to find the maximum-achievable girthgmax⁡g_{\max }gmax​of the corresponding multitype QC-LDPC codes by some inevitable chains having less complexity than the existing methods. This advantage leads to some new patterns of the weight matrices such that the corresponding codes have some improvements in terms of the maximum-achievable girths or the minimum-distance upper-bounds. In continue, for a given weight-matrix with maximum-achievable girthgmax⁡g_{\max }gmax​, some slope-matrices are constructed by a depth-first search algorithm for which the corresponding multitype QC-LDPC codes with even girthggg,g≤gmax⁡g\le g_{\max }g≤gmax​, have smaller lengths, higher rates, or larger minimum-distances than the state-of-the-art achievements. Simulation results show that the constructed codes have some error-rate advantages than PEG, random-like, CCSDS, and 802.11n/ac IEEE standard LDPC codes.
To obtain efficient and pragmatic channel codes high signal-to-noise ratios (SNRs), an optimized construction of short and high rate protograph quasi-cyclic (QC) low-density parity-check (LDPC) codes is presented. Based on an optimized protograph template, the code framework is firstly produced by the extensions of the variable nodes. By enlarging the dimension of the sub-matrices related to the protograph framework, the base quasi-cyclic (QC) matrix is generated with required code rate and length. Then, the elements in the base matrix are split with even smaller square sub-matrices of the same row and column weights. In this procedure, a progressive edge growth (PEG) algorithm is employed to find the optimized positions of the QC submatrices, which brings larger girth for better code performance. Also the circulant offsets in all QC sub-matrices are optimally searched by a QC improved approximated cycle extrinsic message degree (QCI-ACE) algorithm, which improves the relationship of the unavoidable loops in the code's Tanner graph and thus it improves the error floor. Simulation results show that the codes produced by the proposed method demonstrate quite good bit error rate (BER) performance. In addition, they exhibit good properties of high spectrum efficiency by the high code rate, as well as the low complexity by the short code length. Therefore, the proposed code construction can be efficiently applied in the design of short and high rate protograph QC-LDPC codes with high rate and rational complexity.