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

IEEE Transactions on Information Theory

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

Dung Viet Nguyen, Shashi Kiran Chilappagari, Michael W. Marcellin, Bane V. Vasic

Published Mar 26, 2012• 117 citations
Publisher

Abstract

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.

DOI
10.1109/tit.2011.2173733

Related papers

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

Construction of Optimal Puncturing of Low-Density Parity-Check Codes

S. Suresh Kumar, Manju Rajaram

Low-density parity-check with Length-compatible and low error floors (LDPC-LCLEF) on the binary symmetric channel is presented in this paper. These codes can support a wide range of lengths for a given rate and also the Tanner graphs are free of small trapping sets. This can be obtained by applying the schemes of shortening and puncturing to good LDPC codes and the trapping sets are selected using the trapping set ontology based on their relative harmfulness for the given decoding algorithm. The conventional approach does not guarantee to have a good performance as the degree distributions may be wildly varied. In this paper, a modified algorithm is presented to generate LDPC codes of a given rate with almost their degree distributions are same as the mother code degree distribution. Also the relative harmfulness for different trapping sets are evaluated and decoding failures of one trapping set in presence or absence of other trapping sets are analyzed. To facilitate this discussion, a new description of structured LDPC codes with arrays of permutation matrices as parity-check matrices is given. Numerical results show that the LDPC code constructed by this approach performed much better than the conventional approach.

CiiT international journal of fuzzy systems•Jan 1, 2014•0 citations

Structured LDPC codes from permutation matrices free of small trapping sets

Dung Viet Nguyen, Bane V. Vasic, Michael W. Marcellin +1 more

This paper introduces a class of structured low-density parity-check (LDPC) codes whose parity check matrices are arrays of permutation matrices. The permutation matrices are obtained from Latin squares and form a finite field under some matrix operations. They are chosen so that the Tanner graphs do not contain subgraphs harmful to iterative decoding algorithms. The construction of column-weight-three codes is presented. Although the codes are optimized for the Gallager A/B algorithm over the binary symmetric channel (BSC), their error performance is very good on the additive white Gaussian noise channel (AWGNC) as well.

arXiv:1004.1198•IEEE Information Theory Workshop (ITW)•Aug 1, 2010•25 citations

Short column-weight-three LDPC codes without small trapping sets

Dung Viet Nguyen, Martin P. Leslie, Bane V. Vasic

We introduce a method to construct regular column-weight-three low-density parity-check (LDPC) codes with low error floors for the sum product algorithm (SPA) on the binary symmetric channel (BSC). The Tanner graphs of these codes are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder and are selected based on their relative harmfulness for the SPA. We evaluate the relative harmfulness of different trapping sets for the SPA by using the topological relations among them and by analyzing decoding failures on one trapping set in the presence or absence of other trapping sets. To the best of our knowledge, these codes outperform the best known short length, regular column-weight-three LDPC codes.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2010•2 citations

On the Construction of LDPC Codes Free of Small Trapping Sets by Controlling Cycles

Xiongfei Tao, Yufei Li, Yonghe Liu +1 more

Low-density parity-check (LDPC) codes exhibit excellent error correcting capability. However, small trapping sets in the Tanner graph are harmful to the iterative decoding algorithm. In this letter, we present a method of constructing (3, n) girth-eight quasi-cyclic LDPC codes with low error floor by removing the small trapping sets from the Tanner graph. To address this issue, we analyze the relationship between eight-cycles and small trapping sets of Tanner graphs based on fully connected base graphs without parallel edges. We find that if some eight-cycles are not found in the Tanner graphs, any elementary trapping set in the range of a ≤ 8 and b ≤ 3 is removed naturally. We also derive a lower bound on the permutation size for the construction of such codes. The experimental simulation shows a favorable error rate performance with lower error floor over additive white Gaussian noise channels.

IEEE Communications Letters•Mar 8, 2017•30 citations

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
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.
Low-density parity-check with Length-compatible and low error floors (LDPC-LCLEF) on the binary symmetric channel is presented in this paper. These codes can support a wide range of lengths for a given rate and also the Tanner graphs are free of small trapping sets. This can be obtained by applying the schemes of shortening and puncturing to good LDPC codes and the trapping sets are selected using the trapping set ontology based on their relative harmfulness for the given decoding algorithm. The conventional approach does not guarantee to have a good performance as the degree distributions may be wildly varied. In this paper, a modified algorithm is presented to generate LDPC codes of a given rate with almost their degree distributions are same as the mother code degree distribution. Also the relative harmfulness for different trapping sets are evaluated and decoding failures of one trapping set in presence or absence of other trapping sets are analyzed. To facilitate this discussion, a new description of structured LDPC codes with arrays of permutation matrices as parity-check matrices is given. Numerical results show that the LDPC code constructed by this approach performed much better than the conventional approach.
This paper introduces a class of structured low-density parity-check (LDPC) codes whose parity check matrices are arrays of permutation matrices. The permutation matrices are obtained from Latin squares and form a finite field under some matrix operations. They are chosen so that the Tanner graphs do not contain subgraphs harmful to iterative decoding algorithms. The construction of column-weight-three codes is presented. Although the codes are optimized for the Gallager A/B algorithm over the binary symmetric channel (BSC), their error performance is very good on the additive white Gaussian noise channel (AWGNC) as well.
We introduce a method to construct regular column-weight-three low-density parity-check (LDPC) codes with low error floors for the sum product algorithm (SPA) on the binary symmetric channel (BSC). The Tanner graphs of these codes are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder and are selected based on their relative harmfulness for the SPA. We evaluate the relative harmfulness of different trapping sets for the SPA by using the topological relations among them and by analyzing decoding failures on one trapping set in the presence or absence of other trapping sets. To the best of our knowledge, these codes outperform the best known short length, regular column-weight-three LDPC codes.
Low-density parity-check (LDPC) codes exhibit excellent error correcting capability. However, small trapping sets in the Tanner graph are harmful to the iterative decoding algorithm. In this letter, we present a method of constructing (3, n) girth-eight quasi-cyclic LDPC codes with low error floor by removing the small trapping sets from the Tanner graph. To address this issue, we analyze the relationship between eight-cycles and small trapping sets of Tanner graphs based on fully connected base graphs without parallel edges. We find that if some eight-cycles are not found in the Tanner graphs, any elementary trapping set in the range of a ≤ 8 and b ≤ 3 is removed naturally. We also derive a lower bound on the permutation size for the construction of such codes. The experimental simulation shows a favorable error rate performance with lower error floor over additive white Gaussian noise channels.
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.