solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看3039次
Hardness Results on Finding Leafless Elementary Trapping Sets and Elementary Absorbing Sets of LDPC Codes. (arXiv:1711.10543v2 [cs.IT] UPDATED)
来源于:arXiv
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. 查看全文>>