Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Communications

Stopping Set Elimination by Parity-Check Matrix Extension via Integer Linear Programming

Hossein Falsafain, Sayyed Rasoul Mousavi

Published Apr 1, 2015• 3 citations
Publisher

Abstract

Error-rate floor phenomenon is known to be a serious impediment to the use of low-density parity-check (LDPC) codes for some practical applications that demand high data reliability. In the case of binary erasure channels (BECs), certain error-prone patterns, known as stopping sets, are proven to cause this performance degradation. A possible approach to diminish this drawback over BECs is to eliminate stopping sets by parity-check matrix extension. Given a parity-check matrix H, and a list L of its stopping sets, we present an integer linear programming (ILP) formulation to find a parity-check equation which eliminates the maximum number of stopping sets in L. One of the distinguishing advantages of the proposed scheme is its flexibility for modifications such as: limiting the weight of the new parity-check row, making the new row redundant or linearly independent, 4-cycle avoidance, and taking into account the sizes of stopping sets. Armed with these adjustments, the method can provide good performance improvements, as evidenced by simulation results. Furthermore, for a given Q ∈ N, by extending the basic formulation, we provide an ILP formulation for finding a set of size Q of parity-check equations which can best eliminate the stopping sets in L, among all such sets.

DOI
10.1109/tcomm.2015.2418263

Related papers

Improved Stopping Set Elimination by Parity-Check Matrix Extension of LDPC Codes

Saejoon Kim, Jun Heo, Hyuncheol Park

Stopping sets associated with a parity-check matrix of low-density parity-check codes limit the performance of iterative decoding over the binary erasure channel. In this letter, we propose a parity-check matrix extension scheme that eliminates stopping sets of small sizes. The results show that our proposed scheme provides significant performance improvement compared to previously known parity-check matrix extension schemes.

IEEE Communications Letters•Apr 6, 2011•5 citations

Stopping Set Distributions of Some Linear Codes

Yong Jiang, Shu‐Tao Xia, Fang‐Wei Fu

Stopping sets and stopping set distribution of an low-density parity-check code are used to determine the performance of this code under iterative decoding over a binary erasure channel (BEC). Let $C$ be a binary $[n,k]$ linear code with parity-check matrix $H$, where the rows of $H$ may be dependent. A stopping set $S$ of $C$ with parity-check matrix $H$ is a subset of column indices of $H$ such that the restriction of $H$ to $S$ does not contain a row of weight one. The stopping set distribution $\{T_i(H)\}_{i=0}^n$ enumerates the number of stopping sets with size $i$ of $C$ with parity-check matrix $H$. Note that stopping sets and stopping set distribution are related to the parity-check matrix $H$ of $C$. Let $H^{*}$ be the parity-check matrix of $C$ which is formed by all the non-zero codewords of its dual code $C^{\perp}$. A parity-check matrix $H$ is called BEC-optimal if $T_i(H)=T_i(H^*), i=0,1,..., n$ and $H$ has the smallest number of rows. On the BEC, iterative decoder of $C$ with BEC-optimal parity-check matrix is an optimal decoder with much lower decoding complexity than the exhaustive decoder. In this paper, we study stopping sets, stopping set distributions and BEC-optimal parity-check matrices of binary linear codes. Using finite geometry in combinatorics, we obtain BEC-optimal parity-check matrices and then determine the stopping set distributions for the Simplex codes, the Hamming codes, the first order Reed-Muller codes and the extended Hamming codes.

arXiv:1003.0367•Mar 1, 2010•0 citations

On the probabilistic computation of the stopping redundancy of LDPC codes

Masanori Hirotomo, Yoshiho Konishi, Masakatu Morii

On the binary erasure channel (BEC), the performance of low-density parity-check (LDPC) codes decoded by iterative algorithms is estimated by the small stopping sets in the codes. The size of smallest stopping set is called the stopping distance. Since it depends on the structure of parity-check matrix for the code, we can construct the parity-check matrix by adding dependent rows so that the stopping distance is equal to the minimum distance. The stopping redundancy is defined as the smallest number of rows in such a parity-check matrix. In this paper, we propose a probabilistic algorithm for computing the stopping redundancy of LDPC codes. Additionally, we show numerical results of computing the stopping redundancy of (155,64), (504,252) and (1008,504) LDPC codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•1 citation

An Efficient Algorithm to Find All Small-Size Stopping Sets of Low-Density Parity-Check Matrices

Eirik Rosnes, Øyvind Ytrehus

