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:1604.05256 · Transactions on Emerging Telecommunications Technologies

Check‐hybrid GLDPC codes: Systematic elimination of trapping sets and guaranteed error correction capability

Vida Ravanmehr, Mehrdad Khatami, David Declercq, Bane V. Vasic

Published Oct 12, 2016• 2 citations
arXivHTMLPDF

Abstract

ABSTRACT In this paper, we propose a new approach to construct a class of check‐hybrid generalized low‐density parity‐check (CH‐GLDPC) codes, which are free of small trapping sets. The approach is based on converting some selected check nodes involving a trapping set into super checks corresponding to a 2‐error‐correcting component code. Specifically, we follow 2 main purposes to construct the check‐hybrid codes; first, on the basis of the knowledge of trapping sets of an LDPC code, single parity checks are replaced by super checks to disable the trapping sets. We show that by converting specified single check nodes, denoted as critical checks, to super checks in a trapping set, the parallel bit flipping decoder corrects the errors on a trapping set. The second purpose is to minimize the rate loss through finding the minimum number of such critical checks. We also present an algorithm to find critical checks in a trapping set of a column‐weight 3 LDPC code of girth 8 and then provide upper bounds on the minimum number of such critical checks such that the decoder corrects all error patterns on elementary trapping sets. Guaranteed error correction capability of the CH‐GLDPC codes is also studied. We show that a CH‐GLDPC code in which each variable node is connected to 2 super checks corresponding to a 2‐error‐correcting component code corrects up to 5 errors. The results are also extended to column‐weight 4 LDPC codes of girth 6. Finally, we investigate eliminating of trapping sets of a column‐weight 3 LDPC code of girth 8 using the Gallager B decoding algorithm.

DOI
10.1002/ett.3122

Related papers

Check-hybrid GLDPC codes without small trapping sets

Vida Ravanmehr, David Declercq, Bane V. Vasic

In this paper, we propose a new approach to construct a class of check-hybrid generalized low-density parity-check (GLDPC) codes which are free of small trapping sets. The approach is based on converting some selected check nodes involving a trapping set to super checks corresponding to a shorter error-correcting component code. Specifically, we follow two main purposes to construct the check-hybrid codes: First, replacing single parity checks by super checks is done based on the knowledge of the trapping sets of the global LDPC code. We show that by converting some single checks to super checks in a trapping set, the decoder corrects the errors on a trapping set and hence eliminates the trapping set. Second, the rate-loss caused by replacing the super checks is reduced through finding the minimum number of such critical checks. We first present an algorithm to find possible critical checks in a trapping set. We then provide some upper bounds on the minimum number of such critical checks such that the decoder corrects all error patterns on certain trapping sets in the Tanner graph of the global LDPC code. We also provide a potential fixed set for a class of constructed check-hybrid codes.

Information Theory and Applications Workshop (ITA)•Feb 1, 2014•3 citations

Check-hybrid GLDPC codes: Systematic elimination of trapping sets by super checks

Vida Ravanmehr, David Declercq, Bane V. Vasic

In this paper, we propose a new approach to constructing a class of check-hybrid generalized low-density parity-check (GLDPC) codes which are free of small trapping sets. This approach is based on converting selected checks of an LDPC code involving a trapping set to super checks corresponding to a shorter error correcting component code. In particular, we follow two goals in constructing the check-hybrid GLDPC codes: First, the super checks are replaced based on the knowledge of trapping sets of the global LDPC code. We show that by converting only some single checks to super checks the decoder corrects the errors on a trapping set and hence eliminates the trapping set. Second, the number of super checks required for eliminating certain trapping sets is minimized to reduce the rate-loss. We first give an algorithm to find a set of critical checks in a trapping set of an LDPC code and then we provide some upper bounds on the minimum number of critical checks needed to eliminate certain trapping sets in the parity-check matrix of an LDPC code. A possible fixed set for a class of check-hybrid codes is also given.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•3 citations

On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes

S.K. Chilappagari, Dung Viet Nguyen, B. Vasic +1 more

