13. An Exhaustive Tree Search for Stopping Sets of LDPC Codes

The performance of all error-correcting codes is determined by the minimum Hamming distance between codewords. For codes which are iteratively decoded such as LDPC codes and turbo codes, the performance of the codes for the erasure channel is determined by the stopping set spectrum, the weight (and number) of erasure patterns which cause the iterative decoder to fail to correct all of the erasures. Codes which perform poorly on the erasure channel do not perform well on the AWGN channel. To determine all of the stopping sets of a general (n, k) code is a prohibitive task, for example, a binary (1000, 700) code would require evaluation of \(2^{1000}\) possible stopping sets. It should be noted by the reader that all codewords are also stopping sets, but most stopping sets are not codewords. Fortunately the properties of particular types of codes may be used to reduce considerably the scale of the task, and in particular codes with sparse parity-check matrices such as LDPC codes and turbo codes are amenable to analysis in practice. As the tree search is exhaustive, the emphasis is first on focusing the search so that only low-weight stopping sets are found, up to a specified weight, and second the emphasis is on the efficiency of the algorithms involved.

In a landmark paper in 2007, Rosnes and Ytrehus [7] showed that exhaustive, low-weight stopping set analysis of codes whose parity-check matrix is sparse is feasible using a bounded tree search over the length of the code with no distinction between information and parity bits. A previous paper on the same topic of an exhaustive search of stopping sets of LDPC codes by Wang et al. [2] used a different and much less efficient algorithm. In common with this earlier research, we use similar notation in the following preliminaries.

The code \(\mathscr {C}\) is defined to be binary and linear of length n and dimension k and is a k-dimensional subspace of \(\{0,1\}^n\), and may be specified as the null space of a \(m\times n \) binary parity-check matrix \(\mathbf {H}\) of rank \(n-k\). The number of parity-check equations, m of \(\mathbf {H}\) satisfies \(m\ge (n-k)\), although there are, of course, only \(n-k\) independent parity-check equations. It should be noted, as illustrated in the results below, that the number of parity-check equations m in excess of \(n-k\) can have a dramatic effect on the stopping set weight spectrum, excluding codewords of course, as these are not affected.

