Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0704.2258 · IEEE Information Theory Workshop (ITW)

On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes

Andrew McGregor, Olgica Milenković

Published Sep 1, 2007• 28 citations
arXivHTMLPDF

Abstract

We prove that approximating the size of the smallest trapping set in Tanner graphs of linear block codes, and more restrictively, LDPC codes, is NP-hard. The proof techniques rely on reductions from three NP-hard problems, the set cover, minimum three-dimensional matching, and the minimum Hamming distance problem. The ramifications of our findings are that methods used for estimating the height of the error-floor of long LDPC codes, centered around trapping set enumeration, cannot provide accurate worst-case performance predictions.

DOI
10.1109/itw.2007.4313082

Related papers

On the Hardness of Approximating Stopping and Trapping Sets

Andrew McGregor, Olgica Milenković

We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) codes, is NP-hard. The ramifications of our findings are that methods used for estimating the height of the error-floor of moderate- and long-length LDPC codes, based on stopping and trapping set enumeration, cannot provide accurate worst-case performance predictions for most codes.

IEEE Transactions on Information Theory•Mar 24, 2010•61 citations

On theHardness ofApproximating Stopping and Trapping Setsin LDPC Codes

Olgica Milenković

We provethatapproximating thesizeofthe smallest trapping setinTannergraphsoflinear block codes, andmorerestrictively, LDPC codes, isNP-hard. Theprooftechniques relyonreductions fromthreeNP- hardproblems, thesetcover, minimumthree-dimensional matching, andtheminimumHammingdistance problem. Theramifications ofourfindings arethatmethodsused forestimating theheight oftheerror-floor oflongLDPC codes, centered aroundtrapping setenumeration, cannot provide accurate worst-case performance predictions. I.INTRODUCTION Inthepastdecade, thesearch forefficient andnear- optimal decoding algorithms forlinear block codes cul- minated withtherediscovery andgeneralization ofthe notion ofsparse codesanditerative message passing algorithms. Iterative decoders canapproach theShannon limit ofreliable communication withpolynomial time complexity, provided thattheyoperate onlong, low- density parity-check (LDPC)codes. Thisisachieved by using graphical representations ofcodes, termed Tanner graphs, that contain asmall numberofedges. Onsuch graphs, probabilistic inference oftheformofiterative message passing isknowntohavelinear complexity. Theperformance oflinear blockcodesunderiter- ative decoding, andtheperformance ofLDPC codes inparticular, depends onthestructural properties of their underlying Tannergraphs. Foreachchannel- decoder pair, there exist vertex configurations inthe codegraph onwhichagiven iterative decoder fails. Forsomefrequently encountered Discrete Memoryless Channels (DMCs), suchconfigurations areknownas near-codewords (9), trapping andstopping sets(3), (12), pseudocodewords (7), orinstantons (13). Itisknownthat maximum-likelihood (ML)decoders fail whentransmission errors areconfined toTanner graph configurations corresponding tocodewords, while iterative decoders usually fail tomakecorrect decisions on(strictly) larger setsofconfigurations. Forexample, iterative edge-removal (ER)decoders forcoding overthe

•Jan 1, 2007•0 citations

Finding Small Stopping Sets in the Tanner Graphs of LDPC Codes

Gerd Richter

The performance of low-density parity-check (LDPC) codes over the binary erasure channel for a low erasure probability is limited by small stopping sets. The frame error rate over the additive white Gaussian noise (AWGN) channel for a high signal-to-noise ratio is limited by small trapping sets and by the minimum distance of the LDPC code, which is equal to the codeword with the minimal Hamming weight. In this paper, we present a simple and fast algorithm based on the error impulse method to find small stopping sets in the Tanner graphs of LDPC codes. Since a codeword with small Hamming weight can be represented by a special stopping set, the algorithm can also be used to find the minimum distance of LDPC codes. Furthermore, we use the size of the small stopping sets and the minimum distance of the code to calculate asymptotic performance bounds for LDPC codes transmitted over the binary erasure and the AWGN channel, respectively and compare the bounds with simulations. 1

•Apr 3, 2006•27 citations

Asymptotic distributions of trapping sets in random regular LDPC code ensembles

Olgica Milenković, Emina Soljanin, Philip Whiting

We address the problem of evaluating the asymptotic normalized distributions of a class of combinatorial configurations in random, regular, binary low-density parity-check (LDPC) code ensembles.Among the configurations considered are trapping and stopping sets 1 ; these sets represent induced subgraphs in the Tanner graph of a code that, for certain classes of channels, exhibit a strong influence on the height and point of onset of the error-floor.The techniques used in the derivations are based on large deviation theory and statistical methods for enumerating random-like matrices.These techniques can also be applied in a setting that involves more general structural entities such as subcodes and/or minimal codewords, which are known to characterize other important properties of soft-decision decoders of linear codes.

Allerton Conference on Communication, Control, and Computing•Jan 1, 2005•3 citations

Characterization of small trapping sets in LDPC codes from Steiner triple systems

Stefan Laendner, Olgica Milenković, Johannes B. Huber

