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

Information Theory and Applications Workshop (ITA)

Trapping set enumerators for specific LDPC codes

Shadi Abu‐Surra, David Declercq, D. Divsalar, W.E. Ryan

Published Jan 1, 2010• 48 citations
Publisher

Abstract

In this paper, a method is presented for enumerating the trapping sets of a specific LDPC code given its Tanner graph. The technique involves augmenting the original Tanner graph with additional variable nodes, and then applying a weight-enumeration algorithm to the augmented Tanner graph. The proposed method is used to find trapping set enumerators for several LDPC codes in communication standards. The complexity of the proposed algorithm is discussed.

DOI
10.1109/ita.2010.5454095

Related papers

Designing LDPC Codes without small trapping sets by using Tanner Graph Covers

Miloš Ivković, Shashi Kiran Chilappagari, Bane V. Vasic

We present a method for lowering the error floor of low-density parity check (LDPC) codes. It is based on Tanner graph covers that do not have trapping sets from the original code. The advantages of the method are that it is universal, as it can be applied to any LDPC code/channel model/decoding algorithm and it improves performance at the expense of increasing the code length, without losing the code regularity, without changing the decoding algorithm, and, under certain conditions, without lowering the code rate. We illustrate the method by modifying Tanner, MacKay and Margulis codes to improve performance on the binary symmetric channel (BSC) under the Gallager B decoding algorithm.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•5 citations

Approximate examination of trapping sets of LDPC codes using the probabilistic algorithm

Masanori Hirotomo, Yoshiho Konishi, Masakatu Morii

The performance of LDPC codes decoded by iterative algorithms depends on the structural properties of their underlying Tanner graphs. For general memoryless channels, error patterns dominating the bit and frame error probabilities at the error floor region are termed trapping sets. In this paper, we propose an effective method for finding small-size trapping sets of LDPC codes. In the proposed method, a probabilistic algorithm to find low-weight codewords is applied to finding small trapping sets of LDPC codes. Furthermore, we show numerical results of examining small trapping sets of (504, 252) and (1008, 504) LDPC codes.

International Symposium on Information Theory and its Applications•Dec 1, 2008•14 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

Protograph-based generalized LDPC codes: Enumerators, design, and applications

Shadi Abu‐Surra

Among the recent advances in the area of low-density parity-check (LDPC) codes, protograph-based LDPC codes have the advantages of a simple design procedure and highly structured encoders and decoders. These advantages can also be exploited in the design of protograph-based generalized LDPC (G-LDPC) codes. In this dissertation we provide analytical tools which aid the design of protograph-based LDPC and G-LDPC codes. Specifically, we propose a method for computing the codeword-weight enumerators for finite-length protograph-based G-LDPC code ensembles, and then we consider the asymptotic case when the block-length goes to infinity. These results help the designer identify good ensembles of protograph-based G-LDPC codes in the minimum distance sense (i.e., ensembles which have minimum distances grow linearly with code length). Furthermore, good code ensembles can be characterized by good stopping set, trapping set, or pseudocodeword properties, which assist in the design of G-LDPC codes with low floors. We leverage our method for computing codeword-weight enumerators to compute stopping-set, and pseudocodeword enumerators for the finite-length and the asymptotic ensembles of protograph-based G-LDPC codes. Moreover, we introduce a method for computing trapping set enumerators for finite-length (and asymptotic) protograph-based LDPC code ensembles. Trapping set enumerators for G-LDPC codes represents a more complex problem which we do not consider here. Inspired by our method for computing trapping set enumerators for protograph-based LDPC code ensembles, we developed an algorithm for estimating the trapping set enumerators for a specific LDPC code given its parity-check matrix. We used this algorithm to enumerate trapping sets for several LDPC codes from communication standards. Finally, we study coded-modulation schemes with LDPC codes and pulse position modulation (LDPC-PPM) over the free-space optical channel. We present three different decoding schemes and compare their performances. In addition, we developed a new density evolution tool for use in the design of LDPC codes with good performances over this channel.

•Jan 1, 2009•1 citation

A new method of detecting cycles in Tanner graph of LDPC codes

Bo Li, Gang Wang, Hongjuan Yang

To improve the performance of LDPC codes, we should detect and eliminate cycles in Tanner graph of the parity-check matrix when we make LDPC codes. We improved a logic algebraic algorithm in computing entire routes between the nodes of a communication network, and found a new method of detecting cycles in Tanner graph of LDPC codes. This method applied the logic algebraic calculation rules. First transformed the parity-check matrix and then constructed the relative matrix of the Tanner graph. Through integrating and deleting rows of relative matrix and correcting some elements, this new algorithm can detect all the cycles in a Tanner graph of LDPC codes which code length is n and information bits number is k, just needing integrating and deleting n-1 times and correcting k times. The calculation steps of the algorithm is shown detailed by an (8, 4, 2) LDPC example and its correctness have been validated.