The relation between the girth and the guaranteed error correction capability of¿-left-regular low-density parity-check (LDPC) codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least3 ¿/4is found based on the Moore bound. This bound, combined with the well known expander based arguments, leads to a lower bound on the guaranteed error correction capability. The decoding failures of the bit flipping algorithms are characterized using the notions of trapping sets and fixed sets. The relation between fixed sets and a class of graphs known as cage graphs is studied. Upper bounds on the guaranteed error correction capability are then established based on the order of cage graphs. The results are extended to left-regular and right-uniform generalized LDPC codes. It is shown that this class of generalized LDPC codes can correct a linear number of worst case errors (in the code length) under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. A lower bound on the size of variable node sets which have the required expansion is established.

arXiv:0805.2427•IEEE Transactions on Information Theory•Mar 24, 2010•34 citations

On Trapping Sets and Guaranteed Error Correction Capability of LDPC Codes and GLDPC Codes

Shashi Kiran Chilappagari, Dung Viet Nguyen, Bane Vasic +1 more

The relation between the girth and the guaranteed error correction capability of γ-left regular LDPC codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least 3γ/4 is found based on the Moore bound. An upper bound on the guaranteed error correction capability is established by studying the sizes of smallest possible trapping sets. The results are extended to generalized LDPC codes. It is shown that generalized LDPC codes can correct a linear fraction of errors under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. It is also shown that the bound cannot be improved when γ is even by studying a class of trapping sets. A lower bound on the size of variable node sets which have the required expansion is established.

•Jan 1, 2008•36 citations

On a class of column‐weight 3 decomposable LDPC codes with the analysis of elementary trapping sets

Ghaffar Raeisi, Mohammad Gholami

Abstract A column‐weight LDPC code with the parity‐check matrix is called decomposable if there exists a permutation on the rows of , such that can be decomposed into column‐weight one matrix. In this paper, some variations of edge coloring of graphs are used to construct some column‐weight three decomposable LDPC codes with girths at least six and eight. Applying the presented method on several known classes of bipartite graphs, some classes of column‐weight three decomposable LDPC codes are derived having flexibility in length and rate. Interestingly, the constructed parity‐check matrices based on the proper edge coloring of graphs can be considered as the base matrix of some high rate column‐weight three quasi‐cyclic (QC) LDPC codes with maximum‐achievable girth 20. The paper also leads to a simple characterization of elementary trapping sets of the decomposable codes based on the chromatic index of the corresponding normal graphs. This characterization corresponds to a simple search algorithm finds all possible existing elementary trapping sets in a girth‐6 or girth‐8 column‐weight 3 LDPC code which are layered super set of a short cycle in the Tanner graph of the code. Simulation results indicate that the QC‐LDPC codes with large girths lifted from the constructed base matrices have good performances over AWGN channel.

IET Communications•Apr 22, 2024•0 citations

Two-Bit Bit Flipping Algorithms for LDPC Codes and Collective Error Correction

Dung Viet Nguyen, Bane V. Vasic

A new class of bit flipping algorithms for low-density parity-check codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.

