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

International Conference on Signal Processing and Communications (SPCOM)

Failure analysis of two-bit flipping decoding algorithms

Bane V. Vasic, Dung Viet Nguyen

Published Jul 1, 2014• 1 citation
Publisher

Abstract

We consider a class of bit flipping algorithms for low-density parity-check codes over the binary symmetric channel in which one additional bit at a variable and check nodes is employed. For these two-bit flipping algorithms, we give and illustrate through examples a recursive procedure for finding all uncorrectable error patters and corresponding induced subgraphs, referred as a trapping set profile. This procedure is used to select a small collection of good algorithms that in a decoding diversity approach, run in parallel or serial, outperform Gallager A/B, min-sum and sum product algorithm in the error floor region.

DOI
10.1109/spcom.2014.6983914

Related papers

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

Selecting two-bit bit flipping algorithms for collective error correction

Dung Viet Nguyen, Bane V. Vasic, Michael W. Marcellin

A class of two-bit bit flipping algorithms for decoding low-density parity-check codes over the binary symmetric channel was proposed in [1]. Initial results showed that decoders which employ a group of these algorithms operating in parallel can offer low error floor decoding for high-speed applications. As the number of two-bit bit flipping algorithms is large, designing such a decoder is not a trivial task. In this paper, we describe a procedure to select collections of algorithms that work well together. This procedure relies on a recursive process which enumerates error configurations that are uncorrectable by a given algorithm. The error configurations uncorrectable by a given algorithm form its trapping set profile. Based on their trapping set profiles, algorithms are selected so that in parallel, they can correct a fixed number of errors with high probability.

arXiv:1202.1348•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•1 citation

Two-bit bit flipping decoding of LDPC codes

Dung Viet Nguyen, Bane V. Vasic, Michael W. Marcellin

In this paper, we propose a new class of bit flipping algorithms for low-density parity-check (LDPC) codes over the binary symmetric channel (BSC). 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 increases the guaranteed error correction capability by a factor of at least 2. An additional bit can also be employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis of the proposed algorithms is described. These algorithms outperform the Gallager A/B algorithm and the min-sum algorithm at much lower complexity. Concatenation of two-bit bit flipping algorithms show a potential to approach the performance of belief propagation (BP) decoding in the error floor region, also at lower complexity.

arXiv:1103.0801•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•7 citations

Two-Side State-Aided Bit-Flipping Decoding of Generalized Low Density Parity Check Codes

Sherif Elsanadily, Ashraf M. Mahran, Osama M. Elghandour

A modified bit-flipping (BF) decoding algorithm is proposed for hard-decoding of generalized low- density parity-check codes over binary channels. This approach introduces an extra bit between the variable nodes and constraint nodes representing the decision reliability of each node. The local decoding failure is also analyzed to provide a reasonable treatment for the most of its causes. The approach is not in the direction of constructing codes with minimum trapping sets, but to reduce their effect in the decoder at a cost of little increase in the resources. The algorithm, which is called two-side state-aided BF, is shown by simulations to outperform previous BF algorithms in terms of error performance.

IEEE Communications Letters•Jun 27, 2017•10 citations

MULTI-BIT BIT-FLIPPING ALGORITHM FOR COLUMN WEIGHT-4 LDPC CODES

Xin Wei Xiao, Bane V. Vasic, Shu Lin

Low-density parity-check (LDPC) codes with column weight-4 are widely used in many commu-nication and storage systems. However, traditional hard decision decoding algorithms such as the bit-flipping (BF) algorithm suffer from error floor due to trapping sets in LDPC codes. In this paper, to lower error floor of the BF algorithm over the Binary Symmetric Channel (BSC), we design a set of decoding rules incorporated within the BF algorithm for column weight-4 LDPC codes. Given a column weight-4 LDPC code, the dominate error patterns of the BF algorithm are first specified, and according to the designed rules, additional bits at both variable nodes (VN) and check nodes (CN) provide more information for the BF algorithm to identify the dominate error patterns, so that the BF algorithm could deliberately flip some bits to break them. Simulation results show that the modified BF algorithm eliminates all 4-error patterns and lowers the Bit Error Rate (BER) for at least two orders of magnitude with a trivial increment of complexity.

•Jan 1, 2017•0 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 consider a class of bit flipping algorithms for low-density parity-check codes over the binary symmetric channel in which one additional bit at a variable and check nodes is employed. For these two-bit flipping algorithms, we give and illustrate through examples a recursive procedure for finding all uncorrectable error patters and corresponding induced subgraphs, referred as a trapping set profile. This procedure is used to select a small collection of good algorithms that in a decoding diversity approach, run in parallel or serial, outperform Gallager A/B, min-sum and sum product algorithm in the error floor region.
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.
A class of two-bit bit flipping algorithms for decoding low-density parity-check codes over the binary symmetric channel was proposed in [1]. Initial results showed that decoders which employ a group of these algorithms operating in parallel can offer low error floor decoding for high-speed applications. As the number of two-bit bit flipping algorithms is large, designing such a decoder is not a trivial task. In this paper, we describe a procedure to select collections of algorithms that work well together. This procedure relies on a recursive process which enumerates error configurations that are uncorrectable by a given algorithm. The error configurations uncorrectable by a given algorithm form its trapping set profile. Based on their trapping set profiles, algorithms are selected so that in parallel, they can correct a fixed number of errors with high probability.
In this paper, we propose a new class of bit flipping algorithms for low-density parity-check (LDPC) codes over the binary symmetric channel (BSC). 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 increases the guaranteed error correction capability by a factor of at least 2. An additional bit can also be employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis of the proposed algorithms is described. These algorithms outperform the Gallager A/B algorithm and the min-sum algorithm at much lower complexity. Concatenation of two-bit bit flipping algorithms show a potential to approach the performance of belief propagation (BP) decoding in the error floor region, also at lower complexity.
A modified bit-flipping (BF) decoding algorithm is proposed for hard-decoding of generalized low- density parity-check codes over binary channels. This approach introduces an extra bit between the variable nodes and constraint nodes representing the decision reliability of each node. The local decoding failure is also analyzed to provide a reasonable treatment for the most of its causes. The approach is not in the direction of constructing codes with minimum trapping sets, but to reduce their effect in the decoder at a cost of little increase in the resources. The algorithm, which is called two-side state-aided BF, is shown by simulations to outperform previous BF algorithms in terms of error performance.
Low-density parity-check (LDPC) codes with column weight-4 are widely used in many commu-nication and storage systems. However, traditional hard decision decoding algorithms such as the bit-flipping (BF) algorithm suffer from error floor due to trapping sets in LDPC codes. In this paper, to lower error floor of the BF algorithm over the Binary Symmetric Channel (BSC), we design a set of decoding rules incorporated within the BF algorithm for column weight-4 LDPC codes. Given a column weight-4 LDPC code, the dominate error patterns of the BF algorithm are first specified, and according to the designed rules, additional bits at both variable nodes (VN) and check nodes (CN) provide more information for the BF algorithm to identify the dominate error patterns, so that the BF algorithm could deliberately flip some bits to break them. Simulation results show that the modified BF algorithm eliminates all 4-error patterns and lowers the Bit Error Rate (BER) for at least two orders of magnitude with a trivial increment of complexity.
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.