An efficient exhaustive search algorithm for elementary trapping sets of variable-regular LDPC codes
In this paper, we propose an efficient exhaustive search algorithm for elementary trapping sets (ETS) of variable-regular low-density parity-check (LDPC) codes. Recently, Karimi and Banihashemi proposed a characterization of ETSs, which was based on viewing an ETS as a layered superset (LSS) of a short cycle in the code's Tanner graph. A notable advantage of LSS characterization is that it corresponds to a simple LSS-based search algorithm (expansion technique) that starts from short cycles of the graph and finds the ETSs with LSS structure efficiently. Compared to the LSS-based search, which is based on a single LSS expansion technique, the new search algorithm involves two additional expansion techniques. The introduction of the new techniques results in significant improvements in search efficiency compared to the LSS-based search. We prove that using the three expansion techniques, each and every ETS structure can be obtained starting from a simple cycle. We also provide extensive simulation results that show, compared to the LSS-based search, up to three orders of magnitude improvement in search speed and memory requirements can be achieved.
|Conference||2016 IEEE International Conference on Communications, ICC 2016|
Hashemi, Y. (Yoones), & Banihashemi, A. (2016). An efficient exhaustive search algorithm for elementary trapping sets of variable-regular LDPC codes. Presented at the 2016 IEEE International Conference on Communications, ICC 2016. doi:10.1109/ICC.2016.7511551