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

arXiv:2310.12556 · Facta Universitatis Series Mathematics and Informatics

AN EFFICIENT ALGORITHM FOR COUNTING CYCLES IN QC AND APM LDPC CODES

Mohammad Gholami, Zahra Gholami

Published Dec 13, 2024• 0 citations
arXivHTMLPDF

Abstract

In this paper, a new method is given for counting cycles in the Tanner graph of a (Type-I) quasi-cyclic (QC) low-density parity-check (LDPC) code which the complexity mainly is dependent on the base matrix, independent from the CPM-size of the constructed code. Interestingly, for large CPM-sizes, in comparison of the existing methods, this algorithm efficiently counts the cycles of any lengths in the Tanner graphs of QC-LDPC codes. In fact, the algorithm recursively counts the cycles in the paritycheck matrix column-by-column by finding all non-isomorph tailless backtrackless closed (TBC) walks in the base graph and enumerating theoretically their corresponding cycles in the same equivalent class. Moreover, this approach can be modified in few steps to find the cycle distributions of a class of LDPC codes based on Affine permutation matrices (APM-LDPC codes). Interestingly, unlike the existing methods which count the cycles up to 2g - 2, where g is the girth, the proposed algorithm can be used to enumerate the cycles of arbitrary length in the Tanner graph. Moreover, the proposed cycle searching algorithm improves upon various previously known methods, in terms of computational complexity and memory requirements.

DOI
10.22190/fumi230814046g

Related papers

An Efficient Strategy to Count Cycles in the Tanner Graph of Quasi-Cyclic LDPC Codes

Anthony Gómez-Fonseca, Roxana Smarandache, David G. M. Mitchell

In this paper, we present an efficient strategy to enumerate the number of k-cycles, g≤k<2g, in the Tanner graph of a quasi-cyclic low-density parity-check (QC-LDPC) code with girth g using its polynomial parity-check matrix H. This strategy works for both (dv,dc)-regular and irregular QC-LDPC codes. In this approach, we note that the mth power of the polynomial adjacency matrix can be used to describe walks of length m in the protograph and can therefore be sufficiently described by the matrices Bm(H)(HHT)m/2H(m2), where m≥0. We provide formulas for the number of k-cycles, Nk, by just taking into account repetitions in some multisets constructed from the matrices Bm(H). This approach is shown to have low complexity. For example, in the case of QC-LDPC codes based on the 3×nv fully-connected protograph, the complexity of determining Nk, for k=4,6,8,10 and 12, is O(nv2log(N)), O(nv2log(nv)log(N)), O(nv4log4(nv)log(N)), O(nv4log(nv)log(N)) and O(nv6log6(nv)log(N)), respectively. The complexity, depending logarithmically on the lifting factor N, gives our approach, to the best of our knowledge, a significant advantage over previous works on the cycle distribution of QC-LDPC codes.

IEEE Journal on Selected Areas in Information Theory•Jan 1, 2023•8 citations

Counting Short Cycles of Quasi Cyclic Protograph LDPC Codes

Mehdi Karimi, Amir H. Banihashemi

An efficient method for counting short cycles in the Tanner graphs of quasi cyclic (QC) protograph low-density parity-check (LDPC) codes is presented. The method is based on the relationship between the number of short cycles in the graph and the eigenvalues of the directed edge matrix of the graph. We demonstrate that for a QC protograph LDPC code, the complexity of computing such eigenvalues can be reduced significantly by representing the directed edge matrix as a block circulant matrix. Numerical results are presented to show the lower complexity of the proposed method compared to the existing algorithms for counting short cycles. These results also reveal that QC LDPC codes on average have a superior short cycle and girth distribution compared to similar randomly constructed codes.

IEEE Communications Letters•Feb 10, 2012•34 citations

A new algorithm of counting the number of small stopping sets and girth in QC-LDPC Codes

Lingjun Kong, Yang Xiao

It is well known that the performance of low-density parity check (LDPC) codes under iterative decoding is determined by certain combinatorial structures (such as stopping sets and girth) in the Tanner graph. The difficulty in enumerating all possible combinations of the columns may prevent an efficient search of good LDPC codes with small stopping sets and girth. To solve the problem, this paper presents a new algorithm of counting the number of small stopping sets and girth by analyzing the shapes of the cycles of Tanner graph in parity check matrix for designing good LDPC codes which is less complex than the existing algorithms. This method can be used effectively to evaluate the performance of LDPC codes according to their small stopping sets and girth distributions.

•Oct 1, 2008•0 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

4-CYCLE FREE APM LDPC CODES WITH AN EXPLICIT CONSTRUCTION

Zahra Gholami, Mohammad Gholami

Recently, a class of low-density parity-check codes based on affine permutation matrices, called APM-LDPC codes, have been considered which have some advantages than quasi-cyclic (QC) LDPC codes in terms of minimum-distance, cycle distribution, and error-rate performance. Moreover, some explicit constructions for exponent matrices of conventional APM-LDPC codes with girth at least 6 have been investigated. In this paper, a class of 4-cycle free APM-LDPC codes is constructed by a new explicit method such that the constructed codes have better cycle distributions rather than the recently proposed APM codes with girth 6. As simulation results show, the constructed codes outperform PEG and random-like LDPC codes with the same rates and lengths.

Journal of Algebraic Systems•Jan 1, 2021•0 citations

Anti Quasi-Cyclic LDPC Codes

Zahra Gholami, Mohammad Gholami