In this work, we introduce an efficient algorithm to find all stopping sets, of size less than some threshold, of a fixed low-density parity-check (LDPC) matrix. The solution is inspired by the algorithm proposed by Rosnes and Ytrehus in 2005 to find an exhaustive list of all small-size turbo stopping sets in a turbo code. The efficiency of the proposed algorithm is demonstrated by several numerical examples. For instance, we have applied the algorithm to the well-known (3, 5)-regular (155, 64) Tanner code and found all stopping sets of size at most 18 in about 1 min on a standard desktop computer. Also, we have verified that the minimum stopping set size of the (4896, 2474) Ramanujan-Margulis code is indeed 24, and that the corresponding multiplicity is exactly 204. Furthermore, we have applied the algorithm to the IEEE 802.16e LDPC codes and determined the minimum stopping set size and the corresponding multiplicity exactly for these codes. Finally, as an application, we present a greedy algorithm to find a small number of redundant parity checks to add to the original parity-check matrix in order to remove all stopping sets in the corresponding Tanner graph of size less than the minimum distance. An extensive case study of the (155, 64) Tanner code illustrates the usefulness of the algorithm, and we present a 110 times 155 redundant parity-check matrix for this code with no stopping sets of size less than the minimum distance. Simulation results of iterative decoding on the binary erasure channel show performance improvements for low-to-medium erasure probabilities when this redundant parity-check matrix is used for decoding.

IEEE Transactions on Information Theory•Aug 24, 2009•63 citations

Permutation Decoding and the Stopping Redundancy Hierarchy of Linear Block Codes

Thorsten Hehn, Olgica Milenković, Stefan Laendner +1 more

We investigate the stopping redundancy hierarchy of linear block codes and its connection to permutation decoding techniques. An element in the ordered list of stopping redundancy values represents the smallest number of possibly linearly dependent rows in any parity-check matrix of a code that avoids stopping sets of up to a given size. Redundant parity-check equations can be shown to have a similar effect on decoding performance as permuting the coordinates of the received codeword according to a selected set of automorphisms of the code. Based on this finding we develop new decoding strategies for data transmission over the binary erasure channel that combine iterative message passing and permutation decoding in order to avoid errors confined to stopping sets. We also introduce the notion of s-SAD sets, containing the smallest number of automorphisms of a code with the property that they move any set of not more than s erasures into positions that do not correspond to stopping sets within a judiciously chosen parity-check matrix.

arXiv:cs/0702050•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•3 citations

Small stopping sets in projective low-density parity-check codes

Yuichiro Fujiwara, Yu Tsunoda

It is known that redundant parity-check equations can improve the performance of an LDPC code by reducing the number of harmful substructures in the parity-check matrix. However, it is a difficult problem to design a parity-check matrix in such a way that it avoids substructures that are known to be harmful to iterative decoding while keeping the number of redundant parity-check equations moderate and ensuring other desirable properties. We explicitly give redundant parity-check matrices for cyclic regular LDPC codes of length n and minimum distance d ~ √n in which there are only n parity-check equations but no stopping sets of size d+1 or smaller except for those that correspond to the nonzero codewords of the smallest weight. We do this by showing that the well-known projective LDPC codes from the incidence matrices of projective planes PG(2, q) with q even have this property. This result may give insight into how the small number of redundant parity-check equations in the geometric LDPC codes may be contributing to the good performance reported in the literature. We also give a slightly improved upper bound on the size of a smallest generic erasure correcting set.

