In this paper, a probabilistic analysis of the cycle distribution of protograph-based spatially coupled low-density parity-check (SC LDPC) codes is presented. In particular, we derive the probability that cycles of specific, but arbitrary, length are broken as a result of spatial coupling with a random spreading matrix in a general edge spreading process. Our results show that the probability of existence of cycles in SC codes is O(1/m), where m is the code memory. This result is independent of the cycle length.

In this paper, we propose a new technique, based on the so-called breadth-first search algorithm, to count the short cycles of a bipartite graph. For a general bipartite graph with |V| nodes and girth g, our technique 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. Moreover, for bi-regular bipartite graphs, the latter complexity is further reduced to O(|V|2Δ). Compared to the fastest known algorithm, which has a complexity O(g|V|2Δ2), the proposed method always has a lower complexity for counting g-cycles and (g + 2)-cycles. It also has a lower complexity for counting (g + 4)-cycles in bi-regular graphs and in scenarios where g is increased with the size of the graph. Related to the problem of counting short cycles, we also demonstrate, using a long-standing conjecture, that there is no algorithm with time complexity less than O(|V|2-2/1±i ) that can determine whether a given sparse bipartite graph has a cycle of length 4i. An important application of the results presented here is to count the short cycles of Tanner graphs of low-density parity-check (LDPC) codes.

The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for given integers α, β, and -y, and degree sequences π and π', the problem of determining whether there exists a simple bipartite graph with degree sequences (π, π') that has at most α (β and -y) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence π, a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is π and has a girth of at least six. In addition to these complexity results, we devise a quasi-polynomial time algorithm that can construct a bipartite graph with given (irregular) degree sequences and a girth that increases logarithmically with the size of the graph. Compared to the well-known progressive-edge-growth (PEG) algorithm, the proposed method, in some cases, results in Tanner graphs with larger girth, particularly for scenarios where the degree sequences of the graph are strictly enforced.

Counting short cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. There are two computational approaches to count short cycles (with length smaller than 2g, where g is the girth of the graph) in bipartite graphs. The first approach is applicable to a general (irregular) bipartite graph, and uses the spectrum {ηi} of the directed edge matrix of the graph to compute the multiplicity Nkof k-cycles with kk= Σiηik/(2k). This approach has a computational complexity O(|E|3), where |E| is number of edges in the graph. The second approach is only applicable to bi-regular bipartite graphs, and uses the spectrum {λi} of the adjacency matrix (graph spectrum) and the degree sequences of the graph to compute Nk. The complexity of this approach is O(|V|3), where |V| is number of nodes in the graph. This complexity is less than that of the first approach, but the equations involved in the computations of the second approach are complex and tedious, particularly for k ≥ g+6. In fact, the computational complexity of the equations increases exponentially with k. In this paper, we establish an analytical relationship between the two spectra {ηi} and {λi} for bi-regular bipartite graphs. Through this relationship, the former spectrum can be derived from the latter through simple equations with computational complexity constant in k. This allows the computation of Nkusing Nk= Σiηik/(2k) but with a complexity of O(|V|3) rather than O(|E|3).

The problem of finding bipartite (Tanner) graphs with given degree sequences that have large girth and few short cycles is of great interest in many applications including construction of good low-density parity-check (LDPC) codes. In this paper, we prove that for a given set of integers α, β, and γ, and degree sequences π and π', the problem of determining whether there exists a simple bipartite graph with degree sequences (π, π') that has at most α (β and γ) cycles of length four (six and eight, respectively) is NP-complete. This is proved by a two-step polynomial-time reduction from the 3-Partition Problem. On the other hand, using connections to linear hypergraphs, we prove that given the degree sequence π, a polynomial time algorithm can be devised to determine whether there exists a bipartite graph whose degree sequence on one side of the bipartition is π and has a girth of at least six.

Counting short cycles in bipartite graphs is a fundamental problem of interest in many fields including the analysis and design of low-density parity-check (LDPC) codes. There are two computational approaches to count short cycles (with length smaller than 2g, where g is the girth of the graph) in bipartite graphs. The first approach is applicable to a general (irregular) bipartite graph, and uses the spectrum {ηi} of the directed edge matrix of the graph to compute the multiplicity Nk of k-cycles with kk=Σiηik/(2k). This approach has a computational complexity O(|E|3), where |E| is number of edges in the graph. The second approach is only applicable to bi-regular bipartite graphs, and uses the spectrum {λi} of the adjacency matrix (graph spectrum) and the degree sequences of the graph to compute Nk. The complexity of this approach is O(|V|3), where |V| is number of nodes in the graph. This complexity is less than that of the first approach, but the equations involved in the computations of the second approach are very tedious, particularly for k ≥ g + 6. In this paper, we establish an analytical relationship between the two spectra {ηi} and {λi} for bi-regular bipartite graphs. Through this relationship, the former spectrum can be derived from the latter through simple equations. This allows the computation of Nkusing Nk= Σiηik/(2k) but with a complexity of O(|V|3) rather than O(|E|3).

