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 Information and Communication Technology Convergence (ICTC)

Analysis of Bit-Flipping Algorithm of Irregular Low-Density Parity-Check Codes

Myungin Kim, Jeongseok Ha

Published Oct 21, 2020• 1 citation
Publisher

Abstract

In this work, we analytically derive the evolution of single-bit messages in the bit-flipping algorithm (BFA) for irregular low-density parity-check (LDPC) codes on the binary symmetric channel (BSC). In particular, the analysis tracks the probability distributions of the flipping functions and the bit-decision error at each iteration, which is possible by introducing a state variable at each variable node. The probability distributions are indirectly obtained by taking advantage of the state and state transition probabilities. The analysis will be confirmed by comparing analytic evaluations with simulation results. For the comparison, we implement LDPC codes at a finite length.

DOI
10.1109/ictc49870.2020.9289331

Related papers

Density Evolution of the Bit-Flipping Decoding Algorithm of Regular Low-Density Parity-Check Codes

Myungin Kim, Jeongseok Ha

In this paper, we develop the density evolution of bit-flipping algorithm (BFA) for regular low-density parity-check (LDPC) codes and analyze the evolution of probability density for the bit-decision error. In contrast to the sum-product algorithm (SPA) and min-sum algorithm (MSA), the density evolution for BFA has remained untouched, which motivates this work. In the developed density evolution for BFA, we first introduce a state variable which is a function of bit-decision result and the flipping function value at each iteration. Then, the state probability is derived, with which the density of bit-decision error is obtained. To confirm the derivations, we design regular LDPC codes and compare the empirical evaluations of bit-error rates and the derived probability of bit-decision errors.

International Conference on Information and Communication Technology Convergence (ICTC)•Oct 1, 2019•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

Hybrid Hard-Decision Iterative Decoding of Irregular Low-Density Parity-Check Codes

Pirouz Zarrinkhat, Amir H. Banihashemi

Time-invariant hybrid (HscrTI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on HscrTIalgorithms with majority-based (MB) binary message-passing constituents, we use density evolution (DE) and finite-length simulation to analyze the performance and the convergence properties of these algorithms over (memoryless) binary symmetric channels. To apply DE, we generalize degree distributions to have the irregularity of both the code and the decoding algorithm embedded in them. A tight upper bound on the threshold of MB HscrTIalgorithms is derived, and it is proven that the asymptotic error probability for these algorithms tends to zero, at least exponentially, with the number of iterations. We devise optimal MB HscrTIalgorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB HscrTIalgorithms are more robust and can better cope with unknown channel conditions, and thus can be practically more attractive.

IEEE Transactions on Communications•Feb 1, 2007•6 citations

A Two-Bit Weighted Bit-Flipping Decoding Algorithm for LDPC Codes

Jieun Oh, Jeongseok Ha

This letter proposes a novel two-bit weighted bit-flipping algorithm (TB-WBFA) for low-density parity-check (LDPC) codes on the binary symmetric channel. The proposed TB-WBFA produces reliability bits for the bit-decision results and syndrome values at bit and check nodes, respectively. The reliability bits are exchanged between bit and check nodes as the decoding proceeds. The message update in check nodes is carefully devised with simple bitwise operations, which are especially suitable for high-speed operations. It will be demonstrated that the proposed TB-WBFA achieves a significant performance improvement over existing bit-flipping decoding algorithms by conducting performance comparisons for LDPC codes under various setups, i.e., different rates, lengths, and structures.

IEEE Communications Letters•Feb 26, 2018•16 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

Estimation of Bit and Frame Error Rates of Low-Density Parity-Check Codes on Binary Symmetric Channels

Hua Xiao, Amir H. Banihashemi

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSC) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.

arXiv:cs/0612011•Canadian Workshop on Information Theory (CWIT)•Jun 1, 2007•12 citations
In this work, we analytically derive the evolution of single-bit messages in the bit-flipping algorithm (BFA) for irregular low-density parity-check (LDPC) codes on the binary symmetric channel (BSC). In particular, the analysis tracks the probability distributions of the flipping functions and the bit-decision error at each iteration, which is possible by introducing a state variable at each variable node. The probability distributions are indirectly obtained by taking advantage of the state and state transition probabilities. The analysis will be confirmed by comparing analytic evaluations with simulation results. For the comparison, we implement LDPC codes at a finite length.
In this paper, we develop the density evolution of bit-flipping algorithm (BFA) for regular low-density parity-check (LDPC) codes and analyze the evolution of probability density for the bit-decision error. In contrast to the sum-product algorithm (SPA) and min-sum algorithm (MSA), the density evolution for BFA has remained untouched, which motivates this work. In the developed density evolution for BFA, we first introduce a state variable which is a function of bit-decision result and the flipping function value at each iteration. Then, the state probability is derived, with which the density of bit-decision error is obtained. To confirm the derivations, we design regular LDPC codes and compare the empirical evaluations of bit-error rates and the derived probability of bit-decision errors.
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.
Time-invariant hybrid (HscrTI) decoding of irregular low-density parity-check (LDPC) codes is studied. Focusing on HscrTIalgorithms with majority-based (MB) binary message-passing constituents, we use density evolution (DE) and finite-length simulation to analyze the performance and the convergence properties of these algorithms over (memoryless) binary symmetric channels. To apply DE, we generalize degree distributions to have the irregularity of both the code and the decoding algorithm embedded in them. A tight upper bound on the threshold of MB HscrTIalgorithms is derived, and it is proven that the asymptotic error probability for these algorithms tends to zero, at least exponentially, with the number of iterations. We devise optimal MB HscrTIalgorithms for irregular LDPC codes, and show that these algorithms outperform Gallager's algorithm A applied to optimized irregular LDPC codes. We also show that compared to switch-type algorithms, such as Gallager's algorithm B, where a comparable improvement is obtained by switching between different MB algorithms, MB HscrTIalgorithms are more robust and can better cope with unknown channel conditions, and thus can be practically more attractive.
This letter proposes a novel two-bit weighted bit-flipping algorithm (TB-WBFA) for low-density parity-check (LDPC) codes on the binary symmetric channel. The proposed TB-WBFA produces reliability bits for the bit-decision results and syndrome values at bit and check nodes, respectively. The reliability bits are exchanged between bit and check nodes as the decoding proceeds. The message update in check nodes is carefully devised with simple bitwise operations, which are especially suitable for high-speed operations. It will be demonstrated that the proposed TB-WBFA achieves a significant performance improvement over existing bit-flipping decoding algorithms by conducting performance comparisons for LDPC codes under various setups, i.e., different rates, lengths, and structures.
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.
A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSC) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.