---
abstract: 'LDPC codes are used in many applications, however, their error correcting capabilities are limited by the presence of stopping sets and trappins sets. Trappins sets and stopping sets occur when specific low-wiehgt error patterns cause a decoder to fail. Trapping sets were first discovered with investigation of the error floor of the Margulis code. Possible solutions are constructions which avoid creating trapping sets, such as progressive edge growth (PEG), or methods which remove trapping sets from existing constructions, such as graph covers. This survey examines trapping sets and stopping sets in LDPC codes over channels such as BSC, BEC and AWGNC.'
author:
- 'Aiden Price and Joanne Hall, *Member, IEEE*.[^1][^2][^3]'
title: A Survey on Trapping Sets and Stopping Sets
---

[Shell : Bare Demo of IEEEtran.cls for IEEE Communications Society Journals]{}

LDPC codes, trapping sets, stopping sets, QC-LDPC codes, Margulis codes, AWGNC, PEG algorithm, graph covers.

Introduction
============

technology advances, we wish to communicate over longer distances and have the ability to stay connected even over poor communication channels. While quasi-cyclic low-density parity-check (QC-LDPC) codes are one of the best ways to achieve this [@2DDOV2016], their performance in many cases is limited by the presence of trapping sets and stopping sets. Trapping sets and stopping sets can cause iterative decoding methods to fail with relatively few errors. Finding ways to avoid or remove trapping sets and stopping sets will further improve the already high performance of LDPC codes and bring their performance curves even closer to the Shannon limit [@MN1996], [@S1948].

Performance optmization is becoming incresingly crucial as the world moves further into the digital age. An increase in the speed at which digital communication occurs through modern applications such as WiFi [@802.11n2009WiFi] and DVB-S2 [@302307v1.3.1ETSI2013] has drastic implications on the overall productivity of the world.

In 1962, Gallager [@G1962] introduced low-density parity-check codes (LDPCs). LDPC codes are a class of binary linear block codes with a sparse parity-check matrix. An advantage of using LDPC codes is that they are able to provide error control which is very close to the capacity for many different channels [@MN1996]. This categorizes LDPC codes as one of few capacity-approaching codes; error correction methods which can allow the noise in a channel to be set very close to its theoretical maximum while maintaining error-correcting ability [@BCH2011].

The performance of an error correction method is based upon two properties; the performance of such a code over a channel with variable noise and the optimal bit error ratio (BER) of a code with sufficient signal-to-noise ratio (SNR). The optimal BER is known as the error floor of a code [@R2003], and is discussed in different papers in terms of bit error rate (BER), frame error rate (FER), block error rate and symbol error rate, depending on the application being addressed (see [@JW2004], [@ICV2008] for examples of such error floor analysis). Consideration of the error floor is one of the most important aspects of constructing a high-performing LDPC code [@ICV2008].

Analysis of the performance of LDPC codes over the binary erasure channel (BEC) led to the discovery of stopping sets in 2002 [@DPTRU2002]. The Margulis construction [@Margulis1982] improved upon the performance of Gallager codes, though a weakness in this construction led to a high error floor over the additive white Gaussian noise channel (AWGNC) compared to the performance of other constructions of the time [@MP2003]. This high error floor was due to the presence of stopping sets. Stopping sets over BEC as described in [@DPTRU2002] became a well understood problem and led to the definition of trapping sets, which are defined over AWGNC and BSC. In some early works trapping sets are called near-code words [@R2003], [@MP2003].

Trapping sets and stopping sets are an important topic, worthy of a stand-alone survey.

Preliminaries and Notation
==========================

In order to engage with the literature on stopping sets and trapping sets an overview of the preliminaries is necessary. We provide a short review of the literature surrounding LDPC codes, the common transmission channels, and common decoding techniques.

\[def: LC\][@B2014] A binary $[n, k, d]$ **linear code**, $\mathcal{C}$, is a $k$-dimensional subspace of an $n$-dimensional vector space, $\mathbb{F}_{2}^{n}$ which is used to provide structure to a message vector for transmission over a channel.

In order to transmit messages over communication channels using an error correcting code, we encode the message using a generator matrix.

\[def: GM\][@BCH2011] The **generator matrix**, **G**, of a code, $\mathcal{C}$, is a matrix which has dimensions $k \times n$. The $k$ rows of $\mathbf{G}$ correspond to linearly independent code words which form a basis of $\mathcal{C}$.

One of the most important aspects of error correction is the process of decoding. A parity-check matrix allows us to identify whether errors have been introduced during transmission. This matrix can also be represented by a Tanner graph.

\[def: PCM\][@BCH2011] A **parity-check matrix**, $\mathbf{H}$, of $\mathcal{C}$ is a matrix which generates the nullspace of the code. This means that a code word, $\mathbf{c}$, is in the code, $\mathcal{C}$, iff $\mathbf{H}\cdot\mathbf{c}^{T} = \mathbf{0}$, where $\mathbf{0}$ is an $r \times 1$ null vector. $\mathbf{H}$ has dimensions $(n-k) \times n$.

\[def: TG\][@B2014] The parity-check matrix, $\mathbf{H}$, may be represented by a bipartite graph with variable node set, $V$, and check node set, $C$. This bipartite graph is denoted $G(\mathbf{H}) = (V \cup C, E)$, where the columns of $\mathbf{H}$ indicate the variable nodes in $V$ and the rows of $\mathbf{H}$ indicate the check nodes in $C$. For $i \in V$ and $j \in C$, $(i, j) \in E$ if and only if $H_{ij} = 1$. This bipartite graph is known as a **Tanner graph** with $r = n-k$ check nodes and $n$ variable nodes (see Fig. \[ER Tanner\]).

We can also refer to individual variable nodes; let the $i$-th variable node be $v_{i}$ and the $j$-th check node be $c_{j}$ [@Richter2006].

\[def: LDPC\][@MM2010] If a parity-check matrix of a code is sparse, then the corresponding code, $\mathcal{C}$, is called a **low-density parity-check (LDPC) code**.

We note that the classification of **sparse** used in the context of LDPC codes is that there are fewer ones in the parity-check matrix than there are zeros [@BCH2011]. The sparse nature of LDPC codes means that decoding processes have a fast run-time, as there are fewer operations to compute when compared to a non-sparse parity-check matrix. Two more important features of Tanner graphs are neighbours and node degrees.

\[def: NND\][@MM2010][@SS2012] For a variable node $v_{i}$ and check node $c_{j}$, if $(i,j) \in E$ we say that nodes $v_{i}$ and $c_{j}$ are **neighbours**. The **degree** of a node in the Tanner graph is defined as the number of edges it is connected to.

From the node degree definition we can also define regular LDPC codes.

\[def: RLDPC\][@G1962] An LDPC code is called $(d_{v},d_{c})\mathbf{-regular}$ if each variable node, $v$, has degree $d_{v}$ and each check node, $c$, has degree $d_{c}$. We denote an LDPC code of this form a $\mathcal{C}(d_{v},d_{c})$ code.

LDPC codes are designed to be used as error-correction methods over a variety of communication channels. There are three communication channels discussed in this paper; the binary erasure channel (BEC), the binary symmetric channel (BSC) and the additive white gaussian noise channel (AWGNC) [@H1986]. Though these channels handle data transmission in different ways, their encoding and decoding goals are the same.

Encoding and Verification
-------------------------

The process of transforming a message vector into its associated code word is known as encoding. Every code word $\mathbf{c} = [c_{0},c_{1},...,c_{n-1}] \in \mathcal{C}$ can be expressed as $$\mathbf{c} = \mathbf{m}\cdot\mathbf{G}.$$ Where $\mathbf{m} = [m_{0},m_{1},...,m_{k-1}]$ is the mesage vector [@BCH2011]. The code word, $\mathbf{c}$, has the original $k$ information bits as well as an additional $r$ parity bits to give the code word a length of $n$ bits. As the parity-check matrix, $\mathbf{H}$, is the nullspace of the code, we can use it as a verification method to test if a recieved vector is a code word [@B2014]. The product $\mathbf{H}\cdot\mathbf{c}^{T}$ is denoted the **syndrome**, $\mathbf{s}$, of $\mathbf{c}$ through $\mathbf{H}$. For a given vector, $\mathbf{v}$, $$\mathbf{v} \in \mathcal{C} \text{ iff } \mathbf{s} = \mathbf{H}\cdot\mathbf{v}^{T} = \mathbf{0}.$$ There must be an even number of ones in the components of the product $\mathbf{H}\cdot\mathbf{c}^{T}$ which add to give $\mathbf{s} = 0$. This is known as the even-parity constraint [@MN1996]. After a code word, $\mathbf{c}$, is transmitted through a channel, the other party receives a vector, $\mathbf{v}$. If $ \mathbf{s} = \mathbf{H}\cdot\mathbf{v}^{T} \neq \mathbf{0}$, then $\mathbf{v} \notin \mathcal{C}$ and so we use error correcting techniques in attempt to correct $\mathbf{v}$ and recover $\mathbf{c}$.

