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 Information Theory (ISIT)

On the Tanner Cycle Distribution of QC-LDPC Codes from Polynomial Parity-Check Matrices

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

Published Jun 25, 2023• 0 citations
Publisher

Abstract

In this paper, we present an efficient strategy to enumerate the number of k-cycles, g ≤ kc, nv)-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 ${B_m}(H) \triangleq {\left( {H{H^ \top }} \right)^{\left\lfloor {m/2} \right\rfloor }}{H^{(m\,\bmod \,2)}}$, where m ≥ 0. For example, in the case of QC-LDPC codes based on the 3 × nvfully-connected protograph, the complexity of determining the number of k-cycles, ${\mathcal{N}_k}$, for k = 4, 6 and 8, is $O\left( {n_v^2\log (N)} \right)$, $O\left( {n_v^2\log \left( {{n_v}} \right)\log (N)} \right)$ and $O\left( {n_v^4{{\log }^4}\left( {{n_v}} \right)\log (N)} \right)$, 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.

DOI
10.1109/isit54713.2023.10207005

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

On the Tanner Graph Cycle Distribution of Random LDPC, Random Protograph-Based LDPC, and Random Quasi-Cyclic LDPC Code Ensembles

Ali Dehghan, Amir H. Banihashemi

In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasicyclic (QC) LDPC codes. We prove that for a random bipartite graph, with a given (irregular) degree distribution, the distributions of cycles of different length tend to independent Poisson distributions, as the size of the graph tends to infinity. We derive asymptotic upper and lower bounds on the expected values of the Poisson distributions that are independent of the size of the graph, and only depend on the degree distribution and the cycle length. For a random lift of a bi-regular protograph, we prove that the asymptotic cycle distributions are essentially the same as those of random bipartite graphs as long as the degree distributions are identical. For random QC-LDPC codes, however, we show that the cycle distribution can be quite different from the other two categories. In particular, depending on the protograph and the value of c, the expected number of cycles of length c, in this case, can be either 8(N) or 8(1), where N is the lifting degree (code length). We also provide numerical results that match our theoretical derivations. Our results provide a theoretical foundation for emperical results that were reported in the literature but were not well-justified. They can also be used for the analysis and design of LDPC codes and associated algorithms that are based on cycles.

arXiv:1701.02379•IEEE Transactions on Information Theory•Feb 14, 2018•61 citations

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

Mohammad Gholami, Zahra Gholami

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.

arXiv:2310.12556•Facta Universitatis Series Mathematics and Informatics•Dec 13, 2024•0 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

Trade-Based LDPC Codes

Farzane Amirzade, Daniel Panario, Mohammad‐Reza Sadeghi

LDPC codes based on multi-edge protographs potentially have larger minimum distances compared to their counterparts, single-edge protographs. However, considering different features of their Tanner graph, such as short cycles, girth and other graphical structures, is harder than for Tanner graphs from single-edge protographs. Here, we provide a novel approach to construct the parity-check matrix of an LDPC code which is based on trades obtained from block designs. We employ our method to construct multi-edge quasi-cyclic (QC) LDPC codes.We use those trade-based matrices to define base matrices of multi-edge protographs. The construction of exponent matrices corresponding to these base matrices has less complexity than the ones proposed in the literature. We prove that these base matrices result in QC-LDPC codes with smaller lower bounds on the lifting degree than existing ones.

arXiv:2107.07466•IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•4 citations

On the Girth of Tanner QC-LDPC Cycle Codes: An Algebraic Number Theory Approach

Haipeng Yu, Manjie Zhou, Zhongyang Yu +2 more

Tanner quasi-cyclic low-density parity-check (QC-LDPC) codes form an important family of structured LDPC codes with favorable girth properties. This paper studies the girth of Tanner (2, L)-regular QC-LDPC codes (referred to as Tanner QC-LDPC cycle codes) for arbitrary integers L>2 and develops a novel algebraic number theoretic method to determine the girth for all sufficiently large primes p with p≡1(mod2L). We first analyze the case L=3 and prove that the girth is 12 for every prime p≡1(mod6) through exhaustive resultant computations. We then extend the method to arbitrary L and obtain a clear classification: when L is even, the girth is exactly 8 for all admissible primes; when L is odd, the girth attains the maximum value 12 for all sufficiently large admissible primes. The proof transforms cycle existence conditions into polynomial equations and applies resultant theory. This approach converts the infinite task of checking all primes into a finite set of algebraic checks. Numerical simulations show that the Tanner (2, 5)-regular non-binary code over GF(64) achieves a coding gain of approximately 0.2 dB over the 5G LDPC code of equivalent binary length.

