those developed by the Consultative Committee for Space Data System (CCSDS) [2]. The subensemble of quasi-cyclic LDPC (QC-LDPC) codes is attractive for both implementation and analysis purposes since its members can be described in a compact and simple way [3], [4]. It is well-known that the structure of QC-LDPC codes, and the graph representation of an LDPC code in general, plays a fundamental role in determining the performance of the code under iterative decoding algorithms. In fact, the girth [5], together with the number of short cycles [6], and other graphical structures composed of short cycles, such as trapping sets [7], are important parameters to measure the iterative decoding performance of the code. As a consequence, researchers have been actively trying to find ways to not only reduce but eliminate, when possible, all the short cycles in a graph [8], and/or combinations of those cycles [7], [9], [10], in an attempt to improve the performance of the corresponding code.

It is well-known that enumerating the k-cycles in a general graph is hard [11], [12]. Consequently, a lot of effort has been dedicated to reduce the complexity of solving these problems.

Several algorithms have been designed for cycle enumeration with complexities depending on the number of vertices, the number of edges, and the number of cycles. For a graph G = (V, E) with set of vertices V and set of edges E, having cardinalities |V | and |E|, respectively, there are some well-known algorithms designed to enumerate its cycles, including the Tarjan algorithm [13] and the Johnson algorithm [14]. The complexities of these algorithms are O (|V ||E|(c + 1))

and O ((|V | + |E|)(c + 1)), respectively, where c is the number of cycles. Other approaches, which will be elaborated upon below, focus on particular families of graphs and on specific members of these families, like the family of bipartite graphs and, some of its members, the Tanner graphs of QC-LDPC codes, for example.

The topic of enumerating cycles in a bipartite graph G = (V, E), where V = V c ∪ V s is the set of vertices, V c and V s are the sets of check nodes and variable nodes, respectively, having cardinalities |V c | and |V s |, respectively, has a rich literature. In [6], an algorithm is presented to count k-cycles, k = g, g + 2, g + 4, in a bipartite graph with complexity growing as O (gn 3 ), where g is the girth of G (the length of a shortest cycle in G) and n = max (|V c |, |V s |). In [15], a message-passing algorithm for counting short cycles in a graph is presented. This algorithm is capable of counting k-cycles, with g ≤ k ≤ 2g -2, in the case of bipartite graphs, with complexity growing as O g|E| 2 . In [16], a matrix of size 2|E| × 2|E|, called the directed edge matrix, is constructed and used to count the number of short cycles. This strategy requires to calculate the trace of the kth power of this matrix or, equivalently, the eigenvalues of the kth power of the adjacency matrix. Such an approach has complexity O |E| 3 and becomes prohibitively high with an increase in the size of the Tanner graph.

In more recent works, a computational technique is presented in [8] to determine the numbers of g-cycles in a (c + 1, d + 1)-bi-regular bipartite graph from its adjacency matrix is given. These results were extended in [17], providing a strategy to compute the multiplicity of k-cycles, g + 2 ≤ k ≤ 2g -2, in bi-regular bipartite graphs, as a function of the spectrum and the node degrees (the number of neighbors connected to the nodes). This work also contains closed form equations for the multiplicity of 4-cycles and 6-cycles in irregular bipartite graphs. In [18], a technique/algorithm based on a modified breadth-first search (BFS) algorithm, which establishes parent/child relationships between the nodes in the graph depending on their distance from the source node, is proposed to count the short cycles of a bipartite graph. This approach has a time complexity of O |V | 2 ∆ to count g-cycles and (g + 2)-cycles, and a time complexity of O |V | 2 ∆ 2 to count (g + 4)-cycles, where ∆ is the maximum node degree in the graph.

If a graph has a specific structure, such as a quasi-cyclic representation, then it is possible to reduce the complexity of enumerating their cycles by exploiting said structure. The directed edge matrix approach discussed in [16] was further analyzed in [19] in the case of QC-LDPC codes.

