Exhaustive search for small fully absorbing sets and the corresponding low error-floor decoder
Gyu Bum Kyung, Chih-Chun Wang · 2010
This work provides an exhaustive search algorithm for finding small fully absorbing sets (FASs) of arbitrary low-density parity-check (LDPC) codes. In particular, given any LDPC code, the problem of finding all FASs of size less than t is formulated as an integer programming problem, for which a new branch-&-bound algorithm is devised. New node selection and the tree-trimming mechanisms are designed to further enhance the efficiency of the algorithm. The proposed algorithm is capable of finding all FASs of size ≤ 11 with no larger than 2 induced odd-degree check nodes for LDPC codes of length ≤ 1000. The resulting exhaustive list of small FASs is then used to devise a new post-processing decoder. Numerical results show that by taking advantage of the exhaustive list of small FASs, the proposed decoder significantly lowers the error floor for codes of practical lengths and outperforms the state-of-the-art low-error-floor decoders.