RECORD
An Efficient Algorithm for Finding Dominant Trapping Sets of LDPC Codes
Information Theory · Submitted 23 Aug 2011
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. The algorithm can be used to estimate the error floor of LDPC codes or to be part of the apparatus to design LDPC codes with low error floors. For regular codes, the algorithm is initiated with a set of short cycles as the input. For irregular codes, in addition to short cycles, variable nodes with low degree and cycles with low approximate cycle extrinsic message degree (ACE) are also used as the initial inputs. The initial inputs are then expanded recursively to dominant trapping sets of increasing size. At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes and cycles with low ACE. The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find other graphical objects, such as absorbing sets and Zyablov-Pinsker (ZP) trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. | contribution 1.00 | 0.93 | 0.38 | asserted 1.00 |
| s1 | The algorithm can be used to estimate the error floor of LDPC codes or to be part of the apparatus to design LDPC codes with low error floors. | contribution 0.45 | 0.24 | 0.12 | hedged possibility 0.67 |
| s2 | For regular codes, the algorithm is initiated with a set of short cycles as the input. | method 1.00 | 0.63 | 0.03 | asserted 1.00 |
| s3 | For irregular codes, in addition to short cycles, variable nodes with low degree and cycles with low approximate cycle extrinsic message degree (ACE) are also used as the initial inputs. | method 1.00 | 0.60 | 0.03 | asserted 1.00 |
| s4 | The initial inputs are then expanded recursively to dominant trapping sets of increasing size. | method 1.00 | 0.77 | 0.05 | asserted 1.00 |
| s5 | At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes and cycles with low ACE. | method 0.91 | 0.77 | 0.09 | asserted 1.00 |
| s6 | The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find other graphical objects, such as absorbing sets and Zyablov-Pinsker (ZP) trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. | contribution 0.81 | 0.61 | 0.11 | asserted 0.97 |
| s7 | Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. | result 0.99 | 0.95 | 0.24 | asserted 1.00 |
| s8 | In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets. | result 0.99 | 0.92 | 0.25 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. The algorithm can be used to estimate the error floor of LDPC codes or to be part of the apparatus to design LDPC codes with low error floors. For regular codes, the algorithm is initiated with a set of short cycles as the input. For irregular codes, in addition to short cycles, variable nodes with low degree and cycles with low approximate cycle extrinsic message degree (ACE) are also used as the initial inputs. The initial inputs are then expanded recursively to dominant trapping sets of increasing size. At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes and cycles with low ACE. The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find other graphical objects, such as absorbing sets and Zyablov-Pinsker (ZP) trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.
Human review
How the literature uses it
1 arXiv paper cite this in 2 sentences
Papers citing it · 1 sentence without a confident label
Cites it as background 1 paper
-
Further work on trapping sets includes algorithms to enumerate the occurrence of small trapping sets in specific codes [ref] and the characterization of trapping set parameters in random ensembles of LDPC codes [ref] .
Error Floor Approximation for LDPC Codes in the AWGN Channel · Introduction · 0.96
What it cites · 7 sentences without a confident label
Uses the method or tool of 1 paper
-
Based on the importance sampling technique of [ref] , the trapping sets in Table [ref] with size $l$, $6≤l≤12$, were used to estimate the error floor of this code for a 3-bit quantized min-sum decoder over the AWGN channel.
A General Method for Finding Low Error Rates of LDPC Codes · Irregular Codes · 1.00
Compares with 1 paper
-
As another comparison for the running time of the proposed algorithm, it took the algorithm 55 minutes to find all the absorbing sets of size less than 15, while the same task took 8.2 hours for the impulse method of [ref] on a comparable computer (2.2-GHz CPU with 1 GB RAM).
A General Method for Finding Low Error Rates of LDPC Codes · Regular Codes · 0.97
Cites as background 2 papers
-
Efficient search algorithms have been devised to find small (dominant) stopping and trapping sets [ref] , [ref] , [ref] , [ref] , [ref] , [ref] , [ref] .
A General Method for Finding Low Error Rates of LDPC Codes · Introduction · 0.82
-
In the case of the binary symmetric channel (BSC) and the additive white Gaussian noise (AWGN) channel, the error-prone patterns are called trapping sets [ref] , near codewords [ref] or pseudo codewords [ref] .
Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes · Introduction · 0.96
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.