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

Abstract

In this paper, we discuss the problems of finding minimum stopping sets and trapping sets in Tanner graphs, using integer linear programming. These problems are important for establishing reliable communication across noisy channels. Indeed, stopping sets and trapping sets correspond to combinatorial structures in information-theoretic codes which lead to errors in decoding once a message is received. We present integer linear programs (ILPs) for finding stopping sets and several trapping set variants. In the journal version of this paper, we prove that two of these trapping set problem variants are NP-hard for the first time. The effectiveness of our approach is demonstrated by finding stopping sets of size up to 48 in the (4896, 2474) Margulis code. This compares favorably to the current state-of-the-art, which finds stopping sets of size up to 26. For the trapping set problems, we show for which cases an ILP yields very efficient solutions and for which cases it performs poorly. The proposed approach is applicable to codes represented by regular and irregular graphs alike.

Publication Date

1-1-2018

Publication Title

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Volume

10856 LNCS

Number of Pages

402-415

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/978-3-319-96151-4_34

Socpus ID

85050604712 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85050604712

This document is currently not available here.

Share

COinS