Exhaustive Enumeration of Elementary Trapping Sets of an Arbitrary Tanner Graph

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).