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

Algorithmicand CombinatorialAnalysis of Trapping Setsin StructuredLDPC Codes

Stefan Laendner, Olgica Milenković

Published Jan 1, 2005• 0 citations
OpenAlex

Abstract

Several combinatorial properties oflow-density parity-check (LDPC)codes, suchasminimumdistance, di- ameter, stopping number, girth andcycle-length distribution ofthecorresponding Tanner graph, areknowntoinfluence their performance underiterative decoding. Recently, anew class ofcombinatorial configurations, termed trapping sets, wasshowntobeofsignificant importance indetermining the properties ofLDPCcodes intheerror-floor region. Verylittle isknownbothabout theexistence/parameters oftrapping sets instructured LDPCcodes andaboutpossible techniques for reducing their negative influence onthecode's performance. Inthispaper, we willaddress boththese problems from analgorithmic andcombinatorial perspective. We will first provide anumerical studyofthetrapping phenomena for theMargulis code, whichexhibits afairly higherror-floor. Basedonthisanalysis, conducted fortwodifferent imple- mentations ofiterative belief propagation, wewill propose a novel decoding process, termed averaged decoding. Averaged decoding provides forasignificant reduction inthenumber ofincorrectly decoded frames intheerror-floor region of theMargulis code.Furthermore, basedontheresults of thealgorithmic approach, wesuggest anovel combinatorial characterizations oftrapping sets intheclass ofLDPCcodes basedonfinite geometries. Projective geometry LDPCcodes aresuspected tohaveextremely lowerror-floors, whichis a property thatwemayattribute tothenon-existence of certain smaUl trapping sets inthecodegraph.

Related papers

Algorithmic and Combinatorial Analysis of Trapping Sets in Structured LDPC Codes

Stefan Laendner, Olgica Milenković

Several combinatorial properties of low-density parity-check (LDPC) codes, such as minimum distance, diameter, stopping number, girth and cycle-length distribution of the corresponding Tanner graph, are known to influence their performance under iterative decoding. Recently, a new class of combinatorial configurations, termed trapping sets, was shown to be of significant importance in determining the properties of LDPC codes in the error-floor region. Very little is known both about the existence/parameters of trapping sets in structured LDPC codes and about possible techniques for reducing their negative influence on the code's performance. In this paper, we address both these problems from an algorithmic and combinatorial perspective. We first provide a numerical study of the trapping phenomena for the Margulis code, which exhibits a fairly high error-floor. Based on this analysis, conducted for two different implementations of iterative belief propagation, we propose a novel decoding process, termed averaged decoding. Averaged decoding provides for a significant reduction in the number of incorrectly decoded frames in the error-floor region of the Margulis code. Furthermore, based on the results of the algorithmic approach, we suggest a novel combinatorial characterizations of trapping sets in the class of LDPC codes based on finite geometries. Projective geometry LDPC codes are suspected to have extremely low error-floors, which is a property that we may attribute to the non-existence of certain small trapping sets in the code graph.

•Dec 10, 2005•140 citations

Asymptotic Spectra of Trapping Sets in Regular and Irregular LDPC Code Ensembles

Olgica Milenković, Emina Soljanin, Philip Whiting

We evaluate the asymptotic normalized average distributions of a class of combinatorial configurations in random, regular and irregular, binary low-density parity-check (LDPC) code ensembles. Among the configurations considered are trapping and stopping sets. These sets represent subsets of variable nodes in the Tanner graph of a code that play an important role in determining the height and point of onset of the error-floor in its performance curve. The techniques used for deriving the spectra include large deviations theory and statistical methods for enumerating binary matrices with prescribed row and column sums. These techniques can also be applied in a setting that involves more general structural entities such as subcodes and/or minimal codewords, that are known to characterize other important properties of soft-decision decoders of linear block codes

IEEE Transactions on Information Theory•Jan 1, 2007•134 citations

Analysis of failures of decoders for LDPC codes

Shashi Kiran Chilappagari

Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown.An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC).For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability.We also propose an algorithm to identify the most probable noise configurations, also known as instantons, that lead to error floor for linear programming (LP) decoding over the BSC. With the insight gained from the above analysis techniques, we propose novel code construction techniques that result in codes with superior error floor performance.

