Stopping set elimination by parity-check matrix extension via integer linear programming

Hossein Falsafain, Seyed Rasoul Mousavi

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


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 ∈ N, by extending the basic formulation, we provide an ILP formulation for finding a set of size of parity-check equations which can best eliminate the stopping sets in L, among all such sets.
Original languageEnglish
Pages (from-to)1533-1540
Number of pages8
JournalIEEE Transactions on Communications
Issue number5
Early online date31 Mar 2015
Publication statusPublished - May 2015


Dive into the research topics of 'Stopping set elimination by parity-check matrix extension via integer linear programming'. Together they form a unique fingerprint.

Cite this