In this approach, the authors proved that if the LDPC code is quasi-cyclic, then its directed edge matrix can be written as an array of circulant matrices. By exploiting the circulant structure to compute the eigenvalues as in [20], the complexity of this approach is reduced from O N 3 In this paper, we present an efficient strategy to count the number of k-cycles, k < 2g, in the Tanner graph of QC-LDPC codes having girth g. This strategy, which works for both (d v , d c )regular and irregular QC-LDPC codes, is formally analyzed from a complexity perspective in the case of the 3 × n v fully-connected (all-ones) protograph, and exemplified to count cycles using an irregular protograph used in the CCSDS standards [2]. Our approach has low complexity, shown to be depending logarithmically on the lifting factor N . Additionally, we illustrate how we can easily generalize the strategy for the n c × n v case, with n c > 3, maintaining the same low complexity. To the best of our knowledge, no such approach has been presented with such low complexity, even though it is well known to use modulo operations to determine cycles in a QC-LDPC graph [21], [22]. Consequently, this gives our approach a significant advantage over September 12, 2023 DRAFT any previous work on the cycle distribution of QC-LDPC codes.

This paper is structured in the following way. In Section II, we introduce the necessary definitions, notation and background. In Section III, we define an equivalence of closed walks, that applies to TBC walks, to provide a general formula to count the number of k-cycles, N k , for From the parity-check matrix H, we construct a bipartite graph G = (V, E), called a Tanner graph [24], by considering H as its biadjacency matrix. This bipartite graph represents the QC-

of vertices and edges such that e l = (v l-1 , v l ) ∈ E for all 1 ≤ l ≤ m. The first vertex appearing in the alternating sequence, v 0 , is called the base point of W . A walk W is said to be closed if the two endpoints are the same, this is, when v 0 = v m . A closed walk W is backtrackless if e l = e l+1 for all l = 1, 2, . . . , m -1. A backtrackless closed walk W is tailless if e m = e 1 , and W is called, in this case, a TBC walk. A cycle is a closed walk W having distinct vertices and distinct edges, and if its alternating sequence has k edges in it, then we call W a k-cycle. The length of a shortest cycle is called the girth of the graph.

The adjacency matrix A = (A ij ) is the symmetric binary matrix with

and A ij = 0 otherwise. After some reordering of the vertices, if necessary, we can write A, for either the scalar or polynomial representation of H, in the compact expression

where H T denotes the transpose of H. The powers of A, and in particular the matrices

give information about the walks [25]. It is not difficult to see that, for any nonnegative integer t, we have

Since G is a bipartite graph, any k-cycle has even length, so k = 2m for some m. We can form a walk of length k, or simply a k-walk, by taking the union of two walks of length m having the same two endpoints. If all the vertices and edges traversed in this k-walk are distinct, then the k-walk is a k-cycle. For example, if k = 4, then any 4-cycle is formed by the union of two different walks of length 2 having the same two endpoints. We can count the number of walks of length 2 between any two vertices by calculating the square of the adjacency matrix A. For

The equation ( 4) gives the number of walks of length 2 between vertices v i and v j since we have two edges joining v i to v l to v j whenever A il = A lj = 1. This argument was generalized in the following theorem.

September 12, 2023 DRAFT Theorem 1 ( [26]). If A m = ((A m ) ij ) is the mth power of the adjacency matrix A, then the entry (A m ) ij is equal to the number of walks of length m between the vertices v i and v j .

