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)

Check-hybrid GLDPC codes without small trapping sets

Vida Ravanmehr, David Declercq, Bane V. Vasic

Published Feb 1, 2014• 3 citations
Publisher

Abstract

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.

DOI
10.1109/ita.2014.6804215

Related papers

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

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

Vida Ravanmehr, Mehrdad Khatami, David Declercq +1 more

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.

arXiv:1604.05256•Transactions on Emerging Telecommunications Technologies•Oct 12, 2016•2 citations

On the Construction of Structured LDPC Codes Free of Small Trapping Sets

Dung Viet Nguyen, Shashi Kiran Chilappagari, Michael W. Marcellin +1 more

We present a method to construct low-density parity-check (LDPC) codes with low error floors on the binary symmetric channel. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the trapping set ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum–product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four cycles.

IEEE Transactions on Information Theory•Mar 26, 2012•117 citations

LDPC Codes from Latin Squares Free of Small Trapping Sets

Dung Viet Nguyen, Shashi Kiran Chilappagari, Michael W. Marcellin +1 more

This paper is concerned with the construction of low-density parity-check (LDPC) codes with low error floors. Two main contributions are made. First, a new class of structured LDPC codes is introduced. The parity check matrices of these codes are arrays of permutation matrices which are obtained from Latin squares and form a finite field under some matrix operations. Second, a method to construct LDPC codes with low error floors on the binary symmetric channel (BSC) is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum product algorithm (SPA) by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets.

arXiv:1008.4177•Aug 24, 2010•4 citations

Generalized LDPC code with single-parity-check product constraints at super check nodes

Y. Min, Francis C. M. Lau, Chi Kong Tse

Due to the more complex constraints, generalized low-density parity-check (GLDPC) codes can achieve better error performance but require much higher decoding complexities compared with the standard LDPC codes. In this paper, single-parity-check product-codes (SPC-PCs) are considered as the constituent codes in the super check nodes of a GLDPC code. Moreover, turbo iterations are used in decoding the SPC-PCs. The error performance and the decoder complexity of the proposed GLDPC code are compared with other LDPC code and GLDPC code.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 1, 2012•7 citations

Generalized Belief Propagation to break trapping sets in LDPC codes

Jean-Christophe Sibel, Sylvain Reynal, David Declercq

In this paper, we focus on the Generalized Belief Propagation (GBP) algorithm to solve trapping sets in Low-Density Parity-Check (LDPC) codes. Trapping sets are topological structures in Tanner graphs of LDPC codes that are not correctly decoded by Belief Propagation (BP), leading to exhibit an error-floor in the Bit-Error Rate (BER). Stemming from statistical physics of spin glasses, GBP consists in passing messages between clusters of Tanner graph nodes in another graph called the region-graph. Here, we introduce a specific clustering of nodes, based on a novel local loopfree principle, that breaks trapping sets such that the resulting region-graph is locally loopfree. We then construct a hybrid decoder made of BP and GBP that proves to be a powerful decoder as it clearly improves the BER and defeats the error-floor.

Australian Communications Theory Workshop•Feb 1, 2014•1 citation
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.
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.
We present a method to construct low-density parity-check (LDPC) codes with low error floors on the binary symmetric channel. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the trapping set ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum–product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four cycles.
This paper is concerned with the construction of low-density parity-check (LDPC) codes with low error floors. Two main contributions are made. First, a new class of structured LDPC codes is introduced. The parity check matrices of these codes are arrays of permutation matrices which are obtained from Latin squares and form a finite field under some matrix operations. Second, a method to construct LDPC codes with low error floors on the binary symmetric channel (BSC) is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum product algorithm (SPA) by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets.
Due to the more complex constraints, generalized low-density parity-check (GLDPC) codes can achieve better error performance but require much higher decoding complexities compared with the standard LDPC codes. In this paper, single-parity-check product-codes (SPC-PCs) are considered as the constituent codes in the super check nodes of a GLDPC code. Moreover, turbo iterations are used in decoding the SPC-PCs. The error performance and the decoder complexity of the proposed GLDPC code are compared with other LDPC code and GLDPC code.
In this paper, we focus on the Generalized Belief Propagation (GBP) algorithm to solve trapping sets in Low-Density Parity-Check (LDPC) codes. Trapping sets are topological structures in Tanner graphs of LDPC codes that are not correctly decoded by Belief Propagation (BP), leading to exhibit an error-floor in the Bit-Error Rate (BER). Stemming from statistical physics of spin glasses, GBP consists in passing messages between clusters of Tanner graph nodes in another graph called the region-graph. Here, we introduce a specific clustering of nodes, based on a novel local loopfree principle, that breaks trapping sets such that the resulting region-graph is locally loopfree. We then construct a hybrid decoder made of BP and GBP that proves to be a powerful decoder as it clearly improves the BER and defeats the error-floor.