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

Journal of Signal Processing

Low-complexity Cycle Elimination Algorithms for QC LDPC Codes

HU Shu-kai

Published Jan 1, 2013• 0 citations
OpenAlex

Abstract

Quasi-cyclic LDPC code is a kind of half-structured low density parity check code.Its block-based property leads to highly structured integrated circuits implementation,without significant performance loss.An algorithm searching shift values for the nonzero entries in base matrix of a Quasi-cyclic LDPC code is proposed along with its improved version.By expanding the Tanner graph of the corresponding expansion matrix,cycles with given length can be detected.Unlike some former algorithms,arithmetic operations are avoided,which leads to a considerable complexity reduction.Given the same base matrix with code rate 0.5 as is used in the IEEE 802.16e standard,LDPC codes constructed by the proposed algorithms have better cycle distributions and achieve slightly improved error-correction performance than the IEEE 802.16e LDPC code as well.

Related papers

Improved cycle elimination algorithm for construction of QC-LDPC codes

Xudong Guo

A novel construction algorithm for quasi-cyclic low-density parity-check codes is proposed,with which we can obtain the improved girth of the corresponding Tanner graph by generalizing Yang et al.'s constraint for any cycle detected in the base matrix to detect and break the cycles in the parity check matrix.Compared with the existing cycle elimination(CE) algorithm,a better error performance can be achieved and cycle-8 free.Simulation results show that the proposed algorithm for constructing the irregular LDPC code of rate 1/2 achieves the performance of codeword error rate of 2×10-6at Eb/N0=1.5dB with 80 iterations by the belief-propagation decoding algorithm.

Journal of Xidian University•Jan 1, 2010•0 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

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

A novel algorithm for removing cycles in quasi-cyclic LDPC codes

Keke Liu, Zesong Fei, Jingming Kuang +1 more

In this paper, an algorithm for removing cycles in quasi-cyclic(QC) LDPC codes is presented. This algorithm can ensure that the code after cycle removal process preserves the quasi-cyclic structure and significantly improves the flexibility in parameter selection (such as the length of the code) of algebraic constructions of QC-LDPC codes. Besides, it has far lower computational complexity than the existing cycle removal algorithm. Experimental results show that this algorithm is very effective in improving the performance of the QC-LDPC codes and can construct code which has better performance than the corresponding binary LDPC code based on IEEE 802.16e standard.

IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)•Sep 1, 2009•6 citations

Combinatorial optimization for improving QC LDPC codes performance

Irina E. Bocharova, Boris D. Kudryashov, Rolf Johannesson

Techniques for searching for good quasi-cyclic (QC) LDPC block codes of short and moderate lengths which are suitable for practical purposes are studied. To facilitate implementations only codes whose parity-check matrices having bidiagonal structure of their submatrices and consequently having low encoding complexity are considered. The problem of finding QC LDPC codes with the near-optimum frame or bit error rate performance is split into two independent steps: searching for the near-optimum column degree distribution of the parity-check matrix together with the best base matrix for this degree distribution and searching for the near-optimum labeling of the chosen base matrix. Sets of parameters and criteria for both steps are introduced and discussed. They allow further reduction of the search complexity without significant loss of the search optimality. New QC LDPC block codes of various code rates are obtained and their BER and FER performances are compared with those of the LDPC block codes as well as the turbo codes defined in the IEEE 802.16 WiMAX standard.

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

The design of structured LDPC codes with algorithmic graph construction

Wojciech Sułek

Low-Density Parity-Check (LDPC) codes are among the most effective modern error-correcting codes due to their excellent correction performance and highly parallel decoding scheme. Moreover, the nonbinary extension of such codes further increases performance in the short-block regime. In this paper, we review the key elements for the construction of implementation-oriented binary and nonbinary codes. These Quasi-Cyclic LDPC (QC-LDPC) codes additionally feature efficient encoder and decoder implementation frameworks. We then present a versatile algorithm for the construction of both binary and nonbinary QC-LDPC codes that have low encoding complexity and an optimized corresponding graph structure. Our algorithm uses a progressive edge growth algorithm, modified for QC-LDPC graph construction, and then performs an iterative global search for optimized cyclic shift values within the QC-LDPC circulants. Strong error correction performance is achieved by minimizing the number of short cycles, and cycles with low external connectivity, within the code graph. We validate this approach via error rate simulations of a transmission system model featuring an LDPC coder-decoder, digital modulation, and additive white Gaussian noise channels. The obtained numerical results validate the effectiveness of the proposed construction algorithm, with a number of constructed codes exhibiting either similar or superior performance to industry standard binary codes and selected nonbinary codes from the literature.