IEEE Information Theory Workshop (ITW)•Aug 1, 2019•0 citations
Error-rate floor phenomenon is known to be a serious impediment to the use of low-density parity-check (LDPC) codes for some practical applications that demand high data reliability. In the case of binary erasure channels (BECs), certain error-prone patterns, known as stopping sets, are proven to cause this performance degradation. A possible approach to diminish this drawback over BECs is to eliminate stopping sets by parity-check matrix extension. Given a parity-check matrix H, and a list L of its stopping sets, we present an integer linear programming (ILP) formulation to find a parity-check equation which eliminates the maximum number of stopping sets in L. One of the distinguishing advantages of the proposed scheme is its flexibility for modifications such as: limiting the weight of the new parity-check row, making the new row redundant or linearly independent, 4-cycle avoidance, and taking into account the sizes of stopping sets. Armed with these adjustments, the method can provide good performance improvements, as evidenced by simulation results. Furthermore, for a given Q ∈ N, by extending the basic formulation, we provide an ILP formulation for finding a set of size Q of parity-check equations which can best eliminate the stopping sets in L, among all such sets.
Stopping sets and stopping set distribution of an low-density parity-check code are used to determine the performance of this code under iterative decoding over a binary erasure channel (BEC). Let CCC be a binary [n,k][n,k][n,k] linear code with parity-check matrix HHH, where the rows of HHH may be dependent. A stopping set SSS of CCC with parity-check matrix HHH is a subset of column indices of HHH such that the restriction of HHH to SSS does not contain a row of weight one. The stopping set distribution {Ti(H)}i=0n\{T_i(H)\}_{i=0}^n{Ti​(H)}i=0n​ enumerates the number of stopping sets with size iii of CCC with parity-check matrix HHH. Note that stopping sets and stopping set distribution are related to the parity-check matrix HHH of CCC. Let H∗H^{*}H∗ be the parity-check matrix of CCC which is formed by all the non-zero codewords of its dual code C⊥C^{\perp}C⊥. A parity-check matrix HHH is called BEC-optimal if Ti(H)=Ti(H∗),i=0,1,...,nT_i(H)=T_i(H^*), i=0,1,..., nTi​(H)=Ti​(H∗),i=0,1,...,n and HHH has the smallest number of rows. On the BEC, iterative decoder of CCC with BEC-optimal parity-check matrix is an optimal decoder with much lower decoding complexity than the exhaustive decoder. In this paper, we study stopping sets, stopping set distributions and BEC-optimal parity-check matrices of binary linear codes. Using finite geometry in combinatorics, we obtain BEC-optimal parity-check matrices and then determine the stopping set distributions for the Simplex codes, the Hamming codes, the first order Reed-Muller codes and the extended Hamming codes.
On the binary erasure channel (BEC), the performance of low-density parity-check (LDPC) codes decoded by iterative algorithms is estimated by the small stopping sets in the codes. The size of smallest stopping set is called the stopping distance. Since it depends on the structure of parity-check matrix for the code, we can construct the parity-check matrix by adding dependent rows so that the stopping distance is equal to the minimum distance. The stopping redundancy is defined as the smallest number of rows in such a parity-check matrix. In this paper, we propose a probabilistic algorithm for computing the stopping redundancy of LDPC codes. Additionally, we show numerical results of computing the stopping redundancy of (155,64), (504,252) and (1008,504) LDPC codes.
In this work, we introduce an efficient algorithm to find all stopping sets, of size less than some threshold, of a fixed low-density parity-check (LDPC) matrix. The solution is inspired by the algorithm proposed by Rosnes and Ytrehus in 2005 to find an exhaustive list of all small-size turbo stopping sets in a turbo code. The efficiency of the proposed algorithm is demonstrated by several numerical examples. For instance, we have applied the algorithm to the well-known (3, 5)-regular (155, 64) Tanner code and found all stopping sets of size at most 18 in about 1 min on a standard desktop computer. Also, we have verified that the minimum stopping set size of the (4896, 2474) Ramanujan-Margulis code is indeed 24, and that the corresponding multiplicity is exactly 204. Furthermore, we have applied the algorithm to the IEEE 802.16e LDPC codes and determined the minimum stopping set size and the corresponding multiplicity exactly for these codes. Finally, as an application, we present a greedy algorithm to find a small number of redundant parity checks to add to the original parity-check matrix in order to remove all stopping sets in the corresponding Tanner graph of size less than the minimum distance. An extensive case study of the (155, 64) Tanner code illustrates the usefulness of the algorithm, and we present a 110 times 155 redundant parity-check matrix for this code with no stopping sets of size less than the minimum distance. Simulation results of iterative decoding on the binary erasure channel show performance improvements for low-to-medium erasure probabilities when this redundant parity-check matrix is used for decoding.
We investigate the stopping redundancy hierarchy of linear block codes and its connection to permutation decoding techniques. An element in the ordered list of stopping redundancy values represents the smallest number of possibly linearly dependent rows in any parity-check matrix of a code that avoids stopping sets of up to a given size. Redundant parity-check equations can be shown to have a similar effect on decoding performance as permuting the coordinates of the received codeword according to a selected set of automorphisms of the code. Based on this finding we develop new decoding strategies for data transmission over the binary erasure channel that combine iterative message passing and permutation decoding in order to avoid errors confined to stopping sets. We also introduce the notion of s-SAD sets, containing the smallest number of automorphisms of a code with the property that they move any set of not more than s erasures into positions that do not correspond to stopping sets within a judiciously chosen parity-check matrix.
It is known that redundant parity-check equations can improve the performance of an LDPC code by reducing the number of harmful substructures in the parity-check matrix. However, it is a difficult problem to design a parity-check matrix in such a way that it avoids substructures that are known to be harmful to iterative decoding while keeping the number of redundant parity-check equations moderate and ensuring other desirable properties. We explicitly give redundant parity-check matrices for cyclic regular LDPC codes of length n and minimum distance d ~ √n in which there are only n parity-check equations but no stopping sets of size d+1 or smaller except for those that correspond to the nonzero codewords of the smallest weight. We do this by showing that the well-known projective LDPC codes from the incidence matrices of projective planes PG(2, q) with q even have this property. This result may give insight into how the small number of redundant parity-check equations in the geometric LDPC codes may be contributing to the good performance reported in the literature. We also give a slightly improved upper bound on the size of a smallest generic erasure correcting set.