The polynomial representation of QC-LDPC codes allows for a reduction in the complexity of our computations, so we will work with the polynomial parity-check matrix rather than with its scalar version. First, we consider the triangle operator introduced in [25

The kth power of the scalar adjacency matrix A of the Tanner graph can be used to determine the number of k-walks between any two vertices, as we have seen in Theorem 1. The kth power of the polynomial version of the adjacency matrix, however, does not help us to count the number of k-walks between any two vertices of the Tanner graph, but, as we will see, it can be used to describe the edges traversed in a k-walk between any two vertices in the protograph. For example, if A is the polynomial version of the adjacency matrix (1), then

and every term of the polynomial (A 2 ) ij (x) is a product of the form x c il x c lj = x c il +c lj , where

x c il and x c lj come from the polynomials A il (x) and A lj (x), respectively. Each one of the two circulants x c il and x c lj correspond to a unique edge in the protograph, and the order in which they appear in the product is the order used to traverse the walk in the protograph. The exponent c il + c lj , in consequence, corresponds to the two edges traversed from vertex v i to vertex v l to vertex v j in the protograph. In the same way, every term of (A 3 ) ij (x) is a product of the form x c il x c lk x c kj = x c il +c lk +c kj , and the exponent c il + c lk + c kj corresponds to the three edges traversed in the protograph from vertex v i to vertex v l to vertex v k to vertex v j . In general, them corresponds to a walk of length m and the specific order in which it is traversed, which is nicely described by the way the matrix multiplication in (3) is performed. This allows us to state a polynomial version of Theorem 1.

is the mth power of the polynomial adjacency matrix A, then every term of the polynomial (A m ) ij (x) is of the form x c il 1 x c l 1 l 2 • • • x c lmj and corresponds to a walk of length m between the vertices v i and v j in the protograph.

in Theorem 3 is called a permutation shift.

scribing two m-walks between vertices v i and v j in the protograph, then the combination

of the first walk and the reversal of the second one describes a closed (2m)-walk that starts and ends at the vertex v i , and that has the vertex v j midway. Hence, the entries (A m ) ij (x) of the power A m describe all the m-walks in the protograph and can be used to count certain cycles in the Tanner graph. The strategy of counting cycles in the Tanner graph presented in this paper requires to keep track of TBC walks in the protograph. This is why we are interested in analyzing the way each walk is traversed. First, we introduce some required concepts on graph covers.

At the beginning of this section, we explained the process to construct a Tanner graph from a protograph. In the sequel, we will need a little more mathematical accuracy, so we define the lifting process from a topological point of view. Let G = (V, E) be a protograph described by Lemmas 5 and 7, based on some results from [27], are useful to study both the images of cycles in the Tanner graph and the preimages of TBC walks in the protograph.

Lemma 5 ([28], [29]). Let G be an N -fold graph cover of the protograph G. Let W be a k-walk in G starting at vertex v and ending at vertex v , and having edge sequence e 1 , e 2 , . . . , e k with associated circulant permutation matrices x s 1 , x s 2 , . . . , x s k . Then the permutation shift s that maps ṽ, the inverse image of v in G, to ṽ , the inverse image of v in G, through the walk W is given by

Remark 6. If the walk W in Lemma 5 is traversed in the opposite direction starting at vertex v and ending at vertex v, then its permutation shift is given by s = N -s mod N .

We denote by Z N the additive group of integers modulo N . For any element a ∈ Z N , the order of a is the smallest integer m such that a m = m • a = 0.

). Let G be an N -fold graph cover of the protograph G and let W be a k-cycle in G. Then W is projected onto a TBC walk W of length k/m, where m ≥ 1 is the order of the permutation shift of W in Z N .

Remark 8. The order of a TBC walk W , which is referred to as the order of its permutation shift s in the previous lemmas when considered as an element of Z N , is given by N/ gcd (N, s),

where s is as in (6) and gcd denotes the greatest common divisor.

We combine the following lemma with our analysis of TBC walk to count cycles in the Tanner graph.

). Let G be an N -fold graph cover of the protograph G and let W be a closed k-walk in G. Then the inverse image of W in G is the union of N/m closed (km)-walks, where m ≥ 1 is the order of the permutation shift of W in Z N .

We extend the result in Lemma 9, stated for closed k-walks, to TBC walks of length k. and ẽ km , which are consecutive edges in W , are equal, then their projection onto G will give the same edge, again contradicting the assumption that W is backtrackless. This concludes the proof.

The following lemma explain why we restrict our analysis to k-cycles with k < 2g, where g is the girth of the Tanner graph. Lemma 11 ([15]). Let G be a graph with girth g. Then the set of TBC walks of length k coincides with the set of k-cycles if k < 2g.

Notice that the set of TBC walks of length k and the set of k-cycles are not equal if k ≥ 2g.

For the case when k = 2g, let W be a g-cycle. The double traversal of W , denoted by W 2 , is a TBC walk of length 2g, but it is not a (2g)-cycle because the intermediate vertices are not distinct. For k > 2g, a similar argument is used. However, even if f does divide N , there are instances where the set W (d, f ) is automatically empty. If the protograph is the n c × n v fully-connected (all-ones), it is not possible to obtain a TBC walk of length 4 from the double traversal of a walk of length 2, forcing W (2, f ) to be empty. If the protograph is a multiedge graph, as we will discuss later, then it is possible to have a nonempty set W (2, f ).

The following theorem gives the number of k-cycles in the Tanner graph using the walks described by the entries of the polynomial parity-check matrix H. corresponding Tanner graph G with parity-check matrix H is given by

where N is the lifting factor.

Proof: Suppose that H has girth g. By Lemma 7, any k-cycle W in the Tanner graph projects onto a (naturally shortest) TBC walk W of length d having permutation shift of order k/d in Z N . Hence, to count the number of k-cycles in the Tanner graph, it is enough to count the TBC walks that will be lifted to k-cycles.

