Short cycles in the Tanner graph of a low-density parity-check (LDPC) code degrade belief-propagation decoding, and counting them is a standard task in code design. This paper does not count them faster. It counts them with a certificate: for each of the four LDPC codes of the IEEE 802.11n (WiFi) standard at block length n = 648, the number of shortest cycles is obtained from a machine-checked identity — the trace-formula gap law, proved sorry-free in Lean 4 in the companion paper (Part VI) — and cross-checked by three mutually independent computations that agree exactly: the non-backtracking trace tr(B^g)/2g, the gap law (tr(A^g) − p_g)/2g, and direct enumeration. The census reads c_6 = 3942 (rate 1/2), c_6 = 8046 (rate 2/3), c_4 = 54 (rate 3/4, where the girth collapses to 4) and c_6 = 32346 (rate 5/6), and it tells a design story: the rate-3/4 code pays for its density with four-cycles, the most damaging kind, while the rate-5/6 code buys its girth back at the price of thirty-two thousand hexagons. The counting algorithms of the coding-theory literature are faster and reach further; the contribution here is the certification layer — an exact identity backed by a theorem with a checkable proof — which, to the best of the author's knowledge, no prior cycle-counting tool carries. Applied companion to the godsil-gutman-lean series (Part VI). Census computed with AI assistance (Claude, Anthropic); the mathematics and all claims are the author's responsibility.
Short cycles in the Tanner graph of a low-density parity-check (LDPC) code degrade belief-propagation decoding, and counting them is a standard task in code design. This paper does not count them faster. It counts them with a certificate: for each of the four LDPC codes of the IEEE 802.11n (WiFi) standard at block length n = 648, the number of shortest cycles is obtained from a machine-checked identity — the trace-formula gap law, proved sorry-free in Lean 4 in the companion paper (Part VI) — and cross-checked by three mutually independent computations that agree exactly: the non-backtracking trace tr(B^g)/2g, the gap law (tr(A^g) − p_g)/2g, and direct enumeration. The census reads c_6 = 3942 (rate 1/2), c_6 = 8046 (rate 2/3), c_4 = 54 (rate 3/4, where the girth collapses to 4) and c_6 = 32346 (rate 5/6), and it tells a design story: the rate-3/4 code pays for its density with four-cycles, the most damaging kind, while the rate-5/6 code buys its girth back at the price of thirty-two thousand hexagons. The counting algorithms of the coding-theory literature are faster and reach further; the contribution here is the certification layer — an exact identity backed by a theorem with a checkable proof — which, to the best of the author's knowledge, no prior cycle-counting tool carries. Applied companion to the godsil-gutman-lean series (Part VI). Census computed with AI assistance (Claude, Anthropic); the mathematics and all claims are the author's responsibility.
Short cycles in the Tanner graph of a low-density parity-check (LDPC) code degrade belief-propagation (BP) decoding, and counting them is a standard step in code design and evaluation. This paper does not count them faster. It contributes a short-cycle diagnostic whose defining identity is a machine-checked theorem -- the trace-formula gap law tr(A^k) - p_k = tr(B^k), with A the adjacency matrix, B the Hashimoto non-backtracking operator and p_k the power sums of the matching-polynomial roots -- and whose per-code outputs are validated by three mutually independent computations that agree exactly. We report a certified census of the four deployed LDPC codes of the IEEE 802.11n (WiFi) standard at block length n=648, and, to our knowledge the first such diagnostic on a quantum LDPC code, of the IBM "gross code" [[144,12,12]] bivariate-bicycle (BB) code, finding girth 6 and c_6=144 shortest cycles. We then give a covering-tower factorization: a BB code whose Tanner graph is a double cover of a smaller code's Tanner graph inherits its short-cycle profile through the classical Artin-Ihara / 2-lift identity tr B^k(cover) = tr B^k(base) + tr B_s^k(base), verified exactly on the gross/[[72,12,6]] pair (c_6 doubles, 144 = 2*72). The contribution is the theorem-backed, cross-validated, reproducible methodology and its transfer from classical to quantum codes; the underlying mathematics is classical and is not claimed as new. We are explicit about what the certificate does and does not guarantee.
For a given block length sequences of the underlying Tanner graph (TG), the short circles of low-density parity check (LDPC) codes can have considerable variation in performance. By analyzing the shapes of the cycles of TG in parity check matrix, this paper presents a method of counting the number of 4-cycles, 6-cycles, 8-cycles and 10-cycles. Taking out a certain number of rows for different cycles, counting the number of cycles contained in these rows, then adding up all the number of cycles that contained in all possible combinations of the rows in the matrix, and we can get the number of cycles in the matrix. This method can be used effectively to evaluate the performance of LDPC codes according to their short circles distributions. Applying this method, we counting the number of cycles in the random LDPC codes and the quasi-cyclic LDPC codes, the BER performance shows that the random LDPC codes outperform the quasi-cyclic LDPC codes although their girth performance is not as good as the quasi-cyclic 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.
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, 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.
For a given block length sequence of the underlying Tanner graph (TG),the short circles of low-density parity check (LDPC) codes can have considerable variation in performance.By analyzing the shapes of the cycles of TG in parity check matrix,this paper presents a method of counting the number of 4-cycles,6-cycles,8-cycles and 10-cycles.Taking out a certain number of rows for different cycles,counting the number of cycles contained in these rows,then add up all the number of cycles that contained in all possi- ble combination of the rows in the matrix,and we can get the number of cycles in the matrix.This method can be used effectively to eval- uate the performance of LDPC codes according to their short circles distributions.Applying this method,we counting the number of cycles in the random LDPC codes and the quasi-cyclic LDPC codes,the BER performance shows that the random LDPC codes outperform the quasi-cyclic LDPC codes although it's girth performance is not as good as the quasi-cyclic LDPC codes.