# The Manifestation of Stopping Sets and Absorbing Sets as Deviations on the Computation Trees of LDPC Codes

Authors: Eric Psota; Lance C. Pérez
Journal: Journal of Electrical and Computer Engineering
 (2010)

---

## Abstract

The error mechanisms of iterative message-passing decoders for low-density parity-check codes are studied. A tutorial review is given of the various graphical structures, including trapping sets, stopping sets, and absorbing sets that are frequently used to characterize the errors observed in simulations of iterative decoding of low-density parity-check codes. The connections between trapping sets and deviations on computation trees are explored in depth using the notion ofproblematic trapping sets in order to bridge the experimental and analytic approaches to these error mechanisms. A new iterative algorithm for finding low-weight problematic trapping sets is presented and shown to be capable of identifying many trapping sets that are frequently observed during iterative decoding of low-density parity-check codes on the additive white Gaussian noise channel. Finally, a new method is given for characterizing the weight of deviations that result from problematic trapping sets.


---

## Body

## 1. Introduction

Prior to 1993, channel codes were typically designed with the goal of maximizing the minimum distance of the code [1, 2]. The combination of a code with a large minimum distance and a decoder that minimizes the probability of codeword error often resulted in good asymptotic performance. The discovery of turbo codes [3] and the rediscovery of low-density parity-check (LDPC) codes [4] revealed that codes with relatively poor minimum distance properties could achieve near-capacity performance at bit error rates of Pb<10-6. This resulted in a reduced emphasis on maximizing minimum distance when design codes for use on the additive white Gaussian noise (AWGN) channel. As with many other classes of codes, there are no practical bounds for the decoders used for turbo codes and LDPC codes and simulations are required to accurately determine the performance at practical operating points.With the discovery of turbo codes and the various subsequent iterative decoders, the phenomenon of the error floor has become prominent in practical code design. The termerror floor refers to the situation where the error rate at the output of the decoder suddenly starts to decrease at a slower rate as a function of increasing signal-to-noise ratio (SNR); that is, the performance curve flattens out. The error floors that occur with iterative decoding of turbo codes and LDPC codes are problematic in practical systems because it is difficult to predict the specific operating point at which they occur, and thus design engineers risk using codes that may have unknown error floors that limit the performance of the system. In the case of iterative decoding of turbo codes, it has been shown that the error floor is usually the result of the overall turbo code having low weight codewords that begin to limit the performance of the code after some SNR is reached [5]. The minimum distance of a turbo code can be increased, and hence the likelihood of an error floor sufficiently mitigated, through the use of various interleaver designs [6, 7].Low-density parity-check codes with iterative decoding are also known to exhibit error floors [8, 9], albeit at much lower bit error rates than the error floors of turbo codes of similar block length. In many cases, because of the exceptionally low bit error rates at which the error floors of LDPC codes appear, it is not practical to use Monte Carlo simulations to demonstrate the existence of these error floors. The inability to run conventional computer simulations down to the error floor combined with the lack of practical upper bounds for LDPC codes has inhibited the deployment of LDPC codes in high-throughput applications that require near error-free performance with bit error rates of Pb<10-15.LDPC codes are most commonly decoded using iterative message-passing decoders such as the min-sum decoder [10] and the sum-product decoder [11] due to their excellent performance and low implementation complexity. Many attempts have been made to estimate the performance of these decoders by characterizing their error mechanisms. Three of the most well-known error mechanisms are stopping sets [12], trapping sets [13], and absorbing sets [8]. Unfortunately, none of these mechanisms leads to strict upper bounds on the performance of iterative decoding over the AWGN channel, and thus they are of limited use in determining error floors. Wiberg showed that deviations on the computation trees of LDPC codes can be used to compute tight upper bounds on the performance of LDPCs with iterative decoders [10]; however, it is computationally intractable to do so after even a small number of decoder iterations. A practical method for determining the error floor of LDPCs with iterative decoding has yet to be discovered.This paper attempts to make progress on this problem by integrating the precise, but computational intractable, work of Wiberg with the experimental studies of the error mechanisms observed when iteratively decoding LDPCs. The paper begins with a tutorial review of the existing methods for analyzing the performance of iterative message-passing decoders. Then, the notion of aproblematic trapping set is introduced and its relationship to deviations is examined in detail, with the goal of determining what makes deviations either more or less problematic during iterative message-passing decoding. Finally, an iterative method is given for finding problematic trapping sets using the weights of deviations on the computation trees.


## 2. Background

The following model for channel coding is used throughout this paper. First, a vectoru∈𝔽2K of K information bits is generated by a binary source. The binary source is assumed to be memoryless, which is often the result of source coding (data compression), and therefore all information sequences in 𝔽2K are equally probable. A binary K×N generator matrix G may be used by the channel encoder to map the information bits u to a length N codeword c∈𝔽2N, via the mapping c=uG. Here, it is assumed that the matrix G is full-rank, and thus the rate of the code is R=K/N.Before a codewordc∈C is transmitted over the channel, it is modulated via the transformation (1)xi=m(ci)=2ci-1,for alli=0,…,N-1. The received signal vector y∈ℝN is given by (2)y=x+n,wheren∈ℝN is the Gaussian noise vector. The log-likelihood ratio (LLR) vector, often used for soft-decision decoding, is given by (3)λi=PY∣X(yi∣-1)PY∣X(yi∣1),for alli=1,…,N. This reduces to λi=(-2/σ2)yi when n is a vector of AWGN. An estimate ĉ of the transmitted codeword c is derived from the received vector y at the channel decoder. Finally, the information bits û extracted from ĉ are passed to the sink.As mentioned earlier, each of the information sequencesu∈𝔽2K is equiprobable. Since there is a one-to-one mapping between information sequences and codewords, all codewords in the code C are equiprobable as well. Therefore, P(ci)=P(cj) for all ci,cj∈C, where P(ci) is the probability that codeword ci is transmitted. When considering the performance of linear codes, equiprobable codewords allow for the assumption that the all-zeros codeword was transmitted. The all-zeros codeword assumption is used throughout this paper.From the generator matrixG, it is possible to derive an (N-K)×N parity-check matrix H for the code. Aparity-check matrix of a code C is any matrix H, such that HcT=0 for all c∈C. LDPC codes are often defined by their parity-check matrix H. In particular, LDPC codes are a class of codes with sparse parity-check matrices. Asparse parity-check matrix is any binary matrix that contains more binary 0s than binary 1s. A (dV,dF)-regular LDPC code is one that has a fixed number dV of binary 1s in each column of the parity-check matrix and some fixed number dF of binary 1s in each row of the parity-check matrix. An example of a (2,3)-regular LDPC code of length N=6 and dimension K=3 is given by the parity-check matrix
(4)H(2,3)=[111000110100001011000111].
The parity-check matrix of a length N, dimension K code must contain at least (N-K) rows, since the kernel of G has dimension (N-K). However, it is possible for the parity-check matrix to contain more than (N-K) rows. Therefore, the number of rows in the parity-check matrix is denoted by M, where M≥(N-K).ATanner graph is a bipartite graphical representation of a low-density parity-check matrix. To construct a Tanner graph from a parity-check matrix, each column i in the parity-check matrix is assigned to a corresponding variable node vi in the Tanner graph, and each row j is assigned to a corresponding check node fj in the Tanner graph. The set of all variable nodes is V, and the set of all check nodes is F. There is an edge ei,j between variable node vi and check node fj in the Tanner graph if and only if the entry in H at the intersection of the jth row and ith column is a binary 1. The Tanner graph T=(V⋃F,E) is thus defined by the set of variable nodes V, the set of check nodes F, and the set of edges E. The Tanner graph corresponding to the parity-check matrix H(2,3) (given by (4)) is shown in Figure 1.Figure 1
Tanner graph of a(2,3)-regular LDPC code.Note that in the Tanner graphs of irregular LDPC codes variable nodes and check nodes do not all have the same number of incident edges. The number of check nodes that a specific variable nodevi is connected to is denoted by dvi, and the number of variable nodes that a specific check node fi is connected to is denoted dfi.


### 2.1. Iterative Message-Passing Decoding

