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

2012 International Conference on Computing, Networking and Communications (ICNC)

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

Xueqin Jiang, Moon Ho Lee, Hui-Ming Wang, Jun Li, Miaowen Wen

Published Feb 1, 2016• 5 citations
Publisher

Abstract

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.

DOI
10.1109/iccnc.2016.7440704

Related papers

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

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

Design of Quasi-Cyclic LDPC Codes with Maximized Girth Property

Watid Phakphisut, Patanasak Prompakdee, Pornchai Supnithi

In this paper, we propose the construction of quasi-cyclic (QC) LDPC codes based on the modified progressive edge-growth (PEG) algorithm to achieve the maximum local girth. Although the previously designed QC-LDPC codes based on the PEG algorithm has more flexible code rates than the conventional QC-LDPC code, in the design process, multiple choices of the edges may be chosen. In the proposed algorithm, we aim to maximize the girth property by choosing the suitable edges and thus improve the error correcting performance. Simulation results show that the QC-LDPC codes constructed from the proposed method give higher proportion of high local girths than other methods, particularly, at high code rates. In addition, the proposed codes offer superior bit error rate and block error rate performances to the previous PEG-QC codes over the additive white Gaussian noise (AWGN) channel.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2013•0 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

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
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.
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.
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.
In this paper, we propose the construction of quasi-cyclic (QC) LDPC codes based on the modified progressive edge-growth (PEG) algorithm to achieve the maximum local girth. Although the previously designed QC-LDPC codes based on the PEG algorithm has more flexible code rates than the conventional QC-LDPC code, in the design process, multiple choices of the edges may be chosen. In the proposed algorithm, we aim to maximize the girth property by choosing the suitable edges and thus improve the error correcting performance. Simulation results show that the QC-LDPC codes constructed from the proposed method give higher proportion of high local girths than other methods, particularly, at high code rates. In addition, the proposed codes offer superior bit error rate and block error rate performances to the previous PEG-QC codes over the additive white Gaussian noise (AWGN) channel.
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.
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.