IEEE Transactions on Communications•Feb 28, 2014•25 citations
ABSTRACT In this paper, we propose a new approach to construct a class of check‐hybrid generalized low‐density parity‐check (CH‐GLDPC) codes, which are free of small trapping sets. The approach is based on converting some selected check nodes involving a trapping set into super checks corresponding to a 2‐error‐correcting component code. Specifically, we follow 2 main purposes to construct the check‐hybrid codes; first, on the basis of the knowledge of trapping sets of an LDPC code, single parity checks are replaced by super checks to disable the trapping sets. We show that by converting specified single check nodes, denoted as critical checks, to super checks in a trapping set, the parallel bit flipping decoder corrects the errors on a trapping set. The second purpose is to minimize the rate loss through finding the minimum number of such critical checks. We also present an algorithm to find critical checks in a trapping set of a column‐weight 3 LDPC code of girth 8 and then provide upper bounds on the minimum number of such critical checks such that the decoder corrects all error patterns on elementary trapping sets. Guaranteed error correction capability of the CH‐GLDPC codes is also studied. We show that a CH‐GLDPC code in which each variable node is connected to 2 super checks corresponding to a 2‐error‐correcting component code corrects up to 5 errors. The results are also extended to column‐weight 4 LDPC codes of girth 6. Finally, we investigate eliminating of trapping sets of a column‐weight 3 LDPC code of girth 8 using the Gallager B decoding algorithm.
In this paper, we propose a new approach to construct a class of check-hybrid generalized low-density parity-check (GLDPC) codes which are free of small trapping sets. The approach is based on converting some selected check nodes involving a trapping set to super checks corresponding to a shorter error-correcting component code. Specifically, we follow two main purposes to construct the check-hybrid codes: First, replacing single parity checks by super checks is done based on the knowledge of the trapping sets of the global LDPC code. We show that by converting some single checks to super checks in a trapping set, the decoder corrects the errors on a trapping set and hence eliminates the trapping set. Second, the rate-loss caused by replacing the super checks is reduced through finding the minimum number of such critical checks. We first present an algorithm to find possible critical checks in a trapping set. We then provide some upper bounds on the minimum number of such critical checks such that the decoder corrects all error patterns on certain trapping sets in the Tanner graph of the global LDPC code. We also provide a potential fixed set for a class of constructed check-hybrid codes.
In this paper, we propose a new approach to constructing a class of check-hybrid generalized low-density parity-check (GLDPC) codes which are free of small trapping sets. This approach is based on converting selected checks of an LDPC code involving a trapping set to super checks corresponding to a shorter error correcting component code. In particular, we follow two goals in constructing the check-hybrid GLDPC codes: First, the super checks are replaced based on the knowledge of trapping sets of the global LDPC code. We show that by converting only some single checks to super checks the decoder corrects the errors on a trapping set and hence eliminates the trapping set. Second, the number of super checks required for eliminating certain trapping sets is minimized to reduce the rate-loss. We first give an algorithm to find a set of critical checks in a trapping set of an LDPC code and then we provide some upper bounds on the minimum number of critical checks needed to eliminate certain trapping sets in the parity-check matrix of an LDPC code. A possible fixed set for a class of check-hybrid codes is also given.
The relation between the girth and the guaranteed error correction capability of¿-left-regular low-density parity-check (LDPC) codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least3 ¿/4is found based on the Moore bound. This bound, combined with the well known expander based arguments, leads to a lower bound on the guaranteed error correction capability. The decoding failures of the bit flipping algorithms are characterized using the notions of trapping sets and fixed sets. The relation between fixed sets and a class of graphs known as cage graphs is studied. Upper bounds on the guaranteed error correction capability are then established based on the order of cage graphs. The results are extended to left-regular and right-uniform generalized LDPC codes. It is shown that this class of generalized LDPC codes can correct a linear number of worst case errors (in the code length) under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. A lower bound on the size of variable node sets which have the required expansion is established.
The relation between the girth and the guaranteed error correction capability of γ-left regular LDPC codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least 3γ/4 is found based on the Moore bound. An upper bound on the guaranteed error correction capability is established by studying the sizes of smallest possible trapping sets. The results are extended to generalized LDPC codes. It is shown that generalized LDPC codes can correct a linear fraction of errors under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. It is also shown that the bound cannot be improved when γ is even by studying a class of trapping sets. A lower bound on the size of variable node sets which have the required expansion is established.
Abstract A column‐weight LDPC code with the parity‐check matrix is called decomposable if there exists a permutation on the rows of , such that can be decomposed into column‐weight one matrix. In this paper, some variations of edge coloring of graphs are used to construct some column‐weight three decomposable LDPC codes with girths at least six and eight. Applying the presented method on several known classes of bipartite graphs, some classes of column‐weight three decomposable LDPC codes are derived having flexibility in length and rate. Interestingly, the constructed parity‐check matrices based on the proper edge coloring of graphs can be considered as the base matrix of some high rate column‐weight three quasi‐cyclic (QC) LDPC codes with maximum‐achievable girth 20. The paper also leads to a simple characterization of elementary trapping sets of the decomposable codes based on the chromatic index of the corresponding normal graphs. This characterization corresponds to a simple search algorithm finds all possible existing elementary trapping sets in a girth‐6 or girth‐8 column‐weight 3 LDPC code which are layered super set of a short cycle in the Tanner graph of the code. Simulation results indicate that the QC‐LDPC codes with large girths lifted from the constructed base matrices have good performances over AWGN channel.
A new class of bit flipping algorithms for low-density parity-check codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.