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.
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.
In this paper, we study the relationships between the girth of the Tanner graph of a quasi cyclic (QC) protograph low-density parity-check (LDPC) code, on one hand, and the lifting degree and the size and the structure of the base graph, on the other hand. As a result, for a given base graph and a given lifting degree, we derive an upper bound on the girth of the resulting lifted graphs (codes). The upper bounds derived here are generally tighter than the existing bounds. The results presented in this work can be used to select an appropriate lifting degree for a given base graph, in order to have a desired girth, or to provide some insight in designing good base graphs, or to properly select the base graph's edge permutations.
In this paper, we study the relationships between the girth of the Tanner graph of a quasi-cyclic (QC) protograph low-density parity-check (LDPC) code, the lifting degree, and the size and the structure of the base graph. As a result, for a given base graph, we derive a lower bound on the lifting degree as a necessary condition for the lifted graph to have a certain girth. This also provides an upper bound on the girth of the family of graphs lifted from a given base graph with a given lifting degree. The upper bounds derived here, which are applicable to both regular and irregular base graphs with no parallel edges, are in some cases more general and in some other cases tighter than the existing bounds. The results presented in this work can be used to design cyclic liftings with relatively small degree and relatively large girth. As an example, we present new QC protograph LDPC code constructions with girth 8 using fully connected base graphs. These constructions provide upper bounds on the lifting degree required for achieving girth 8 using fully connected base graphs.
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.
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.
The performance of low-density parity-check (LDPC) codes in the error floor region is closely related to some combinatorial structures of the code's Tanner graph, collectively referred to as {\it trapping sets (TSs)}. In this paper, we study the asymptotic average number of different types of trapping sets such as {\em elementary TSs (ETS)}, {\em leafless ETSs (LETS)}, {\em absorbing sets (ABS)}, {\em elementary ABSs (EABS)}, and {\em 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 its 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.