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

Lecture notes in computer science

Finding Minimum Stopping and Trapping Sets: An Integer Linear Programming Approach

Alvaro Velasquez, K. Subramani, Steven Drager

Published Jan 1, 2018• 5 citations
Publisher
DOI
10.1007/978-3-319-96151-4_34

Related papers

Experiments in quadratic 0–1 programming

Francisco Barahona, Michael Jünger, Gerhard Reinelt

Mathematical Programming•May 1, 1989•208 citations

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

Hossein Falsafain, Sayyed Rasoul Mousavi

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.

IEEE Transactions on Communications•Apr 1, 2015•4 citations

Mathematical Programming Models and Exact Algorithms

Abraham P. Punnen, Renata Sotirov

Springer eBooks•Jan 1, 2022•3 citations

On the Number of Minimum Stopping Sets and Minimum Codewords of Array LDPC Codes

Haiyang Liu, Lianrong Ma, Jie Chen

For an odd prime q and an integer m ≤ q, a binary mq × q2quasi-cyclic parity-check matrix H(m,q) can be constructed for a class of array LDPC code C(m,q). In this letter, the closed-form formula for the numbers of minimum stopping sets of H(m,q) and minimum codewords of C(m,q) are given for 2 ≤ m ≤ 3 and for (m,q)=(4,5) and (4,7).

IEEE Communications Letters•Jul 1, 2010•16 citations

Enumerators for Protograph-Based Ensembles of LDPC and Generalized LDPC Codes

Shadi Abu‐Surra, D. Divsalar, W.E. Ryan

Protograph-based LDPC and generalized LDPC (G-LDPC) codes have the advantages of a simple design procedure and highly structured encoders and decoders. The design of such “protograph-based codes” relies on what is effectively a computer-based search. As such, following Gallager, it is prudent to restrict the search to a “good ensemble,” for example, an ensemble whose minimum distance grows linearly with codeword length. A good ensemble can also mean one with good stopping set, trapping set, or pseudocodeword properties. In this paper, ensemble codeword weight enumerators for finite-length LDPC and G-LDPC codes based on protographs were derived, and then the asymptotic case was considered. The asymptotic results allow us to determine whether or not the typical relative minimum distance in the ensemble grows linearly with codeword length. Then, the codeword weight enumerator technique is adapted to yield ensemble stopping set, trapping set, and pseudocodeword enumerators for protograph LDPC and G-LDPC codes. In this case, the asymptotic results allow us to determine whether or not the typical relative smallest stopping set size, trapping set size, and pseudoweight grows linearly with codeword length. Trapping set enumerators for G-LDPC code ensembles represent a more complex problem which we do not consider here.

IEEE Transactions on Information Theory•Jan 21, 2011•100 citations

Optimal State Determination: A Conjecture

Igor D. Ivanović

Springer eBooks•Jan 1, 1987•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.
Protograph-based LDPC and generalized LDPC (G-LDPC) codes have the advantages of a simple design procedure and highly structured encoders and decoders. The design of such “protograph-based codes” relies on what is effectively a computer-based search. As such, following Gallager, it is prudent to restrict the search to a “good ensemble,” for example, an ensemble whose minimum distance grows linearly with codeword length. A good ensemble can also mean one with good stopping set, trapping set, or pseudocodeword properties. In this paper, ensemble codeword weight enumerators for finite-length LDPC and G-LDPC codes based on protographs were derived, and then the asymptotic case was considered. The asymptotic results allow us to determine whether or not the typical relative minimum distance in the ensemble grows linearly with codeword length. Then, the codeword weight enumerator technique is adapted to yield ensemble stopping set, trapping set, and pseudocodeword enumerators for protograph LDPC and G-LDPC codes. In this case, the asymptotic results allow us to determine whether or not the typical relative smallest stopping set size, trapping set size, and pseudoweight grows linearly with codeword length. Trapping set enumerators for G-LDPC code ensembles represent a more complex problem which we do not consider here.