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 International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)

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

Keke Liu, Zesong Fei, Jingming Kuang, Xiangming Li

Published Sep 1, 2009• 6 citations
Publisher

Abstract

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.

DOI
10.1109/pimrc.2009.5450003

Related papers

Low-complexity Cycle Elimination Algorithms for QC LDPC Codes

HU Shu-kai

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.

Journal of Signal Processing•Jan 1, 2013•0 citations

Construction of Quasi-Cyclic LDPC codes with large girth based on circulant permutation matirx

Peng Yang, Xiaoxiao Bao, Hui Zhao

In this paper, we propose an algorithm for removing short-cycles in Quasi-Cyclic (QC) Low-density parity-check (LDPC) codes. First using an algorithm with lower computational complexity, all the cycles in the parity check matrix H are found. Then following a ruler, we adjust the shift value of circulant permutation matrix (CPM) to remove the short-cycles. This algorithm could ensure that the code after cycle removal process preserves the quasi-cyclic structure. Simulation results show that: comparing with the codes (504,252) and (1008, 504), we achieve 0.1dB improvement both.

Wireless and Optical Communications Conference•May 1, 2013•4 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

(3, L) quasi-cyclic LDPC codes: Simplified exhaustive search and designs

Cheng Sun, Hengzhou Xu, Dan Feng +1 more

There exist lots of (3, L)-regular quasi-cyclic (QC) LDPC codes constructed from finite fields, protographs, array codes, and computer search under some design rules. For a given code length and rate, how to select the best one from these codes is considerable. In this paper, we study (3, L)-regular QC LDPC codes from the perspective of graph isomorphism, and non-isomorphic (3, L)-regular QC LDPC codes are determined. By analyzing the cycle structures of the resulting non-isomorphic codes, an efficient algorithm for counting cycles is presented. Also proposed is a simplified exhaustive search of non-isomorphic (3, L)-regular QC LDPC codes free of cycles of length less than g0, where g0is the estimated optimal girth value for a given code length. Based on these two algorithms, we can easily construct a (3, L)-regular QC LDPC code with optimized cycle distribution for a given L and code length. Numerical results show that the constructed codes have better performance under the iterative decoding algorithms.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2016•10 citations

Construction of QC-LDPC Codes from Sidon Sequence Using Permutation and Segmentation

Lintao Zhang, Juhua Wang

By utilizing a Sidon sequence, two new methods are proposed to construct quasi-cyclic (QC) low-density parity-check (LDPC) codes. The first method yields a QC-LDPC code without 4-cycles and the second method gives a QC-LDPC code without 4-cycles and 6-cycles. In the literature there are two methods which employ mathematical objects somewhat resembling a Sidon sequence to remove 4-cycles, and there are two explicit constructions which guarantee the absence of 4-cycles and 6-cycles. Compared with the former, our first method is much more flexible in selecting parameters while providing identical or better performance. Compared with the latter, our second method provides much better performance.

IEEE Communications Letters•May 23, 2022•9 citations

Design of non-binary quasi-cyclic LDPC codes by absorbing set removal

Behzad Amiri, Jorge Arturo Flores Castro, Lara Dolecek

Non-binary quasi-cyclic (NB-QC) codes are a class of graph-based codes with high performance and implementation-friendly structure. In this paper, we introduce a new method for designing NB-QC codes with improved performance in the low error-rate region. Specifically, we propose a construction which reduces the number of non-binary absorbing sets, which are known to cause errors when decoding non-binary LDPC codes. Our construction is based on a careful selection of the code design parameters. Simulation results demonstrate the superior performance of codes designed according to our technique compared to existing state-of-the-art NB-QC codes.

IEEE Information Theory Workshop (ITW)•Nov 1, 2014•2 citations
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.
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.
In this paper, we propose an algorithm for removing short-cycles in Quasi-Cyclic (QC) Low-density parity-check (LDPC) codes. First using an algorithm with lower computational complexity, all the cycles in the parity check matrix H are found. Then following a ruler, we adjust the shift value of circulant permutation matrix (CPM) to remove the short-cycles. This algorithm could ensure that the code after cycle removal process preserves the quasi-cyclic structure. Simulation results show that: comparing with the codes (504,252) and (1008, 504), we achieve 0.1dB improvement both.
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.
There exist lots of (3, L)-regular quasi-cyclic (QC) LDPC codes constructed from finite fields, protographs, array codes, and computer search under some design rules. For a given code length and rate, how to select the best one from these codes is considerable. In this paper, we study (3, L)-regular QC LDPC codes from the perspective of graph isomorphism, and non-isomorphic (3, L)-regular QC LDPC codes are determined. By analyzing the cycle structures of the resulting non-isomorphic codes, an efficient algorithm for counting cycles is presented. Also proposed is a simplified exhaustive search of non-isomorphic (3, L)-regular QC LDPC codes free of cycles of length less than g0, where g0is the estimated optimal girth value for a given code length. Based on these two algorithms, we can easily construct a (3, L)-regular QC LDPC code with optimized cycle distribution for a given L and code length. Numerical results show that the constructed codes have better performance under the iterative decoding algorithms.
By utilizing a Sidon sequence, two new methods are proposed to construct quasi-cyclic (QC) low-density parity-check (LDPC) codes. The first method yields a QC-LDPC code without 4-cycles and the second method gives a QC-LDPC code without 4-cycles and 6-cycles. In the literature there are two methods which employ mathematical objects somewhat resembling a Sidon sequence to remove 4-cycles, and there are two explicit constructions which guarantee the absence of 4-cycles and 6-cycles. Compared with the former, our first method is much more flexible in selecting parameters while providing identical or better performance. Compared with the latter, our second method provides much better performance.
Non-binary quasi-cyclic (NB-QC) codes are a class of graph-based codes with high performance and implementation-friendly structure. In this paper, we introduce a new method for designing NB-QC codes with improved performance in the low error-rate region. Specifically, we propose a construction which reduces the number of non-binary absorbing sets, which are known to cause errors when decoding non-binary LDPC codes. Our construction is based on a careful selection of the code design parameters. Simulation results demonstrate the superior performance of codes designed according to our technique compared to existing state-of-the-art NB-QC codes.