2015/10/16 by Yoones Hashemi, Amir H. Banihashemi, Hashemi, Yoones +1
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Cooperative Communication and Network Coding #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1510.04954
openalex publication_date 2015/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we propose a new characterization for elementary trapping sets (ETSs) 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 that starts from short cycles of the graph and finds the ETSs with LSS structure efficiently. Compared to the LSS-based characterization of Karimi and Banihashemi, which is based on a single LSS expansion technique, the new characterization involves two additional expansion techniques. The introduction of the new techniques mitigates two problems that LSS-based characterization/search suffers from: (1) exhaustiveness, (2) search efficiency. We prove that using the three expansion techniques, any ETS structure can be obtained starting from a simple cycle, no matter how large the size of the structure a or the number of its unsatisfied check nodes b are. We also demonstrate that for the proposed characterization/search to exhaustively cover all the ETS structures within the (a,b) classes with a ≤ amax, b ≤ bmax, for any value of amax and bmax, the length of the short cycles required to be enumerated is less than that of the LSS-based characterization/search. We also prove that the three expansion techniques, proposed here, are the only expansions needed for characterization of ETS structures starting from simple cycles in the graph, if one requires each and every intermediate sub-structure to be an ETS as well. Extensive simulation results are provided to show that, compared to LSS-based search, significant improvement in search speed and memory requirements can be achieved.