The min-sum (MS) and sum-product (SP) decoders are low-complexity, sub-optimal iterative decoders that can be used to decode low-density parity-check codes. Given a particular parity-check matrix, the MS decoder operates by passing messages between the check nodes and the variable nodes along the edges of the Tanner graph of the code.Before introducing the decoders, some additional notation is necessary. The set of neighbors of check nodefi in the Tanner graph is denoted N(fi)={vj∣hi,j=1}, and similarly the set of neighbors of variable node vi in the Tanner graph is denoted N(vi)={fj∣hj,i=1}. To denote the set of neighbors of check node fi excluding variable node vj, the notation N(fi)∖vj is used. Similarly, the set of neighbors of variable node vj excluding check node fi is denoted N(vj)∖fi. During decoding, messages are passed between neighboring check nodes and variable nodes along the edges of the Tanner graph. Messages from check node fi to variable node vj∈N(fi) are denoted by mfi→vj, and messages from variable node vi to check node fj∈N(vi) are denoted mvi→fj. Given the transmitted codeword x, the channel output y available at the receiver, and a maximum number of iterations ℓmax, the steps for MS and SP decoding are given in the following algorithmAlgorithm 1 (Min-Sum/Sum-Product Decoding).
Step 1 (Initialization).
Set the number of iterations toℓ=0. For all messages mfi→vj, set
(5)mvi→fj=λi=PY∣X(yi∣-1)PY∣X(yi∣1)=-2σ2yi.Step 2 (Check Node Update).
Setℓ=ℓ+1. For all messages mvi→fj, setMin-Sum:
(6)mfi→vj=(∏vk∈N(fi)∖vjsgn(mvk→fi))(minvk∈N(fi)∖vj∣mvk→fi).Sum-Product:(7)mfi→vj=2·tanh-1(∏vk∈N(fi)∖vjtanh(mvk→fi2)).Step 3 (Variable Node Update).
For all messagesmvi→fj, set
(8)mvi→fj=λi+∑fk∈N(vi)∖fjmfk→vi.Step 4 (Check Stop Criteria).
For allmvi, set
(9)mvi=λi+∑fk∈N(vi)mfk→vi.
For all ĉi, set
(10)ĉi={0ifmvi>0,1ifmvi<0,
with P(ĉi=0∣mvi=0)=P(ĉi=1∣mvi=0)=0.5.If HĉT=0 or ℓ≥ℓmax, stop decoding, else return to Step 2.
One of the primary strengths of the min-sum and sum-product decoders is the relatively small number of operations performed during each iteration. During each iteration, the messagesmvi→fj and mfj→vi must be computed for each binary 1 in the parity-check matrix. For a (dV,dF)-regular LDPC code, there are (N×dV)=(M×dF) binary 1s in the parity-check matrix. When the degree of the nodes and the number of iterations is fixed, the complexity of MS decoding scales linearly with the length N of the code.
In practice, the min-sum and sum-product decoders do not always output a codeword. It has been shown that when the MS decoder does not output a codeword after a large number (>200) of iterations has been performed, the output often cycles in a repeating sequence of two or more noncodeword outputs [14]. In Sections 2.2 through Section 2.4, three different characterizations are given for the noncodeword outputs of iterative message-passing decoders.


### 2.2. Stopping Sets

The notion of stopping sets was first introduced by Forney et al. [15] in 2001. Two years later, a formal definition of stopping sets was given by Di et al. [12]. They demonstrated that the bit and word error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix.Definition 1 (stopping sets [12]).
A stopping set𝒮 is a subset of the set of variable nodes V, such that any check node connected to a variable node contained in 𝒮 is connected to at least two variable nodes in 𝒮.A small example of a stopping set is given in Figure2. Consider the subset 𝒮={v1,v2,v3,v4} of the set of variable nodes V. There are five check nodes {f1,f2,f3,f4,f5} connected to the set 𝒮, and each of them is connected to 𝒮 at least two times. Note that only f2 is connected to the set 𝒮 an odd number of times; If each of the check nodes is connected to 𝒮 an even number of times, 𝒮 corresponds to a codeword support set where all bits in 𝒮 can be flipped without changing the overall parity of any of the check nodes.Figure 2
Example of a stopping set in the Tanner graph of an LDPC code.The intuition behind stopping sets begins with an understanding of iterative message-passing decoders. Information given to a specific variable node from a neighboring check node is derived from all other variable nodes connected to that check node. Consider two variable nodesvi,vj∈N(fk), where both variable nodes contain an erasure. In this case, each of the sets N(fk)∖vi and N(fk)∖vj contains at least one erasure, thus making it impossible for the check node fk to determine the parity of either set. For this reason, none of the check nodes connected to a stopping set is capable of resolving erasures, if each variable node contained in the stopping set begins with an erasure from the channel.Work relating linear programming (LP) pseudocodewords to stopping sets for the binary erasure channel [15], and both the binary symmetric channel (BSC) and the additive white Gaussian noise channel [16], has revealed a relationship between linear programming pseudocodewords and the size of stopping sets. Although stopping sets have a strong relationship with LP pseudocodewords, the performance of neither the MS decoder or the SP decoder on the BSC and AWGN channels can be predicted using stopping sets alone.


### 2.3. Trapping Sets

Trapping sets, also referred to as near-codewords, were first introduced by MacKay and Postol [13] to provide an explanation for the weaknesses of algebraically constructed low-density parity-check codes. They define trapping sets as follows.Definition 2 (trapping sets [13]).
Consider a lengthN code with parity-check matrix H, and let 𝒯⊆{1,…,N} be a set containing |𝒯|=t coordinates. Consider a length-N binary vector y with 1s in the coordinates of 𝒯 and 0s elsewhere. If the syndrome s=Hy has Hamming weight wt, the set 𝒯 is referred to as a (t,wt) trapping set.Consider the trapping set shown in Figure3, where the set 𝒯={1,2,3,4} corresponds with a set of variable nodes {v1,v2,v3,v4} in the Tanner graph of the parity-check matrix H. There are four variable nodes in the set, so t=4, and if all variable nodes are set to a binary 1, only check nodes f2 and f3 are connected to an odd number of binary 1s, so the syndrome s has Hamming weight equal to 2. Therefore, according to Definition 2, this set of variable nodes defines a (4,2) trapping set.Figure 3
Example of a(4,2) trapping set in the Tanner graph of an LDPC code.It is important to note that any set of variable nodes can be considered a trapping set defined by some set of parameters, and the significance of trapping sets varies greatly depending on the parameters(t,wt). In much the same way that low-weight codewords are problematic to decoding, erroneous channel information is more likely to affect the majority of variable nodes in a trapping set which has low-weight t. Richardson [17] shows that trapping sets with small weight t and a small number of unsatisfied check nodes wt are more likely to cause errors. When a trapping set has small wt, the extrinsic information being passed into 𝒯 can not overcome the intrinsic information reinforced within 𝒯.In [17], trapping sets are examined for different decoders on the binary erasure channel, binary symmetric channel, and the additive white Gaussian noise channel. Whereas stopping sets can be used to precisely determine the probability of error on the BEC, trapping sets appear to cause errors on the AWGN channel. Richardson [17] uses the parameters and multiplicity of various problematic trapping sets to estimate the error floor of LDPC codes at bit error rates where simulations are not feasible. Unfortunately, the somewhat vague definition of problematic trapping sets makes it difficult to use them for performance analysis.


### 2.4. Absorbing Sets

In an attempt to clarify the ambiguity of problematic trapping sets, Zhang et al. introduced the notion of absorbing sets [8]. They define absorbing sets as follows.Definition 3 (Absorbing Sets [8]).
Let𝒜⊆V be a set containing |𝒜|=a variable nodes. Also, let O(𝒜)⊆F be a set of check nodes such that |O(𝒜)|=wa, and each check node in the set O(𝒜) has an odd number of edges connected to 𝒜. If each variable node in 𝒜 is connected to strictly more check nodes in F∖O(𝒜) than in O(𝒜), the set 𝒜 is referred to as a (a,wa) absorbing set. A fully absorbing set also satisfies the condition that each variable node in V is connected to more check nodes in F∖O(𝒜) than in O(𝒜).Note that an(a,wa) absorbing set is also an (a,wa) trapping set, but the converse is not always true. Figure 4 shows an example of a (4,1) absorbing set. The set of variable nodes in this absorbing set is 𝒜={v1,v2,v3,v4}, and the set of unsatisfied check nodes is O(𝒜)={f4}. The variable node v2 is not connected to f4, and the variable nodes v1, v3, and v4 are each connected to f4 and at least two other check nodes in F. Therefore, each of the variable nodes in 𝒜 is connected to more satisfied check nodes than unsatisfied check nodes. Also, note that the (4,2) trapping set in Figure 3 is not an absorbing set because variable nodes v2 and v4 are connected to two unsatisfied check nodes and only one satisfied check node.Figure 4
Example of a(4,1) absorbing set in the Tanner graph of an LDPC code.Simulations show that the majority of errors encountered in the error floor region during sum-product decoding of the IEEE 802.3 an low-density parity-check code could be attributed to absorbing sets [8, 9]. Although absorbing sets appear to be useful for estimating the performance of iterative message-passing decoding, they do not lead to strict upper bounds. For upper bounds, it is possible to use the concept of deviations on the computation tree.


### 2.5. Computation Trees and Deviations

In his 1996 dissertation, Wiberg [10] presented groundbreaking analytical results with respect to iterative decoding of low-density parity-check codes. He provided extensive analysis of both the MS and SP decoders by introducing a model of iterative decoding known as the computation tree. Wiberg showed that the MS decoder minimizes the probability of word error when decoding a code whose Tanner graph is a tree, while for the same type of code the SP decoder minimizes the probability of bit error.In addition to introducing computation trees, Wiberg also introduced the concept of deviations. Wiberg proved that deviations on the computation tree with negative cost are required in order for errors to occur during MS and SP decoding. Because of the importance of computation trees and deviations in understanding finite tree-based decoding, they are examined in detail in this section.Consider a low-density parity-check code represented by a Tanner graphT=(V⋃F,E). A computation tree rooted at variable node vi after ℓ iterations is denoted Rvi(ℓ). In order to construct a computation tree from the Tanner graph, a variable node vi is placed at the top level (root) of a descending tree. To construct the next level in the tree directly below vi, each of vi’s neighbors in N(vi) is added to this level and connected to vi. This process continues level-by-level, where nodes in the previous level are used to determine nodes on next level, while maintaining that each node in the computation tree has the same set of neighbors as its corresponding node in the Tanner graph. For example, if variable node vj on the last completed level is connected to check node fk on the level above it, then all check nodes in N(vj)∖fk must appear on the next level and be connected to vj, thereby ensuring that vj is connected to exactly one copy of each check node in N(vj).Figure5 gives an example of a Tanner graph, and its corresponding computation tree rooted at v1 after two iterations. Nodes at the bottom level of the computation tree are referred to as leaf nodes. Notice that the leaf nodes are the only nodes in the computation tree that are not connected to a copy of each of their neighbors in the original Tanner graph.Computation tree of a simple repetition code afterℓ=2 iterations.
(a)
Tanner graph(b)
Computation treeComputation trees are precise models for analyzing the performance and behavior of min-sum and sum-product decoding for a finite set of iterations. Each of these decoders can be precisely modeled afterℓ iterations by constructing N different computation trees that contain 2ℓ+1 levels of nodes including the root node. The N computation trees are each rooted at a different variable node from the original Tanner graph. Then, for every variable node vi in each computation tree, the LLR cost γi is assigned to that variable node. At this point, MS or SP decoding operations can be performed from the leaf nodes up to the root node. The final cost at each of the root nodes determines the binary estimate of the transmitted codeword computed by the decoder. Because the MS and SP decoders are optimal on Tanner graphs that are trees, the MS and SP decoders are optimal on each of the computation trees derived from the Tanner graph. MS chooses the least cost valid configuration on the tree, where a valid configuration refers to any assignment of binary numbers to the variable nodes such that each check node is adjacent to an even number of variable nodes assigned to a binary 1. The SP decoder, on the other hand, chooses the value at the root node that has the highest probability over all valid configurations.Although the computation tree model is precise, after a small number of iterations it becomes impractical to analyze the performance of specific codes by considering all valid configurations on the computation tree. The number of valid configurations on the computation tree can be computed by treating the computation tree as a Tanner graph. In order to define a Tanner graph given the computation tree, treat all check nodes and variable nodes in the computation tree separately. For example, if multiple copies of variable nodev1 are distributed throughout the computation tree, each copy is treated as a distinct variable node. After regarding each variable node in the computation tree as distinct, one can show that each check node on the computation tree corresponds to a linearly independent parity-check equation. If there are |Rvi(ℓ)(V)| variable nodes and |Rvi(ℓ)(F)| check nodes on a computation tree rooted at variable node vi after ℓ iterations, then there are a total of 2|Rvi(ℓ)(V)|-|Rvi(ℓ)(F)| valid configurations on the tree. On a (dV,dF)-regular LDPC code, the number of variable nodes after ℓ iterations is given by(11)|Rvi(ℓ)(V)|=1+∑i=0ℓ-1dV(dF-1)(((dV-1)(dF-1))i),
and the number of check nodes is given by (12)|Rvi(ℓ)(F)|=∑i=0ℓ-1dV(((dV-1)(dF-1))i).To illustrate the growth rate in the number of valid configurations on the computation tree, consider an LDPC code where each variable node has degreedV=3 and each check node has degree dF=6. These commonly used code parameters result in what are known as a (3,6)-regular LDPC codes. Table 1 shows the number of variable nodes given by (13)|Rvi(ℓ)(V)|=1+∑i=0ℓ-115(10i),Table 1
The number of nodes and valid configurations on the computation tree of a(3,6)-regular LDPC code.
IterationsVariable NodesCheck NodesConfigurations11638192216633≈104031666333≈10401the number of checks nodes given by(14)|Rvi(ℓ)(F)|=∑i=0ℓ-13·10i,and the corresponding number of valid configurations on the computation tree after 1, 2, and 3 iterations. Note that the growth rate is not affected by the block length of the code.Table1 illustrates the computational complexity associated with considering each valid configuration on the computation tree. In light of this, Wiberg [10] derived a simplified bound on the performance of MS decoding operating on a particular computation tree. In order to obtain this bound, Wiberg introduced the concept of deviations on the computation tree.Definition 4 (Deviation [10]).
Adeviation is any set of variable nodes on the computation tree satisfying the following three conditions.(1)
Each check node in the computation tree is adjacent to either two or zero variable nodes in the deviation set.(2)
A deviation set contains the root node of the computation tree.(3)
No proper and nonempty subset of variable nodes in the deviation from a valid configuration on the computation tree.Figure6 shows an example of a deviation on the computation tree given in Figure 5(b). The larger blue variable nodes are contained in the deviation, whereas the smaller red nodes are not.Figure 6
Example of a deviation on the computation tree.Wiberg uses the set of deviations on the computation tree to derive an upper bound on the performance of the min-sum decoder. It is necessary, but not sufficient, for at least one deviationδ in the set of all deviations Δ to have negative cost in order for an error to occur at the root node. The cost of the deviation, denoted by G(δ), can be found by summing the LLR cost of each of the nodes in the support of the deviation. The cost of a deviation is given by (15)G(δ)=∑vi∈δγi,where copies ofvi∈δ are counted as many times as they appear in the deviation. A necessary, but not sufficient, condition for an error to occur on the computation tree rooted at variable node vi is given by [10] (16)minδ∈ΔG(δ)<0.Using this condition, a bound can be derived on the probability that the minimum-cost configuration on the computation tree contains a binary 1 at the root node. This bound is(17)P(vi=1)≤P(minδ∈ΔG(δ)<0),≤⋃δ∈ΔP(G(δ)<0),which can be further loosened to(18)P(vi=1)≤∑δ∈ΔP(G(δ)<0),
by using the union bound.Wiberg [10] shows that the bound given by (18) can be used to predict the performance of min-sum decoding of infinite-length codes after a specific number of iterations. Wiberg begins by assuming that the computation trees have no repeated nodes. This assumption simplifies the weight enumerators of the deviations for regular LDPC codes. Wiberg also shows that (18) can be used to bound MS decoder performance when there are multiple copies of each variable node in the tree. Thus, in theory, Wiberg’s deviation bound can be used to bound the performance of MS decoding of finite length codes. The following proposition shows that the number of deviations grows exponentially with dV, thus making it computationally intractable to enumerate the deviations even after a small number of iterations.Proposition 1.
LetRvi(ℓ) be the computation tree of a (dV,dF)-regular LDPC code, rooted at variable node vi after ℓ iterations. Then, the number of deviations that exist on Rvi(ℓ) is
(19)(dF-1)∑i=1ℓdV(dV-1)i-1.Proof.
By the definition of a deviation, we must assign the root nodevi to a binary 1. Each of the dV check nodes immediately below vi must assign exactly one of the their (dF-1) child variable nodes to a binary 1. Thus, there are a total of (dF-1)dV deviations after one iteration. In addition, there are exactly dV leaf nodes in the support of each deviation after one iteration.
Each of the previousdV leaf nodes gets connected to (dV-1) check nodes after two iterations. Each of these check nodes assigns one of their (dF-1) child variable nodes to a binary 1. Therefore, for each deviation after one iteration there are (dF-1)dV(dV-1) different deviations after two iterations. This brings the total number of deviations to (dF-1)dV(dF-1)dV(dV-1)=(dF-1)(dV)2 after two iterations. The total number of leaf nodes in the support of the deviation after two iterations is dV(dV-1).
Following this pattern, thedV(dV-1) variable nodes in support of the deviation after two iterations branchs out to dV(dV-1)2 check nodes. There are (dF-1)dV(dV-1)2 ways of assigning the leaf nodes to the support of the previous deviation. This brings the total number of deviations to (dF-1)(dV)2(dF-1)dV(dV-1)2=(dF-1)(dV)3-(dV)2+dV after three iterations.
Afterℓ iterations, the dV(dV-1)ℓ-2 old leaf nodes in the support of the deviation branch out to dV(dV-1)ℓ-1 new leaf nodes in the support of the deviation. There are (dF-1)dV(dV-1)ℓ-1 ways of assigning the support to the previous deviation, and the total number of deviations after ℓ iterations is(20)∏i=1ℓ(dF-1)dV(dV-1)i-1=(dF-1)∑i=1ℓdV(dV-1)i-1.The number of deviations on the computation tree of a(3,6)-regular low-density parity-check code is given in Table 2 for iterations 1 through 5. Even after only a small number of iterations, it becomes impractical to enumerate each of the deviations in order to compute the upper bound on the probability of bit error of the root variable node of the computation tree.Table 2
Number of deviations at iterations 1–5 for a(3,6)-regular LDPC code.
Iterations# of deviations112521,953,12534.7684×101442.8422×103151.0097×1065Using computation trees, Wiberg provided a precise model of the behavior of the min-sum and sum-product decoders. Unfortunately, the size of the computation trees and the number of configurations on them grows too large for practical analysis. Deviations provide a simplified approach to the analysis of computation trees, but the number of deviations also grows exponentially with the number of iterations.


## 2.1. Iterative Message-Passing Decoding

The min-sum (MS) and sum-product (SP) decoders are low-complexity, sub-optimal iterative decoders that can be used to decode low-density parity-check codes. Given a particular parity-check matrix, the MS decoder operates by passing messages between the check nodes and the variable nodes along the edges of the Tanner graph of the code.Before introducing the decoders, some additional notation is necessary. The set of neighbors of check nodefi in the Tanner graph is denoted N(fi)={vj∣hi,j=1}, and similarly the set of neighbors of variable node vi in the Tanner graph is denoted N(vi)={fj∣hj,i=1}. To denote the set of neighbors of check node fi excluding variable node vj, the notation N(fi)∖vj is used. Similarly, the set of neighbors of variable node vj excluding check node fi is denoted N(vj)∖fi. During decoding, messages are passed between neighboring check nodes and variable nodes along the edges of the Tanner graph. Messages from check node fi to variable node vj∈N(fi) are denoted by mfi→vj, and messages from variable node vi to check node fj∈N(vi) are denoted mvi→fj. Given the transmitted codeword x, the channel output y available at the receiver, and a maximum number of iterations ℓmax, the steps for MS and SP decoding are given in the following algorithmAlgorithm 1 (Min-Sum/Sum-Product Decoding).
Step 1 (Initialization).
Set the number of iterations toℓ=0. For all messages mfi→vj, set
(5)mvi→fj=λi=PY∣X(yi∣-1)PY∣X(yi∣1)=-2σ2yi.Step 2 (Check Node Update).
Setℓ=ℓ+1. For all messages mvi→fj, setMin-Sum:
(6)mfi→vj=(∏vk∈N(fi)∖vjsgn(mvk→fi))(minvk∈N(fi)∖vj∣mvk→fi).Sum-Product:(7)mfi→vj=2·tanh-1(∏vk∈N(fi)∖vjtanh(mvk→fi2)).Step 3 (Variable Node Update).
For all messagesmvi→fj, set
(8)mvi→fj=λi+∑fk∈N(vi)∖fjmfk→vi.Step 4 (Check Stop Criteria).
For allmvi, set
(9)mvi=λi+∑fk∈N(vi)mfk→vi.
For all ĉi, set
(10)ĉi={0ifmvi>0,1ifmvi<0,
with P(ĉi=0∣mvi=0)=P(ĉi=1∣mvi=0)=0.5.If HĉT=0 or ℓ≥ℓmax, stop decoding, else return to Step 2.
One of the primary strengths of the min-sum and sum-product decoders is the relatively small number of operations performed during each iteration. During each iteration, the messagesmvi→fj and mfj→vi must be computed for each binary 1 in the parity-check matrix. For a (dV,dF)-regular LDPC code, there are (N×dV)=(M×dF) binary 1s in the parity-check matrix. When the degree of the nodes and the number of iterations is fixed, the complexity of MS decoding scales linearly with the length N of the code.
In practice, the min-sum and sum-product decoders do not always output a codeword. It has been shown that when the MS decoder does not output a codeword after a large number (>200) of iterations has been performed, the output often cycles in a repeating sequence of two or more noncodeword outputs [14]. In Sections 2.2 through Section 2.4, three different characterizations are given for the noncodeword outputs of iterative message-passing decoders.


## 2.2. Stopping Sets

The notion of stopping sets was first introduced by Forney et al. [15] in 2001. Two years later, a formal definition of stopping sets was given by Di et al. [12]. They demonstrated that the bit and word error probabilities of iteratively decoded LDPC codes on the binary erasure channel (BEC) can be determined exactly from the stopping sets of the parity-check matrix.Definition 1 (stopping sets [12]).
A stopping set𝒮 is a subset of the set of variable nodes V, such that any check node connected to a variable node contained in 𝒮 is connected to at least two variable nodes in 𝒮.A small example of a stopping set is given in Figure2. Consider the subset 𝒮={v1,v2,v3,v4} of the set of variable nodes V. There are five check nodes {f1,f2,f3,f4,f5} connected to the set 𝒮, and each of them is connected to 𝒮 at least two times. Note that only f2 is connected to the set 𝒮 an odd number of times; If each of the check nodes is connected to 𝒮 an even number of times, 𝒮 corresponds to a codeword support set where all bits in 𝒮 can be flipped without changing the overall parity of any of the check nodes.Figure 2
Example of a stopping set in the Tanner graph of an LDPC code.The intuition behind stopping sets begins with an understanding of iterative message-passing decoders. Information given to a specific variable node from a neighboring check node is derived from all other variable nodes connected to that check node. Consider two variable nodesvi,vj∈N(fk), where both variable nodes contain an erasure. In this case, each of the sets N(fk)∖vi and N(fk)∖vj contains at least one erasure, thus making it impossible for the check node fk to determine the parity of either set. For this reason, none of the check nodes connected to a stopping set is capable of resolving erasures, if each variable node contained in the stopping set begins with an erasure from the channel.Work relating linear programming (LP) pseudocodewords to stopping sets for the binary erasure channel [15], and both the binary symmetric channel (BSC) and the additive white Gaussian noise channel [16], has revealed a relationship between linear programming pseudocodewords and the size of stopping sets. Although stopping sets have a strong relationship with LP pseudocodewords, the performance of neither the MS decoder or the SP decoder on the BSC and AWGN channels can be predicted using stopping sets alone.


## 2.3. Trapping Sets

Trapping sets, also referred to as near-codewords, were first introduced by MacKay and Postol [13] to provide an explanation for the weaknesses of algebraically constructed low-density parity-check codes. They define trapping sets as follows.Definition 2 (trapping sets [13]).
Consider a lengthN code with parity-check matrix H, and let 𝒯⊆{1,…,N} be a set containing |𝒯|=t coordinates. Consider a length-N binary vector y with 1s in the coordinates of 𝒯 and 0s elsewhere. If the syndrome s=Hy has Hamming weight wt, the set 𝒯 is referred to as a (t,wt) trapping set.Consider the trapping set shown in Figure3, where the set 𝒯={1,2,3,4} corresponds with a set of variable nodes {v1,v2,v3,v4} in the Tanner graph of the parity-check matrix H. There are four variable nodes in the set, so t=4, and if all variable nodes are set to a binary 1, only check nodes f2 and f3 are connected to an odd number of binary 1s, so the syndrome s has Hamming weight equal to 2. Therefore, according to Definition 2, this set of variable nodes defines a (4,2) trapping set.Figure 3
Example of a(4,2) trapping set in the Tanner graph of an LDPC code.It is important to note that any set of variable nodes can be considered a trapping set defined by some set of parameters, and the significance of trapping sets varies greatly depending on the parameters(t,wt). In much the same way that low-weight codewords are problematic to decoding, erroneous channel information is more likely to affect the majority of variable nodes in a trapping set which has low-weight t. Richardson [17] shows that trapping sets with small weight t and a small number of unsatisfied check nodes wt are more likely to cause errors. When a trapping set has small wt, the extrinsic information being passed into 𝒯 can not overcome the intrinsic information reinforced within 𝒯.In [17], trapping sets are examined for different decoders on the binary erasure channel, binary symmetric channel, and the additive white Gaussian noise channel. Whereas stopping sets can be used to precisely determine the probability of error on the BEC, trapping sets appear to cause errors on the AWGN channel. Richardson [17] uses the parameters and multiplicity of various problematic trapping sets to estimate the error floor of LDPC codes at bit error rates where simulations are not feasible. Unfortunately, the somewhat vague definition of problematic trapping sets makes it difficult to use them for performance analysis.


## 2.4. Absorbing Sets

In an attempt to clarify the ambiguity of problematic trapping sets, Zhang et al. introduced the notion of absorbing sets [8]. They define absorbing sets as follows.Definition 3 (Absorbing Sets [8]).
Let𝒜⊆V be a set containing |𝒜|=a variable nodes. Also, let O(𝒜)⊆F be a set of check nodes such that |O(𝒜)|=wa, and each check node in the set O(𝒜) has an odd number of edges connected to 𝒜. If each variable node in 𝒜 is connected to strictly more check nodes in F∖O(𝒜) than in O(𝒜), the set 𝒜 is referred to as a (a,wa) absorbing set. A fully absorbing set also satisfies the condition that each variable node in V is connected to more check nodes in F∖O(𝒜) than in O(𝒜).Note that an(a,wa) absorbing set is also an (a,wa) trapping set, but the converse is not always true. Figure 4 shows an example of a (4,1) absorbing set. The set of variable nodes in this absorbing set is 𝒜={v1,v2,v3,v4}, and the set of unsatisfied check nodes is O(𝒜)={f4}. The variable node v2 is not connected to f4, and the variable nodes v1, v3, and v4 are each connected to f4 and at least two other check nodes in F. Therefore, each of the variable nodes in 𝒜 is connected to more satisfied check nodes than unsatisfied check nodes. Also, note that the (4,2) trapping set in Figure 3 is not an absorbing set because variable nodes v2 and v4 are connected to two unsatisfied check nodes and only one satisfied check node.Figure 4
Example of a(4,1) absorbing set in the Tanner graph of an LDPC code.Simulations show that the majority of errors encountered in the error floor region during sum-product decoding of the IEEE 802.3 an low-density parity-check code could be attributed to absorbing sets [8, 9]. Although absorbing sets appear to be useful for estimating the performance of iterative message-passing decoding, they do not lead to strict upper bounds. For upper bounds, it is possible to use the concept of deviations on the computation tree.


## 2.5. Computation Trees and Deviations

In his 1996 dissertation, Wiberg [10] presented groundbreaking analytical results with respect to iterative decoding of low-density parity-check codes. He provided extensive analysis of both the MS and SP decoders by introducing a model of iterative decoding known as the computation tree. Wiberg showed that the MS decoder minimizes the probability of word error when decoding a code whose Tanner graph is a tree, while for the same type of code the SP decoder minimizes the probability of bit error.In addition to introducing computation trees, Wiberg also introduced the concept of deviations. Wiberg proved that deviations on the computation tree with negative cost are required in order for errors to occur during MS and SP decoding. Because of the importance of computation trees and deviations in understanding finite tree-based decoding, they are examined in detail in this section.Consider a low-density parity-check code represented by a Tanner graphT=(V⋃F,E). A computation tree rooted at variable node vi after ℓ iterations is denoted Rvi(ℓ). In order to construct a computation tree from the Tanner graph, a variable node vi is placed at the top level (root) of a descending tree. To construct the next level in the tree directly below vi, each of vi’s neighbors in N(vi) is added to this level and connected to vi. This process continues level-by-level, where nodes in the previous level are used to determine nodes on next level, while maintaining that each node in the computation tree has the same set of neighbors as its corresponding node in the Tanner graph. For example, if variable node vj on the last completed level is connected to check node fk on the level above it, then all check nodes in N(vj)∖fk must appear on the next level and be connected to vj, thereby ensuring that vj is connected to exactly one copy of each check node in N(vj).Figure5 gives an example of a Tanner graph, and its corresponding computation tree rooted at v1 after two iterations. Nodes at the bottom level of the computation tree are referred to as leaf nodes. Notice that the leaf nodes are the only nodes in the computation tree that are not connected to a copy of each of their neighbors in the original Tanner graph.Computation tree of a simple repetition code afterℓ=2 iterations.
(a)
Tanner graph(b)
Computation treeComputation trees are precise models for analyzing the performance and behavior of min-sum and sum-product decoding for a finite set of iterations. Each of these decoders can be precisely modeled afterℓ iterations by constructing N different computation trees that contain 2ℓ+1 levels of nodes including the root node. The N computation trees are each rooted at a different variable node from the original Tanner graph. Then, for every variable node vi in each computation tree, the LLR cost γi is assigned to that variable node. At this point, MS or SP decoding operations can be performed from the leaf nodes up to the root node. The final cost at each of the root nodes determines the binary estimate of the transmitted codeword computed by the decoder. Because the MS and SP decoders are optimal on Tanner graphs that are trees, the MS and SP decoders are optimal on each of the computation trees derived from the Tanner graph. MS chooses the least cost valid configuration on the tree, where a valid configuration refers to any assignment of binary numbers to the variable nodes such that each check node is adjacent to an even number of variable nodes assigned to a binary 1. The SP decoder, on the other hand, chooses the value at the root node that has the highest probability over all valid configurations.Although the computation tree model is precise, after a small number of iterations it becomes impractical to analyze the performance of specific codes by considering all valid configurations on the computation tree. The number of valid configurations on the computation tree can be computed by treating the computation tree as a Tanner graph. In order to define a Tanner graph given the computation tree, treat all check nodes and variable nodes in the computation tree separately. For example, if multiple copies of variable nodev1 are distributed throughout the computation tree, each copy is treated as a distinct variable node. After regarding each variable node in the computation tree as distinct, one can show that each check node on the computation tree corresponds to a linearly independent parity-check equation. If there are |Rvi(ℓ)(V)| variable nodes and |Rvi(ℓ)(F)| check nodes on a computation tree rooted at variable node vi after ℓ iterations, then there are a total of 2|Rvi(ℓ)(V)|-|Rvi(ℓ)(F)| valid configurations on the tree. On a (dV,dF)-regular LDPC code, the number of variable nodes after ℓ iterations is given by(11)|Rvi(ℓ)(V)|=1+∑i=0ℓ-1dV(dF-1)(((dV-1)(dF-1))i),
and the number of check nodes is given by (12)|Rvi(ℓ)(F)|=∑i=0ℓ-1dV(((dV-1)(dF-1))i).To illustrate the growth rate in the number of valid configurations on the computation tree, consider an LDPC code where each variable node has degreedV=3 and each check node has degree dF=6. These commonly used code parameters result in what are known as a (3,6)-regular LDPC codes. Table 1 shows the number of variable nodes given by (13)|Rvi(ℓ)(V)|=1+∑i=0ℓ-115(10i),Table 1
The number of nodes and valid configurations on the computation tree of a(3,6)-regular LDPC code.
IterationsVariable NodesCheck NodesConfigurations11638192216633≈104031666333≈10401the number of checks nodes given by(14)|Rvi(ℓ)(F)|=∑i=0ℓ-13·10i,and the corresponding number of valid configurations on the computation tree after 1, 2, and 3 iterations. Note that the growth rate is not affected by the block length of the code.Table1 illustrates the computational complexity associated with considering each valid configuration on the computation tree. In light of this, Wiberg [10] derived a simplified bound on the performance of MS decoding operating on a particular computation tree. In order to obtain this bound, Wiberg introduced the concept of deviations on the computation tree.Definition 4 (Deviation [10]).
Adeviation is any set of variable nodes on the computation tree satisfying the following three conditions.(1)
Each check node in the computation tree is adjacent to either two or zero variable nodes in the deviation set.(2)
A deviation set contains the root node of the computation tree.(3)
No proper and nonempty subset of variable nodes in the deviation from a valid configuration on the computation tree.Figure6 shows an example of a deviation on the computation tree given in Figure 5(b). The larger blue variable nodes are contained in the deviation, whereas the smaller red nodes are not.Figure 6
Example of a deviation on the computation tree.Wiberg uses the set of deviations on the computation tree to derive an upper bound on the performance of the min-sum decoder. It is necessary, but not sufficient, for at least one deviationδ in the set of all deviations Δ to have negative cost in order for an error to occur at the root node. The cost of the deviation, denoted by G(δ), can be found by summing the LLR cost of each of the nodes in the support of the deviation. The cost of a deviation is given by (15)G(δ)=∑vi∈δγi,where copies ofvi∈δ are counted as many times as they appear in the deviation. A necessary, but not sufficient, condition for an error to occur on the computation tree rooted at variable node vi is given by [10] (16)minδ∈ΔG(δ)<0.Using this condition, a bound can be derived on the probability that the minimum-cost configuration on the computation tree contains a binary 1 at the root node. This bound is(17)P(vi=1)≤P(minδ∈ΔG(δ)<0),≤⋃δ∈ΔP(G(δ)<0),which can be further loosened to(18)P(vi=1)≤∑δ∈ΔP(G(δ)<0),
by using the union bound.Wiberg [10] shows that the bound given by (18) can be used to predict the performance of min-sum decoding of infinite-length codes after a specific number of iterations. Wiberg begins by assuming that the computation trees have no repeated nodes. This assumption simplifies the weight enumerators of the deviations for regular LDPC codes. Wiberg also shows that (18) can be used to bound MS decoder performance when there are multiple copies of each variable node in the tree. Thus, in theory, Wiberg’s deviation bound can be used to bound the performance of MS decoding of finite length codes. The following proposition shows that the number of deviations grows exponentially with dV, thus making it computationally intractable to enumerate the deviations even after a small number of iterations.Proposition 1.
LetRvi(ℓ) be the computation tree of a (dV,dF)-regular LDPC code, rooted at variable node vi after ℓ iterations. Then, the number of deviations that exist on Rvi(ℓ) is
(19)(dF-1)∑i=1ℓdV(dV-1)i-1.Proof.
By the definition of a deviation, we must assign the root nodevi to a binary 1. Each of the dV check nodes immediately below vi must assign exactly one of the their (dF-1) child variable nodes to a binary 1. Thus, there are a total of (dF-1)dV deviations after one iteration. In addition, there are exactly dV leaf nodes in the support of each deviation after one iteration.
Each of the previousdV leaf nodes gets connected to (dV-1) check nodes after two iterations. Each of these check nodes assigns one of their (dF-1) child variable nodes to a binary 1. Therefore, for each deviation after one iteration there are (dF-1)dV(dV-1) different deviations after two iterations. This brings the total number of deviations to (dF-1)dV(dF-1)dV(dV-1)=(dF-1)(dV)2 after two iterations. The total number of leaf nodes in the support of the deviation after two iterations is dV(dV-1).
Following this pattern, thedV(dV-1) variable nodes in support of the deviation after two iterations branchs out to dV(dV-1)2 check nodes. There are (dF-1)dV(dV-1)2 ways of assigning the leaf nodes to the support of the previous deviation. This brings the total number of deviations to (dF-1)(dV)2(dF-1)dV(dV-1)2=(dF-1)(dV)3-(dV)2+dV after three iterations.
Afterℓ iterations, the dV(dV-1)ℓ-2 old leaf nodes in the support of the deviation branch out to dV(dV-1)ℓ-1 new leaf nodes in the support of the deviation. There are (dF-1)dV(dV-1)ℓ-1 ways of assigning the support to the previous deviation, and the total number of deviations after ℓ iterations is(20)∏i=1ℓ(dF-1)dV(dV-1)i-1=(dF-1)∑i=1ℓdV(dV-1)i-1.The number of deviations on the computation tree of a(3,6)-regular low-density parity-check code is given in Table 2 for iterations 1 through 5. Even after only a small number of iterations, it becomes impractical to enumerate each of the deviations in order to compute the upper bound on the probability of bit error of the root variable node of the computation tree.Table 2
Number of deviations at iterations 1–5 for a(3,6)-regular LDPC code.
Iterations# of deviations112521,953,12534.7684×101442.8422×103151.0097×1065Using computation trees, Wiberg provided a precise model of the behavior of the min-sum and sum-product decoders. Unfortunately, the size of the computation trees and the number of configurations on them grows too large for practical analysis. Deviations provide a simplified approach to the analysis of computation trees, but the number of deviations also grows exponentially with the number of iterations.


## 3. Stopping Sets, Absorbing Sets, and Resulting Deviations

Deviations can be used to define a necessary condition for an error to occur during iterative decoding. The condition simply states that there must be at least one deviation with cost less than zero, assuming that  the all-zeros codeword was sent. However, this condition says nothing about which deviations are more or less likely to cause errors. What is known is that at high SNRs low-weight, deviations are much more likely to cause errors than high-weight deviations. Thus it is reasonable to expect that low-weight stopping sets and low-weight deviations coincide over the BEC channel, since low-weight stopping sets are precisely the cause of errors for iterative decoding over the BEC [15]. For the same reason, one can expect that trapping sets, or more specifically absorbing sets, coincide with low-weight deviations over the AWGN channel, since they have been frequently observed to cause errors at high SNR during iterative decoding of LDPC codes over the AWGN channel [8, 17]. Connections between stopping/absorbing sets and deviations and their effect on decoding performance are examined in this section.


### 3.1. Stopping Sets as Deviations

Stopping sets consist of a subset𝒮 of the variable nodes, such that each check node connected to an element in 𝒮 is connected at least twice. According to the definition of a deviation given in Definition 4, each check node connected to the variable nodes in a deviation is connected exactly two times. These two properties can be used to study the relationship between stopping sets and their corresponding deviations.First, consider a computation tree where each of the variable nodes begins with an assignment of a binary 0. Then, assign all copies of variable nodes in𝒮 to a binary 1. If 𝒮 does not correspond with a codeword in C, the resulting configuration on the computation tree will not be a valid configuration. For example, consider check node f2 in Figure 2. Each time, check node f2 appears in the computation tree, it will be connected to three variable nodes assigned to a binary 1, including the parent variable node and two child variable nodes. If one of the child variable nodes of f2 along with all of its descendants is set to a binary 0, check node f2 will be satisfied. If this is done for every unsatisfied check node in the computation tree, a deviation is created that contains only variable nodes in 𝒮. Thus, this method allows one to create a deviation from a stopping set.Using the method previously described, a deviation can be constructed using only the variable nodes contained in a stopping set. This is illustrated in Figure7(a), where a portion of the deviation defined by the set 𝒮 from Figure 2 is given. Since only one of the child variable nodes can be included in the deviation, it is sufficient to randomly include v2 and exclude v4, since both nodes are included in 𝒮. The effect of this deviation is now examined over the BEC and the BSC. Stopping sets are known to cause errors over the BEC. The reason for this is illustrated by Figure 7(b). When each variable node in 𝒮 is received as an erasure ε, it only takes one erasure below f2 to cause an erasure message to be sent from f2 to v1. However, even though two erasures are connected below f2 in Figure 7(b), the same erasure message is sent up to v1. This example illustrates that a deviation containing all erasures is sufficient for an erasure output at the root node. Thus there is a strong connection between stopping sets and deviations over the BEC, since both cause errors using iterative decoding and deviations can be created from stopping sets.A small portion of a deviation on a computation tree illustrating the impact of stopping set deviations on the BEC and BSC channels.
(a)
Deviation(b)
Costs on the BEC(c)
Costs on the BSCThe reason stopping sets will not cause errors as frequently over the BSC is illustrated in Figure7(c). A deviation containing only the variable nodes in a stopping set exists on a computation tree rooted at any one of the variable nodes in 𝒮 regardless of the channel. However, the impact of deviations is not the same across all channels. For example, if two messages of -1 (representing binary 1s) are being sent from v2 and v4, the message sent from f2 up to v1 is a +1 (representing a binary 0). This example shows that while a deviation created from a stopping set is sufficient to cause erasure outputs from the decoder over the BEC, this same deviation may not cause errors over the BSC.From Figure7, it is clear that deviations created from stopping sets have a different effect on iterative decoding over the binary erasure channel and the binary symmetric channel. While it is not as clear how deviations created from stopping sets will effect decoding over the AWGN channel, some similarities can be drawn between the BEC and the AWGN. In terms of channel LLR costs, an erasure over the BEC behaves like a LLR cost of zero over the AWGN. A real-valued LLR interpretation of the BEC channel can be created using real-valued costs of -1.0,+1.0, and 0.0 to represent a binary 1, 0, and an erasure ɛ, respectively. Binary information is transmitted as x=-1.0 and x=+1.0 over the AWGN channel, and the probability P(y=+1.0∣x=-1.0)=P(y=-1.0∣x=+1.0)<P(y=0.0∣x=-1.0)=P(y=0.0∣x=+1.0), regardless of the channel SNR. Thus, it is reasonable to suspect that the AWGN channel behaves more like the BEC than the BSC, especially at high channel SNR.


### 3.2. Absorbing Sets as Deviations

Absorbing sets project to deviations on the computation tree in a different way than stopping sets. Since each check node connected to a stopping set𝒮 is connected at least twice, a deviation can easily be defined using only nodes in 𝒮 on any computation tree rooted at a node in 𝒮. Unlike stopping sets, absorbing sets can have only a single connection to a check node. When an absorbing set has a single connection to a check node, it is not possible to form a deviation on any computation tree using only the variable nodes in 𝒜, unless there is a stopping set 𝒮⊆𝒜. If 𝒮⊆𝒜, a deviation can be formed on the computation tree by simply avoiding variable nodes in 𝒜 that are not in 𝒮.For an absorbing set𝒜 that does not contain a stopping set, it is of interest to know how the absorbing set manifests itself as a deviation on the computation tree rooted at one of the variable nodes in 𝒜. This manifestation takes the form of a deviation with as many variable nodes in 𝒜 as possible. Because it is known that each variable node is connected to strictly more satisfied check nodes than unsatisfied check nodes, it is possible to compute a bound on the number of variable nodes in a deviation δ that are contained in 𝒜 for regular LDPC codes.Consider an absorbing set𝒜 on the Tanner graph of a (dV,dF)-regular low-density parity-check code. Let each variable node vi∈𝒜 be connected to at least d𝒜>dV/2 satisfied check nodes. A computation tree rooted at a variable node vi∈𝒜 after ℓ iterations is given by Rviℓ. A deviation on this computation tree can be constructed by selecting the nodes in the deviation level-by-level. The deviation construction begins by including the root node vi at level ℓ=0. At the next level, one variable node connected to each of the check nodes in N(vi) must be included in δ. When possible, variable nodes in 𝒜 will always be included in δ. Therefore, after ℓ=1 there are at least 1+d𝒜 variable nodes in δ that are also in 𝒜, and at most dV-d𝒜 variable nodes in δ that are not in 𝒜. Continuing to level ℓ=2 in the computation tree, each of the d𝒜 variable nodes in 𝒜 at level ℓ=1 in δ connects to d𝒜-1 new variable nodes in 𝒜 and dV-d𝒜 new variable nodes not in 𝒜. Each of the dV-d𝒜 variable nodes at level ℓ=1 in δ that are not in 𝒜 connects to dV-1 variable nodes that are not it 𝒜. After ℓ=2, the number of variable nodes in δ that are also in 𝒜 is(21)|δ𝒜|≥1+d𝒜∑i=1ℓ(d𝒜-1)i-1.
Similarly, the total number of variable nodes in δ is(22)|δ|=1+dV∑i=1ℓ(dV-1)i-1.
Therefore, the number of variable nodes in δ that are not in 𝒜 is |δ|-|δ𝒜|.It is clear from (21) and (22) that the lower bound on the portion of variable nodes in 𝒜 within the deviation δ given by |δ𝒜|/|δ| approaches zero as ℓ approaches infinity. Thus, the bound does not appear to be an accurate method for calculating the true portion. The bound given by (21) is computed under the worst-case scenario that, after a deviation reaches a check node with only one connection to the set 𝒜, the descendants of that check node contained in the deviation do not contain any more variable nodes in 𝒜. On a connected Tanner graph with no nodes of degree one and d𝒜≠dV, this assumption is most likely never true, since nodes in 𝒜 will eventually (with increasing ℓ) be included in the descendants of the failed check node, and consequently the variable nodes will also be included in any deviation which is a manifestation of 𝒜.For finite-length,(dV,dF)-regular low-density parity check codes, it is possible to determine the exact number of variable nodes |δ𝒜| after a given number of iterations ℓ. In order to find |δ𝒜|, each variable node vi∈𝒜 is assigned a LLR cost of λi=0.0 and each variable node vj∈V∖𝒜 is assigned a LLR cost of λj=+1.0. Then, using the resulting LLR cost vector, MS decoding is performed for ℓ iterations. The final cost mi for any variable node vi∈𝒜, is the number of nodes in the minimum-cost deviation on the computation tree rooted at vi after ℓ iterations. Deviations for (dV,dF)-regular LDPC codes contain a fixed number of variable nodes determined by (22), and the only way to reduce the cost of the deviation is to include variable nodes from the set 𝒜. Thus, the minimum-cost deviation on the computation tree of a (dV,dF)-regular LDPC code will include the maximum number of variable nodes in 𝒜 that is possible, and the MS decoder will output the cost of this deviation. It is important to note that the cost of the deviation returned by the MS decoder corresponds to the number of variable nodes in the deviation that are not in 𝒜. Therefore, in order to determine the number of variable nodes in the deviation that are in 𝒜, it is necessary to subtract this MS decoder cost from the result given by (22).Example 1.
Consider the lengthN=20, dimension K=10, (3,6)-regular low-density parity-check code defined by the parity check matrix(23)H=[01000010010010010001001001000010100100100100100100100000110000110000010001101000001010001001001000010100010010010100000100010011000100010010100100001010000010101000010101000010010010001010000011000100].A (3,1) fully absorbing set is defined by the set of variable nodes 𝒜1={v3,v7,v16}, where columns 1 through 20 of H corresponds to the set of variable nodes {v0,v1,…,v19}. After 50 iterations, each of the deviations on each of the N computation trees contains |δ|≈3.378×1015 variable nodes, as computed by (22). After setting the LLR costs for variable nodes in 𝒜1 to λ=0.0, and all other LLR cost to λ=+1.0, the output of the MS decoder after 50 iterations for variable node v7 is a cost of mv7=3.044×1014. Therefore, the minimum-weight deviation contains 3.073×1015=3.378×1015-3.044×1014 variable nodes also contained in the absorbing set 𝒜1. Thus, a deviation can be formed on the computation tree with 91% of its variable nodes coming from 𝒜1. In contrast, the bound given by (21) for (3,6)-regular LDPC codes after 50 iterations with d𝒜=2 only guarantees that 101 variable nodes from 𝒜1 will be included in the minimum weight deviation. This huge disparity between the bound and the actual result given by MS decoding reveals the effects of the assumptions used to derive (21). It is worth noting that the proportion of variable nodes in 𝒜1 in the minimum weight deviation after 51 and 52 iterations were also 91%, so this proportion appears to stabilize after a sufficient number of iterations.
Using this same method on the(3,3) fully absorbing set 𝒜2={v0,v7,v18}, it is found that the minimum weight deviation after 50 iterations contains 2.696×1015 copies of the variable nodes in 𝒜2, equivalent to 78% of the total number of variable nodes in the deviation. By comparing the properties of the minimum-weight deviations resulting from 𝒜1 and 𝒜2, one might expect that 𝒜1 is more likely to cause errors than 𝒜2. This is because 91% of the cost of the deviation resulting from 𝒜1 is determined by the variable nodes in 𝒜1, compared to only 78% for 𝒜2. Simulation results in Section 4 show that 𝒜1 causes errors much more frequently than 𝒜2.


## 3.1. Stopping Sets as Deviations

Stopping sets consist of a subset𝒮 of the variable nodes, such that each check node connected to an element in 𝒮 is connected at least twice. According to the definition of a deviation given in Definition 4, each check node connected to the variable nodes in a deviation is connected exactly two times. These two properties can be used to study the relationship between stopping sets and their corresponding deviations.First, consider a computation tree where each of the variable nodes begins with an assignment of a binary 0. Then, assign all copies of variable nodes in𝒮 to a binary 1. If 𝒮 does not correspond with a codeword in C, the resulting configuration on the computation tree will not be a valid configuration. For example, consider check node f2 in Figure 2. Each time, check node f2 appears in the computation tree, it will be connected to three variable nodes assigned to a binary 1, including the parent variable node and two child variable nodes. If one of the child variable nodes of f2 along with all of its descendants is set to a binary 0, check node f2 will be satisfied. If this is done for every unsatisfied check node in the computation tree, a deviation is created that contains only variable nodes in 𝒮. Thus, this method allows one to create a deviation from a stopping set.Using the method previously described, a deviation can be constructed using only the variable nodes contained in a stopping set. This is illustrated in Figure7(a), where a portion of the deviation defined by the set 𝒮 from Figure 2 is given. Since only one of the child variable nodes can be included in the deviation, it is sufficient to randomly include v2 and exclude v4, since both nodes are included in 𝒮. The effect of this deviation is now examined over the BEC and the BSC. Stopping sets are known to cause errors over the BEC. The reason for this is illustrated by Figure 7(b). When each variable node in 𝒮 is received as an erasure ε, it only takes one erasure below f2 to cause an erasure message to be sent from f2 to v1. However, even though two erasures are connected below f2 in Figure 7(b), the same erasure message is sent up to v1. This example illustrates that a deviation containing all erasures is sufficient for an erasure output at the root node. Thus there is a strong connection between stopping sets and deviations over the BEC, since both cause errors using iterative decoding and deviations can be created from stopping sets.A small portion of a deviation on a computation tree illustrating the impact of stopping set deviations on the BEC and BSC channels.
(a)
Deviation(b)
Costs on the BEC(c)
Costs on the BSCThe reason stopping sets will not cause errors as frequently over the BSC is illustrated in Figure7(c). A deviation containing only the variable nodes in a stopping set exists on a computation tree rooted at any one of the variable nodes in 𝒮 regardless of the channel. However, the impact of deviations is not the same across all channels. For example, if two messages of -1 (representing binary 1s) are being sent from v2 and v4, the message sent from f2 up to v1 is a +1 (representing a binary 0). This example shows that while a deviation created from a stopping set is sufficient to cause erasure outputs from the decoder over the BEC, this same deviation may not cause errors over the BSC.From Figure7, it is clear that deviations created from stopping sets have a different effect on iterative decoding over the binary erasure channel and the binary symmetric channel. While it is not as clear how deviations created from stopping sets will effect decoding over the AWGN channel, some similarities can be drawn between the BEC and the AWGN. In terms of channel LLR costs, an erasure over the BEC behaves like a LLR cost of zero over the AWGN. A real-valued LLR interpretation of the BEC channel can be created using real-valued costs of -1.0,+1.0, and 0.0 to represent a binary 1, 0, and an erasure ɛ, respectively. Binary information is transmitted as x=-1.0 and x=+1.0 over the AWGN channel, and the probability P(y=+1.0∣x=-1.0)=P(y=-1.0∣x=+1.0)<P(y=0.0∣x=-1.0)=P(y=0.0∣x=+1.0), regardless of the channel SNR. Thus, it is reasonable to suspect that the AWGN channel behaves more like the BEC than the BSC, especially at high channel SNR.


## 3.2. Absorbing Sets as Deviations

Absorbing sets project to deviations on the computation tree in a different way than stopping sets. Since each check node connected to a stopping set𝒮 is connected at least twice, a deviation can easily be defined using only nodes in 𝒮 on any computation tree rooted at a node in 𝒮. Unlike stopping sets, absorbing sets can have only a single connection to a check node. When an absorbing set has a single connection to a check node, it is not possible to form a deviation on any computation tree using only the variable nodes in 𝒜, unless there is a stopping set 𝒮⊆𝒜. If 𝒮⊆𝒜, a deviation can be formed on the computation tree by simply avoiding variable nodes in 𝒜 that are not in 𝒮.For an absorbing set𝒜 that does not contain a stopping set, it is of interest to know how the absorbing set manifests itself as a deviation on the computation tree rooted at one of the variable nodes in 𝒜. This manifestation takes the form of a deviation with as many variable nodes in 𝒜 as possible. Because it is known that each variable node is connected to strictly more satisfied check nodes than unsatisfied check nodes, it is possible to compute a bound on the number of variable nodes in a deviation δ that are contained in 𝒜 for regular LDPC codes.Consider an absorbing set𝒜 on the Tanner graph of a (dV,dF)-regular low-density parity-check code. Let each variable node vi∈𝒜 be connected to at least d𝒜>dV/2 satisfied check nodes. A computation tree rooted at a variable node vi∈𝒜 after ℓ iterations is given by Rviℓ. A deviation on this computation tree can be constructed by selecting the nodes in the deviation level-by-level. The deviation construction begins by including the root node vi at level ℓ=0. At the next level, one variable node connected to each of the check nodes in N(vi) must be included in δ. When possible, variable nodes in 𝒜 will always be included in δ. Therefore, after ℓ=1 there are at least 1+d𝒜 variable nodes in δ that are also in 𝒜, and at most dV-d𝒜 variable nodes in δ that are not in 𝒜. Continuing to level ℓ=2 in the computation tree, each of the d𝒜 variable nodes in 𝒜 at level ℓ=1 in δ connects to d𝒜-1 new variable nodes in 𝒜 and dV-d𝒜 new variable nodes not in 𝒜. Each of the dV-d𝒜 variable nodes at level ℓ=1 in δ that are not in 𝒜 connects to dV-1 variable nodes that are not it 𝒜. After ℓ=2, the number of variable nodes in δ that are also in 𝒜 is(21)|δ𝒜|≥1+d𝒜∑i=1ℓ(d𝒜-1)i-1.
Similarly, the total number of variable nodes in δ is(22)|δ|=1+dV∑i=1ℓ(dV-1)i-1.
Therefore, the number of variable nodes in δ that are not in 𝒜 is |δ|-|δ𝒜|.It is clear from (21) and (22) that the lower bound on the portion of variable nodes in 𝒜 within the deviation δ given by |δ𝒜|/|δ| approaches zero as ℓ approaches infinity. Thus, the bound does not appear to be an accurate method for calculating the true portion. The bound given by (21) is computed under the worst-case scenario that, after a deviation reaches a check node with only one connection to the set 𝒜, the descendants of that check node contained in the deviation do not contain any more variable nodes in 𝒜. On a connected Tanner graph with no nodes of degree one and d𝒜≠dV, this assumption is most likely never true, since nodes in 𝒜 will eventually (with increasing ℓ) be included in the descendants of the failed check node, and consequently the variable nodes will also be included in any deviation which is a manifestation of 𝒜.For finite-length,(dV,dF)-regular low-density parity check codes, it is possible to determine the exact number of variable nodes |δ𝒜| after a given number of iterations ℓ. In order to find |δ𝒜|, each variable node vi∈𝒜 is assigned a LLR cost of λi=0.0 and each variable node vj∈V∖𝒜 is assigned a LLR cost of λj=+1.0. Then, using the resulting LLR cost vector, MS decoding is performed for ℓ iterations. The final cost mi for any variable node vi∈𝒜, is the number of nodes in the minimum-cost deviation on the computation tree rooted at vi after ℓ iterations. Deviations for (dV,dF)-regular LDPC codes contain a fixed number of variable nodes determined by (22), and the only way to reduce the cost of the deviation is to include variable nodes from the set 𝒜. Thus, the minimum-cost deviation on the computation tree of a (dV,dF)-regular LDPC code will include the maximum number of variable nodes in 𝒜 that is possible, and the MS decoder will output the cost of this deviation. It is important to note that the cost of the deviation returned by the MS decoder corresponds to the number of variable nodes in the deviation that are not in 𝒜. Therefore, in order to determine the number of variable nodes in the deviation that are in 𝒜, it is necessary to subtract this MS decoder cost from the result given by (22).Example 1.
Consider the lengthN=20, dimension K=10, (3,6)-regular low-density parity-check code defined by the parity check matrix(23)H=[01000010010010010001001001000010100100100100100100100000110000110000010001101000001010001001001000010100010010010100000100010011000100010010100100001010000010101000010101000010010010001010000011000100].A (3,1) fully absorbing set is defined by the set of variable nodes 𝒜1={v3,v7,v16}, where columns 1 through 20 of H corresponds to the set of variable nodes {v0,v1,…,v19}. After 50 iterations, each of the deviations on each of the N computation trees contains |δ|≈3.378×1015 variable nodes, as computed by (22). After setting the LLR costs for variable nodes in 𝒜1 to λ=0.0, and all other LLR cost to λ=+1.0, the output of the MS decoder after 50 iterations for variable node v7 is a cost of mv7=3.044×1014. Therefore, the minimum-weight deviation contains 3.073×1015=3.378×1015-3.044×1014 variable nodes also contained in the absorbing set 𝒜1. Thus, a deviation can be formed on the computation tree with 91% of its variable nodes coming from 𝒜1. In contrast, the bound given by (21) for (3,6)-regular LDPC codes after 50 iterations with d𝒜=2 only guarantees that 101 variable nodes from 𝒜1 will be included in the minimum weight deviation. This huge disparity between the bound and the actual result given by MS decoding reveals the effects of the assumptions used to derive (21). It is worth noting that the proportion of variable nodes in 𝒜1 in the minimum weight deviation after 51 and 52 iterations were also 91%, so this proportion appears to stabilize after a sufficient number of iterations.
Using this same method on the(3,3) fully absorbing set 𝒜2={v0,v7,v18}, it is found that the minimum weight deviation after 50 iterations contains 2.696×1015 copies of the variable nodes in 𝒜2, equivalent to 78% of the total number of variable nodes in the deviation. By comparing the properties of the minimum-weight deviations resulting from 𝒜1 and 𝒜2, one might expect that 𝒜1 is more likely to cause errors than 𝒜2. This is because 91% of the cost of the deviation resulting from 𝒜1 is determined by the variable nodes in 𝒜1, compared to only 78% for 𝒜2. Simulation results in Section 4 show that 𝒜1 causes errors much more frequently than 𝒜2.


## 4. Finding Problematic Trapping Sets

Any set of nodes can be interpreted as a trapping set, including stopping sets, absorbing sets, and fully absorbing sets. This is because trapping sets are only defined by the number of variable nodes in the set and the number of failed check nodes. In order to simplify analysis, the trapping sets studied in this paper are restricted to the study of problematic trapping sets.Definition 5 (Problematic Trapping Set).
Aproblematic trapping set is a trapping set such that the number of failed check nodes connected to the trapping set is less than or equal to the number variable nodes contained in the trapping set.Because trapping sets with small weight and a small number of failed check nodes are often the cause of errors at high SNR [17], it is unlikely that the restriction to problematic trapping sets will eliminate error patterns of interest. In Section 3, it was shown that MS decoding can be used to determine the proportion of variable nodes that are both inside and outside an absorbing set. The same idea is used in this section to find problematic trapping sets using MS decoding. The iterative method given by Algorithm 1 operates by forcing the trapping set to contain one variable node, and then adding more variable nodes one-by-one that decrease the cost of the minimum-cost deviation the most.Algorithm 1:Iterative problematic trapping set finder.
forifixed=1,…,NSetmmin=∞.Setχ={ifixed}.whilemmin>0.0fori=1,…,N-Setχ=χ⋃{i}.-Setλk=0.0 for all k∈χ.-Setλk=1.0 for all k∈V∖χ.-Perform MS Decoding forℓ iterations.if minj=1,…,Nmvj<mmin-Setmmin=minj=1,…,Nmvj.-Setjmin=argminj=1,…,Nmvj.end-Setχ=χ⋂({V∖{i}}⋃{ifixed}).end-Setχ=χ⋃{jmin}.-Create a binary vectorvwith vk=1 if k∈χ, andvk=0 if k∈V∖χ.-Compute the integar syndromesint=HvT.-Compute the binary syndromesbin=HvT withHamming weightws.-Compute the integar vectorz=HTsbinif mink=1,…,Msint,k≥2χ is a (|χ|,ws) Stopping Set.endχ is a (|χ|,ws) Trapping Set.if zk<⌊dvk2⌋ for all k∈χχ is a (|χ|,ws) Absorbing Set.endif zk<⌊dvk2⌋ for all k=1,…,Nχ is a (|χ|,ws) Fully Absorbing Set.endendendOnce Algorithm1 reaches cost mmin=0.0, it is possible to discover more problematic trapping sets by removing nodes one-by-one from the set 𝒳 that result in the smallest increase in the cost mmin. In order to examine the efficacy of Algorithm 1, the length N=20, dimension K=10, (3,6)-regular low-density parity-check code given in Example 1 was used. This code was chosen because the Hamming weight of all of its codewords could be enumerated, and thus the minimum distance of the code could be easily computed. Applying Alogorithm 1 to this code resulted in a total of 37 trapping sets with parameters shown in Table 3. Note that the proportion of nodes in each set that are included in the minimum weight deviation is given by “Dev. %”. This code was found to have minimum distance equal to 4, so only stopping/trapping/absorbing sets of weight less than or equal to 3 are tabulated.Table 3
Stopping/trapping/absorbing sets of a lengthN=20, dimension K=10, (3,6)-regular LDPC code with weight of 3 or less found using Algorithm 1, and the number of times they were observed after 1000 iterations of SP decoding at SNR = 8.0 dB.
SetSizeDev. %Stop.Abs.Full Abs.Observed{v0,v17}(2,2)74%X16{v1,v19}(2,2)73%X7{v2,v14}(2,2)71%X4{v3,v16}(2,2)72%X7{v4,v17}(2,2)72%X28{v6,v15}(2,2)76%X0{v7,v17}(2,2)73%X6{v8,v11}(2,2)75%X21{v9,v14}(2,2)73%X19{v10,v18}(2,2)73%X4{v11,v19}(2,2)76%X28{v6,v12}(2,2)76%X0{v6,v12,v15}(3,1)100%XXX908{v0,v10,v17}(3,1)91%XX9{v1,v4,v19}(3,1)90%XX20{v2,v5,v14}(3,1)89%XX6{v3,v7,v16}(3,1)91%XX26{v4,v14,v17}(3,1)90%XX35{v6,v7,v17}(3,1)92%XX0{v8,v11,v18}(3,1)91%XX28{v9,v14,v19}(3,1)90%XX20{v7,v10,v18}(3,1)91%XX16{v11,v15,v19}(3,1)91%XX17{v0,v7,v18}(3,3)80%X0{v1,v14,v19}(3,3)64%0{v2,v5,v19}(3,3)79%X0{v0,v4,v14}(3,3)79%X0{v5,v6,v15}(3,3)86%0{v7,v12,v15}(3,3)86%0{v2,v9,v12}(3,3)78%X0{v6,v11,v12}(3,3)85%0{v12,v13,v15}(3,3)85%0{v13,v14,v19}(3,3)57%X0{v7,v17,v18}(3,3)85%0Other275In order to determine how effective Algorithm1 is at locating problematic trapping sets, the same length N=20, dimension K=10, (3,6)-regular low-density parity-check code was simulated using sum-product decoding over the additive white Gaussian noise channel with an SNR of Eb/N0 = 8.0 dB. A total of 1500 noncodeword outputs with weight less than or equal to 3 were observed during SP decoding after 1000 iterations. It is important to note that the noncodewords outputs were not simply the last quantized output given after 1000 iterations. The output of SP decoding typically changes after each iteration when it does not converge to a codeword. For this reason, the noncodeword outputs were computed by averaging the cost mvi for each variable node vi from i=1,…,N over the last 200 iterations to compute a final output cost. This is similar to the method used in [14] for characterizing the changing outputs of the MS decoder.Table3 shows the number of observed output errors, and compares them to the problematic trapping sets found using Algorithm 1. Approximately 82% of the observed errors corresponded to one of the problematic trapping sets found using Algorithm 1. Also, the number of times a particular problematic trapping set is observed indicates how problematic the set is to the SP decoder. The single most problematic set, resulting in over 60% of the output errors, was the (3,1) set that satisfies the definitions of a stopping set, absorbing set, and fully absorbing set. Errors falling into the “Other” category were highly variable, and no specific output pattern in this set accounted for more than 6 of the total observed errors.The problematic trapping sets with the highest proportion of nodes within their corresponding deviation were the(3,1) trapping sets. Not surprisingly, the (3,1) stopping set has the highest proportion of variable nodes in its deviation. While the proportions were noticeably different between different-sized sets, the difference was minimal within sets of the same size. Furthermore, it is difficult to make any connections between proportions within sets of the same size and their corresponding probability of causing an error. One possible reason for this might be the overlap between the different problematic trapping sets, and between the problematic trapping sets and codewords. For example, the reason that the (2,2) fully absorbing set {v6,v12} did not appear in the simulations might be because two of its variable nodes overlap with the exceptionally problematic (3,1) stopping set, and thus any significant channel noise received by variable nodes v6 and v12 may be highly likely to cause the (3,1) stopping set to be output by the decoder.It is worth noting that the average value of received information within the absorbing sets of weight less than or equal to three wasy=0.102115. Recall that a binary 0 is modulated to x=-1.0, so the mean value of the noise within the absorbing sets was +1.102115. This cost further justifies the earlier assertion that the AWGN channel behaves more like the BEC channel at high SNR than the BSC channel, since an erasure over the BEC can be interpreted as noise of +1.0 and a bit flip over the BSC can be interpreted as noise of +2.0.Algorithm1 was able to find 82% of the most problematic errors with weight less than dmin. In order to test the algorithm on an LDPC code with longer block length, a length N=200, K=100, (3,6)-regular LDPC code was used. The resulting output of Algorithm 1 was 1019 absorbing sets, 941 fully absorbing sets, and 1 stopping set, and the sizes of the sets ranged from 3 to 9. Only sets containing less than 10 variable nodes were considered problematic, since the code is known to contain a codeword of weight 10. Simulations were performed using SP decoding at SNR = 5.0 dB, at which the bit error rate of the code is Pb=4.8×10-9. Overall, 40 noncodeword errors were observed, of which 20 were error patterns of weight less than 10. Of these, all were absorbing sets and 19 were fully absorbing sets. Unlike the results given for the length N=20 code, only two of the 20 absorbing sets was found by Algorithm 1. However, the two that were found were the two smallest absorbing sets, including (5,3) and (6,4) fully absorbing sets.As expected, the number of trapping sets grows very large when increasing the size and dimension of the code. Algorithm1 is capable of locating the majority of problematic trapping sets for a small length N=20 LDPC code, but for the larger length N=200 LDPC code it was only able to identify the two smallest sets observed during simulations. This is likely due to the fact that the code had not yet reached its error floor, as evidenced by the fact that half of the observed error patterns had weight greater than or equal to the weight of a known codeword. Because error floors occur at such low bit error rates for large LDPC codes, it is difficult to observe problematic trapping sets using simulations. Thus, the effectiveness of Algorithm 1 at identifying problematic trapping sets remains unknown for large codes with error floors beyond the reach of simulations.


## 5. The Weight of Deviations Induced byProblematic Trapping Sets

In [17], Richardson characterizes trapping sets by their size and the number of associated failed check nodes. To find the impact of the trapping sets with respect to probability of error, Richardson uses simulations that force the noise in the trapping set and push the received information away from modulated 0s and towards modulated 1s. The result is an estimate of the probability of error caused by trapping sets at high SNR. In this section, a new method is used to examine the probability of error associated with trapping sets. Instead of using simulations to estimate the probability of error, deviations induced by the trapping set are created to analyze the probability of error. Since bounds on the probability of error can be derived from deviations, if one could prove that minimum-weight deviations were induced by problematic trappings sets and then computed the weights of the deviations, it may be possible determine the probability of error associated with trapping sets without having to rely on simulations.It may seem surprising that almost all problematic trapping sets listed in Table3 result in a deviation where the variable nodes within the trappings set make up the majority of the variable nodes within that deviation. For example, consider the fully absorbing set given by the nodes {v11,v19}. While there are only two variable nodes contained in the absorbing set, they make up 76% of the variable nodes in a deviation that exists on the computation tree rooted at either variable node within the set. This implies that there might be a way of cleverly designing deviations which contain a disproportionately large number of certain variable nodes. A deviation rooted at variable node v19 after 4 iterations is shown in Figure 8. This deviation was designed to include more copies of variable nodes v11 and v19 than other variable nodes. Overall, the number of copies of each variable node in the deviation is #v11=16, #v19=13, #v6=9, #v12=5, and #v15=3. Although the overall configuration contains 5 different variable nodes, almost 2/3 of them are copies of v11 or v19. Now, consider the subgraph of the Tanner graph defined by these 5 variable nodes, shown in Figure 9. This subgraph defines a (5,1) stopping set. It was shown in Section 3.1 that, because it is a stopping set, the deviation in Figure 8 could continue to grow indefinitely without the need for variable nodes outside the stopping set.Figure 8
Deviation designed to maximize the number of copies ofv11 and v19.Figure 9
Subgraph of the Tanner graph.To construct the deviation in Figure8, decisions were made at check nodes f0 and f6. Those decisions are expressed in the directed bipartite graph shown in Figure 10. The number of decisions for each check node is equivalent to the number of edges incident to the check node. Check nodes f1, f4, f5, and f9 each have two copies in the directed graph to preserve the fact that they have bidirectional edges. However, check nodes f0 and f6 do not simply have bidirectional edges connecting them to each of their incident variable nodes, as demonstrated by the deviation in Figure 8. This comes from the fact that check nodes with degree higher than 2 are still only connected to 2 variable nodes within the deviation. Thus, at each check node with degree greater than 2, a decision is made as to which variable nodes it includes in the deviation.Figure 10
Subgraph of the Tanner graph with repeated check nodes and directed edges.Using the adjacency matrix of the directed bipartite graph, it is possible to compute the number of copies, or the multiplicity, of each node at each level in the deviation. The method for computing the multiplicity of nodes in the deviation is similar to the method given in [18] for computing the multiplicity of nodes on computation trees. For the directed Tanner graph given in Figure 10, the adjacency matrix is given by(24)A=[00010000000010100000001011100000000010000000100000100000000001110001010000001000000010001000000100100000100100000001001000000010001010000010001000000100].The columns and rows ofA correspond, in the same order, to the nodes v6, v11, v12, v15, v19, f01, f02, f03, f04, f11, f12, f41, f42, f51, f52, f61, f62, f63, f91, and f92. Beginning with a vector m0 which has a 1 in the position of the root node and 0s elsewhere, the number of nodes on each level i of the deviation can be calculated recursively using(25)mi={Ami-1,ifiiseven,Ami-1-Bmi-2,ifiisodd,
where B is used to subtract the parent check nodes at each check node level in the deviation. The matrix B for the directed Tanner graph in Figure 10 is given by(26)B=[000010000000011100110011001100000011100110].Using the recursive formula given by (25), the number of variable nodes at different levels in the computation tree is given in Table 4. The deviation at level i=100 exists on the computation tree rooted at variable node v19 after ℓ=50 iterations. This deviation contains a total of 3.38×1015 variable nodes, over 63% of which are copies of v11 and v19. Using a similar method to that given in [19], the effective weight of the deviation can be calculated. First, let avi be the number of copies of variable node vi within the deviation, and let b be the total number of variable nodes in the deviation. The cost of the deviation is modeled by the normal distribution (27)𝒩(∑vi∈𝒮avib,∑vi∈𝒮(avibσ)2),Table 4
The multiplicity of variable nodes contained in the deviation created using the directed graph given in Figure10.
iv6v11v12v15v1900000121200042110262221584112252032646815878506603.4×1084.9×1081.7×1088.5×1075.3×1081003.6×10145.2×10141.8×10148.9×10135.5×1014Total7.1×10141.0×10153.6×10141.8×10141.1×1015whereσ2 is the variance of the AWGN noise. This random variable can be rescaled resulting in the distribution (28)𝒩((∑vi∈𝒮avi∑vi∈𝒮(avi)2)2,(∑vi∈𝒮avi∑vi∈𝒮(avi)2)2σ2),where the mean(29)(∑vi∈𝒮avi∑vi∈𝒮(avi)2)2,
is the weight of the deviation. Note that if all avi were equal, the weight of the set 𝒮 would be equal to the number of nodes it contains, which is consistent with the notion of Hamming weight when 𝒮 is equal to a codeword. From Table 4, the weight of the deviation created from the directed Tanner graph in Figure 10 after ℓ=50 iterations is 3.8784. This is less than the Hamming weight of the minimum distance codeword in the code, which has weight 4.0. Thus, the minimum weight of deviations on the computation tree rooted at v19 is probably less than the minimum distance of the code.


## 6. Conclusion

Practical methods for predicting and understanding the performance of low-density parity-check codes with iterative decoders are needed in order to avoid the use of codes with error floors. Trapping sets, which include absorbing sets and stopping sets, provide insight into the error mechanisms of iterative decoders but are too imprecise to be used to make design decisions with respect to error floors. Deviations on computation trees are precise and can be used to compute strict upper bounds on the performance of MS and SP decoding, but computing these bounds quickly becomes computationally intractable. The paper examined the connections between trapping sets and their corresponding deviations through the notion of problematic trapping sets in an attempt to find a practical and precise method for predicting the performance of LDPC codes with iterative decoding.It was shown that the variable nodes in a stopping set can be used to define a deviation, while trapping sets and absorbing sets only define a deviation if a subset of their variable nodes forms a stopping set. When trapping sets and absorbing sets do not include a stopping set, it is necessary to include additional variable nodes in order to construct a corresponding deviation. The number and proportion of variable nodes outside the set that are needed to construct the deviation can be found experimentally using a modification of the MS decoder. This modified MS algorithm leads to an iterative method for identifying low-weight problematic trapping sets in an LDPC code. Simulation results demonstrate that this method is capable of finding many of the low-weight trapping sets that determine the performance of LDPC codes at moderate SNRs. The efficacy of this algorithm is limited by computational constraints.Finally, an analytical approach for determining the weight of deviations induced by trapping sets on the computation tree was introduced. This approach involves determining the minimum-weight stopping set that contains a given trapping set, and then determining a directed Tanner graph from the stopping set that favors certain variable nodes within the trapping set. It was then shown that the effective weight of the deviation can be found using a recursive method for computing the multiplicity of variable nodes within the deviation, In one example, it was proven that a deviation exists on the computation tree with weight less than the Hamming weight of the code. This result shows that trapping sets probably result in a necessary condition for an error to occur during iterative decoding, and in certain cases, this condition is satisfied with probability higher than the probability of an ML codeword error.



---

*Source: 432495-2010-08-04.xml*