The upper bound on the error correcting ability of an LDPC code is determined by the minimum distance of the code. In order to define the minimum distance of a code, we will first define Hamming weight and Hamming distance.

[@PW1972] The **Hamming weight**, $w$, of a vector is the number of its non-zero elements. The Hamming weight of a binary vector is therefore the number of ones in the vector. The **Hamming distance**, $d$, between two vectors, $\mathbf{x}$ and $\mathbf{y}$, is the number of places in which they differ; written as $d(\mathbf{x},\mathbf{y})$.

In the literature, Hamming weight and Hamming distance are often referred to using the terms “weight” and “distance” [@B2014]. The weight of code words affects the number of operations performed in decoding and the distance between code words affects how many errors can be corrected.

[@H1986] The **minimum distance of a code**, $\mathcal{C}$, is defined as the smallest Hamming distance between any two code words in the code, $$d(\mathcal{C}) = min \{d(\mathbf{x},\mathbf{y}) \, | \, \mathbf{x},\mathbf{y} \in \mathcal{C}, \mathbf{x} \neq \mathbf{y}\}.$$

The following theorem and corollary describe a code’s error detection and correction abilities using minimum distance [@H1986].

[[@H1986]]{} A code $\mathcal{C}$ can detect up to $s$ errors in any code word if $d(\mathcal{C}) \geq s + 1$. A code $\mathcal{C}$ can correct up to $t$ errors in any code word if $d(\mathcal{C}) \geq 2t + 1$.

[[@H1986]]{} If a code $\mathcal{C}$ has minimum distance $d$, then $\mathcal{C}$ can be used to either detect up to $d-1$ errors, or to correct up to $(d-1)/2$ errors in any code word.

If the minimum distance of a code is too small, then it cannot provide sufficient error correction. This is demonstrated in Example \[ex:distance\]

\[ex:distance\] Let two code words be given as; $$\begin{aligned}
c_{1} &= [0 1 0 0 0 0 1 1 1 1] \\
c_{2} &= [0 1 0 0 1 1 1 0 1 0].\end{aligned}$$ The distance between these codewords is given as $d(c_{1},c_{2}) = 4$. Take the following error vector: $$\begin{aligned}
e &= [0 0 0 0 1 1 0 1 0 1].\end{aligned}$$ If $e$ is added to $c_{1}$ then the resulting code word is identical to $c_{2}$, demonstrating the importance of minimum distance.

The minimum distance of an LDPC code is also related to its code-rate; a large code rate lowers the upper bound on the minimum distance of a code.

The **code rate**, $R(\mathcal{C})$, of an LDPC code is the portion of information bits sent in comparison to the entire code vector sent, written as $$R(\mathcal{C}) =\frac{k}{n},$$ where $0 \leq R(\mathcal{C}) \leq 1$.

The code rate and minimum distance often determine the error correcting capability of an LDPC code, though the decoding algorithm plays a direct part in the time it takes to decode messages.

Communication Channels and Decoding Basics
------------------------------------------

The communication channel by which transmission occurs impacts the error correction algorithms that are chosen. A communication channel can be modelled as a triple which contains an input alphabet, an output alphabet and the probability of transition between a symbol in the input alphabet and a symbol in the output alphabet [@S1948].

The binary erasure channel (BEC) is one of the simplest, non-trivial channel models [@RU2008],[@Elias1955].

[@Poddar2007],[@MM2010] The **Binary Erasure Channel (BEC)** is a communication channel with two input symbols, $0$ and $1$, and three output symbols, $0$, $1$ and $e$ (the erasure symbol). The BEC has an erasure probability, $p$, where given an input, $c_{i}$, the output, $v_{i}$, is defined by the probability formulae $P[v_{i} = c_{i}] = 1-p$ and $P[v_{i} = e] = p$.

Analysis of the BEC significantly advanced modern understanding of error correction [@RU2008]. An example of a simple decoding process over the BEC is the Edge Removal algorithm.

[@MM2010] \[ERalg\] Let $\mathbf{c}\in\mathcal{C}\subseteq\{0,1\}^{n}$ be a binary code word transmitted over the BEC and $\mathbf{v}\in\{0,1,e\}^{n}$ be the received vector. The **Edge Removal (ER)** algorithm proceeds as follows:

1.  Initial Step: The value of each received vector bit, $v_{i}$ is assigned to each variable node $i \in V$ of the Tanner Graph.

2.  The check nodes $c_{i}\in C$ count the number of erased bits which are neighbours in the Tanner graph, $G(H)$.

3.  If check node $c_{i}$ neighbours only one $e$ symbol in $v$, the even parity constraint uniquely determines the original value of $e$ for that variable node.

4.  Repeat steps (2) and (3) until either all erasures have been recovered or until every check node that is a neighbour of an erased bit is a neighbour of at least two erased bits.

For step (4) above, if the latter occurs, then the decoder has failed due to the presence of a stopping set (see Section \[SSoverBEC\]).

We provide an example of the ER decoding process in Fig. \[ER Tanner\], where $\circ$ represents a variable node and $\square$ a check node. This example is found in [@Richter2006].

For this decoding example, we use an irregular $5 \times 10$ parity-check matrix, $\mathbf{H}$ and demonstrate the decoding of received vector $v = [e,0,e,1,1,1,1,0,1,e]$ using the ER algorithm over the BEC.

Another communication channel is the binary symmetric channel (BSC).

[@MM2010], [@Poddar2007] The **Binary Symmetric Channel (BSC)** is a communication channel with two input symbols, $0$ and $1$, and two output symbols, also $0$ and $1$. The BSC has an error probability, $p$, where given an input, $c_{i}$, the output, $v_{i}$, is defined by the probability formulae $P[v_{i} = c_{i}] = 1-p$ and $P[v_{i} = \bar{\mathbf{c}_{i}}] = p$.

An example of a decoding process over the BSC is the Gallager A algorithm [@G1962].

[@G1962], [@Poddar2007], [@Shokrollahi2003] \[GAalg\] Let $\mathbf{c}\in\mathcal{C}\in\{0,1\}^{n}$ be a binary code word transmitted over the BSC and $\mathbf{v}\in\{0,1\}^{n}$ be the received vector. The **Gallager A** algorithm proceeds as follows:

1.  Initial Step: The value of each received vector bit, $v_{i}$ is assigned to each variable node $i \in V$ of the Tanner graph.

2.  After this, a check node $c_{i}$ sends to all neighbouring variable nodes $v_{i}, \dots, v_{j}$ the sum (mod 2) of all of the adjacent variable nodes except for the node itself (where $j$ is the degree of check node $c_{i}$).

3.  Each variable node, $v_{i}$ then sends the following to their adjacent check nodes: If all messages from check nodes $c_{i}$ other than the target check node of the message are equal, then $v_{i}$ sends that message back, otherwise it resends its prior value.

4.  Repeat steps (2) and (3) until either all variables nodes send the same values over two consecutive iterations or when a pre-set max iteration count is reached.

The **Gallager B** algorithm offers improved decoding with an additional step on each loop within the algorithm [@Shokrollahi2003]. For each degree, $j$, and each check node loop, $i$, there is a pre-chosen threshold value, $b_{i,j}$. Throughout the steps involved in check node $c_{i}$ for each variable node, $v$, and each adjacent check node, $c$, if at least $b_{i,j}$ neighbours of $v$ excluding $c$ sent the same information in the previous round, then $v$ sends that information to $c$; otherwise $v$ sends its received value to $c$. Algorithm A is a special case of algorithm B, where $b_{i,j} = j - 1$ independent of the round [@Shokrollahi2003].

Throughout the decoding procedure, if the pre-set max iteration count is reached without completion, the decoder has failed due to the existence of a trapping set (see Section \[TSoverOther\]). An example of the first steps of the Gallager A algorithm (see Fig. \[GA Tanner\]) demonstrates the differences between the decoding considerations made between the BEC and the BSC.

The most complex channel considered here is the binary input additive white gaussian noise channel, expressed commonly either as the BI-AWGNC or just as the AWGNC [@TKJ2007].

[@TKJ2007] \[defn:AWGN\] Let $X \in \{0,1\}^{*}$ be a message vector, where $^{*}$ denotes an arbitrary length. The **additive white Gaussian noise channel (AWGNC)** maps the input vector, $X$, to the vector $X' \in \{+1,-1\}^{*}$ and then adds the result with Gaussian white noise to give an output vector $Y = X' + W$, where $W \sim \mathcal{N}(0,N_{0}/2E_{b})$.