Let W be a k-cycle in the Tanner graph and let W be its projection, a TBC walk of length N k . In this section, we focus on the fully-connected (all-ones) protograph and discuss how to determine N k with a strategy that has complexity logarithmic on the lifting factor N . We show that this involves determining the cardinality of the sets W (d, f ), for integers d ≥ 0 and f ≥ 1, in a simple way. We note that, by studying the all-ones protograph, we also have the framework for any binary (regular or irregular) protograph because "masking" (replacing ones with zeros) [31] makes the problem simpler since various exponents are removed from the calculation. In Section VI, we show how to extend the approach to general (non-binary) protographs.

Let C be a QC-LDPC code with parity check matrix H given by

where

In numerical examples, we can assume, without loss of generality, that l 0,j = l i,0 = 0 for i ∈ [n c ] and j ∈ [n v ], as a way to reduce the complexity of the computations. In the theoretical results, however, we do not automatically set them to 0 in order to analyze TBC walk patterns in detail.

Consider the following definition.

Definition 17. A multiset (shortened to mset) is a collection of elements in which elements are allowed to repeat. The number of times an element occurs in a multiset is called its multiplicity.

The cardinality of a multiset is the sum of the multiplicities of its elements.

By Theorem 2, following the discussion in [32], girth(H) > 4 if and only if each one of the nc

If one of these msets has a repeated element (a repetition), some 4-cycles appears in the Tanner graph and the exact amount of them is calculated in the following theorem.

Theorem 18. Let H be as in (8). A repetition in any of the following nc

lifts to exactly N 4-cycles in the Tanner graph. The total number of 4-cycles in the Tanner graph, N 4 , is given by

DRAFT September 12, 2023 where W (4, 1) is the set of all nonequivalent TBC walks associated to the repetitions in the msets above.

Proof: The msets

, describe all nonequivalent walks of length 2 in the matrix H. A repetition in any of the msets gives a TBC walk of length 4 with

. By Theorem 10, this TBC walk lifts to N 4-cycles. The same approach works for all the other msets and, by letting W (4, 1) be the set of all nonequivalent TBC walks associated to the repetitions, the result follows.

Example 19. Let H be the polynomial parity-check matrix given by

This matrix has girth 4 for lifting factor N = 5. Calculating the three msets in Theorem 18 over Z 5 , we obtain A 0,1 = {0, 4, 3, 2, 1}, A 0,2 = {0, 3, 4, 0, 3}, and A 1,2 = {0, 4, 1, 3, 2}. Notice that there are two repetitions in the second mset, so there are two elements in W (4, 1), specifically

Hence, the number of 4-cycles N 4 in the Tanner

If we take N = 10, then the parity-check matrix H has girth 6. To confirm that there is no 4-cycle in H, we calculate the three msets in Theorem 18 over Z 10 and we obtain A 0,1 = {0, 9, 8, 7, 6}, A 0,2 = {0, 8, 9, 5, 3}, and A 1,2 = {0, 9, 1, 8, 7}.

Since there is no repetition in these msets, we conclude that N 4 = 0.

Remark 20. Theorem 18 was used to calculate the number of elements in W (4, 1), but the strategy can be modified in a straightforward way to count the number of elements in W (4, 2).

In this case, we are not simply targeting repetitions in the msets A i,i . Instead, we are looking for two elements α l and α l with α l = α l , coming from the same mset, such that 2

The double traversal of the TBC walk that corresponds to the permutation shift α l -α l is an element of W (4, 2). This approach is used to compute W (4, s), for any s, by requiring

September 12, 2023 DRAFT

In the rest of the section, for space constraints, we will take n c = 3 in (8), so H is given by

By Theorem 2, as discussed in [32], girth(H) > 6 if and only if, for m ∈ [n v ] and l ∈ [n v ]\{m}, all the elements in each one of the msets

are distinct. In the following theorem, we rewrite these conditions in a way that is helpful to count 6-cycles in the Tanner graph.

Theorem 21. Let H be as in (10) and, for m ∈ [n v ], consider the following msets

where W (6, 1) is the set of all nonequivalent TBC walks associated to the repetitions in one of the pairs above, and

where R A 1,m ,A 2,m is the number of repetitions α l = α l between the msets A 1,m and A 2,m .

Proof: Suppose that there is a repetition in the pair A 1,m , A 2,m as in the statement. Then, for

we use the shorthand [h α 1 , h α 2 , . . . , h α k ] β 1 ,β 2 ,...,βm . If W has length k = 2m + 1 and its permutation shift is given by

we use the shorthand

