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 Symposium on Wireless Personal Multimedia Communications (WPMC)

Investigation of simple threshold shifting for bit-flip decoding

Julian L. Webber, Toshihiko Nishimura, Takeo Ohgane, Yasutaka Ogawa

Published Jan 1, 2011• 2 citations
OpenAlex

Abstract

Remarkably low error rates can be obtained using low-density parity-check (LDPC) codes and their use is now an increasingly common option in communications standards. The classic decoders based on belief propagation offer very high performance but have high implementation complexity. Therefore over the last decade simpler architectures such as the bit flipping class of algorithms have been researched. Recently, a number of adaptive threshold algorithms have been proposed in which at each iteration a bit is either flipped if it is below an inversion threshold, or the threshold is lowered. By choosing certain values of the scaling factor, the scaling can be efficiently implemented using a small number of shift and add operations. This work looks at how the scaling factor affects the convergence and error performance, and investigates an algorithm that switches between two scaling values based on the syndrome sum. The dual scaling method maintained the error performance compared to that with a single scaling but the iteration count was significantly reduced.

Related papers

A study on adaptive thresholds for reduced complexity bit-flip decoding

Julian L. Webber, Toshihiko Nishimura, Takeo Ohgane +1 more

Low-density parity-check (LDPC) codes are capacity approaching codes that have rapidly been adopted in modern systems such as the IEEE 802.11n and long term evolution advanced (LTE-A) communications standards. The decoders based on the iterative belief propagation offer exceedingly high performance but unfortunately have high computational complexity. Therefore significant research has focused on lower complexity architectures based on the family of so-called bit-flipping algorithms. In the basic bit-flipping algorithm the number of failed parity checks for each bit is calculated and the sign of the bit with the maximum failed checks is inverted. Inverting bits above a certain threshold removes the complexity of calculating a maximum function and adaptive thresholds on each bit further simplifies the design. The choice of threshold updates directly affects the error and convergence performances. Here we describe a simple architecture that has two decoders with different scaling factors and select the branch with the lowest syndrome sum. It is shown that the addition of a random uniform perturbation to the threshold can reduce the average iteration count further by providing an escape from stuck decoding states.

International Conference on Advanced Communication Technology•Jan 1, 2012•5 citations

Performance investigation of reduced complexity bit-flipping using variable thresholds and noise perturbation

Julian L. Webber, Toshihiko Nishimura, Takeo Ohgane +1 more

The near Shannon capacity approaching low-density parity-check (LDPC) linear block codes are now in widespread use in modern systems including the long term evolution advanced (LTE-A) cellular, 802.11η Wi-Fi and DVB-S2 satellite communications standards. The decoders based on the iterative belief propagation algorithm provide near optimum performance but also have very high computational complexity. Therefore significant research has recently focused on reduced complexity architectures based on the group of so-called bit-flipping algorithms. In the basic bit-flipping algorithm the number of failed parity checks for each bit is computed and the bit with the maximum failed parity checks is inverted. Inverting bits above a certain threshold removes the complexity involved with a maximum-search and, adaptive thresholds on each bit can further reduce the computation overhead. The criterion for the threshold update affects the error and convergence performances. Here, we describe a low-complexity architecture that has two (or more) decoder branches each with a different threshold scaling factor and select the threshold and bits at each iteration from the branch with the lowest syndrome sum. We then investigate the effect of adding a random Uniform or Gaussian noise perturbation to the threshold in order to reduce the average iteration count further in order to provide the opportunity to escape from stuck decoding states.

International Conference on Advanced Communication Technology•Feb 1, 2014•1 citation

Modified Bit-Flipping Decoding of Low-Density Parity-Check Codes

Yuan Hua Liu, Mei Ling Zhang

A novel bit-flipping (BF) algorithm with low complexity for high-throughput decoding of low-density parity-check (LDPC) codes is presented. At each iteration, a novel threshold pattern is used to determine the code bits whether to be flipped or not, and the flipping error probability is effectively decreased. Compared with the weighted BF algorithm and its modifications, the modified BF algorithm has significantly lower complexity and decoding time. Through simulations the proposed BF algorithm is shown to achieve excellent performance and fast convergence speed while maintaining significantly low complexity thus facilitating high-throughput decoding.

Advanced materials research•Jun 1, 2013•0 citations

Adaptive Threshold Technique for Bit-Flipping Decoding of Low-Density Parity-Check Codes

Junho Cho, Wonyong Sung

The bit-flipping (BF) algorithm for decoding of low-density parity-check (LDPC) codes requires less complex hardware than other decoding algorithms, but its error correcting performance needs to be improved. In this letter, a threshold adaptation scheme is applied to BF algorithm based decoding of LDPC codes. Our experiments show that the optimal threshold value for BF depends on the error conditions, and threshold adjustment during decoding helps to prevent meaningless no-flipping iterations. Based on these statistical observations, the adaptive threshold technique is proposed to pursue both the maximum error correcting capability and the fastest decoding convergence.

IEEE Communications Letters•Aug 5, 2010•32 citations

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

The Syndrome Bit Flipping Algorithm for LDPC Codes

Emmanuel Boutillon, Chris Winstead, Fakhreddine Ghaffari

