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

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

Xin Wei Xiao, Bane V. Vasic, Shu Lin

Published Jan 1, 2017• 0 citations
OpenAlex

Abstract

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.

Related papers

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

Weighted candidate bit based bit-flipping decoding algorithms for LDPC codes

Zhu Qing, Lenan Wu

In order to improve the bit-flipping (BF) decoding algorithms, a weighted hard-decision based BF decoding algorithm for low-density parity-check (LDPC) codes is presented, in which the weights of variable-nodes are employed. A new metric is defined for the weight of candidate bits not only in unsatisfied parity check equations but also in satisfied ones. The connection between min-sum decoding algorithm and the proposed algorithm is presented. Simulation results show that the new decoding algorithm can provide better FER performance and faster convergence speed than the original candidate bit based bit-flipping (CBBF) algorithm.

International Conference on Consumer Electronics, Communications and Networks (CECNet)•Nov 1, 2013•4 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

Improved Bit-Flipping Method for Decoding Structured Low-Density Parity-Check Codes

Meiling Zhang

An improved bit-flipping(BF) algorithm with low complexity for decoding structured low-density parity-check codes(LDPC) is proposed to improve the performance of the hard-decision BF algorithm.The hard-decision bits are divided into two groups based on the magnitudes of the received symbols,and at each iteration,the proposed algorithm can flip more than one bit with using two thresholds,and the flipping error probability is effectively decreased.The improved BF algorithm requires some real number comparisons before iterations and requires only logical operations during the iterations.Compared with the weighted bit-flipping algorithm and its modifications,the new method is with significantly lower complexity.Simulations show that the proposed algorithm is provided with very fast convergence speed and excellent performance with significantly low complexity.

Beijing Youdian Xueyuan xuebao•Jan 1, 2012•0 citations

An efficient bit-flipping decoding algorithm for LDPC codes

Tso-Cho Chen

In this paper, a new method for improving hard-decision bit-flipping (BF) decoding is proposed for low-density parity-check codes. The flipping criterion is derived theoretically from the soft-decision belief-propagation decoding algorithm. The proposed BF decoding algorithm is channel independent and is improved by introducing a more efficient method for computing the reliability of the parity checks. Extensive simulations are provided to demonstrate the efficiency of the proposed algorithm. Simulation results show that the proposed algorithm can achieve about 1.5dB coding gain improvement at BER = 5×10−6while reducing up to 48% iterations for decoding and maintaining low decoding complexity, compared with the conventional weighted BF algorithm.

Cross Strait Quad-Regional Radio Science and Wireless Technology Conference (CSQRWC)•Jul 1, 2012•6 citations

Hybrid Bit-Flip Decoding Algorithm for LDPC Codes

Changjia Chen

A Hybrid Bit Flip(HBF) decoding algorithm for Low-Density Parity-Check (LDPC) codes is proposed in this paper. The algorithm makes full use of the soft output of belief-propagation (BP) (decoding) algorithm for LDPC codes, and greatly improves the bit error rate (BER) of the classical bit-flip (BF) algorithm. The simulation results in AWGN channel show that the HBF algorithm outperforms the BP algorithm under almost the same computational complexity. Furthermore, the former can achieve much lower error floor than the latter can do.

Journal of Beijing Jiaotong University•Jan 1, 2005•2 citations
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.
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.
In order to improve the bit-flipping (BF) decoding algorithms, a weighted hard-decision based BF decoding algorithm for low-density parity-check (LDPC) codes is presented, in which the weights of variable-nodes are employed. A new metric is defined for the weight of candidate bits not only in unsatisfied parity check equations but also in satisfied ones. The connection between min-sum decoding algorithm and the proposed algorithm is presented. Simulation results show that the new decoding algorithm can provide better FER performance and faster convergence speed than the original candidate bit based bit-flipping (CBBF) algorithm.
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.
An improved bit-flipping(BF) algorithm with low complexity for decoding structured low-density parity-check codes(LDPC) is proposed to improve the performance of the hard-decision BF algorithm.The hard-decision bits are divided into two groups based on the magnitudes of the received symbols,and at each iteration,the proposed algorithm can flip more than one bit with using two thresholds,and the flipping error probability is effectively decreased.The improved BF algorithm requires some real number comparisons before iterations and requires only logical operations during the iterations.Compared with the weighted bit-flipping algorithm and its modifications,the new method is with significantly lower complexity.Simulations show that the proposed algorithm is provided with very fast convergence speed and excellent performance with significantly low complexity.
In this paper, a new method for improving hard-decision bit-flipping (BF) decoding is proposed for low-density parity-check codes. The flipping criterion is derived theoretically from the soft-decision belief-propagation decoding algorithm. The proposed BF decoding algorithm is channel independent and is improved by introducing a more efficient method for computing the reliability of the parity checks. Extensive simulations are provided to demonstrate the efficiency of the proposed algorithm. Simulation results show that the proposed algorithm can achieve about 1.5dB coding gain improvement at BER = 5×10−6while reducing up to 48% iterations for decoding and maintaining low decoding complexity, compared with the conventional weighted BF algorithm.
A Hybrid Bit Flip(HBF) decoding algorithm for Low-Density Parity-Check (LDPC) codes is proposed in this paper. The algorithm makes full use of the soft output of belief-propagation (BP) (decoding) algorithm for LDPC codes, and greatly improves the bit error rate (BER) of the classical bit-flip (BF) algorithm. The simulation results in AWGN channel show that the HBF algorithm outperforms the BP algorithm under almost the same computational complexity. Furthermore, the former can achieve much lower error floor than the latter can do.