By Theorem 2, as discussed in [32], girth(H) > 8 if and only if the following nine equations are satisfied:

x [h,j,j,i] u,v 0 = 0,

x [i,h,h,j] x [i,j,j,h] u,v 0 = 0,

x [j,h,h,i] u,v 0 = 0.

The exponents of the circulants in each one of these equations describe the walks of length 4 in the protograph, and these are the walks that we study to form the TBC walks of length 8 that can lift to 8-cycles in the Tanner graph. For example, there are two exponents in the first equation, namely [h, i, i, h] u,v and [h, j, j, h] u,v , and they give three possible TBC walk patterns:

Notice that each of these three 8-walks is a TBC walk if the conditions

and u = u are satisfied. Once all the TBC walk patterns have been constructed, from all the nine equations above, the next task is to eliminate duplicates. The following list contains all 6 nonequivalent TBC walk patterns obtained from the equations above:

In the following theorem, we rewrite these conditions in a way that is helpful to count 8-cycles in the Tanner graph.

Theorem 24. Let H be as in (10) and, for u, v ∈ [n v ] with u = v, consider the following msets

Then this repetition α u,v = α u ,v lifts to a collection of 8-cycles in the Tanner graph if u = u and v = v . The same result follows if the pair A 1,1 , A 1,2 is replaced by any of the other five pairs.

Moreover, these six pairs are sufficient to describe all 8-cycles. The total number of 8-cycles in the Tanner graph, N 8 , is given by

September 12, 2023 DRAFT

where W (8, 1) is the set of all nonequivalent TBC walks associated to the repetitions in the msets above and W (4, 2) is the set of all nonequivalent TBC walks of length 4 having permutation shift of order 2 in Z N . The cardinality of W (8, 1) is given by

where R X 1 ,X 2 is the number of repetitions α u,v = α u ,v between the msets X 1 and X 2 , the coefficient of each R X 1 ,X 2 is coming from the number of equivalent walks for the corresponding

and R * c X 1 ,X 2 and R * nc X 1 ,X 2 are the numbers of repetitions α u,v = α u ,v between the msets X 1 and X 2 satisfying and not satisfying the conditions u = v and v = u, respectively.

Proof: To show that a repetition in any of these pairs lifts to a collection of 8-cycles in the Tanner graph, we proceed as before. Consider a repetition in the pair A 1,1 , A 1,2 , so there are

Then this is equivalent to [h, i, i, h, h, i, i, h] u,v,v ,u = 0 in Z N . To guarantee that this permutation shift represents a TBC walk, in addition to the conditions u = v and u = v required in the construction of the msets A 1,1 and A 1,2 , respectively, we need to ensure that u = u and v = v . By Theorem 10, this TBC walk lifts to a collection of 8-cycles. The same approach works for the remaining pairs. The proof that these msets are sufficient to describe all 8-cycles was addressed before the statement of the theorem.

The formula for N 8 in (15) follows from equation (7) in Theorem 16. It remains to show that |W (8, 1)| is given by (16). Once a TBC walk pattern is fixed, say [h, i, i, h, h, j, j, h] u,v,v ,u for some u, v, u , v ∈ [n v ], it is possible that at least one of its equivalent walks has the same pattern. In this case, there is only one equivalent walk with the same TBC walk pattern and it has permutation shift [h, i, i, h, h, j, j, h] v,u,u ,v . Hence, when analyzing the contribution of the repetitions in the pair A 2,1 , A 2,2 to the set W (8, 1), we have to divide the total number of repetitions by the number of equivalent expressions for the TBC walk pattern, which is 2 in this case. This is due to the fact that the tuples (u, v, v , u ) and (v, u, u , v ) are always distinct since we require u = v, v = v , v = u and u = u. If we do the same for all the nonequivalent TBC DRAFT September 12, 2023 walk patterns, we obtain the following equivalent walks:

In the case of the pairs A 4,1 , A

x x 2 x 4 x 8 x 16

x 5 x 10 x 20 x 9 x 18

x 25 x 19 x 7 x 14 x 28

Then H has girth 8 for N = 31. We use Theorem 24 to count the number of 8-cycles, N 8 , in the Tanner graph. Some computations show that

are distinct. Following the strategy used before, the elements in each one of these msets describe the walks of length 5 in the protograph, and these are the walks that we study to form the TBC walks of length 10 that can lift to 10-cycles in the Tanner graph. In the following theorem, we rewrite these conditions in a way that is helpful to count 10-cycles in the Tanner graph.