•Jan 1, 2008•0 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

On absorbing sets of structured sparse graph codes

Lara Dolecek

In contrast to the capacity approaching performance of iteratively decoded low-density parity check (LDPC) codes, many practical finite-length LDPC codes exhibit performance degradation, manifested in a so-called error floor. Previous work has linked this phenomenon to the presence of certain combinatorial structures within the Tanner graph representation of the code, termed absorbing sets. Absorbing sets are stable under the bit-flipping operations and have been shown to act as fixed points (¿absorbers¿) for a wider class of iterative decoding algorithms. Codes often possess absorbing sets whose size is smaller than the minimum distance: the smallest absorbing sets are deemed most detrimental culprits behind the error floor. This paper focuses on the elementary combinatorial bounds of the smallest (candidate) absorbing sets. For certain classes of practical codes we demonstrate the tightness of these bounds and show how can the structure of the code and the structure of the absorbing sets be utilized to increase the size of the smallest absorbing sets without compromising other code properties such as the node degrees and the girth. As such, this work provides a step towards a better code design by taking into account the combinatorial nature of fixed points of iterative decoding algorithms.

Information Theory and Applications Workshop (ITA)•Jan 1, 2010•20 citations

Error floors and finite geometries

Shu Lin, Qiuju Diao, Ian F. Blake

