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.
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.
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.
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.
One of the most efficient approaches to improving the frame error rate (FER) performance of low-density parity-check (LDPC) codes is based on adding both auxiliary variable nodes (AVN) and the corresponding redundant parity checks (RPC) to the binary parity-check matrices of the code. It is known that for the LDPC codes, whose Tanner graphs contain length four cycles, this technique allows for substantial improvement in the FER performance of the belief-propagation (BP) decoding on the binary erasure channel (BEC) channel. The AVN-based technique followed by adding orthogonal redundant parity-checks is known to be efficient for both the BEC and additive white Gaussian noise (AWGN) channels. In this paper, firstly, the AVN-based approach is generalized to efficiently removing cycles of length larger than four. Secondly, the AVN-based technique is reformulated in terms of labeled base matrices of quasi-cyclic (QC) LDPC codes. An improved iterative decoding of QC LDPC codes is proposed, which is applied to the labeled base matrices of QC LDPC codes extended by the AVN-RPC technique.
Bivariate bicycle (BB) codes of Bravyi \emph{et al.}~\cite{Bravyi2024} are quantum low-density parity-check codes with weight-6 checks, exemplified by [[144,12,12]] with kd2/n=12. We develop the algebraic structure theory of BB-type codes with weight-8 checks (weight-4 generator polynomials) and use it, together with an exactly validated search pipeline, to construct and certify new codes. We prove an exact dimension formula k=2dimR/(A,B) (forcing even k), a 4ℓm-element symmetry group on generator pairs, an X/Z distance equality dX=dZ, and a family of subgroup-coset kernel vectors giving rigorous distance upper bounds and a design rule for high-distance constructions; all distances are computed exhaustively by a cross-validated bit-mask verifier. At n=144 the pipeline returns a census of 53 codes whose strongest members surpass the BB benchmark: [[144,6,d≥15]] exceeds the benchmark distance 12 (certified d≥15), [[144,10,12]] reaches it with weight-8 checks, and [[144,16,10]] encodes a third more logical qubits at kd2/n=11.11 (7.4% below benchmark) while decoding no worse. At n=72, [[72,14,8]] attains kd2/n=12.44---more than twice the same-length BB code---and decodes better; a circuit-level memory experiment places our weight-8 codes at ≈0.1% pseudo-threshold versus ≈0.4% for the BB reference under an identical model, quantifying the threshold cost of the heavier checks. All structural statements are verified numerically on the whole census.
The finite-length performance of quantum low-density parity-check (LDPC) codes under iterative decoding is governed by small substructures of the Tanner graph, principally short cycles and absorbing sets. While the classical theory of these substructures for quasi-cyclic codes is well developed through discrete Fourier transform (DFT) methods, these tools do not directly address the two-block tensor structure HX=[H1∣I⊗BT] of the lifted-product (quasi-cyclic generalised hypergraph product, QC-GHP) codes that dominate current quantum LDPC constructions. In this paper we develop a quantum-specific spectral framework that exploits this structure. At its core is a DFT block-diagonalisation of HXHXT that reduces moment-trace and cycle computations from an (r1ℓ)×(r1ℓ) matrix to a sum of ℓ small r1×r1 Hermitian matrices, with the second block entering only as a scalar shift. From this result we derive a closed-form 4-cycle count for generalised bicycle codes via additive energies, a joint Sidon characterisation of girth 6 in the spirit of Fossorier's classical criterion, a Fourier expression for the number of (3,3) elementary absorbing sets in column-weight-3 codes via the Wang-Dolecek-Wesel triangle bijection, and a lower bound on stopping-set sizes using the expander mixing lemma.
Short cycles have an important influence on iterative decoding for low-density parity-check(LDPC) codes.By using tree expanding of Tanner graphs and the analysis of the influence of invalid cycles and duplicate cycles,a formula for counting short cycles of LDPC codes is derived.With the derived formula,an algorithm for counting short cycles of Tanner graphs based on tree expanding is proposed.The proposed algorithm can count short cycles with arbitrary lengths,and thus overcomes the disadvantage of existing algorithms that count short cycles with given lengths.Numerical results of counting short cycles of some typical LDPC codes show the correctness of the proposed algorithm.