Theorem 26. Let H be as in (10) and, for u, v ∈ [n v ], with u = v and v = m, consider the following msets Moreover, these msets, running over all m ∈ [n v ], are sufficient to describe all 10-cycles. The total number of 10-cycles in the Tanner graph, N 10 , is given by

where W (10, 1) is the set of all TBC walks associated to the repetitions in the msets above, and

where R X 1,m ,X 2,m is the number of repetitions α u = α u between the msets X 1,m and X 2,m .

Proof: To show that a repetition in any of these msets lifts to a collection of 10-cycles in the Tanner graph, we proceed as before. Consider a repetition in the pair A 1,m , A 2,m , so there To prove that these pairs are sufficient to describe all 10-cycles in the Tanner graph, it is enough to analyze the three msets described in the calculation of the conditions. From the first mset

there are only 5 ways to form a TBC walk and these are given by the following TBC walk patterns:

The second pattern is equivalent to the first one by considering the assignment given by

The third pattern is not equivalent to the first one, and it is not difficult to see that since the circulants x i l and x j l are visited a different amount of times. The fourth pattern is equivalent to the first one by considering the assignment (as before) given by

The fifth pattern is not equivalent to the first one nor to the third one since the circulants x h l and x j l , and x h l and x i l , respectively, are visited a different amount of times. The same strategy is used to show that each TBC walk pattern described by the other two msets is equivalent to one of the three nonequivalent patterns described here. Hence, these three pairs, running over all m ∈ [n v ], are sufficient to describe all 10-cycles.

The formula for N 10 in ( 19) follows from equation ( 7) in Theorem 16. It remains to show that |W (10, 1)| is given by (20). Since the pairs X 1,m , X 2,m , with X ∈ {A, B, C} and running over all m ∈ [n v ], are sufficient to describe all the TBC walks of length 10, we used the three TBC walk patterns [h, i,

u,v,m,v ,u to construct all their equivalent walks. It turns out that none of the corresponding equivalent walks has any of this three TBC walk patterns, so each repetition is counted exactly once, and we conclude the proof.

Example 27. Let H be the parity-check matrix of the [155, 64, 20] Tanner code given by ( 18) in Example 25. We use Theorem 26 to count the number of 10-cycles in the Tanner graph. For each

In the following theorem, we rewrite these conditions in a way that is helpful to count 12-cycles in the Tanner graph.

Theorem 28. Let H be as in (10) and, for u, v, w ∈ [n v ] with u = v, v = w, consider the following msets

Let (u, v, w, α u,v,w ) ∈ A 1,1 and (u , v , w , α u ,v ,w ) ∈ A 1,2 be such that α u,v,w = α u ,v ,w . Then this repetition α u,v,w = α u ,v ,w lifts to a collection of 12-cycles in the Tanner graph if u = u and w = w . The same result follows if the pair A 1,1 , A 1,2 is replaced by any of the other pairs.

Moreover, these pairs are sufficient to describe all 12-cycles. The total number of 12-cycles in the Tanner graph, N 12 , is given by

where W (12, 1) is the set of all nonequivalent TBC walks associated to the repetitions in the msets above, and W (4, 3) and W (6, 2) are the sets of all nonequivalent TBC walks of length 4 and 6, respectively, having permutation shift of order 3 and 2 in Z N , respectively. The cardinality of W (12, 1) is given by

where R X 1 ,X 2 is the number of repetitions α u,v,w = α u ,v ,w between the msets X 1 and X 2 , the coefficient of each R X 1 ,X 2 is coming from the number of equivalent walks for the corresponding TBC walk pattern, R * A 2,1 ,A 2,2 is given by

are the numbers of repetitions α u,v,w = α u ,v ,w between the msets A 2,1 and A 2,2 satisfying, and not satisfying, the conditions u = w, v = v and w = u, respectively,

and, R * * c X 1 ,X 2 and R * * nc X 1 ,X 2 are the numbers of repetitions α u,v,w = α u ,v ,w between the msets X 1 and X 2 satisfying, and not satisfying, the conditions u = v, v = u = w and w = v, respectively.

Proof: To show that a repetition in any of these pairs lifts to a collection of 12-cycles in the Tanner graph, we proceed as before. Consider a repetition in the pair A 1,1 , A 1,2 , so there are

] u,v,w,w ,v ,u = 0 in Z N . To guarantee that this permutation shift represents a TBC walk, additionally to the conditions u = v and v = w, and u = v and v = w required in the construction of the msets A 1,1 and

