Hardness Results on Finding Leafless Elementary Trapping Sets and Elementary Absorbing Sets of LDPC Codes
From MaRDI portal
Publication:5224073
Abstract: Leafless elementary trapping sets (LETSs) are known to be the problematic structures in the error floor region of low-density parity-check (LDPC) codes over the additive white Gaussian (AWGN) channel under iterative decoding algorithms. While problems involving the general category of trapping sets, and the subcategory of elementary trapping sets (ETSs), have been shown to be NP-hard, similar results for LETSs, which are a subset of ETSs are not available. In this paper, we prove that, for a general LDPC code, finding a LETS of a given size a with minimum number of unsatisfied check nodes b is NP-hard to approximate with any guaranteed precision. We also prove that finding the minimum size a of a LETS with a given b is NP-hard to approximate. Similar results are proved for elementary absorbing sets, a popular subcategory of LETSs.
Cited in
(5)- On the complexity of and solutions to the minimum stopping and trapping set problems
- Eliminating trapping sets in low-density parity-check codes by using Tanner graph covers
- Characterization and Efficient Search of Non-Elementary Trapping Sets of LDPC Codes With Applications to Stopping Sets
- On the Smallest Absorbing Sets of LDPC Codes From Finite Planes
- Extremal absorbing sets in low-density parity-check codes
This page was built for publication: Hardness Results on Finding Leafless Elementary Trapping Sets and Elementary Absorbing Sets of LDPC Codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224073)
