Hardness Results on Finding Leafless Elementary Trapping Sets and\n Elementary Absorbing Sets of LDPC Codes

2017/11/28 by Ali Dehghan, Amir H. Banihashemi, Dehghan, Ali +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.1711.10543

openalex publication_date 2017/11/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Leafless elementary trapping sets (LETSs) are known to be the problematic\nstructures in the error floor region of low-density parity-check (LDPC) codes\nover the additive white Gaussian (AWGN) channel under iterative decoding\nalgorithms. While problems involving the general category of trapping sets, and\nthe subcategory of elementary trapping sets (ETSs), have been shown to be\nNP-hard, similar results for LETSs, which are a subset of ETSs are not\navailable. In this paper, we prove that, for a general LDPC code, finding a\nLETS of a given size a with minimum number of unsatisfied check nodes b is\nNP-hard to approximate with any guaranteed precision. We also prove that\nfinding the minimum size a of a LETS with a given b is NP-hard to approximate.\nSimilar results are proved for elementary absorbing sets, a popular subcategory\nof LETSs.\n

Related

• On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes
• An Efficient Algorithm for Finding Dominant Trapping Sets of LDPC Codes
• Characterization and Efficient Search of Non-Elementary Trapping Sets of LDPC Codes with Applications to Stopping Sets
• Characterization and Efficient Exhaustive Search Algorithm for Elementary Trapping Sets of Irregular LDPC Codes
• On Characterization of Elementary Trapping Sets of Variable-Regular LDPC Codes