, respectively, we need to ensure that u = u and w = w . By Theorem 10, this TBC walk lifts to a collection of 12-cycles. The same approach works for the remaining pairs. The proof that these msets are sufficient to describe all 12-cycles was addressed before the statement of the theorem.

The formula for N 12 in (21) follows from equation ( 7) in Theorem 16. It remains to show that |W (12, 1)| is given by (22). If for each nonequivalent TBC walk pattern we find the equivalent walks, then we obtain the following:

Recall that once we choose a TBC walk pattern W having permutation shift [W ] u,v,w,w ,v ,u , we need to impose the conditions u = v, v = w, w = w , w = v , v = u , and u = u to make it a TBC walk. For the pair A m,1 , A m,2 with m ∈ {1, 6, 8, 12}, the two tuples of indices (u, v, w, w , v , u ) and (u , v , w , w, v, u) are always distinct, otherwise we will have u = u and w = w. Hence, every TBC walk having this TBC walk pattern is always counted twice. The same situation happens in the following pairs and tuples of indices:

• pair A 4,1 , A 4,2 and tuples of indices (u, v, w, w , v , u ), (w , w, v, u, u , v ); and

• pair A m,1 , A m,2 with m ∈ {5, 7, 9, 11} and tuples of indices (u, v, w, w , v , u ), (v, u, u , v , w , w).