Performance of LDPC decoders at high SNR is dominated by trapping sets that induce an error floor in the performance curve. We propose a new algorithm that resolves trapping sets and lowers the error floor. The new algorithm, called Syndrome Bit Flipping (SBF), computes the sum of adjacent parity violations at each symbol node. Bits are flipped by comparing the syndrome sum against a time-varying threshold called the decoding key. SBF is compared to other bit-flipping decoders on the Binary Symmetric Channel (BSC), and is demonstrated as a post-processing step for a Noisy Gradient Descent Bit-Flipping (NGDBF) hardware decoder. We demonstrate the post-processing method for an LDPC code defined in the 802.3an standard, and find that the frame error rate is improved by at least two orders of magnitude, even as the required iterations are reduced by 33%.

IEEE Communications Letters•May 1, 2023•10 citations
Remarkably low error rates can be obtained using low-density parity-check (LDPC) codes and their use is now an increasingly common option in communications standards. The classic decoders based on belief propagation offer very high performance but have high implementation complexity. Therefore over the last decade simpler architectures such as the bit flipping class of algorithms have been researched. Recently, a number of adaptive threshold algorithms have been proposed in which at each iteration a bit is either flipped if it is below an inversion threshold, or the threshold is lowered. By choosing certain values of the scaling factor, the scaling can be efficiently implemented using a small number of shift and add operations. This work looks at how the scaling factor affects the convergence and error performance, and investigates an algorithm that switches between two scaling values based on the syndrome sum. The dual scaling method maintained the error performance compared to that with a single scaling but the iteration count was significantly reduced.
Low-density parity-check (LDPC) codes are capacity approaching codes that have rapidly been adopted in modern systems such as the IEEE 802.11n and long term evolution advanced (LTE-A) communications standards. The decoders based on the iterative belief propagation offer exceedingly high performance but unfortunately have high computational complexity. Therefore significant research has focused on lower complexity architectures based on the family of so-called bit-flipping algorithms. In the basic bit-flipping algorithm the number of failed parity checks for each bit is calculated and the sign of the bit with the maximum failed checks is inverted. Inverting bits above a certain threshold removes the complexity of calculating a maximum function and adaptive thresholds on each bit further simplifies the design. The choice of threshold updates directly affects the error and convergence performances. Here we describe a simple architecture that has two decoders with different scaling factors and select the branch with the lowest syndrome sum. It is shown that the addition of a random uniform perturbation to the threshold can reduce the average iteration count further by providing an escape from stuck decoding states.
The near Shannon capacity approaching low-density parity-check (LDPC) linear block codes are now in widespread use in modern systems including the long term evolution advanced (LTE-A) cellular, 802.11η Wi-Fi and DVB-S2 satellite communications standards. The decoders based on the iterative belief propagation algorithm provide near optimum performance but also have very high computational complexity. Therefore significant research has recently focused on reduced complexity architectures based on the group of so-called bit-flipping algorithms. In the basic bit-flipping algorithm the number of failed parity checks for each bit is computed and the bit with the maximum failed parity checks is inverted. Inverting bits above a certain threshold removes the complexity involved with a maximum-search and, adaptive thresholds on each bit can further reduce the computation overhead. The criterion for the threshold update affects the error and convergence performances. Here, we describe a low-complexity architecture that has two (or more) decoder branches each with a different threshold scaling factor and select the threshold and bits at each iteration from the branch with the lowest syndrome sum. We then investigate the effect of adding a random Uniform or Gaussian noise perturbation to the threshold in order to reduce the average iteration count further in order to provide the opportunity to escape from stuck decoding states.
A novel bit-flipping (BF) algorithm with low complexity for high-throughput decoding of low-density parity-check (LDPC) codes is presented. At each iteration, a novel threshold pattern is used to determine the code bits whether to be flipped or not, and the flipping error probability is effectively decreased. Compared with the weighted BF algorithm and its modifications, the modified BF algorithm has significantly lower complexity and decoding time. Through simulations the proposed BF algorithm is shown to achieve excellent performance and fast convergence speed while maintaining significantly low complexity thus facilitating high-throughput decoding.
The bit-flipping (BF) algorithm for decoding of low-density parity-check (LDPC) codes requires less complex hardware than other decoding algorithms, but its error correcting performance needs to be improved. In this letter, a threshold adaptation scheme is applied to BF algorithm based decoding of LDPC codes. Our experiments show that the optimal threshold value for BF depends on the error conditions, and threshold adjustment during decoding helps to prevent meaningless no-flipping iterations. Based on these statistical observations, the adaptive threshold technique is proposed to pursue both the maximum error correcting capability and the fastest decoding convergence.
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.
Performance of LDPC decoders at high SNR is dominated by trapping sets that induce an error floor in the performance curve. We propose a new algorithm that resolves trapping sets and lowers the error floor. The new algorithm, called Syndrome Bit Flipping (SBF), computes the sum of adjacent parity violations at each symbol node. Bits are flipped by comparing the syndrome sum against a time-varying threshold called the decoding key. SBF is compared to other bit-flipping decoders on the Binary Symmetric Channel (BSC), and is demonstrated as a post-processing step for a Noisy Gradient Descent Bit-Flipping (NGDBF) hardware decoder. We demonstrate the post-processing method for an LDPC code defined in the 802.3an standard, and find that the frame error rate is improved by at least two orders of magnitude, even as the required iterations are reduced by 33%.