Low-density parity-check (LDPC) codes based on affine permutation matrices, APM-LDPC codes, have been attracted recently, because of some advantages rather than QC-LDPC codes in minimum-distance, cycle distribution and error-rate performance. In this letter, circulant and anti-circulant permutation matrices are used to define a class of LDPC codes, called AQC-LDPC codes, which can be considered as an special case of APM-LDPC codes. In fact, each AQC-LDPC code can be verified by a sign matrix and a slope matrix which are helpful to show each cycle in the Tanner graph by a modular linear equation. For the normal sign matrix A , if -1 ϵ, A, it is shown that the corresponding AQC-LDPC code has maximum-girth 8. Finally, two explicit constructions for AQC-LDPC codes with girths 6, 8 are presented which have some benefits rather than the explicitly constructed QC and APM LDPC codes in minimum-distance, cycle distributions and bit-error-rate performances.

IEEE Communications Letters•Mar 26, 2018•5 citations
In this paper, a new method is given for counting cycles in the Tanner graph of a (Type-I) quasi-cyclic (QC) low-density parity-check (LDPC) code which the complexity mainly is dependent on the base matrix, independent from the CPM-size of the constructed code. Interestingly, for large CPM-sizes, in comparison of the existing methods, this algorithm efficiently counts the cycles of any lengths in the Tanner graphs of QC-LDPC codes. In fact, the algorithm recursively counts the cycles in the paritycheck matrix column-by-column by finding all non-isomorph tailless backtrackless closed (TBC) walks in the base graph and enumerating theoretically their corresponding cycles in the same equivalent class. Moreover, this approach can be modified in few steps to find the cycle distributions of a class of LDPC codes based on Affine permutation matrices (APM-LDPC codes). Interestingly, unlike the existing methods which count the cycles up to 2g - 2, where g is the girth, the proposed algorithm can be used to enumerate the cycles of arbitrary length in the Tanner graph. Moreover, the proposed cycle searching algorithm improves upon various previously known methods, in terms of computational complexity and memory requirements.
In this paper, we present an efficient strategy to enumerate the number of k-cycles, g≤k<2g, in the Tanner graph of a quasi-cyclic low-density parity-check (QC-LDPC) code with girth g using its polynomial parity-check matrix H. This strategy works for both (dv,dc)-regular and irregular QC-LDPC codes. In this approach, we note that the mth power of the polynomial adjacency matrix can be used to describe walks of length m in the protograph and can therefore be sufficiently described by the matrices Bm(H)(HHT)m/2H(m2), where m≥0. We provide formulas for the number of k-cycles, Nk, by just taking into account repetitions in some multisets constructed from the matrices Bm(H). This approach is shown to have low complexity. For example, in the case of QC-LDPC codes based on the 3×nv fully-connected protograph, the complexity of determining Nk, for k=4,6,8,10 and 12, is O(nv2log(N)), O(nv2log(nv)log(N)), O(nv4log4(nv)log(N)), O(nv4log(nv)log(N)) and O(nv6log6(nv)log(N)), respectively. The complexity, depending logarithmically on the lifting factor N, gives our approach, to the best of our knowledge, a significant advantage over previous works on the cycle distribution of QC-LDPC codes.
An efficient method for counting short cycles in the Tanner graphs of quasi cyclic (QC) protograph low-density parity-check (LDPC) codes is presented. The method is based on the relationship between the number of short cycles in the graph and the eigenvalues of the directed edge matrix of the graph. We demonstrate that for a QC protograph LDPC code, the complexity of computing such eigenvalues can be reduced significantly by representing the directed edge matrix as a block circulant matrix. Numerical results are presented to show the lower complexity of the proposed method compared to the existing algorithms for counting short cycles. These results also reveal that QC LDPC codes on average have a superior short cycle and girth distribution compared to similar randomly constructed codes.
It is well known that the performance of low-density parity check (LDPC) codes under iterative decoding is determined by certain combinatorial structures (such as stopping sets and girth) in the Tanner graph. The difficulty in enumerating all possible combinations of the columns may prevent an efficient search of good LDPC codes with small stopping sets and girth. To solve the problem, this paper presents a new algorithm of counting the number of small stopping sets and girth by analyzing the shapes of the cycles of Tanner graph in parity check matrix for designing good LDPC codes which is less complex than the existing algorithms. This method can be used effectively to evaluate the performance of LDPC codes according to their small stopping sets and girth distributions.
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.
Recently, a class of low-density parity-check codes based on affine permutation matrices, called APM-LDPC codes, have been considered which have some advantages than quasi-cyclic (QC) LDPC codes in terms of minimum-distance, cycle distribution, and error-rate performance. Moreover, some explicit constructions for exponent matrices of conventional APM-LDPC codes with girth at least 6 have been investigated. In this paper, a class of 4-cycle free APM-LDPC codes is constructed by a new explicit method such that the constructed codes have better cycle distributions rather than the recently proposed APM codes with girth 6. As simulation results show, the constructed codes outperform PEG and random-like LDPC codes with the same rates and lengths.
Low-density parity-check (LDPC) codes based on affine permutation matrices, APM-LDPC codes, have been attracted recently, because of some advantages rather than QC-LDPC codes in minimum-distance, cycle distribution and error-rate performance. In this letter, circulant and anti-circulant permutation matrices are used to define a class of LDPC codes, called AQC-LDPC codes, which can be considered as an special case of APM-LDPC codes. In fact, each AQC-LDPC code can be verified by a sign matrix and a slope matrix which are helpful to show each cycle in the Tanner graph by a modular linear equation. For the normal sign matrix A , if -1 ϵ, A, it is shown that the corresponding AQC-LDPC code has maximum-girth 8. Finally, two explicit constructions for AQC-LDPC codes with girths 6, 8 are presented which have some benefits rather than the explicitly constructed QC and APM LDPC codes in minimum-distance, cycle distributions and bit-error-rate performances.