For the pair A 2,1 , A 2,2 , the two tuples of indices (u, v, w, w , v , u ) and (w , v , u , u, v, w) are not always distinct. There are two possible scenarios: either u = w, v = v and w = u, which gives only one distinct tuple, or the two tuples are distinct. The total contribution coming from the first scenario is taken as it is, and the total contribution coming from the second scenario should be divided by 2. The case is different for the pairs A 3,1 , A 3,2 , A 10,1 , A 10,2 and A 13,1 , A 13,2 . The six tuples (u, v,

and (u , v , w , w, v, u) are not necessarily distinct. In fact, there are two possible scenarios: either u = v, v = u = w and w = v, which gives only two distinct tuples, or the six tuples are all distinct. The total contribution coming from the first scenario should be divided by 2, and the total contribution coming from the second scenario should be divided by 6. This analysis concludes the proof.

Example 29. Let H be the parity-check matrix of the [155, 64, 20] Tanner code given by (18) in Example 25. We use Theorem 28 to count the number of 12-cycles in the Tanner graph. Remark 30. The Tanner graph of a QC-LDPC code based on the n c × n v fully-connected protograph, with 2 ≤ n c < n v , has girth at most 12 [33]. Hence, equation (7) can be used to count cycles of length up to 22. For space constraints, we are not including the analysis to September 12, 2023 DRAFT determine N k with k = 14, 16, 18, 20, 22, although similar expressions and algorithms can be obtained in the same way.

In this section, we determine the complexity of our approach and compare it to other results in the literature. Let H be the parity-check matrix of a QC-LDPC code given in (10) and let N be the lifting factor. The following analysis is performed for the 3 × n v fully-connected protograph, but it is not difficult to see that a generalization of our strategy for the n c × n v fully-connected protograph, with n c > 3, having Theorem 18 as a reference, involves the same complexity, with the exception that more msets should be calculated.

In Theorem 18, to count the number of 4-cycles in the Tanner graph, we need to construct the nc 2 = nc(nc-1)

, and check for repetitions in each one of them. Since each mset has n v elements, it is sufficient to do (nv-1)nv 2 comparisons in each one of them. This implies that the complexity of determining N 4 is O(n 2 v log(N )). To count the number of 6-cycles in the Tanner graph using Theorem 21, we need to construct one pair of msets

m and (l , α l ) ∈ A 2,m for some l, l ∈ [n v ], we are interested in repetitions α l = α l such that l = l . This implies that the complexity of determining N 6 is O(n 2 v log(n v ) log(N )). To determine the complexity of counting 8-cycles in the Tanner graph, we proceed as before and use Theorem 24 and, in particular, equations (15) and (16). In this case, we need to construct the six pairs X 1 , X 2 in Theorem 24. Each one of these msets has n v (n v -1) elements. If Theorem 28 and, in particular, equations ( 21) and (22), are used to count the number of 12cycles in the Tanner graph. In this case, we need to construct the thirteen pairs of msets X 1 , X 2

given in the statement of the theorem. For u, v, w, u , v , w ∈ [n v ], we want to identify tuples

and α u,v,w = α u ,v ,w . To construct each α u,v,w and α u ,v ,w , we need to choose three indices.

The worst case scenario happens when determining the value R * * X 1 ,X 2 in equation ( 22), where we need to check whether u = v, v = u = w, and w = v is true or false. When combined, this has complexity O(n 6 v log 6 (n v ) log(N )).

Although omitted for space constraints, an argument similar to the analysis above can be used to conclude that the complexity of determining N k is upper-bounded by O(n

if k = 14, 18 and 22, and O(n

and 20. We recall that the reason to limit our analysis to k ≤ 22, in the case of the fully-connected protograph, follows from Lemma 11 and Remark 30. For the general case, if the protograph is any graph described by the base matrix B = (b ij ) nc×nv , where we allow the protograph to be a multi-edge graph, a similar analysis can be used. The weight of the ith row of B, denoted by B row (i) , is given by B

Let w row denote the maximum row weight of B, so w row = max i∈[nc] B row (i) . In the worst-case scenario, the complexity of determining N k , k < 2g, is given by O(w k/2 row log k/2 (w row ) log(N )).

To show how fast we can calculate the number of k-cycles, N k , in the Tanner graph of a QC-LDPC code, we include some tables. Table I shows the number of k-cycles for the parity-check matrix H in Example 25 for lifting factor N . For the same parity-check matrix H, in Table II, we provide the time taken to count the number of k-cycles using our algorithms. The computations were done using SageMath [34] in a MacBook Pro (13-inch, 2018, Four Thunderbolt 3 Ports) with a 2.3 GHz Quad-Core Intel Core i5 processor and 16 GB 2133 MHz LPDDR3 of memory.

In Section IV, we analyzed how to count the number of k-cycles, 4 ≤ k ≤ 12, in a Tanner graph lifted from the fully-connected (all-ones) protograph using a description of the TBC walks in the protograph. The strategy of using the TBC walks to count k-cycles in the Tanner graph only works when k < 2g. In this section, we apply this strategy to an irregular protograph. Consider the QC-LDPC code having parity-check matrix H given by

Since we are interested in studying the cycle structure of this protograph, we will apply the same strategy used in Section IV. To do this, we use again Theorem 2 and the product HH T .

Notice that HH T = 8I + C H , where the entries (C H ) ij of the matrix C H are given by

As

However, the combination of two of them does not guarantee the appearance of 4-cycles in the Tanner because they may not be describing a TBC walk in the protograph. For example, combining h 1 -i 1 and h 2 -i 1 gives a walk of length 4 having permutation shift h 1 -i 1 + i 1 -h 2 , which is not a TBC walk because the circulant x i 1 is traversed twice (in opposite directions) consecutively in a row. If the second walk is h 3 -i 2 instead, then we have a TBC walk with permutation shift h 1 -i 1 + i 2 -h 3 that lifts to a collection of 4-cycles in the Tanner graph if its value is 0 in Z N . There are 160 nonequivalent TBC walks obtained in this fashion and we use them to count 4-cycles in the Tanner graph.

Theorem 31. Let H be as in (26). Then there are 160 nonequivalent TBC walks of length 4. Remark 32. There is a noticeable difference between the formulas in ( 9) and ( 27) for the number of 4-cycles, N 4 , in the cases of the fully-connected (all-ones) protograph and the irregular protograph in this section, respectively. In the first case, we cannot have a TBC walk of length 2 in the protograph because any pair of check and variable nodes have at most one edge joining them. This requires any TBC walk to have length at least 4 taking into account that the protograph is a bipartite graph. In the second case, it is possible to have a TBC walk of length 2 since there are some pairs of check and variable nodes with two edges joining them.

Example 33. Let H be as in (25) and let the lifting factor be N = 16. Then H has girth 6, so the number of 4-cycles, N 4 , is 0 and we can verify this in the following way. Some computations show that there are no TBC walk of length 2 having permutation shift of order 2 in Z 16 , and that none of the TBC walks of length 4 described in Theorem 31 have permutation shift 0 in Z 16 .

Hence, the number of 4-cycles, N 4 , in the Tanner graph is In the following example, we apply the strategy used before to count k-cycles, k > 4, in another parity-check matrix H based on (26). The formulas for N k should be adapted for the irregular protograph as we did in (27).

Example 34. For lifting factor N = 64, consider the parity-check matrix H given by Since these expressions are congruent to 0 modulo 64, and there are 14 of them, then there are