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

Allerton Conference on Communication, Control, and Computing

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

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

Published Sep 1, 2010• 2 citations
Publisher

Abstract

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.

DOI
10.1109/allerton.2010.5706904

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

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

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

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

Improving the Error Floor Performance of LDCP Codes with Better Codes and Better Decoders

Dung Viet Nguyen

Error correcting codes are used in virtually all communication systems to ensure reliable transmission of information. In 1948, Shannon established an upper-bound on the maximum rate at which information can be transmitted reliably over a noisy channel. Reliably transmitting information with a rate close to this theoretical limit, known as the channel capacity, has been the goal of channel coding scientists for the last five decades. The rediscovery of low-density parity-check (LDPC) codes in the 1990s added much-renewed excitement in the coding community. LDPC codes are interesting because they can approach channel capacity under sub-optimum decoding algorithms whose complexity is linear in the code length. Unsurprisingly, LDPC codes quickly attained their popularity in practical applications such as magnetic storage, wireless and optical communications. One, if not the most, important and challenging problem in LDPC code research is the study and analysis of the error floor phenomenon. This phenomenon is described as an abrupt degradation in the frame error rate performance of LDPC codes in the high signal-to-noise ratio region. Error floor is harmful because its presence prevents the LDPC decoder from reaching very low probability of decoding failure, an important requirement for many applications. Not long after the rediscovery of LDPC codes, scientists established that error floor is caused by certain harmful structures, most commonly known as trapping sets, in the Tanner representation of a code. Since then, the study of error floor mostly consists of three major problems: 1) estimating error floor; 2) constructing LDPC codes with low error floor and 3) designing decoders that are less susceptible to error floor. Although some parts of this dissertation can be used as important elements in error floor estimation, our main contributions are a novel method for constructing LDPC codes with low error floor and a novel class of low complexity decoding algorithms that can collectively alleviate error floor. These contributions are summarized as follows. A method to construct LDPC codes with low error floors on the binary symmetric channel 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 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. A new class of bit flipping algorithms for LDPC 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.

•Jan 1, 2012•1 citation
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.
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.
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.
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 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.
Error correcting codes are used in virtually all communication systems to ensure reliable transmission of information. In 1948, Shannon established an upper-bound on the maximum rate at which information can be transmitted reliably over a noisy channel. Reliably transmitting information with a rate close to this theoretical limit, known as the channel capacity, has been the goal of channel coding scientists for the last five decades. The rediscovery of low-density parity-check (LDPC) codes in the 1990s added much-renewed excitement in the coding community. LDPC codes are interesting because they can approach channel capacity under sub-optimum decoding algorithms whose complexity is linear in the code length. Unsurprisingly, LDPC codes quickly attained their popularity in practical applications such as magnetic storage, wireless and optical communications. One, if not the most, important and challenging problem in LDPC code research is the study and analysis of the error floor phenomenon. This phenomenon is described as an abrupt degradation in the frame error rate performance of LDPC codes in the high signal-to-noise ratio region. Error floor is harmful because its presence prevents the LDPC decoder from reaching very low probability of decoding failure, an important requirement for many applications. Not long after the rediscovery of LDPC codes, scientists established that error floor is caused by certain harmful structures, most commonly known as trapping sets, in the Tanner representation of a code. Since then, the study of error floor mostly consists of three major problems: 1) estimating error floor; 2) constructing LDPC codes with low error floor and 3) designing decoders that are less susceptible to error floor. Although some parts of this dissertation can be used as important elements in error floor estimation, our main contributions are a novel method for constructing LDPC codes with low error floor and a novel class of low complexity decoding algorithms that can collectively alleviate error floor. These contributions are summarized as follows. A method to construct LDPC codes with low error floors on the binary symmetric channel 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 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. A new class of bit flipping algorithms for LDPC 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.