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 Advanced Communication Technology

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

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

Published Feb 1, 2014• 1 citation
Publisher

Abstract

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.

DOI
10.1109/icact.2014.6779175

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

Investigation of simple threshold shifting for bit-flip decoding

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

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.

International Symposium on Wireless Personal Multimedia Communications (WPMC)•Jan 1, 2011•2 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

An Improved Iterative Bit-flipping Decoding Algorithm for Low-density Parity-check Codes

Meiling Zhang

An improved iterative bit-flipping(BF) algorithm adapted for decoding low-density parity-check(LDPC) codes is proposed to improve the performance of the hard-decision BF decoding algorithm.The new algorithm uses an alternating threshold pattern to determine the bits whether to be flipped or not,and the flipping error probability is effectively decreased.Simulation results show that compared with BF algorithm,the improved BF algorithm improves both the error-correction performance and the convergence speed while maintaining the low computational complexity.

Telecommunication Engineering•Jan 1, 2012•0 citations

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

Düşük yoğunluklu eşlik denetim kodları için kod çözme algoritmalarının karşılaştırılması.

Kolaylı, Mert

Low-density parity-check (LDPC) codes are a subclass of linear block codes. These codes have parity-check matrices in which the ratio of the non-zero elements to all elements is low. This property is exploited in defining low complexity decoding algorithms. Low-density parity-check codes have good distance properties and error correction capability near Shannon limits. In this thesis, the sum-product and the bit-flip decoding algorithms for low-density parity-check codes are implemented on Intel Pentium M 1,86 GHz processor using the software called MATLAB. Simulations for the two decoding algorithms are made over additive white gaussian noise (AWGN) channel changing the code parameters like the information rate, the blocklength of the code and the column weight of the parity-check matrix. Performance comparison of the two decoding algorithms are made according to these simulation results. As expected, the sum-product algorithm, which is based on soft-decision decoding, outperforms the bit-flip algorithm, which depends on hard-decision decoding. Our simulations show that the performance of LDPC codes improves with increasing blocklength and number of iterations for both decoding algorithms. Since the sum-product algorithm has lower error-floor characteristics, increasing the number of iterations is more effective for the sum-product decoder compared to the bit-flip decoder. By having better BER performance for lower information rates, the bit-flip algorithm performs according to the expectations; however, the performance of the sum-product decoder deteriorates for information rates below 0.5 instead of improving. By irregular construction of LDPC codes, a performance improvement is observed especially for low SNR values.

•Jan 1, 2006•0 citations
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.
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.
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.
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.
An improved iterative bit-flipping(BF) algorithm adapted for decoding low-density parity-check(LDPC) codes is proposed to improve the performance of the hard-decision BF decoding algorithm.The new algorithm uses an alternating threshold pattern to determine the bits whether to be flipped or not,and the flipping error probability is effectively decreased.Simulation results show that compared with BF algorithm,the improved BF algorithm improves both the error-correction performance and the convergence speed while maintaining the low computational complexity.
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.
Low-density parity-check (LDPC) codes are a subclass of linear block codes. These codes have parity-check matrices in which the ratio of the non-zero elements to all elements is low. This property is exploited in defining low complexity decoding algorithms. Low-density parity-check codes have good distance properties and error correction capability near Shannon limits. In this thesis, the sum-product and the bit-flip decoding algorithms for low-density parity-check codes are implemented on Intel Pentium M 1,86 GHz processor using the software called MATLAB. Simulations for the two decoding algorithms are made over additive white gaussian noise (AWGN) channel changing the code parameters like the information rate, the blocklength of the code and the column weight of the parity-check matrix. Performance comparison of the two decoding algorithms are made according to these simulation results. As expected, the sum-product algorithm, which is based on soft-decision decoding, outperforms the bit-flip algorithm, which depends on hard-decision decoding. Our simulations show that the performance of LDPC codes improves with increasing blocklength and number of iterations for both decoding algorithms. Since the sum-product algorithm has lower error-floor characteristics, increasing the number of iterations is more effective for the sum-product decoder compared to the bit-flip decoder. By having better BER performance for lower information rates, the bit-flip algorithm performs according to the expectations; however, the performance of the sum-product decoder deteriorates for information rates below 0.5 instead of improving. By irregular construction of LDPC codes, a performance improvement is observed especially for low SNR values.