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 · IEEE Journal on Selected Areas in Information Theory · 2023
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.