The error-floor performance of low-density parity-check (LDPC) codes under iterative decoding is governed by combinatorial configurations in the Tanner graph of the code termed trapping sets. Finding the smallest trapping set in a Tanner graph is an NP-hard problem. However, for codes constructed from designs one can partially characterize trapping sets and enumerate them efficiently. We focus on LDPC codes based on Steiner triple systems (STS), and quantify small trapping sets for bit-flipping decoding over the BSC and small trapping sets for the AWGN channel. Furthermore, we provide simulation results that show that the enumeration scheme at hand provides good estimates for the error-floor behavior of STS LDPC codes.

International Symposium on Turbo Codes and Iterative Information Processing•Sep 1, 2010•14 citations

Finding Leafless Elementary Trapping Sets and Elementary Absorbing Sets of LDPC Codes is Hard

Ali Dehghan, Amir H. Banihashemi

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 α 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.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•3 citations
We prove that approximating the size of the smallest trapping set in Tanner graphs of linear block codes, and more restrictively, LDPC codes, is NP-hard. The proof techniques rely on reductions from three NP-hard problems, the set cover, minimum three-dimensional matching, and the minimum Hamming distance problem. The ramifications of our findings are that methods used for estimating the height of the error-floor of long LDPC codes, centered around trapping set enumeration, cannot provide accurate worst-case performance predictions.
We provethatapproximating thesizeofthe smallest trapping setinTannergraphsoflinear block codes, andmorerestrictively, LDPC codes, isNP-hard. Theprooftechniques relyonreductions fromthreeNP- hardproblems, thesetcover, minimumthree-dimensional matching, andtheminimumHammingdistance problem. Theramifications ofourfindings arethatmethodsused forestimating theheight oftheerror-floor oflongLDPC codes, centered aroundtrapping setenumeration, cannot provide accurate worst-case performance predictions. I.INTRODUCTION Inthepastdecade, thesearch forefficient andnear- optimal decoding algorithms forlinear block codes cul- minated withtherediscovery andgeneralization ofthe notion ofsparse codesanditerative message passing algorithms. Iterative decoders canapproach theShannon limit ofreliable communication withpolynomial time complexity, provided thattheyoperate onlong, low- density parity-check (LDPC)codes. Thisisachieved by using graphical representations ofcodes, termed Tanner graphs, that contain asmall numberofedges. Onsuch graphs, probabilistic inference oftheformofiterative message passing isknowntohavelinear complexity. Theperformance oflinear blockcodesunderiter- ative decoding, andtheperformance ofLDPC codes inparticular, depends onthestructural properties of their underlying Tannergraphs. Foreachchannel- decoder pair, there exist vertex configurations inthe codegraph onwhichagiven iterative decoder fails. Forsomefrequently encountered Discrete Memoryless Channels (DMCs), suchconfigurations areknownas near-codewords (9), trapping andstopping sets(3), (12), pseudocodewords (7), orinstantons (13). Itisknownthat maximum-likelihood (ML)decoders fail whentransmission errors areconfined toTanner graph configurations corresponding tocodewords, while iterative decoders usually fail tomakecorrect decisions on(strictly) larger setsofconfigurations. Forexample, iterative edge-removal (ER)decoders forcoding overthe
The performance of low-density parity-check (LDPC) codes over the binary erasure channel for a low erasure probability is limited by small stopping sets. The frame error rate over the additive white Gaussian noise (AWGN) channel for a high signal-to-noise ratio is limited by small trapping sets and by the minimum distance of the LDPC code, which is equal to the codeword with the minimal Hamming weight. In this paper, we present a simple and fast algorithm based on the error impulse method to find small stopping sets in the Tanner graphs of LDPC codes. Since a codeword with small Hamming weight can be represented by a special stopping set, the algorithm can also be used to find the minimum distance of LDPC codes. Furthermore, we use the size of the small stopping sets and the minimum distance of the code to calculate asymptotic performance bounds for LDPC codes transmitted over the binary erasure and the AWGN channel, respectively and compare the bounds with simulations. 1
We address the problem of evaluating the asymptotic normalized distributions of a class of combinatorial configurations in random, regular, binary low-density parity-check (LDPC) code ensembles.Among the configurations considered are trapping and stopping sets 1 ; these sets represent induced subgraphs in the Tanner graph of a code that, for certain classes of channels, exhibit a strong influence on the height and point of onset of the error-floor.The techniques used in the derivations are based on large deviation theory and statistical methods for enumerating random-like matrices.These techniques can also be applied in a setting that involves more general structural entities such as subcodes and/or minimal codewords, which are known to characterize other important properties of soft-decision decoders of linear codes.
The error-floor performance of low-density parity-check (LDPC) codes under iterative decoding is governed by combinatorial configurations in the Tanner graph of the code termed trapping sets. Finding the smallest trapping set in a Tanner graph is an NP-hard problem. However, for codes constructed from designs one can partially characterize trapping sets and enumerate them efficiently. We focus on LDPC codes based on Steiner triple systems (STS), and quantify small trapping sets for bit-flipping decoding over the BSC and small trapping sets for the AWGN channel. Furthermore, we provide simulation results that show that the enumeration scheme at hand provides good estimates for the error-floor behavior of STS LDPC codes.
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 α 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.