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 nonzero 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.
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 nonzero 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.
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.
The relation between the girth and the guaranteed error correction capability of¿-left-regular low-density parity-check (LDPC) codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least3 ¿/4is found based on the Moore bound. This bound, combined with the well known expander based arguments, leads to a lower bound on the guaranteed error correction capability. The decoding failures of the bit flipping algorithms are characterized using the notions of trapping sets and fixed sets. The relation between fixed sets and a class of graphs known as cage graphs is studied. Upper bounds on the guaranteed error correction capability are then established based on the order of cage graphs. The results are extended to left-regular and right-uniform generalized LDPC codes. It is shown that this class of generalized LDPC codes can correct a linear number of worst case errors (in the code length) under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. A lower bound on the size of variable node sets which have the required expansion is established.
Trapping sets are known to be the main cause for the error floor of low-density parity-check (LDPC) codes. They are often classified by their size a and the number of unsatisfied check nodes b in their subgraph. Trapping sets can be partitioned into two categories of elementary and non-elementary, where the first category are those whose subgraph only contains degree-1 and degree-2 check nodes. Empirical results have shown that often the most harmful trapping sets are elementary. In this letter, we derive a lower bound on the size of the smallest non-elementary trapping sets for a given b in variable-regular LDPC codes. The derived lower bound demonstrates that the size of the smallest possible non-elementary trapping set is, in general, larger than that of an elementary trapping set with the same b value. This provides a theoretical justification as to why non-elementary trapping sets are often not among the most harmful trapping sets.
In this paper, we study the graphical structure of elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. ETSs are known to be the main cause of error floor in LDPC coding schemes. For the set of LDPC codes with a given variable node degree dl and girth g, we identify all the non-isomorphic structures of an arbitrary class of (a,b) ETSs, where a is the number of variable nodes and b is the number of odd-degree check nodes in the induced subgraph of the ETS. Our study leads to a simple characterization of dominant classes of ETSs (those with relatively small values of a and b) based on short cycles in the Tanner graph of the code. For such classes of ETSs, we prove that any set S in the class is a layered superset (LSS) of a short cycle, where the term "layered" is used to indicate that there is a nested sequence of ETSs that starts from the cycle and grows, one variable node at a time, to generate S. This characterization corresponds to a simple search algorithm that starts from the short cycles of the graph and finds all the ETSs with LSS property in a guaranteed fashion. Specific results on the structure of ETSs are presented for dl=3,4,5,6, g=6,8 and a,b≤10 in this paper. The results of this paper can be used for the error floor analysis and for the design of LDPC codes with low error floors.
In this paper, we give lower bounds on the size of (a, b) elementary trapping sets (ETSs) of variable-regular LDPC codes with any girth, g, and irregular ones with girth 8, where a is the size and b is the number of degree-one check nodes. Our proposed lower bounds are analytical, applicable to all values of g and b, based on graph theories and tighter than the existing ones in the literature. Our results mostly depend on the girth. We also propose results, which are independent of the girth and rely on the variables a, b, y, and the column weight value. We obtain the tightest lower bounds on the size of ETSs of variable-regular LDPC codes with girth eight. These results provide us with a chance to present a method to achieve the minimum size of ETSs of irregular LDPC codes with girth, especially those whose column weight values are a subset of (2, 3, 4, 5, 61 and fulfill the inequality (b/a) <; 1. Moreover, we present a range of numerical results about (a, b) ETSs with girths 8 and 10 to compare the tightness between our proposed lower bounds and the existing bounds in the literature.
A (v,g)-cage is a (not necessarily unique) smallest v-regular graph of girth g. On such a graph, a nonbinary (2,v)-regular low-density parity-check (LDPC) code can be defined such that the Tanner graph has girth 2g and the code length achieves the minimum possible. In this paper, we focus on two aspects of this class of codes, structural property and code optimization. We find that, in addition to those found previously, many cages can be used to construct structured LDPC codes. We show that all cages with even girth can be structured as protograph-based codes, many of which have block-circulant Tanner graphs. We also find that four cages with odd girth can be structured as protograph-based codes with block-circulant Tanner graphs. For code optimization, we develop an ontology-based approach. All possible inter-connected cycle patterns that lead to low symbol-weight codewords are identified to put together the ontology. By doing so, it becomes handleable to estimate and optimize distance spectrum of equivalent binary image codes. We further analyze some known codes from the Consultative Committee for Space Data Systems recommendation and design several new codes. Numerical results show that these codes have reasonably good minimum bit distance and perform well under iterative decoding.