International Conference on Wireless Communications and Signal Processing (WCSP)•Nov 1, 2009•5 citations

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

Andrew McGregor, Olgica Milenković

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.

arXiv:0704.2258•IEEE Information Theory Workshop (ITW)•Sep 1, 2007•28 citations
In this paper, a method is presented for enumerating the trapping sets of a specific LDPC code given its Tanner graph. The technique involves augmenting the original Tanner graph with additional variable nodes, and then applying a weight-enumeration algorithm to the augmented Tanner graph. The proposed method is used to find trapping set enumerators for several LDPC codes in communication standards. The complexity of the proposed algorithm is discussed.
We present a method for lowering the error floor of low-density parity check (LDPC) codes. It is based on Tanner graph covers that do not have trapping sets from the original code. The advantages of the method are that it is universal, as it can be applied to any LDPC code/channel model/decoding algorithm and it improves performance at the expense of increasing the code length, without losing the code regularity, without changing the decoding algorithm, and, under certain conditions, without lowering the code rate. We illustrate the method by modifying Tanner, MacKay and Margulis codes to improve performance on the binary symmetric channel (BSC) under the Gallager B decoding algorithm.
The performance of LDPC codes decoded by iterative algorithms depends on the structural properties of their underlying Tanner graphs. For general memoryless channels, error patterns dominating the bit and frame error probabilities at the error floor region are termed trapping sets. In this paper, we propose an effective method for finding small-size trapping sets of LDPC codes. In the proposed method, a probabilistic algorithm to find low-weight codewords is applied to finding small trapping sets of LDPC codes. Furthermore, we show numerical results of examining small trapping sets of (504, 252) and (1008, 504) LDPC 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.
Among the recent advances in the area of low-density parity-check (LDPC) codes, protograph-based LDPC codes have the advantages of a simple design procedure and highly structured encoders and decoders. These advantages can also be exploited in the design of protograph-based generalized LDPC (G-LDPC) codes. In this dissertation we provide analytical tools which aid the design of protograph-based LDPC and G-LDPC codes. Specifically, we propose a method for computing the codeword-weight enumerators for finite-length protograph-based G-LDPC code ensembles, and then we consider the asymptotic case when the block-length goes to infinity. These results help the designer identify good ensembles of protograph-based G-LDPC codes in the minimum distance sense (i.e., ensembles which have minimum distances grow linearly with code length). Furthermore, good code ensembles can be characterized by good stopping set, trapping set, or pseudocodeword properties, which assist in the design of G-LDPC codes with low floors. We leverage our method for computing codeword-weight enumerators to compute stopping-set, and pseudocodeword enumerators for the finite-length and the asymptotic ensembles of protograph-based G-LDPC codes. Moreover, we introduce a method for computing trapping set enumerators for finite-length (and asymptotic) protograph-based LDPC code ensembles. Trapping set enumerators for G-LDPC codes represents a more complex problem which we do not consider here. Inspired by our method for computing trapping set enumerators for protograph-based LDPC code ensembles, we developed an algorithm for estimating the trapping set enumerators for a specific LDPC code given its parity-check matrix. We used this algorithm to enumerate trapping sets for several LDPC codes from communication standards. Finally, we study coded-modulation schemes with LDPC codes and pulse position modulation (LDPC-PPM) over the free-space optical channel. We present three different decoding schemes and compare their performances. In addition, we developed a new density evolution tool for use in the design of LDPC codes with good performances over this channel.
To improve the performance of LDPC codes, we should detect and eliminate cycles in Tanner graph of the parity-check matrix when we make LDPC codes. We improved a logic algebraic algorithm in computing entire routes between the nodes of a communication network, and found a new method of detecting cycles in Tanner graph of LDPC codes. This method applied the logic algebraic calculation rules. First transformed the parity-check matrix and then constructed the relative matrix of the Tanner graph. Through integrating and deleting rows of relative matrix and correcting some elements, this new algorithm can detect all the cycles in a Tanner graph of LDPC codes which code length is n and information bits number is k, just needing integrating and deleting n-1 times and correcting k times. The calculation steps of the algorithm is shown detailed by an (8, 4, 2) LDPC example and its correctness have been validated.
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.