Axioms•May 21, 2026•0 citations
In this paper, we present an efficient strategy to enumerate the number of k-cycles, g ≤ kc, nv)-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)≜(HH⊤)⌊m/2⌋H(m  mod  2){B_m}(H) \triangleq {\left( {H{H^ \top }} \right)^{\left\lfloor {m/2} \right\rfloor }}{H^{(m\,\bmod \,2)}}Bm​(H)≜(HH⊤)⌊m/2⌋H(mmod2), where m ≥ 0. For example, in the case of QC-LDPC codes based on the 3 × nvfully-connected protograph, the complexity of determining the number of k-cycles, Nk{\mathcal{N}_k}Nk​, for k = 4, 6 and 8, is O(nv2log⁡(N))O\left( {n_v^2\log (N)} \right)O(nv2​log(N)), O(nv2log⁡(nv)log⁡(N))O\left( {n_v^2\log \left( {{n_v}} \right)\log (N)} \right)O(nv2​log(nv​)log(N)) and O(nv4log⁡4(nv)log⁡(N))O\left( {n_v^4{{\log }^4}\left( {{n_v}} \right)\log (N)} \right)O(nv4​log4(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.
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.
In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasicyclic (QC) LDPC codes. We prove that for a random bipartite graph, with a given (irregular) degree distribution, the distributions of cycles of different length tend to independent Poisson distributions, as the size of the graph tends to infinity. We derive asymptotic upper and lower bounds on the expected values of the Poisson distributions that are independent of the size of the graph, and only depend on the degree distribution and the cycle length. For a random lift of a bi-regular protograph, we prove that the asymptotic cycle distributions are essentially the same as those of random bipartite graphs as long as the degree distributions are identical. For random QC-LDPC codes, however, we show that the cycle distribution can be quite different from the other two categories. In particular, depending on the protograph and the value of c, the expected number of cycles of length c, in this case, can be either 8(N) or 8(1), where N is the lifting degree (code length). We also provide numerical results that match our theoretical derivations. Our results provide a theoretical foundation for emperical results that were reported in the literature but were not well-justified. They can also be used for the analysis and design of LDPC codes and associated algorithms that are based on cycles.
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.
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.
LDPC codes based on multi-edge protographs potentially have larger minimum distances compared to their counterparts, single-edge protographs. However, considering different features of their Tanner graph, such as short cycles, girth and other graphical structures, is harder than for Tanner graphs from single-edge protographs. Here, we provide a novel approach to construct the parity-check matrix of an LDPC code which is based on trades obtained from block designs. We employ our method to construct multi-edge quasi-cyclic (QC) LDPC codes.We use those trade-based matrices to define base matrices of multi-edge protographs. The construction of exponent matrices corresponding to these base matrices has less complexity than the ones proposed in the literature. We prove that these base matrices result in QC-LDPC codes with smaller lower bounds on the lifting degree than existing ones.
Tanner quasi-cyclic low-density parity-check (QC-LDPC) codes form an important family of structured LDPC codes with favorable girth properties. This paper studies the girth of Tanner (2, L)-regular QC-LDPC codes (referred to as Tanner QC-LDPC cycle codes) for arbitrary integers L>2 and develops a novel algebraic number theoretic method to determine the girth for all sufficiently large primes p with p≡1(mod2L). We first analyze the case L=3 and prove that the girth is 12 for every prime p≡1(mod6) through exhaustive resultant computations. We then extend the method to arbitrary L and obtain a clear classification: when L is even, the girth is exactly 8 for all admissible primes; when L is odd, the girth attains the maximum value 12 for all sufficiently large admissible primes. The proof transforms cycle existence conditions into polynomial equations and applies resultant theory. This approach converts the infinite task of checking all primes into a finite set of algebraic checks. Numerical simulations show that the Tanner (2, 5)-regular non-binary code over GF(64) achieves a coding gain of approximately 0.2 dB over the 5G LDPC code of equivalent binary length.