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

International Symposium on Information Theory and its Applications

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

Masanori Hirotomo, Yoshiho Konishi, Masakatu Morii

Published Dec 1, 2008• 14 citations
Publisher

Abstract

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.

DOI
10.1109/isita.2008.4895509

Related papers

Detailed evaluation of error floors of LDPC codes using the probabilistic algorithm

Masanori Hirotomo, Masakatu Morii

The performance of LDPC codes decoded by iterative algorithm depends on the structural properties of their underlying Tanner graphs. For discrete memoryless channels, error patterns dominating the frame error rate (FER) in the error floor region are termed trapping set. We have shown approximate examinations of small trapping sets of LDPC codes using the probabilistic algorithm. In this paper, we propose an efficient method for the detailed evaluation of the FER of LDPC codes in the error floor region. The accuracy of the FER lies on the failure probability of the number of trapping sets determined by our probabilistic algorithm and the FER estimated by the importance sampling.

International Symposium on Information Theory and its Applications•Oct 1, 2010•4 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

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

An Iterative Decoding Algorithm with Backtracking to Lower the Error-Floors of LDPC Codes

Jingyu Kang, Qin Huang, Shu Lin +1 more

Error-floors are the main reason for excluding LDPC codes from applications requiring very low bit-error rate. They are attributed to a particular structure in the codes' Tanner graphs, known as trapping sets, which traps the message-passing algorithms commonly used to decode LDPC codes, and prevents decoding from converging to the correct codeword. A technique is proposed to break trapping sets while decoding. Based on decoding results leading to a decoding failure, some bits are identified in a previous iteration and flipped and decoding is restarted. This backtracking may enable the decoder to get out of the trapped state. A semi-analytical method is also proposed to predict the error-floor after backtracking. Simulation results indicate the effectiveness of the proposed technique in lowering the error-floor. The technique, which has moderate complexity overhead, is applicable to any code without requiring a prior knowledge of the structure of its trapping sets.

IEEE Transactions on Communications•Oct 27, 2010•45 citations

An efficient algorithm for finding dominant trapping sets of LDPC codes

Mehdi Karimi Dehkordi, Amir H. Banihashemi

This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. This 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. The algorithm is initiated with a set of short cycles as the input. The cycles 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. 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.

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

A probabilistic algorithm for finding the minimum-size stopping sets of LDPC codes

Masanori Hirotomo, Yoshiho Konishi, Masakatu Morii

On the binary erasure channel, the performance of LDPC codes decoded by iterative algorithms is dominated by small-size stopping sets, especially minimal stopping sets. In this paper, we propose a probabilistic algorithm for computing the minimum size of stopping sets of LDPC codes. In this algorithm, we generate efficiently small-size stopping sets by using the relation between small-size stopping sets and low-weight codewords. In numerical experiments, we could compute the minimum size of stopping sets of LDPC codes of length about 500, 1000 and 5000 with high reliability, and could find smaller stopping sets than that found by conventional methods.

IEEE Information Theory Workshop (ITW)•May 1, 2008•7 citations
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 performance of LDPC codes decoded by iterative algorithm depends on the structural properties of their underlying Tanner graphs. For discrete memoryless channels, error patterns dominating the frame error rate (FER) in the error floor region are termed trapping set. We have shown approximate examinations of small trapping sets of LDPC codes using the probabilistic algorithm. In this paper, we propose an efficient method for the detailed evaluation of the FER of LDPC codes in the error floor region. The accuracy of the FER lies on the failure probability of the number of trapping sets determined by our probabilistic algorithm and the FER estimated by the importance sampling.
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
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.
Error-floors are the main reason for excluding LDPC codes from applications requiring very low bit-error rate. They are attributed to a particular structure in the codes' Tanner graphs, known as trapping sets, which traps the message-passing algorithms commonly used to decode LDPC codes, and prevents decoding from converging to the correct codeword. A technique is proposed to break trapping sets while decoding. Based on decoding results leading to a decoding failure, some bits are identified in a previous iteration and flipped and decoding is restarted. This backtracking may enable the decoder to get out of the trapped state. A semi-analytical method is also proposed to predict the error-floor after backtracking. Simulation results indicate the effectiveness of the proposed technique in lowering the error-floor. The technique, which has moderate complexity overhead, is applicable to any code without requiring a prior knowledge of the structure of its trapping sets.
This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. This 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. The algorithm is initiated with a set of short cycles as the input. The cycles 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. 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.
On the binary erasure channel, the performance of LDPC codes decoded by iterative algorithms is dominated by small-size stopping sets, especially minimal stopping sets. In this paper, we propose a probabilistic algorithm for computing the minimum size of stopping sets of LDPC codes. In this algorithm, we generate efficiently small-size stopping sets by using the relation between small-size stopping sets and low-weight codewords. In numerical experiments, we could compute the minimum size of stopping sets of LDPC codes of length about 500, 1000 and 5000 with high reliability, and could find smaller stopping sets than that found by conventional methods.