On the Exhaustion and Elimination of Trapping Sets: Algorithms & The Suppressing Effect
Chih-Chun Wang · 2007
This paper studies a systematic treatment of trapping sets in finite-length LDPC codes and its related theoretic properties. It is proven that the complexity of deciding the minimal trapping distance is NP-complete. Furthermore, exhausting minimal trapping sets can be achieved by using any good stopping set exhaustion algorithm as a building block. The suppressing effect of cyclic lifting for trapping sets is also studied in this work, which characterizes the probability that a base code trapping sets survives after applying the cyclic lifting technique. The corresponding quantitative knowledge about the origin of small trapping sets in the cyclically lifted codes helps provide definite guidelines for the base code optimization to lower the error-floor over non-erasure channels. Extensive numerical experiments are provided to demonstrate the various techniques discussed in this work.