The performance of low-density parity-check (LDPC) codes in the error floor region is closely related to some substructures of the code's Tanner graph, collectively referred to as trapping sets (TSs). In this paper, we study the asymptotic average number of different types of trapping sets such as elementary TSs (ETS), leafless ETSs (LETS), absorbing sets (ABS), elementary ABSs (EABS), and stopping sets (SS), in random variable-regular and irregular LDPC code ensembles. We demonstrate that, regardless of the type of the TS, as the code's length tends to infinity, the average number of a given structure tends to infinity, to a positive constant, or to zero, if the structure contains no cycle, only one cycle, or more than one cycle, respectively. For the case where the structure contains a single cycle, we derive the asymptotic expected multiplicity of the structure by counting the average number of its constituent cycles and all the possible ways that the structure can be constructed from the cycle. This, in general, involves computing the expected number of cycles of a certain length with a certain given combination of node degrees, or computing the expected number of cycles of a certain length expanded to the desired structure by the connection of trees to its nodes. The asymptotic results obtained in this work, which are independent of the block length and only depend on the code's degree distributions, are shown to be accurate even for finite-length codes.

Cages, defined as regular graphs with minimum number of nodes for a given girth, are well-studied in graph theory. Trapping sets are graphical structures responsible for error floor of low-density parity-check (LDPC) codes, and are well investigated in coding theory. In this paper, we make connections between cages and trapping sets. In particular, starting from a cage (or a modified cage), we construct a trapping set in multiple steps. Based on the connection between cages and trapping sets, we then use the available results in graph theory on cages and derive tight upper bounds on the size of the smallest trapping sets for variable-regular LDPC codes with a given variable degree and girth. The derived upper bounds in many cases meet the best known lower bounds and thus provide the actual size of the smallest trapping sets. Considering that non-zero codewords are a special case of trapping sets, we also derive tight upper bounds on the minimum weight of such codewords, i.e., the minimum distance, of variable-regular LDPC codes as a function of variable degree and girth.

Counting short cycles in bipartite graphs is a fundamental problem of interest in the analysis and design of low-density parity-check codes. The vast majority of research in this area is focused on algorithmic techniques. Most recently, Blake and Lin proposed a computational technique to count the number of cycles of length g in a bi-regular bipartite graph, where g is the girth of the graph. The information required for the computation is the node degree and the multiplicity of the nodes on both sides of the partition, as well as the eigenvalues of the adjacency matrix of the graph (graph spectrum). In this paper, the result of Blake and Lin is extended to compute the number of cycles of length g+2, ... , 2g-2, for bi-regular bipartite graphs, as well as the number of 4-cycles and 6-cycles in irregular and half-regular bipartite graphs, with g ≥ 4 and g ≥ 6, respectively.

Leafless elementary trapping sets (LETSs) are known to be the problematic structures in the error floor region of low-density parity-check (LDPC) codes over the additive white Gaussian (AWGN) channel under iterative decoding algorithms. While problems involving the general category of trapping sets, and the subcategory of elementary trapping sets (ETSs), have been shown to be NP-hard, similar results for LETSs, which are a subset of ETSs are not available. In this paper, we prove that for a general LDPC code, finding a LETS of a given size a with minimum number of odd-degree check nodes b is NP-hard to approximate within any approximation factor. We also prove that finding the minimum size a of a LETS with a given b is NP-hard to approximate within any approximation factor. Similar results are proved for elementary absorbing sets, a popular subcategory of LETSs.

Leafless elementary trapping sets (LETSs) are known to be the problematic structures in the error floor region of low-density parity-check (LDPC) codes over the additive white Gaussian (AWGN) channel under iterative decoding algorithms. While problems involving the general category of trapping sets, and the subcategory of elementary trapping sets (ETSs), have been shown to be NP-hard, similar results for LETSs, which are a subset of ETSs, are not available. In this paper, we prove that, for a general LDPC code, finding a LETS of a given size α with minimum number of unsatisfied check nodes b is NP-hard to approximate with any guaranteed precision. We also prove that finding the minimum size a of a LETS with a given b is NP-hard to approximate. Similar results are proved for elementary absorbing sets, a popular subcategory of LETSs.

The performance of low-density parity-check (LDPC) codes in the error floor region is closely related to some substructures of the code's Tanner graph, collectively referred to as trapping sets (TSs). In this paper, we study the asymptotic average number of different types of trapping sets such as elementary TSs (ETS), leafless ETSs (LETS), absorbing sets (ABS), elementary ABSs (EABS), and stopping sets (SS), in random variable-regular and irregular LDPC code ensembles. We demonstrate that, regardless of the type of the TS, as the code's length tends to infinity, the average number of a given structure tends to infinity, to a positive constant, or to zero, if the structure contains no cycle, only one cycle, or more than one cycle, respectively. For the case where the structure contains a single cycle, we obtain an estimate of the expected number of the structure through the available approximations for the average number of the constituent cycle. These estimates, which are independent of the block length and only depend on the code's degree distributions, are shown to be accurate even for finite-length 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.