Bulletin of the Polish Academy of Sciences Technical Sciences•May 30, 2022•0 citations
Quasi-cyclic LDPC code is a kind of half-structured low density parity check code.Its block-based property leads to highly structured integrated circuits implementation,without significant performance loss.An algorithm searching shift values for the nonzero entries in base matrix of a Quasi-cyclic LDPC code is proposed along with its improved version.By expanding the Tanner graph of the corresponding expansion matrix,cycles with given length can be detected.Unlike some former algorithms,arithmetic operations are avoided,which leads to a considerable complexity reduction.Given the same base matrix with code rate 0.5 as is used in the IEEE 802.16e standard,LDPC codes constructed by the proposed algorithms have better cycle distributions and achieve slightly improved error-correction performance than the IEEE 802.16e LDPC code as well.
A novel construction algorithm for quasi-cyclic low-density parity-check codes is proposed,with which we can obtain the improved girth of the corresponding Tanner graph by generalizing Yang et al.'s constraint for any cycle detected in the base matrix to detect and break the cycles in the parity check matrix.Compared with the existing cycle elimination(CE) algorithm,a better error performance can be achieved and cycle-8 free.Simulation results show that the proposed algorithm for constructing the irregular LDPC code of rate 1/2 achieves the performance of codeword error rate of 2×10-6at Eb/N0=1.5dB with 80 iterations by the belief-propagation decoding algorithm.
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.
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, an algorithm for removing cycles in quasi-cyclic(QC) LDPC codes is presented. This algorithm can ensure that the code after cycle removal process preserves the quasi-cyclic structure and significantly improves the flexibility in parameter selection (such as the length of the code) of algebraic constructions of QC-LDPC codes. Besides, it has far lower computational complexity than the existing cycle removal algorithm. Experimental results show that this algorithm is very effective in improving the performance of the QC-LDPC codes and can construct code which has better performance than the corresponding binary LDPC code based on IEEE 802.16e standard.
Techniques for searching for good quasi-cyclic (QC) LDPC block codes of short and moderate lengths which are suitable for practical purposes are studied. To facilitate implementations only codes whose parity-check matrices having bidiagonal structure of their submatrices and consequently having low encoding complexity are considered. The problem of finding QC LDPC codes with the near-optimum frame or bit error rate performance is split into two independent steps: searching for the near-optimum column degree distribution of the parity-check matrix together with the best base matrix for this degree distribution and searching for the near-optimum labeling of the chosen base matrix. Sets of parameters and criteria for both steps are introduced and discussed. They allow further reduction of the search complexity without significant loss of the search optimality. New QC LDPC block codes of various code rates are obtained and their BER and FER performances are compared with those of the LDPC block codes as well as the turbo codes defined in the IEEE 802.16 WiMAX standard.
Low-Density Parity-Check (LDPC) codes are among the most effective modern error-correcting codes due to their excellent correction performance and highly parallel decoding scheme. Moreover, the nonbinary extension of such codes further increases performance in the short-block regime. In this paper, we review the key elements for the construction of implementation-oriented binary and nonbinary codes. These Quasi-Cyclic LDPC (QC-LDPC) codes additionally feature efficient encoder and decoder implementation frameworks. We then present a versatile algorithm for the construction of both binary and nonbinary QC-LDPC codes that have low encoding complexity and an optimized corresponding graph structure. Our algorithm uses a progressive edge growth algorithm, modified for QC-LDPC graph construction, and then performs an iterative global search for optimized cyclic shift values within the QC-LDPC circulants. Strong error correction performance is achieved by minimizing the number of short cycles, and cycles with low external connectivity, within the code graph. We validate this approach via error rate simulations of a transmission system model featuring an LDPC coder-decoder, digital modulation, and additive white Gaussian noise channels. The obtained numerical results validate the effectiveness of the proposed construction algorithm, with a number of constructed codes exhibiting either similar or superior performance to industry standard binary codes and selected nonbinary codes from the literature.