Each code symbol, $y \in Y$, carries with it a signal to noise ratio (SNR) of $E_{b}/N_{0}$ and the conditional distribution of $Y$ is $$P(y | x') = P_{W}(y-x') = \frac{1}{\sqrt{2\pi(N_{0}/2E_{b})}}\cdot exp\bigg(\frac{-(y-x')^{2}}{(N_{0}/E_{b})}\bigg),$$ which gives the output alphabet for the AWGNC as $y \in \mathbb{R}$. As in the BEC and BSC, we would like to have some indication of the errors that a channel is introducing to the code word. A metric used for the AWGNC is the log likelihood ratio (LLR). $$L(y|x) = ln\bigg(\frac{P(y|x = 0)}{P(y|x = 1)}\bigg).$$

This $L$-value describes the likelihood that $x$ is $0$ or $1$. If $L$ is positive then $P(y|x = 0) > P(y|x = 1)$ and thus the input estimate should be $\hat{x} = 0$. There are methods to map from $Y \in \mathbb{R}$ to $Y' \in \{0,1\}^{*}$ and, as such, all decoding methods used over the BSC can be implemented on the AWGNC. However, high performing decoding algorithms, such as maximum-likelihood decoders, the sum-product algorithm and the max-product algorithm [@R2003],[@CG2005],[@SLG2004] utilize the LLR information to improve decoding speed [@HXMAH2015]. The BSC can be used for these channels as LLR values are defined over the BSC, though the AWGNC more closely models the influence of real-world communication channels and is favoured for high performance simulations [@BCH2011],[@TKJ2007].

The BSC has a conditional LLR function as the bit flipping probabilities are well understood for the outputs $$L_{BSC}(y|x) = 
\begin{cases} 
      ln(\frac{1-p}{p}) & y = 0 \\
      ln(\frac{p}{1-p}) & y = 1
   \end{cases}$$ As the noise determines the values of $y$ in the AWGNC and $y \in \mathbb{R}$, the LLR on this channel is defined as $$L_{AWGNC}(y|x) = 4\frac{E_{b}}{N_{0}}y.$$

The decoding algorithms used on the AWGNC are far more complex than those on the BEC and BSC and, as such, we provide an overview of various methods rather than detailed definitions and examples. Decoding methods used over the AWGNC tend to be message passing algorithms, where nodes send information to their neighbours to correct errors based on the structure of the parity-check matrix [@SLG2006]. The original message-passing algorithm [@G1962] is an example of a flooding schedule [@KFL2001] where in each iteration, all variable nodes and subsequently all check nodes pass new messages to their neighbours. Another example of a flooding schedule is the sum-product algorithm (see [@CG2005]).

An improved schedule, where both variable nodes and check nodes send messages to each other throughout a single iteration is known by many names including serial scheduling [@ZF2002], [@KK2003], layered scheduling [@Hocevar2004] and sequential scheduling [@CGW2007]. These algorithms offer an improved decoding performance as information is moving through the Tanner graph more frequently. Examples of decoding algorithms using this scheduling include the max-product algorithm (MPA) [@SLG2004] and the belief propagation algorithm (BPA) [@CGW2007]. BPA is widely used in LDPC code analysis and is based on the likelihood that a node takes a value given its current value and the values of nearby nodes from previous iterations [@Shokrollahi2003].

Error correction must be implemented differently for each channel. The edge removal algorithm, for example, deals with erasures and thus is not suitable over the BSC. Errors which occur during transmission that are not corrected by the decoding algorithm form what is known as the **bit error ratio** (BER); the ratio of bits that cannot be corrected versus the total number of bits transmitted [@R2003] [@Haykin2008].

In order to test the performance of LDPC codes, we can simulate the transmission of messages over an increasing signal-to-noise ratio (SNR) and calculate the BER of a code under varying conditions. As SNR grows larger, the BER of a code will suddenly decrease depending on the conditions of the channel and the error correcting capability of the LDPC code in use. This curve is known as the **waterfall** region [@R2003]. The best scenario for correcting errors is when the probability of error during transmission over a channel is negligible and when the implemented error correcting code can correct many errors.

\[defn:errorfloor\] [@R2003] The waterfall region eventually ends in all BER graph curves as anomalous errors cause decoders to fail even with a high SNR ratio. The lowest the BER becomes before levelling is called the **error floor** of a code.

The BER is a standard way to analyze the error correcting ability of a code as well as the frame error ratio (FER) [@R2003], [@ICV2008], [@Richter2006]. The FER is the ratio of frames or whole messages transmitted which cannot be fully corrected versus the total number of frames transmitted. The largest contributors to the error floor stopping sets and trapping sets.

Cycles and Girth {#CandG}
================

The decoding method we choose has direct implications for the accuracy and efficiency of decoding. Cycles were the first known negative characteristic of LDPC codes and were extensively studied as they impacted on the accuracy of high performance LDPC codes [@TJVW2003]. A **cycle** in a graph is a sequence of connected nodes which form a closed loop where the initial and final node are the same and no edge is used more than once [@BCH2011]. The **cycle length** is the number of edges a cycle contains, and the length of the smallest cycle in a graph is denoted as its **girth** [@SS2012].

If no cycles exist within the Tanner graph of a parity-check matrix, then the iterative belief propagation decoding technique is always successful with sufficient iterations [@RSU2001]. However, if the neighbours of a node are not conditionally independent then belief propagation methods become inaccurate [@TJVW2003]. The inferred solution is to construct a parity-check matrix with no cycles. However, as discussed in Section \[chap:Solutions\], this is unessecary as not all cycles negatively impact the decoding efficiency of LDPC codes. In fact, the restriction of girth can lead to constraints on the structure of the code which further impedes the decoding efficiency [@TJVW2003].

The cycles which negatively impact the decoding efficiency of LDPC codes combine to form what are known as stopping sets and trapping sets [@DDOV2015]. These sets lead to a high error floor in otherwise efficienct LDPC code constructions throughout various communication channels and affect all high performing decoding algorithms.

Stopping Sets over BEC {#SSoverBEC}
======================

Stopping sets are collections of variable and check nodes in the Tanner graph of an LDPC code which greatly reduce its error correcting ability. These sets cause decoding to fail when certain variable nodes are affected by errors after transmission. Stopping sets were first described in 2002 by Di et al [@DPTRU2002], who were researching the average erasure probabilities of bits and blocks over the BEC.

\[defn:SS\][@DPTRU2002] Let $G(H)$ be a Tanner graph and $\mathcal{V}$ be the set of variable nodes in $G(H)$. A **stopping set**, $\mathcal{S}$, is a subset of $\mathcal{V}$, such that all neighbours of $\mathcal{S}$ are connected to $\mathcal{S}$ at least twice.

The empty set is also a stopping set and the space of stopping sets is closed under union [@DPTRU2002]; if $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ are both stopping sets then so is $\mathcal{S}_{1} \cup \mathcal{S}_{2}$. The following lemma describes a stopping set by the performance of the LDPC code’s decoding algorithm.

\[lem: UMSS\] [@DPTRU2002] Let $G$ be the generator for an LDPC code over the BEC and $\mathcal{E}$ denote the subset of the set of variable nodes which is erased by the channel after the transmission of a message. Then the set of erasures which remain when the decoder stops is equal to the **unique maximal stopping set** of $\mathcal{E}$.

Definition \[defn:SS\] is now widely accepted [@OVZ2005],[@RB2013],[@RDVW2014]. Given a BEC with erasure probability $\epsilon$, the performance of the code over the BEC is completely determined by the presence of stopping sets [@R2003]. Since stopping sets have a combinatorial characterization, their distributions through various Tanner graphs can be analyzed rigorously [@DPTRU2002], [@OVZ2005].

\[def: SN\][@OVZ2005] Let $\mathbb{S}$ denote the collection of all stopping sets in a Tanner graph, $G(H)$. The **stopping number**, $s^{*}$, of $G(H)$ is the size of the smallest, non-empty stopping set in $\mathbb{S}$.

The stopping number of a code aids in the analysis of the code’s error floor. It is known that the performance of an LDPC code over the BEC is dominated by the small stopping sets in the graph [@R2003]. The larger this value is, the lower the error floor of the code. In some cases, this stopping number increases linearly with the number of variable nodes, $|\mathcal{V}|$, in the Tanner graph [@OVZ2005]. This can be seen more easily using the stopping ratio.

\[def: SR\][@OVZ2005] Let $G(\mathbf{H})$ be a Tanner graph with $n$ variable nodes and stopping number $s^{*}$. The **stopping ratio**, $\sigma^{*}$, of a Tanner graph is defined by $s^{*} / n$; the ratio of its stopping number to the number of variable nodes.

A stopping set in the parity-check matrix of an LDPC code is shown in Example \[SSvisual\].

\[SSvisual\] [@Richter2006] Let $\mathcal{C}$ be the code with the following check matrix

$$\mathbf{H} = 
  \begin{bmatrix}
0 & 0 & 1 & 1 & 0 & 0 & \textbf{1} & 1 & \textbf{1} & 0 \\
1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 & 1 & \textbf{1} & 0 & \textbf{1} & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & \textbf{1} & 1 & \textbf{1} & 1
  \end{bmatrix}.$$

Columns $7$ and $9$ in $\mathbf{H}$ have been highlighted as they belong to a stopping set. The Tanner graph for $\mathcal{C}$ with the stopping set highlighted is shown in Fig. \[SSvisualH\].

A stopping set must be either empty or at least contain two variable nodes. The stopping number, $s^{*}$, of $\mathcal{C}$ is therefore 2 and its stopping ratio, $\sigma^{*}$, $0.2$.

An example showing the impact of a stopping set on the decoder is shown in Fig. \[SSproblem\], where the edge removal decoding algorithm is used over the BEC.

Solutions to the problem of stopping sets (covered in Section \[chap:Solutions\]) involve either avoiding or removing small stopping sets in the Tanner graph, leaving only LDPC codes with large stopping sets [@RB2013]. While stopping sets are well defined and some solutions exist to minimize their effect of the error floor of LDPC codes, the terminology does not support channels without erasure.

Trapping Sets over BSC, AWGN {#TSoverOther}
============================

Trapping sets, much like stopping sets, are also collections of variable nodes and check nodes which impede the error correcting ability of LDPC code. Only small, elementary trapping sets impact the error floor of LDPC codes over the BSC and AWGNC because of clustering [@R2003], [@LM2005].

The definition of trapping sets came shortly after stopping sets were defined. Similarly to the BEC, when decoding over the BSC and AWGNC, sometimes the maximum iteration count is reached when only a small set of variable nodes are in error. Experiments with the argulis codes lead to the definition of trapping sets [@R2003], [@MP2003].

\[def: FS\][@R2003] Let G($\mathbf{H}$) be a Tanner graph. For a received vector, $y$, of length $n$, we define the **failure set**, $\mathbf{T}(y)$, to be the set of bits that are not eventually correct using some arbitrary iterative decorder. Decoding is successful on $y$ if and only if $\mathbf{T}(y) = \emptyset$.

\[def: TS\][@LM2005], [@R2003] If $\mathbf{T}(y) \neq \emptyset$ then $\mathbf{T}(y)$ is a **trapping set**. More specifically, $\mathbf{T}$ is an **(a,b) trapping set** in $\mathbf{H}$ if it has $a$ variable nodes for which the sub-graph induced by $\mathbf{T}$ contains $b \geq 0$ odd-degree check nodes.

Iterative techniques on the BSC and AWGNC distinguish trapping sets from stopping sets over the BEC [@R2003]. If there is only iteration by which the decoding algorithm can become trapped then the notion of trapping sets becomes irrelevant.

![A (5,3) trapping set (left) with critical number $k = 3$ and a (4,4) trapping set (right) with critical number $k = 4$ [@ICV2008]. These $k$ values are found using the Gallager B decoding algorithm and may vary when other decoding algorithms are applied.[]{data-label="TSeg"}](TS_Example){width="2.7in"}

\[lem: TS0\][@R2003] Let $\mathcal{C}$ be a code using a one-step maximum likelihood decoder, then the trapping sets are precisely the non-zero code words.

Though, if the channel is BEC, then an iterative decoding failure is said to be due to stopping sets, making stopping sets and trapping sets equivalent over the BEC.

\[lem: TS = SS\][@R2003] Let $\mathcal{C}$ be a code using a belief propagation algorithm over BEC, then the trapping sets are precisely the stopping sets.

Lemma \[lem: TS = SS\] is an important bridge between trapping sets and stopping sets, allowing us to relate the BEC to the BSC and AWGNC. Decoding failure in an LDPC code over the BSC and AWGNC is largely due to the existence of trapping sets.

Trapping sets pose a real threat to the error correcting ability of LDPC codes; even though there may be very few nodes in error after transmission, if enough of those nodes belong to a trapping set, the decoder will fail.

[@ICV2008] Let $\mathbf{T}$ be a trapping set. The **critical number**, $k$, is the minimal number of variable nodes that have to initially be in error for the decoder to become “trapped" in $\mathbf{T}$.

It is important to note that the variables nodes that are initially in error do not necessarily belong to the trapping set; it is possible that, at some iteration, the trapping set is entered, causing the decoder to fail. In order to become trapped, the decoder must, after some finite number of iterations, be in error on at least one variable node from $\mathbf{T}$ at every iteration thereafter.

Only trapping sets with a small number of variable nodes and check nodes impact the error-floor of LDPC codes [@R2003], [@LM2005].

\[def: STS\][@LM2005] An $(a,b)$ trapping set in a $[n, k, d]$ code is a **small trapping set** if $a \leq \sqrt{n}$ and $b \leq 4a$.

Only these small trapping sets contribute to a larger error-floor [@R2003]. Small trapping sets are also of elementary form [@LM2005].

\[def: ETS\][@LM2005] An **elementary (a,b) trapping set** in a $[n, k, d]$ code is a trapping set for which all check nodes in the induced subgraph have either degree one or two, and there are exactly $b$ degree-one check nodes.

While check nodes of odd degree larger than one are possible, they are very unlikely within small trapping sets [@R2003],[@LM2005]. Techniques to find and remove elementary trapping sets have become crucial when constructing high perfoming codes [@ICV2008], [@RH2006].

Two examples of trapping sets [@ICV2008] are shown in Fig. \[TSeg\]. In Fig. \[TSeg\] the trapping set on the right has a smaller number of variable nodes than the one of the left, however, under the Gallager B decoding algorithm the larger trapping set has a smaller critical number. Thus the performance of the code is limited by the larger trapping set. This idea is quite unintuitive and shows the depth of consideration which must be made when attempting to improve the error floor of LDPC codes.

The problems which trapping sets and stopping sets introduce to LDPC code ares important to research and solve. There do exist methods for constructing LDPC codes by avoiding or removing trapping sets and stopping sets, however, these methods come at the cost of restraining other properties such as code length, density or error correcting ability [@JW2004].

The influence of Stopping Sets and Trapping Sets on LDPC Code Performance
=========================================================================

The original LDPC codes proposed in 1962 by Gallager [@G1962], were construction methods which allowed for varied code rates.

[@MP2003] A **Gallager code** is an LDPC code constructed using a parity-check matrix with uniform row weight $i$ and uniform column weight $j$. The code has length $n$ code words and has code rate $R(\mathcal{C})$, which gives a parity-check matrix, $\mathbf{H}$, with $n$ columns and $k$ rows, where $k = n(1-R(\mathcal{C}))$.

Naive analysis indicated that failed decoding is due to received vectors containing too many errors for the decoding algorithm [@G1962]. Analysis of a range of error patterns by Di et al [@DPTRU2002] determined that this was not always the case; leading to the definition of stopping sets over the BEC.

A variety of analyses of Gallager codes have shown high performance [@MN1996] [@MacKay1999]. A construction in 1982 by Margulis [@Margulis1982] promised an improved performance over the AWGNC.

For each prime, $p$, let $SL_{2}(p)$ be the Special Linear Group whose elements consist of $2 \times 2$ matrices of determinant $1$ over $\mathbb{Z}_{p}$. This group has $k = (p^{2}-1)(p^{2}-p)/(p-1) = (p^{2}-1)p$ elements. For $p \geq 5$, the Margulis code is of length $n = 2k$, with code rate $R(\mathcal{C}) = 1/2$ [@Margulis1982]. The rows of the parity-check matrix are indexed by the elements of $SL_{2}(p)$ and the columns are indexed by two copies of $SL_{2}(p)$; detailed in the following definition.

[@MP2003][@Margulis1982] Let $SL_{2}(p)$ be generated by the following matrices;

$$A = 
  \begin{pmatrix}
1 & 2 \\
0 & 1
  \end{pmatrix}
, B = 
  \begin{pmatrix}
1 & 0\\
2 & 1
  \end{pmatrix}$$

If $g \in SL_{2}(p)$ is the index of a row of the parity-check matrix, a one is placed in the columns corresponding to $gA^{2}$, $gABA^{-1}$ and $gB$ on the left hand side of the matrix and also in the columns corresponding to $gA^{-2}$, $gAB^{-1}A^{-1}$ and $gB^{-1}$ on the right hand side of the matrix. This results in a (3,6)-regular parity-check matrix for a **Margulis code**.

An example of a parity-check matrix generated using the Margulis construction is shown in Fig. \[MargulisH\] to demonstrate the sparse nature of LDPC codes. Another example of a Margulis parity-check matrix can be found in [@MP2003] where $p = 11$ which corresponds to a $1/2$-rate code with $n=2640$. While the code has a higher performance than a random Gallager code, the error floor is still quite high [@MP2003]. This error floor was claimed to be due to near-code words [@MP2003]. A comparison between the Margulis code and a random Gallager code, both with $n=672$, can be seen in Fig. \[MCvGC\].

![Parity-check matrix generated using the Margulis construction, setting $p = 7$ to give a (3,6)-regular $1/2$-rate code with $n=672$. The blue dots represent ones in this matrix with the remaining white space representing zeros.[]{data-label="MargulisH"}](MargulisH){width="3in"}

[@MP2003] Let $\mathbf{H}$ be a parity-check matrix. If $\mathbf{x}$ is a vector of weight $w$ and $$\mathbf{Hx}^{T}=\mathbf{s}$$ where $\mathbf{s}$ is of weight $v$, then $\mathbf{x}$ is a $(w,v)$ **near-code word**.

Near-code words are different from stopping sets. Typical $(w,v)$ near-code words contain $v$ check nodes which are only connected to the variables nodes once. The near-code words in the Margulis code are the $(12,4)$ and $(14,4)$ near-code words [@MP2003].

The high error floors of the Margulis code can be reproduced with a 5 bit approximation to a belief propagation algorithm [@R2003]. Near-code words account for 98% of the error floor performance of the Margulis code. Near code words are trapping sets [@R2003].

Trapping sets are often clustered [@R2003]; if one trapping set is found it will often contain nodes which belong to another trapping set. This makes the search for trapping sets somewhat simpler.

Finding both stopping and trapping sets are NP-hard problems [@MM2010], [@KS2007], which makes solutions to these sets difficult to analyse.

The ER decoding algorithm is simple and the effect of stopping sets can be demonstrated easilly. However, decoding over the BSC or AWGNC is much more complex (see Fig. \[GA Tanner\]). Iterative decoding methods tend to have maximum iteration counts as termination conditions and, as such, demonstrating the effect of trapping sets is difficult to show. In lieu of an example, we remind the reader of the termination conditions for the Gallager A algorithm. This decoder terminates either when all variable nodes send the same values over two consecutive iterations or when some maximum iteration count is reached. In the latter case, the decoder has failed due to the existence of a trapping set.

While we have only discussed the issues with the Margulis code using specific decoding algorithms here, there are many code constructions which contain trapping and stopping sets and decoding algorithms which terminate for the same reasons. For further reading, see [@SCRV2006].

Further reading on stopping sets in LDPC codes include the message passing (MP) algorithm [@LMSS2001] and the maximum-likelihood (ML) decoder [@PF2004]; both over the BEC. Further reading on trapping sets include finite alphabet iterative decoders (FAIDs) [@DDPV2011] and constructions based on Latin squares [@LM2007]. This construction offers high structure by which stopping sets and trapping sets can be analysed.

![BER comparison between the $p=7$ Margulis code (using the same example as presented in Fig. \[MargulisH\]) and a random Gallager code, both with $n = 672$ and decoded using MPA over the AWGNC. These graphs are also known in the literature as waterfall curves [@R2003].[]{data-label="MCvGC"}](Margulis_Gallager_FER){width="3.2in"}

If constructions which avoid trapping and stopping sets exist, then the error floors of the associated LDPC codes will lower significantly. This would improve the speed at which almost all digital communication occurs given the already high performance of LDPC codes in modern applications including WiFi [@802.11n2009WiFi] and DVB-S2 [@302307v1.3.1ETSI2013].

Current Solutions {#chap:Solutions}
=================

The simple goal is to avoid or completely remove every stopping set or trapping set from an LDPC code. This is both not reasonable given the number of cycles in an LDPC construction [@BCH2011] and, more importantly, not necessary [@OVZ2005], [@LM2005].

Only small, elementary trapping sets impact the error floor due to clustering [@R2003], [@LM2005]. If there are enough errors in transmission for a decoder to get trapped in a large trapping set then it is highly likely that it would also be trapped in a small trapping set [@R2003]. If there are not enough errors for the decoder to become trapped in a large trapping set, the received vector can either be successfully decoded or the decoder will fail due to the presence of at least one small trapping set.

The current solutions to trapping sets are the development of constructions which avoid small trapping sets and the removal of trapping sets from existing constructions.

![[@HEA2005] A subgraph (tree) contained in the depth $l$ neighbourhood spreading from the variable node $v_{i}$. Note that $\circ$ here represents a variable node and $\square$ represents a check node.[]{data-label="TreeBF"}](Neighbourhood.pdf){width="3.5in"}

Avoiding Trapping Sets
----------------------

Stopping sets pose threats to the error correction of messages sent over the BEC, however, in practice the AWGNC is used and so, when discussing proposed solutions, we focus on the influence of trapping sets over the AWGNC.

The progressive-edge-growth (PEG) construction [@HEA2001], [@HEA2005] is a method of constructing Tanner graphs with high girth. Many trapping sets include small cycles, so the likelihood of a small trapping set being constructed is small with a graph of high girth [@MSW2007]. In order to give the definition for the PEG construction, some definitions are needed. The PEG construction method uses variable and check node degree sequences [@HEA2005]. The **variable node degree sequence** is denoted $$\begin{aligned}
D_{v} &= \{d_{v_{0}}, d_{v_{1}}, \dots, d_{v_{n-1}}\},
\intertext{where $d_{v_{i}}$ is the degree of variable node $v_{i}$, $ 0 \leq i \leq n-1$, and $d_{v_{0}} \leq d_{v_{1}} \leq \dots \leq d_{v_{n-1}}$. The \textbf{parity check sequence} is denoted}
D_{c} &= \{d_{c_{0}}, d_{c_{1}}, \dots, d_{c_{m-1}}\},\end{aligned}$$ where $d_{c_{j}}$ is the degree of check node $c_{j}$, $ 0 \leq j \leq m-1$, and $d_{c_{0}} \leq d_{c_{1}} \leq \dots \leq d_{c_{m-1}}$.

The construction partitions the set of edges, $E$, to $$\begin{aligned}
E = E_{v_{0}} \cup E_{v_{1}} \cup \dots \cup E_{v_{n-1}},\end{aligned}$$ where $E_{v_{i}}$ contains all edges incident on symbol node $v_{i}$. The $k^{th}$ edge incident on $v_{i}$ is denoted as $E_{v_{i}}^{k}$, where $0 \leq k \leq d_{v_{i}}-1$.

The **neighbourhood** of depth $l$ for variable node $v_{i}$ is $\mathcal{N}_{v_{i}}^{l}$ and is defined as the set of all check nodes included in a subgraph (tree) spreading from variable node $v_{i}$ within depth $l$. This is demonstrated in Fig. \[TreeBF\]. The complement of $\mathcal{N}_{v_{i}}^{l}$ is $\mathcal{N}_{v_{i}}^{-l} = C \backslash \mathcal{N}_{v_{i}}^{l}$, where C is the set of check nodes. The subgraph (tree) generated this way is constructed breadth-first with $v_{i}$ as the root. Given the parameters $n$, $m$ and $D_{v}$, we define the PEG construction as follows.

**Progressive edge-growth algorithm (PEG)** [@HEA2005]:\
**for** $i = 0$ to $n - 1$ do\
**begin**\
**for** $k = 0$ to $d_{v_{i}} - 1$ do\
**begin**\
**if** $k = 0$\
$E_{v_{i}}^{0} \leftarrow$ edge ($c_{j}$, $v_{i}$), where $e_{v_{i}}^{0}$ is the first edge\
incident to $v_{i}$ and $c_{j}$ is a check node that it\
has the lowest check-node degree in\
$E_{v_{0}} \cup E_{v_{1}} \cup \dots \cup E_{v_{i-1}}$.\
**else**\
Expand a subgraph from symbol node $v_{i}$ up to\
depth $l$ in $E_{v_{0}} \cup E_{v_{1}} \cup \dots \cup E_{v_{i-1}}$ until the\
cardinality of $\mathcal{N}_{v_{i}}^{l}$ stops increasing but is less\
than $m$, or $\mathcal{N}_{v_{i}}^{-l} \neq \varnothing$ but $\mathcal{N}_{v_{i}}^{l+1} = \varnothing$, then $E^{k}_{v_{i}} \leftarrow$\
edge ($c_{j}$, $v_{i}$), where $E^{k}_{v_{i}}$ is the $k^{th}$ edge incident\
to $v_{i}$ and $c_{j}$ is a check node chosen from the\
set $\mathcal{N}_{v_{i}}^{-l}$ having the lowest check-node degree.\
**end**\
**end**\
**end**

When presented with check nodes of the same degree, a decision must be made; the selection of a check node at random or the selection of a check node according to some order. An improved construction, the randomized-PEG construction [@VDP2008], chooses at random, though the deterministic nature of the ordered check node process might be of use [@HEA2005]. An example of PEG construction is given in Fig. \[PEGex\], setting $n = 10$, $m = 5$ and $D_{v} = \{2,2,2,2,2,2,2,2,2,2\}$.

The PEG construction maximises the local girth of a variable node when a new edge is added to the node [@HEA2005]. After the discovery of stopping and trapping sets the PEG construction was modified [@DDOV2015], [@VDP2008].

The PEG construction is notable for its ability to create high girth LDPC codes, however, the number of cycles is not controlled. Trapping sets are formed by a combination of several cycles [@DDOV2015]. The PEG algorithm, while having a higher girth than aternate constructions, contains more trapping sets; thus leaving the error floor open to improvement.

The RandPEG construction improves upon the PEG algorithm by minimizing cycles at the same time as reducing the computational complexity of the PEG algorithm [@VDP2008]. This can be further improved by adding an objective function to avoid small trapping sets [@DDOV2015]. Quasi-cyclic LDPC (QC-LDPC) codes, which are used in many applications [@2DDOV2016], [@WYD2008] can be constructed using the Improved RandPEG algorithm [@DDOV2015]. The objective function used in the improved RandPEG algorithm detects all (5,3) and (6,4) trapping sets, removing all (5,3) trapping sets and as many (6,4) trapping sets as possible without adversely affecting the performance of the LDPC code. The characterization of trapping sets is achieved in [@DDOV2015] through the locations of check nodes in different levels of depth-$l$ trees (see Fig. \[TreeBF\]). The resulting construction is as follows:

**Improved RandPEG algorithm (RPEG)** [@DDOV2015]:\
**for** $i = 0$ to $n - 1$ do\
**begin**\
**for** $k = 0$ to $d_{v_{i}} - 1$ do\
**begin**\
**if** $k = 0$\
$E_{v_{i}}^{0} \leftarrow$ edge ($c_{j}$, $v_{i}$), where $e_{v_{i}}^{0}$ is the first edge\
incident to $v_{i}$ and $c_{j}$ is a check node such that\
it has the lowest check-node degree in\
$E_{v_{0}} \cup E_{v_{1}} \cup \dots \cup E_{v_{i-1}}$.\
**else**\
Expand a subgraph from symbol node $v_{i}$ up to\
depth $l$ in $E_{v_{0}} \cup E_{v_{1}} \cup \dots \cup E_{v_{i-1}}$ until the\
cardinality of $\mathcal{N}_{v_{i}}^{l}$ stops increasing but is less\
than $m$, or $\mathcal{N}_{v_{i}}^{-l} \neq \varnothing$ but $\mathcal{N}_{v_{i}}^{l+1} = \varnothing$. Remove from\
$\mathcal{N}_{v_{i}}^{-l}$ all check nodes that appear at least once in\
the depth-$3$ tree spreading from $v_{i}$. This\
removes all check nodes that would create cycles\
of size $< 8$.\
**for** $c_{m}$ in $\mathcal{N}_{v_{i}}^{-l}$ do\
Compute the number of (5,3) and (6,4) trap-\
ping sets that would be created if $c_{m}$ is\
selected. Remove all check nodes that would\
create (5,3) trapping sets and remove check\
nodes which create more than the smallest\
number of (6,4) trapping sets.\
**If** $\mathcal{N}_{v_{i}}^{-l} \neq \varnothing$\
$E^{k}_{v_{i}} \leftarrow$ edge $(c_{m},v_{i})$, where $E^{k}_{v_{i}}$ is the $k^{th}$edge incident to $v_{i}$ and $c_{m}$ is a check node\
chosen from the remaining nodes in $\mathcal{N}_{v_{i}}^{-l}$.\
**else**\
Declare a design failure.\
**end**\
**end**\
**end**\
**end**\
**end**

The Improved RandPEG construction algorithm, while having a high computational complexity, performs the task of avoiding trapping sets optimally for given dimensions of an LDPC code. Possible improvements to this construction method include lowering the computational complexity and potentially lowering the girth. The removal of all cycles is unnecessary as not all cycles contribute to trapping sets [@OVZ2005], [@LM2005]. The inclusion of a lower girth into a construction which also contains no small trapping sets could lead to an LDPC code with a higher decoding performance.

Removing Stopping and Trapping Sets
-----------------------------------

The performance of LDPC codes is constrained by the presence of cycles and trapping sets within the code’s parity-check matrix. We discuss two methods of removing trapping sets; the addition of a redundant parity-check equation [@LHMH2006] and the use of Tanner graph covers [@ICV2008].

Redundant Parity-Check Equations {#redundant-parity-check-equations .unnumbered}
--------------------------------

Adding a redundant parity-check equation is equivalent to adding a redundant row to the parity-check matrix. This has been used in an attempt to remove the trapping sets present in the \[2640, 1320\] Margulis code [@LHMH2006]. The $(12,4)$ and $(14,4)$ trapping sets in the $[2640, 1320]$ Margulis code are elementary point trapping sets [@MP2003]. **Point trapping sets** are subsets of variable nodes that contain all errors ever to occur throughout the decoding process [@LHMH2006].

A redundant parity check row is identified which, when added to the parity-check matrix, potentially disrupts the (12,4) and (14,4) elementary trapping sets. This parity-check row is identified through a genie-aided random search which relies on information about trapped variables not available during decoding [@LHMH2006]. As random searches cannot be used in applied error correction a structured search was considered to be more useful. The structured search identifies variable and check nodes which connect to both the (12,4) and (14,4) trapping sets and combines the projection of the involved nodes such that a redundant parity-check row can be added to eliminate the effect of those trapping sets.

The only way to disrupt the (12,4) and (14,4) trapping sets in the Margulis code is if the projection of both the 12 variables and the 14 variables on the redundant parity-check equation has row weight one [@VDP2008]. This can be most reliably achieved by extending (12,4) trapping sets to (14,4) trapping sets (see Fig. \[TSext\]). Given that the Margulis code has a (3,6)-regular parity-check matrix, an elementary (a,b) trapping set contains a fixed number of check nodes. Let $e$ denote the number of check nodes connected to two variable nodes within the trapping set, then $e = (3a-b)/2$ and therefore two variable nodes and three check nodes must be added to extend a (12,4) trapping set to a (14,4) trapping set [@VDP2008]. At most one check node can be connected to both of the added variable nodes such that 4-cycles are not created. Such an extension which avoids the creation of 4-cycles in the Margulis code is only possible in two configurations.

1.  The two degree-one check nodes of the basic (12,4) trapping set are connected through two additional variable nodes to one additional check node.

2.  In the second configuration, the additional variable nodes do not share a check node.

These configurations are demonstrated in Fig. \[TSext\]. The existing check and variable nodes neighbouring the additional check and variable nodes are linearly combined to generate a redundant parity-check equation. A structured search is then used to ensure that this projection has row weight one in both the (12,4) and (14,4) trapping set.

![[@LHMH2006] The trapping set structure of a $(12,4)$ trapping set and its $(14,4)$ expansion configurations; (a) left and (b) right. For (a), the two expansion variables are denoted $v_{E,1}$ and $v_{E,2}$ and the check node connected to both of the variables nodes is denoted $c_{E}$. The unsatisfied check nodes in the original $(12,4)$ trapping set are denoted $c_{BO,1}$ through $c_{BO,4}$ and the variable nodes connected to these check nodes are denoted $v_{BO,1}$ through $v_{BO,4}$. The check nodes of degree one in the expansion of the trapping set are denoted $c_{EO,1}$ and $c_{EO,2}$. The node labels for (b) follow similarly.[]{data-label="TSext"}](TSext.pdf){width="3.3in"}

The addition of a redundant parity-check equation focuses on point elementary trapping sets from the Margulis code, where the structure of the trapping sets are well known. If this method were applied to other LDPC codes, the location and structure of the trapping sets within such a code are unknown. The redundant rows are computationally inexpensive to compute, however, the code rate of the resulting LDPC code will be reduced and the extra row increases the number of operations per decoding iteration, though by a negligible amount. Another potential problem is the success rate of this solution. The addition of a redundant parity-check equation does not guarantee that the trapping set will be disrupted [@LHMH2006].

Tanner Graph Covers {#tanner-graph-covers .unnumbered}
-------------------

Another method capable of eliminating trapping sets is the utilization of graph covers [@ICV2008]. This method constructs an LDPC code $\mathcal{C}^{(2)}$ of length $2n$ given a code $\mathcal{C}$ of length $n$. The parity check matrix of this code is denoted $H^{(2)}$ and is initialized to

$$H^{(2)} = 
\begin{bmatrix}
    H       & 0 \\
    0       & H
\end{bmatrix}$$

The operation of changing the value of $H^{(2)}_{t,k}$ and $H^{(2)}_{m+t,n+k}$ to “$0$", and $H^{(2)}_{m+t,k}$ and $H^{(2)}_{m,n+k}$ to “$1$" is termed as edge swapping $e$. The graph covers method requires that the locations of dominant trapping sets are known. The method of edge swapping is then described as follows.

**Graph covers algorithm** [@ICV2008]:

1.  Take two copies, $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$, of the code $\mathcal{C}$. Since the codes are identical they share the same trapping sets. Initialize $SwappedEdges=\varnothing$, $FrozenEdges=\varnothing$;

2.  Order the trapping sets by their critical numbers.

3.  Choose a trapping set $\mathbf{T}_{1}$ in the Tanner graph of $\mathcal{C}_{1}$, with minimal critical number. Let $E_{\mathbf{T}_{1}}$ denote the set of all edges in $\mathbf{T}_{1}$. If $E_{\mathbf{T}_{1}} \cap SwappedEdges \neq \varnothing$ go to step 5, else go to step 4.

4.  Swap an arbitrarily chosen edge $e \in E_{\mathbf{T}_{1}} \textbackslash$ $FrozenEdges$. Set $SwappedEdges = SwappedEdges \cup e$.

5.  “Freeze" the edges $E_{\mathbf{T}_{1}}$ from $\mathbf{T}_{1}$ so that they cannot be swapped in the following steps. Set $FrozenEdges = FrozenEdges \cup E_{\mathbf{T}_{1}}$.

6.  Repeat steps 2 to 4 until all trapping sets of the desired size are removed.

Possible improvements to the graph cover method are to prioritize specific edges for swapping and freezing to avoid creating trapping sets of the same critical number [@ICV2008]. However, experimentally, all trapping sets with minimal critical number were removed using the above algorithm [@ICV2008]. The graph covers method gave improved FER results for a Tanner code [@TSF2001], a Margulis code [@RV2000] and a MacKay code [@MacKay2005] using the Gallager B decoding algorithm. While the decoding method was constant throughout these results, the application of graph covers will optimize FER performance using an arbitrary decoding algorithm [@ICV2008].

The LDPC code $\mathcal{C}^{(2)}$ created from code $\mathcal{C}$ has code rate $r^{(2)} \leq r$ and minimum distance $2d \geq d^{(2)} \geq d$. An increase to the minimum distance of the code $\mathcal{C}^{(2)}$ gives higher error correcting capabilities than $\mathcal{C}$. However, a lower code rate could decrease the overall efficiency. The lower row and column weight of $H^{(2)}$ gives $\mathcal{C}^{(2)}$ higher FER performance than $\mathcal{C}$, though with a trade-off of low decoding complexity.

The trade-offs associated with removing trapping sets are more severe than the surveyed construction methods which avoid them (code length, decoding speed from check nodes, etc). The current research goal remains the creation of a construction or modifiable construction which can either avoid or remove small elementary trapping sets without penalty to the code’s error correcting ability or decoding efficiency.

Conclusion
==========

Throughout this survey we have covered the literature surrounding LDPC codes, communication channels and decoding techniques. The negative impact cycles have on LDPC code efficiency is noted and the problem of stopping sets and trapping sets have been defined and discussed including the dominance of small elementary trapping sets over AWGNC. A small variety of partial solutions such as the randomized progressive edge-growth algorithm and Tanner graph covers are discussed. The research goal remains to find constructions of LDPC codes without small trapping sets.

Acknowledgment {#acknowledgment .unnumbered}
==============

The authors would like to thank Professor Ian Turner, who worked closely with us throughout our research, Emeritus Professor Ed Dawson and Dr Harry Bartlett for their help in the final stages before submission, Dr Dhammika Jayalath for his help with the decoding simulations over AWGNC, and Xuan He for his suggestions on how to present our BER data. Computational resources and services used in this work were provided by the HPC and Research Support Group, Queensland University of Technology, Brisbane, Australia. A. Price is supported by an APA Scholarship.

[46]{}

M. Diouf, D. Declercq, S. Ouya, and B. Vasic, “Improved [PEG]{} construction of large girth [QC-LDPC]{} codes,” *IEEE 9th Intern. Symp. Turbo Codes and Iterative Inf. Proc. (ISTC)*, pp. 146–150, 2016.

D. J. MacKay and R. M. Neal, “Near [S]{}hannon limit performance of low density parity check codes,” *Electron. Lett.*, vol. 32, no. 18, pp. 1645–1646, 1996.

C. E. Shannon, “A mathematical theory of communication,” *Bell system Technical Journal*, vol. 27, no. 1, pp. 379–423, 1948.

“IEEE standard for information technology– local and metropolitan area networks– specific requirements– part 11: Wireless lan medium access control (mac) and physical layer (phy) specifications,” *[IEEE]{} Std 802.11n-2009*, pp. 1–565, Oct 2009.

E. ETSI, “302 307 v1. 3.1,” *Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications (DVB-S2)*, 2013.

R. G. Gallager, “Low-density parity-check codes,” *IRE Trans. Inf. Theory*, vol. 8, no. 1, pp. 21–28, 1962.

N. Bonello, S. Chen, and L. Hanzo, “Low-density parity-check codes and their rateless relatives,” *IEEE Commun. Surv. Tuts.*, vol. 13, no. 1, pp. 3–26, 2011.

T. Richardson, “Error floors of [LDPC]{} codes,” *Proc. annual [A]{}llerton conference on commun. control and computing*, vol. 41, no. 3, pp. 1426–1435, 2003.

S. J. Johnson and S. R. Weller, “Codes for iterative decoding from partial geometries,” *IEEE Trans. Commun.*, vol. 52, no. 2, pp. 236–243, 2004.

M. Ivkovic, S. K. Chilappagari, and B. Vasic, “Eliminating trapping sets in low-density parity-check codes by using [T]{}anner graph covers,” *IEEE Trans. Inf. Theory*, vol. 54, no. 8, pp. 3763–3768, 2008.

C. Di, D. Proietti, I. E. Telatar, T. J. Richardson, and R. L. Urbanke, “Finite-length analysis of low-density parity-check codes on the binary erasure channel,” *IEEE Trans. Inf. Theory*, vol. 48, no. 6, pp. 1570–1579, 2002.

G. A. Margulis, “Explicit constructions of graphs without short cycles and low density codes,” *Combinatorica*, vol. 2, no. 1, pp. 71–78, 1982.

D. J. MacKay and M. S. Postol, “Weaknesses of [M]{}argulis and [R]{}amanujan-[M]{}argulis low-density parity-check codes,” *Electronic Notes in Theoretical Computer Science*, vol. 74, pp. 97–104, 2003.

M. Baldi, *[QC-LDPC]{} code-based cryptography*.1em plus 0.5em minus 0.4emSpringer Science & Business, 2014.

G. Richter, “Finding small stopping sets in the tanner graphs of [LDPC]{} codes,” *Turbo Codes & Related Topics; 6th International ITG-Conf. on Source and Channel Coding (TURBOCODING)* pp. 1–5, 2006.

A. McGregor and O. Milenkovic, “On the hardness of approximating stopping and trapping sets,” *IEEE Trans. Inf. Theory*, vol. 56, no. 4, pp. 1640–1650, 2010.

R. Shedsale and N. Sarwade, “A review of construction methods for regular [LDPC]{} codes,” *Indian Journal of Comput. Sci. Eng.*, vol. 3, no. 2, pp. 380–385, 2012.

R. Hill, “A first course in coding theory,” *Oxford: Clarendon Press*, 1986.

W. W. Peterson and E. J. Weldon, “Error-correcting codes,” *MIT press*, 1972.

T. Richardson and R. Urbanke, “Modern coding theory,” *Cambridge University Press*, 2008.

P. Elias, “Coding for two noisy channels,” *Third London Symposium*, vol. 67, 1955.

R. Poddar, “Low density parity check codes,” *Complexity*, vol. 7, p. 8, 2007.

A. Shokrollahi, “[LDPC]{} codes: An introduction,” *Digital Fountain, Inc., Tech. Rep*, p. 2, 2003.

N. Traore, S. Kant, and T. L. Jensen, “Message passing algorithm and linear programming decoding for [LDPC]{} and linear block codes,” *Aalborg University*, pp. 32–53, 2007.

G. Colavolpe and G. Germi, “On the application of factor graphs and the sum-product algorithm to [ISI]{} channels,” *IEEE Trans. Commun.*, vol. 53, no. 5, pp. 818–825, 2005.

E. Sharon, S. Litsyn, and J. Goldberger, “An efficient message-passing schedule for [LDPC]{} decoding,” *Proc. 23rd Conv. Electric. Electron. Engineers*, pp. 223–226, 2004.

P. Hailes, L. Xu, R. G. Maunder, B. M. Al-Hashimi, and L. Hanzo, “A survey of [FPGA]{}-based [LDPC]{} decoders,” *IEEE Commun. Surv. Tuts.*, vol. 18, no. 2, pp. 1098–1122, 2015.

E. Sharon, S. Litsyn, and J. Goldberger, “Convergence analysis of serial message-passing schedules for [LDPC]{} decoding,” *Turbo Codes & Related Topics; 6th International ITG-Conf. on Source and Channel Coding (TURBOCODING)* pp. 1–6, 2006.

F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm,” *IEEE Tran. Inf. theory*, vol. 47, no. 2, pp. 498–519, 2001.

J. Zhang and M. Fossorier, “Shuffled belief propagation decoding,” *Asilomar Conf. on Signals, Systems and Computers*, vol. 1, pp. 8–15, 2002.

H. Kfir and I. Kanter, “Parallel versus sequential updating for belief propagation decoding,” *Physica A: Statistical Mechanics and its Applications*, vol. 330, no. 1, pp. 259–270, 2003.

D. E. Hocevar, “A reduced complexity decoder architecture via layered decoding of [LDPC]{} codes,”, *Signal Processing Systems, 2004*, pp. 107–112, 2004.

A. I. V. Casado, M. Griot, and R. D. Wesel, “Informed dynamic scheduling for belief-propagation decoding of LDPC codes,”, *IEEE International Conf. on Commun.*, pp. 932–937, 2007.

S. Haykin, *Communication systems*.1em plus 0.5em minus 0.4em John Wiley & Sons, 2008.

T. Tian, C. Jones, D. Villasenor, and R. Wesel, “Construction of irregular [LDPC]{} codes with low error floors,” *IEEE Intern. Conf. on Commun. (ICC)*, vol. 5, no. 1, pp. 3125–3129, 2003.

T. Richardson, M. Shokrollahi, and R. Urbanke, “Design of capacity-approaching irregular low-density parity-check codes,” *IEEE Trans. on Inf. Theory*, vol. 47, no. 2, pp. 619–637, 2001.

M. Diouf, D. Declercq, S. Ouya, and B. Vasic, “A [PEG]{}-like [LDPC]{} code design avoiding short trapping sets,” *IEEE Intern. Symp. Inf. Theory (ISIT)*, pp. 1079–1083, 2015.

A. Orlitsky, K. Viswanathan, and J. Zhang, “Stopping set distribution of [LDPC]{} code ensembles,” *IEEE Trans. Inf. Theory*, vol. 51, no. 3, pp. 929–953, 2005.

J. C. S. Ripoll and N. R. Barraza, “A new algorithm to construct [LDPC]{} codes with large stopping sets,” *SIMULATION*, vol. 505, p. 1, 2013.

S. V. Ranganathan, D. Divsalar, K. Vakilinia, and R. D. Wesel, “Design of high-rate irregular non-binary [LDPC]{} codes using algorithmic stopping-set cancellation,” *IEEE Intern. Symp. Inf. Theory*, pp. 711–715, 2014.

S. Laendner and O. Milenkovic, “Algorithmic and combinatorial analysis of trapping sets in structured [LDPC]{} codes,” *2005 Intern. Conf. on Wireless Networks, Commun. and Mobile Computing*, vol. 1, pp. 630–635, 2005.

G. Richter and A. Hof, “On a construction method of irregular [LDPC]{} codes without small stopping sets,” *2006 IEEE Intern. Conf. on Commun.*, vol. 3, pp. 1119–1124, 2006.

D. J. MacKay, “Good error-correcting codes based on very sparse matrices,” *IEEE Trans. Inf. Theory*, vol. 45, no. 2, pp. 399–431, 1999.

M. K. Krishnan and P. Shankar, “Computing the stopping distance of a [T]{}anner graph is [NP]{}-hard,” *IEEE Trans. Inf. Theory*, vol. 53, no. 6, pp. 2278–2280, 2007.

S. Sankaranarayanan, S. K. Chilappagari, R. Radhakrishnan, and B. Vasic, “Failures of the [G]{}allager [B]{} decoder: Analysis and applications,” *Proc. Inf. Theory and Applic. Works. UCSD*, vol. 17, 2006.

M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Efficient erasure correcting codes,” *IEEE Trans. Inf. Theory*, vol. 47, no. 2, pp. 569–584, 2001.

H. Pishro-Nik and F. Fekri, “On decoding of low-density parity-check codes over the binary erasure channel,” *IEEE Trans. Inf. Theory*, vol. 50, no. 3, pp. 439–454, 2004.

L. Danjean, D. Declercq, S. K. Planjery, and B. Vasic, “On the selection of finite alphabet iterative decoders for [LDPC]{} codes on the [BSC]{},” *IEEE Inf. Theory Works. (ITW)*, pp. 345–349, 2011.

S. Laendner and O. Milenkovic, “[LDPC]{} codes based on latin squares: Cycle structure, stopping set, and trapping set analysis,” *IEEE Trans. Commun.*, vol. 55, no. 2, pp. 303–312, 2007.

X.-Y. Hu, E. Eleftheriou, and D.-M. Arnold, “Progressive edge-growth [T]{}anner graphs,” *IEEE Global Telecommun. Conf., 2001*, vol. 2, pp. 995–1001, 2001.

X.-Y. Hu, E. Eleftheriou, and D.-M. Arnold, “Regular and irregular progressive edge-growth [T]{}anner graphs,” *IEEE Trans. on Inf. Theory*, vol. 51, no. 1, pp. 386–398, 2005.

O. Milenkovic, E. Soljanin, and P. Whiting, “Asymptotic spectra of trapping sets in regular and irregular LDPC code ensembles," *IEEE Trans. on Inf. Theory*, vol. 51, no. 1, pp. 39–55, 2007.

A.  Venkiah, D.  Declercq, and C.  Poulliat. “Design of cages with a randomized progressive edge-growth algorithm," *IEEE Commun. Lett.*, vol.  12, no.  4, pp. 301–303, 2008.

Y. Wang, J. Yedidia, and S. Draper, “Construction of high-girth [QC-LDPC]{} codes,” *IEEE 5th Intern. Symp. Turbo Codes and Related Topics*, pp. 180–185, 2008.

S. Laendner, T. Hehn, O. Milenkovic, and J. B. Huber, “When does one redundant parity-check equation matter?” *IEEE Globecom 2006*, pp. 1–6, 2006.

R. Tanner, D. Sridhara, and T. Fuja, “A class of group-structured [LDPC]{} codes,” *Proc. ISCTA*, pp. 365–370, 2001.

J. Rosenthal, and P. Vontobel, “Constructions of [LDPC]{} codes using [R]{}amanujan graphs and ideas from [M]{}argulis,” *Proc. of the 38-th Allerton Conference on Commun., Control, and Computing*, 2000.

D. MacKay, “Encyclopedia of sparse graph codes," 2003.

[Aiden Price]{} was awarded the QUT Dean’s scholarship and received a BSc and $1^{st}$ class honours in mathematics from Queensland University of Technology. Aiden is currently studying a PhD at QUT in the school of mathematics under the supervision of Doctor Harry Bartlett and Emeritus Professor Ed Dawson and is funded by the APA scholarship. His research interests are coding theory and its application to digital communications and cryptography.

[Joanne Hall]{} received a BSc and MPhil in mathematics from the Australian National University. She graduated with a PhD from RMIT University in 2011 under the supervision of Asha Rao in the Information Security and Informatics research group. Dr Hall spent one year as a postdoctoral research scientist at Charles University in Prague and four years as a Lecturer at the Queensland University of Technology in Brisbane. In 2017 she has returned to RMIT University as a Lecturer in the School of Science. Her research interests are algebraic and combinatorial structures and their applications in digital communication.

[^1]: A. Price is with the Science and Engineering Faculty, Queensland University of Technology, Queensland, QLD, Australia. e-mail: a11.price@qut.edu.au.

[^2]: J. Hall is with the School of Science, Royal Melbourne Institute of Technology, Melbourne.

[^3]: Manuscript received MO DATE, YEAR; revised MO DATE, YEAR.
