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

International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC)

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

Yuanhua Liu, Meiling Zhang, Niu Xin-Liang

Published Jul 1, 2016• 1 citation
Publisher

Abstract

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.

DOI
10.1109/imccc.2016.167

Related papers

On the Low Complexity Construction of Quasi-Cyclic Low-Density Parity-Check Codes by Progressive-Block Growth

Qiangy Yuan, Pinyi Ren, Yilin Feng +1 more

In this paper, we propose a novel method with low complexity for constructing quasi-cyclic LDPC codes. The algorithm chooses every circulant permutation matrix sequentially, and makes sure that the current circulant permutation matrix forms no cycles of length 4 and 6 with the existent matrices, finally a family of $(3,L)$ QC-LDPC codes with girth at least 8 is obtained. The main complexity of the algorithm is checking cycles of length 6, the number of which is no more than $L^2$. Simulation results show that, when block length is 1008 and using the iterative belief propagation decoding, the LDPC code constructed by the proposed algorithm out performs the random code about 0.1dB at the bit-error-rate of $ 10^{ - 5}$.

•Jan 1, 2009•1 citation

The Design of Structured Low-Density Parity-Check Codes With Large Girth

Jing Long

This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.

Chinese Journal of Computers•Jan 1, 2007•1 citation

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

Necessary conditions for quasi-cyclic LDPC codes to have a given girth

Kyung-Joong Kim, Jin-Ho Chung, Kyeongcheol Yang

Short cycles in the Tanner graph of a low-density parity-check (LDPC) code may cause a severe performance degradation. In this paper, we investigate the cycle properties of quasi-cyclic LDPC (QC-LDPC) codes. We first analyze a necessary and sufficient condition for a cycle of a given length to exist, by using the sequence representation of a parity-check matrix for a QC-LDPC code. We then derive bounds which are necessary conditions for a QC-LDPC code to have a given girth in terms of its parameters. Our necessary conditions are applicable to any regular or irregular QC-LDPC codes as well as they improve the existing bounds for many classes of regular QC-LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•0 citations

Construction of High-Rate Regular Quasi-Cyclic LDPC Codes Based on Cyclic Difference Families

Hosung Park, Seokbeom Hong, Jong‐Seon No +1 more

For a high-rate case, it is difficult to randomly construct good low-density parity-check (LDPC) codes of short and moderate lengths because their Tanner graphs are prone to have short cycles. Also, the existing high-rate quasi-cyclic (QC) LDPC codes can be constructed only for very restricted code parameters. In this paper, based on special classes of cyclic difference families, we propose a new construction method of high-rate regular QC LDPC codes having parity-check matrices consisting of a single row of circulants with column-weight 3 or 4. The proposed QC LDPC codes can be constructed for various code rates and lengths including the minimum achievable length for given column-weight and design rate under girth 6. It is observed that the parity-check matrices of the proposed QC LDPC codes have full rank for column-weight 3 and just one redundant row for column-weight 4. It is shown that the error correcting performance of the proposed QC LDPC codes of short and moderate lengths is almost the same as that of the existing ones through numerical analysis.

arXiv:1211.3828•IEEE Transactions on Communications•Jul 16, 2013•33 citations

Quasi-cyclic low-density parity-check codes based on decoder optimised progressive edge growth for short blocks

Cornelius T. Healy, Rodrigo C. de Lamare

A novel construction for quasi-cyclic (QC) regular and irregular low-density parity-check (LDPC) codes based on a modification of the QC Progressive Edge Growth (PEG) algorithm is presented. Edge placement of the PEG-based algorithm is enhanced by use of the sum-product algorithm in the design of the parity-check matrix. The proposed algorithm is highly flexible in block length and rate, in particular when compared with algebraic constructions. The codes constructed by the proposed methods are tested in the AWGN channel and performance improvements are achieved. The proposed QC-LDPC codes provide an inherent trade-off between code performance and encoding/decoding complexity.

IEEE International Conference on Acoustics Speech and Signal Processing•Mar 1, 2012•3 citations
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.
In this paper, we propose a novel method with low complexity for constructing quasi-cyclic LDPC codes. The algorithm chooses every circulant permutation matrix sequentially, and makes sure that the current circulant permutation matrix forms no cycles of length 4 and 6 with the existent matrices, finally a family of (3,L)(3,L)(3,L) QC-LDPC codes with girth at least 8 is obtained. The main complexity of the algorithm is checking cycles of length 6, the number of which is no more than L2L^2L2. Simulation results show that, when block length is 1008 and using the iterative belief propagation decoding, the LDPC code constructed by the proposed algorithm out performs the random code about 0.1dB at the bit-error-rate of $ 10^{ - 5}$.
This paper,based on algebra and graph,proposes a method for constructing structured low-density parity-check(LDPC) codes.In this method,the authors design a connected graph with three kinds of special path to ensure that the Tanner graph of the parity check matrix mapped from the connected graph is without short cycles.The construction method results in two classes of(3,k)-regular quasi-cyclic LDPC codes with girth 8 and 12 respectively.Furthermore,by extending this construction method,two classes of LDPC codes with column weight 2,whose girths are respectively 16 and 24,can be obtained.The simulation studies show that these codes can achieve better performance than randomly constructed regular LDPC codes over AWGN channels with iterative decoding.At the BER of 10-5,the new proposed(3,6)-regular(4356,2205) QC-LDPC code performs 1.48dB from the Shannon limit.Moreover,it outperforms the random regular LDPC code of comparable parameters by 0.1dB.For the new proposed structured LDPC codes with column weight 2,they can achieve about 2dB coding gains with respect to the random regular LDPC codes with similar block lengths and code rates.
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 low-density parity-check (LDPC) code may cause a severe performance degradation. In this paper, we investigate the cycle properties of quasi-cyclic LDPC (QC-LDPC) codes. We first analyze a necessary and sufficient condition for a cycle of a given length to exist, by using the sequence representation of a parity-check matrix for a QC-LDPC code. We then derive bounds which are necessary conditions for a QC-LDPC code to have a given girth in terms of its parameters. Our necessary conditions are applicable to any regular or irregular QC-LDPC codes as well as they improve the existing bounds for many classes of regular QC-LDPC codes.
For a high-rate case, it is difficult to randomly construct good low-density parity-check (LDPC) codes of short and moderate lengths because their Tanner graphs are prone to have short cycles. Also, the existing high-rate quasi-cyclic (QC) LDPC codes can be constructed only for very restricted code parameters. In this paper, based on special classes of cyclic difference families, we propose a new construction method of high-rate regular QC LDPC codes having parity-check matrices consisting of a single row of circulants with column-weight 3 or 4. The proposed QC LDPC codes can be constructed for various code rates and lengths including the minimum achievable length for given column-weight and design rate under girth 6. It is observed that the parity-check matrices of the proposed QC LDPC codes have full rank for column-weight 3 and just one redundant row for column-weight 4. It is shown that the error correcting performance of the proposed QC LDPC codes of short and moderate lengths is almost the same as that of the existing ones through numerical analysis.
A novel construction for quasi-cyclic (QC) regular and irregular low-density parity-check (LDPC) codes based on a modification of the QC Progressive Edge Growth (PEG) algorithm is presented. Edge placement of the PEG-based algorithm is enhanced by use of the sum-product algorithm in the design of the parity-check matrix. The proposed algorithm is highly flexible in block length and rate, in particular when compared with algebraic constructions. The codes constructed by the proposed methods are tested in the AWGN channel and performance improvements are achieved. The proposed QC-LDPC codes provide an inherent trade-off between code performance and encoding/decoding complexity.