As in [7], \(\mathscr {S}\) is used to denote a subset of \(\{0,1\}^n\), the set of all binary vectors of length n. At any point in the tree search, a constraint set, \(\mathscr {F}\) is defined consisting of bit positions \(p_i\) and the states of these bit positions \({s_p}_i\), \({s_p}_i \in \{0,1\}^n\). The support set \(\chi (\mathscr {F})\) of the constraint set, \(\mathscr {F}\), is the set of positions where \({s_p}_i=1\), and the Hamming weight of \(\mathscr {F}\) is the number of such positions. The sub-matrix \(\mathbf {H}_{\chi (\mathscr {F})}\) consists of all the columns of \(\mathbf {H}\) where \({s_p}_i=1\), and the row weight of \(\mathbb {H}_{\chi (\mathscr {F})}\) is the number of \(1's\) in that row. An active row of \(\mathbf {H}_{\chi (\mathscr {F})}\) is a row with unity row weight. It is obvious that if all rows of \(\mathbf {H}_{\chi (\mathscr {F})}\) have even row weight then \(\mathscr {F}\) is a codeword, noting that for an iterative decoder codewords are also stopping sets. If at least one row has odd weight, 3 or higher and there are no active rows then \(\mathscr {F}\) is a stopping set but not a codeword. If there are active rows then \(\mathscr {F}\) has either to be appended with additional bit positions or one or more states \({s_p}_i\) need to be changed to form a stopping set. With this set of basic definitions, tree search algorithms may be described which carry out an exhaustive search of \(\{0,1\}^n\) using a sequence of constraints \(\mathscr {F}\) to find all stopping sets whose Hamming weight is \(\le \tau \).

At any given point in the search, the constraint set F is used to represent the set of searched known bits (up to this point) of a code \(\mathscr {C}\), which forms a branch of the tree in the tree search. The set of active rows in \(\mathbf {H}\) is denoted by \(\{\mathfrak {h}_0,...,\mathfrak {h}_{\phi -1}\}\), where \(\phi \) is the total number of active rows. A constraint set F with size n is said to be valid if and only if there exists no active rows in \(\mathbf {H}^{(F)}\). In which case the constraint set is equal to a stopping set. The pseudocode of one particularly efficient algorithm to find all the stopping sets including codeword sets with weight equal to or less than \(\tau \) is given in Algorithm 13.1 below. Each time a stopping set is found, it is stored and the algorithm progresses until the entire \(2^n\) space has been searched.

The modified iterative decoding is carried out on a n-length binary input vector containing erasures in some of the positions. Let \(r_j(F)\) be the rank (ones) of row j, \(j\in \{0,...,m-1\}\) for the constrained position \(\{p_i:(p_i,1)\in F\}\) intersected by row j on \(\mathbf {H}\). And let \(r'_j(F)\) be the rank of row j for the unconstrained position \(\{p_i:(p_i,1)\in \{0,...,n-1\}\backslash F\}\) intersected by row j on \(\mathbf {H}\). The modified iterative decoding algorithm based on belief-propagation decoding algorithm over the binary erasure channel is shown in Algorithm 13.2. As noted in the line with marked (*), the modified iterative decoder is not invoked if the condition of \(r_j\le 1\) and \(r'_j=1\) is not met; or the branch with constraint set F has condition of \(r_j=1\) and \(r'_j=0\). This significantly speeds up the tree search.

As noted in the line with marked (*), the modified iterative decoder is not necessary to call, if the condition of \(r_j\le 1\) and \(r'_j=1\) is not met; or the branch with constraint set F can be ignored, if condition of \(r_j=1\) and \(r'_j=0\) occurs. Thus the computing complexity can be significantly reduced than calling it for every new branch with the corresponding constraint set F.

The algorithms above have been used to evaluate all of the low-weight stopping sets for some well-known LDPC codes. The results are given in Table 13.1 together with the respective references where details of the codes may be found. The total number of stopping sets are shown for a given weight with the number of codewords in parentheses. Interestingly, the Tanner code has 93 parity-check equations, 2 more than the 91 parity-check equations needed to encode the code. If only 91 parity-check equations are used by the iterative decoder there is a stopping set of weight 12 instead of 18 which will degrade the performance of the decoder. The corollary of this is that the performance of some LDPC codes may be improved by introducing additional, dependent, parity-check equations by selecting low-weight codewords of the dual code. A subsequent tree search will reveal whether there has been an improvement to the stopping sets as a result.

An efficient algorithm has been presented which enables all of the low weight stopping sets to be evaluated for some common LDPC codes. Future research is planned that will explore the determination of efficient algorithms for use with multiple computers operating in parallel in order to evaluate all low weight stopping sets for commonly used LDPC codes several thousand bits long.

It has been shown that the indicative performance of an LDPC code may be determined from exhaustive analysis of the low-weight spectral terms of the code’s stopping sets which by definition includes the low-weight codewords. In a breakthrough, Rosnes and Ytrehus demonstrated the feasibility of exhaustive, low-weight stopping set analysis of codes whose parity-check matrix is sparse using a bounded tree search over the length of the code, with no distinction between information and parity bits. For an (n, k) code, the potential total search space is of size \(2^n\) but a good choice of bound dramatically reduces this search space to a practical size. Indeed, the choice of bound is critical to the success of the algorithm. It has been shown that an improved algorithm can be obtained if the bounded tree search is applied to a set of k information bits since the potential total search space is initially reduced to size \(2^k\). Since such a restriction will only find codewords and not all stopping sets, a class of bits is defined as unsolved parity bits, and these are also searched as appended bits in order to find all low-weight stopping sets. Weight spectrum results have been presented for commonly used WiMax LDPC codes in addition to some other well-known LDPC codes.

An interesting area of future research has been identified whose aim is to improve the performance of the iterative decoder, for a given LDPC code, by determining low-weight codewords of the dual code and using these as additional parity-check equations. The tree search may be used to determine improvements to the code’s stopping sets as a result.