© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

IEEE Transactions on Communications

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

Xuan He, Liang Zhou, Junyi Du

Published Dec 29, 2017• 30 citations

Abstract

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.

DOI: 10.1109/tcomm.2017.2787989

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

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

Quasi-Cyclic Low-Density Parity-Check Codes Based on Progressive Cycle Growth Algorithm

Yuanhua Liu, Meiling Zhang, Niu Xin-Liang

Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.

International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC)•Jul 1, 2016•1 citation

Quasi-cyclic LDPC codes based on D and Q matrices through progressive edge growth

Wei Zhan, Guangxi Zhu, Li Peng +1 more

We propose a general method for constructing regular and irregular quasi-cyclic LDPC codes based on the modified PEG (progressive edge growth) graph. The idea of permutation vector is introduced. Through permutation vectors, the QC-LDPC codes based on arbitrary circulant permutation matrices, which are not limited to identity matrix, Q-matrix or D-matrix, can be generated with flexible parameters such as block length, code rate, degree distribution. Simulation results demonstrate that QC-LDPC codes using the new PEG algorithm show an error correction performance comparable to the random LDPC codes based on the traditional PEG algorithm. In addition, the PEG QC-LDPC codes have more hardware-friendly parity check matrices than the random PEG LDPC codes and can fulfill linear-time encoding. The QC-LDPC codes based on D-matrix and Q-matrix are more suitable to be used in QC-LDPC codes than identity matrix because they outperform that of identity matrix by 0.1-0.2 dB in the new PEG algorithm.

International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS)•Jan 1, 2007•7 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

Novel construction and cycle analysis of Quasi-Cyclic Low-Density Parity-Check codes

Wenwen Li, Mao Ai, Jie Qiu +1 more

Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes have practical significance in the field of engineering, thus their construction algorithm is a hot issue in the field of LDPC codes. Based on existing construction methods, particularly the method based on Progressive Edge-Growth (PEG) algorithm, a new construction method of shift matrix is proposed. It can effectively avoid the copy of cycle structures, especially short cycles in base matrix after extension. Besides, it also relieves the time cost caused by random search, and greatly improves the length of cycles when compared with algorithms based on methods such as quadratic congruence and arithmetic sequence. Those algorithms can only eliminate short cycles with length 4, while our method can provide QC-LDPC codes without length 6 at least. Cycle analysis and simulation results show that the newly constructed QC-LDPC codes have good cycle structure and error correction performance.

IEEE International Conference on Progress in Informatics and Computing•Dec 1, 2015•2 citations

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.

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

Short cycles in the Tanner graph of a given LDPC code has negative effect on the performance of iterative decoding. To improve the performance, we presented an approach for constructing Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes whose associated Tanner graph has large girth and a small amount of short cycles. Each column block of the parity check matrix was designed by adding circulant permutation sub-matrices one after another, provided the current parity check matrix has minimal number of short cycles. The condition for the proposed QC-LDPC codes to have girth at least 6 was also analyzed. Regular and irregular QC-LDPC codes with various lengths and rates can be constructed. Simulations show that the proposed QC-LDPC codes have less short cycles and better performance than existing progressive edge growth based QC-LDPC codes.

We propose a general method for constructing regular and irregular quasi-cyclic LDPC codes based on the modified PEG (progressive edge growth) graph. The idea of permutation vector is introduced. Through permutation vectors, the QC-LDPC codes based on arbitrary circulant permutation matrices, which are not limited to identity matrix, Q-matrix or D-matrix, can be generated with flexible parameters such as block length, code rate, degree distribution. Simulation results demonstrate that QC-LDPC codes using the new PEG algorithm show an error correction performance comparable to the random LDPC codes based on the traditional PEG algorithm. In addition, the PEG QC-LDPC codes have more hardware-friendly parity check matrices than the random PEG LDPC codes and can fulfill linear-time encoding. The QC-LDPC codes based on D-matrix and Q-matrix are more suitable to be used in QC-LDPC codes than identity matrix because they outperform that of identity matrix by 0.1-0.2 dB in the new PEG algorithm.

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.

Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes have practical significance in the field of engineering, thus their construction algorithm is a hot issue in the field of LDPC codes. Based on existing construction methods, particularly the method based on Progressive Edge-Growth (PEG) algorithm, a new construction method of shift matrix is proposed. It can effectively avoid the copy of cycle structures, especially short cycles in base matrix after extension. Besides, it also relieves the time cost caused by random search, and greatly improves the length of cycles when compared with algorithms based on methods such as quadratic congruence and arithmetic sequence. Those algorithms can only eliminate short cycles with length 4, while our method can provide QC-LDPC codes without length 6 at least. Cycle analysis and simulation results show that the newly constructed QC-LDPC codes have good cycle structure and error correction performance.