In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasi-cyclic (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 <inline-formula> <tex-math notation="LaTeX">c </tex-math></inline-formula>, the expected number of cycles of length <inline-formula> <tex-math notation="LaTeX">c </tex-math></inline-formula>, in this case, can be either <inline-formula> <tex-math notation="LaTeX">\Theta (N) </tex-math></inline-formula> or <inline-formula> <tex-math notation="LaTeX">\Theta (1) </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula> 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 propose a new characterization for leafless elementary trapping sets (LETSs) of variable-regular lowdensity parity-check codes. Recently, Karimi and Banihashemi proposed a ...characterization of LETSs, which was based on viewing an LETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. A notable advantage of LSS characterization is that it corresponds to a simple LSS-based search algorithm (expansion technique) that starts from short cycles of the graph and finds the LETSs with LSS structure efficiently. Compared with the LSS-based characterization of Karimi and Banihashemi, which is based on a single LSS expansion technique, the new characterization involves two additional expansion techniques. The introduction of the new techniques mitigates two problems that LSS-based characterization/search suffers from: 1) exhaustiveness: not every LETS structure is an LSS of a cycle and 2) search efficiency: LSS-based search algorithm often requires the enumeration of cycles with length much larger than the girth of the graph, where the multiplicity of such cycles increases rapidly with their length. We prove that using the three expansion techniques, any LETS structure can be obtained starting from a simple cycle, no matter how large the size of the structure a or the number of its unsatisfied check nodes b are, i.e., the characterization is exhaustive. We also demonstrate that for the proposed characterization/search to exhaustively cover all the LETS structures within the (a, b) classes with a amax and b bmax, for any value of amax and bmax, the length of the short cycles required to be enumerated is less than that of the LSS-based characterization/search. We, in fact, show that such a length for the proposed search algorithm is minimal. We also prove that the three expansion techniques, proposed here, are the only expansions needed for characterization of LETS structures starting from simple cycles in the graph, if one requires each and every intermediate sub-structure to be a LETS as well. Extensive simulation results are provided to show that, compared with LSS-based search, significant improvement in search speed and memory requirements can be achieved.
This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. The algorithm can be used to estimate the error floor of LDPC codes or as ...a tool to design LDPC codes with low error floors. For regular codes, the algorithm is initiated with a set of short cycles as the input. For irregular codes, in addition to short cycles, variable nodes with low degree and cycles with low approximate cycle extrinsic message degree (ACE) are also used as the initial inputs. The initial inputs are then expanded recursively to dominant trapping sets of increasing size. At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes, and cycles with low ACE. The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find a variety of graphical objects, such as absorbing sets and Zyablov-Pinsker trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.
In this paper, we propose a characterization of elementary trapping sets (ETSs) for irregular low-density parity-check (LDPC) codes. These sets are known to be the main culprits in the error floor ...region of such codes. The characterization of ETSs for irregular codes has been known to be a challenging problem due to the large variety of non-isomorphic ETS structures that can exist within the Tanner graph of these codes. This is a direct consequence of the variety of the degrees of the variable nodes that can participate in such structures. The proposed characterization is based on a hierarchical graphical representation of ETSs, starting from simple cycles of the graph, or from single variable nodes, and involves three simple expansion techniques: degree-one tree (<inline-formula> <tex-math notation="LaTeX">dot </tex-math></inline-formula>), <inline-formula> <tex-math notation="LaTeX">path </tex-math></inline-formula>, and <inline-formula> <tex-math notation="LaTeX">lollipop </tex-math></inline-formula>, thus, the terminology dpl characterization . A similar <inline-formula> <tex-math notation="LaTeX">dpl </tex-math></inline-formula> characterization was proposed in an earlier work by the authors for the leafless ETSs of variable-regular LDPC codes. The present paper generalizes the prior work to codes with a variety of variable node degrees and to ETSs that are not leafless. The proposed <inline-formula> <tex-math notation="LaTeX">dpl </tex-math></inline-formula> characterization corresponds to an efficient search algorithm that, for a given irregular LDPC code, can find all the instances of <inline-formula> <tex-math notation="LaTeX">(a, b) </tex-math></inline-formula> ETSs with size <inline-formula> <tex-math notation="LaTeX">a </tex-math></inline-formula> and with the number of unsatisfied check nodes <inline-formula> <tex-math notation="LaTeX">b </tex-math></inline-formula> within any range of interest <inline-formula> <tex-math notation="LaTeX">a \leq a_{\max } </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">b \leq b_{\max } </tex-math></inline-formula>, exhaustively. Although branch-&-bound exhaustive search algorithms for finding ETSs of irregular LDPC codes exist, to the best of our knowledge, the proposed search algorithm is the first of its kind, in that, it is devised based on a characterization of ETSs that makes the search process efficient. For a constant degree distribution and range of search, the worst-case complexity of the proposed <inline-formula> <tex-math notation="LaTeX">dpl </tex-math></inline-formula> algorithm increases linearly with the block length <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula>. The average complexity, excluding the search for the input simple cycles, is constant in <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula>. Extensive simulation results are presented to show the versatility of the search algorithm, and to demonstrate that, compared to the literature, significant improvement in search speed can be obtained.
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 <inline-formula> <tex-math notation="LaTeX">\boldsymbol {g} </tex-math></inline-formula> in a bi-regular bipartite graph, where <inline-formula> <tex-math notation="LaTeX">\boldsymbol {g} </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">\boldsymbol {g} + \textbf {2}, \ldots, \textbf {2}\boldsymbol {g}-\textbf {2} </tex-math></inline-formula>, for bi-regular bipartite graphs, as well as the number of 4-cycles and 6-cycles in irregular and half-regular bipartite graphs, with <inline-formula> <tex-math notation="LaTeX">\boldsymbol {g} \geq \textbf {4} </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">\boldsymbol {g} \geq \textbf {6} </tex-math></inline-formula>, respectively.
We propose a systematic design of protograph-based quasi-cyclic (QC) low-density parity-check (LDPC) codes with low error floor. We first characterize the trapping sets of such codes and demonstrate, ...using edge coloring techniques, that the QC structure of the code eliminates some of the trapping set structures that can exist in a code with the same degree distribution and girth but lacking the QC structure. Based on this characterization, our design aims at eliminating a targeted collection of trapping sets. Considering the parent/child relationship between the trapping sets in the collection, we search for and eliminate those trapping sets that are in the collection but are not a child of any other trapping set in the collection. An efficient layered algorithm is designed for the search of these targeted trapping sets. Compared to the existing codes in the literature, the designed codes are superior in the sense that they are free of the same collection of trapping sets while having a smaller block length, or a larger collection of trapping sets while having the same block length. In addition, the efficiency of the search algorithm makes it possible to design codes with larger degrees which are free of trapping sets within larger ranges compared to the state-of-the-art.
In this paper, we propose a design technique for the construction of variable-regular time-invariant spatially-coupled low-density parity-check (SC-LDPC) codes with small constraint length and low ...error floor. The proposed technique reduces the error floor by imposing simple constraints on the short cycles in the code's Tanner graph, which in turn, result in the elimination of the most dominant trapping sets of the code. In some cases, we also derive lower bounds on the syndrome former memory for satisfying such constraints. The designed codes are superior to the state-of-the-art in terms of error floor performance and/or decoding complexity and latency.
In this paper, we propose a novel state-space model to represent the behavior of sum-product algorithm (SPA) in the vicinity of a trapping set (TS) of a low-density parity-check (LDPC) code over the ...additive white Gaussian noise (AWGN) channel in the error floor region. The proposed model takes into account the non-linear behavior of SPA in the initial iterations using a quadratic approximation, and dynamically adjusts the operating point of the model in accordance to the statistical properties of TS messages. This is in contrast to the existing linear state-space models which linearly approximate the non-linear behavior of SPA at around the operating point of zero in all iterations. Simulation results are provided to demonstrate the higher accuracy of the proposed model in estimating the error floor of LDPC codes compared to the linear state-space model. We also make connections to the semi-analytical code-dependent technique proposed in 1 for the error floor estimation of LDPC codes, and demonstrate that the proposed state-space model not only is a fully-analytical code-independent counterpart to that method, but also has less complexity and, in some cases, more accuracy.
PDF
