An effective branch-and-bound (B&B) algorithm for exhaustively enumerating the elementary trapping sets (ETSs) in an arbitrary given Tanner graph is described. Given a Tanner graph G and a positive integer ν, we introduce a novel 0-1 integer linear programming (ILP) formulation of the NP-hard problem of finding the minimum ω for which there exists an (ω, ν)-ETS in G. The B&B procedure is then based on the LP relaxation of this 0-1 ILP formulation. Our novel 0-1 ILP description of the problem yields a strong (tight) LP relaxation, which allows the search space to be pruned very effectively, as confirmed by experimental results. An obvious advantage of the proposed approach is that it does not require the input Tanner graph to be of a particular form (e.g., variable-regular).
|Number of pages||4|
|Journal||IEEE Communications Letters|
|Early online date||7 Jul 2016|
|Publication status||Published - Sep 2016|
FingerprintDive into the research topics of 'Exhaustive Enumeration of Elementary Trapping Sets of an Arbitrary Tanner Graph'. Together they form a unique fingerprint.
- School of Computing, Mathematics and Data Sciences - Assistant Professor (Academic)
Person: Teaching and Research