The structure of certain subgraphs of the Tanner graph of an LDPC code, the trapping sets, has been identified as important for the error floor performance of iterative decoding algorithms. To investigate such sets requires the parity check matrix of the code to be generated with sufficient structure that allows useful information to be obtained while giving good codes. Structures that have been considered include combinatorial designs and classical finite geometries. More recently other finite geometric notions such as partial geometries and generalized d-gons have been considered with some success. This work considers aspects of this approach.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 1, 2014•6 citations
Several combinatorial properties oflow-density parity-check (LDPC)codes, suchasminimumdistance, di- ameter, stopping number, girth andcycle-length distribution ofthecorresponding Tanner graph, areknowntoinfluence their performance underiterative decoding. Recently, anew class ofcombinatorial configurations, termed trapping sets, wasshowntobeofsignificant importance indetermining the properties ofLDPCcodes intheerror-floor region. Verylittle isknownbothabout theexistence/parameters oftrapping sets instructured LDPCcodes andaboutpossible techniques for reducing their negative influence onthecode's performance. Inthispaper, we willaddress boththese problems from analgorithmic andcombinatorial perspective. We will first provide anumerical studyofthetrapping phenomena for theMargulis code, whichexhibits afairly higherror-floor. Basedonthisanalysis, conducted fortwodifferent imple- mentations ofiterative belief propagation, wewill propose a novel decoding process, termed averaged decoding. Averaged decoding provides forasignificant reduction inthenumber ofincorrectly decoded frames intheerror-floor region of theMargulis code.Furthermore, basedontheresults of thealgorithmic approach, wesuggest anovel combinatorial characterizations oftrapping sets intheclass ofLDPCcodes basedonfinite geometries. Projective geometry LDPCcodes aresuspected tohaveextremely lowerror-floors, whichis a property thatwemayattribute tothenon-existence of certain smaUl trapping sets inthecodegraph.
Several combinatorial properties of low-density parity-check (LDPC) codes, such as minimum distance, diameter, stopping number, girth and cycle-length distribution of the corresponding Tanner graph, are known to influence their performance under iterative decoding. Recently, a new class of combinatorial configurations, termed trapping sets, was shown to be of significant importance in determining the properties of LDPC codes in the error-floor region. Very little is known both about the existence/parameters of trapping sets in structured LDPC codes and about possible techniques for reducing their negative influence on the code's performance. In this paper, we address both these problems from an algorithmic and combinatorial perspective. We first provide a numerical study of the trapping phenomena for the Margulis code, which exhibits a fairly high error-floor. Based on this analysis, conducted for two different implementations of iterative belief propagation, we propose a novel decoding process, termed averaged decoding. Averaged decoding provides for a significant reduction in the number of incorrectly decoded frames in the error-floor region of the Margulis code. Furthermore, based on the results of the algorithmic approach, we suggest a novel combinatorial characterizations of trapping sets in the class of LDPC codes based on finite geometries. Projective geometry LDPC codes are suspected to have extremely low error-floors, which is a property that we may attribute to the non-existence of certain small trapping sets in the code graph.
We evaluate the asymptotic normalized average distributions of a class of combinatorial configurations in random, regular and irregular, binary low-density parity-check (LDPC) code ensembles. Among the configurations considered are trapping and stopping sets. These sets represent subsets of variable nodes in the Tanner graph of a code that play an important role in determining the height and point of onset of the error-floor in its performance curve. The techniques used for deriving the spectra include large deviations theory and statistical methods for enumerating binary matrices with prescribed row and column sums. These techniques can also be applied in a setting that involves more general structural entities such as subcodes and/or minimal codewords, that are known to characterize other important properties of soft-decision decoders of linear block codes
Ever since the publication of Shannon's seminal work in 1948, the search for capacity achieving codes has led to many interesting discoveries in channel coding theory. Low-density parity-check (LDPC) codes originally proposed in 1963 were largely forgotten and rediscovered recently. The significance of LDPC codes lies in their capacity approaching performance even when decoded using low complexity sub-optimal decoding algorithms. Iterative decoders are one such class of decoders that work on a graphical representation of a code known as the Tanner graph. Their properties have been well understood in the asymptotic limit of the code length going to infinity. However, the behavior of various decoders for a given finite length code remains largely unknown.An understanding of the failures of the decoders is vital for the error floor analysis of a given code. Broadly speaking, error floor is the abrupt degradation in the frame error rate (FER) performance of a code in the high signal-to-noise ratio domain. Since the error floor phenomenon manifests in the regions not reachable by Monte-Carlo simulations, analytical methods are necessary for characterizing the decoding failures. In this work, we consider hard decision decoders for transmission over the binary symmetric channel (BSC).For column-weight-three codes, we provide tight upper and lower bounds on the guaranteed error correction capability of a code under the Gallager A algorithm by studying combinatorial objects known as trapping sets. For higher column weight codes, we establish bounds on the minimum number of variable nodes that achieve certain expansion as a function of the girth of the underlying Tanner graph, thereby obtaining lower bounds on the guaranteed error correction capability. We explore the relationship between a class of graphs known as cage graphs and trapping sets to establish upper bounds on the error correction capability.We also propose an algorithm to identify the most probable noise configurations, also known as instantons, that lead to error floor for linear programming (LP) decoding over the BSC. With the insight gained from the above analysis techniques, we propose novel code construction techniques that result in codes with superior error floor performance.
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.
In contrast to the capacity approaching performance of iteratively decoded low-density parity check (LDPC) codes, many practical finite-length LDPC codes exhibit performance degradation, manifested in a so-called error floor. Previous work has linked this phenomenon to the presence of certain combinatorial structures within the Tanner graph representation of the code, termed absorbing sets. Absorbing sets are stable under the bit-flipping operations and have been shown to act as fixed points (¿absorbers¿) for a wider class of iterative decoding algorithms. Codes often possess absorbing sets whose size is smaller than the minimum distance: the smallest absorbing sets are deemed most detrimental culprits behind the error floor. This paper focuses on the elementary combinatorial bounds of the smallest (candidate) absorbing sets. For certain classes of practical codes we demonstrate the tightness of these bounds and show how can the structure of the code and the structure of the absorbing sets be utilized to increase the size of the smallest absorbing sets without compromising other code properties such as the node degrees and the girth. As such, this work provides a step towards a better code design by taking into account the combinatorial nature of fixed points of iterative decoding algorithms.
The structure of certain subgraphs of the Tanner graph of an LDPC code, the trapping sets, has been identified as important for the error floor performance of iterative decoding algorithms. To investigate such sets requires the parity check matrix of the code to be generated with sufficient structure that allows useful information to be obtained while giving good codes. Structures that have been considered include combinatorial designs and classical finite geometries. More recently other finite geometric notions such as partial geometries and generalized d-gons have been considered with some success. This work considers aspects of this approach.