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

Jounal of Xidian University

Fast quantized belief propagation algorithm for iteratively decoding LDPC codes

Xinmei Wang

Published Jan 1, 2002• 0 citations
OpenAlex

Abstract

A fast quantized belief propagation algorithm is proposed for decoding low-density parity-check(LDPC) codes. With operations performed by addressing tables, the proposed algorithm takes as operands the indices of labels rather than the quantization levels. The intermediate calculations have been contained in operation tables with much higher precision. The required storage can be significantly reduced by applying the symmetry property while keeping low time complexity. Without the increase in time complexity, it is convenient to realize the decoding with uniform quantization or any nonuniform quantizations that is designed for improving the performance. The time-varying decoder also becomes possible. This algorithm makes it possible to apply LDPC codes to practical systems or to realize fast simulation systems. Some simulation results are also given. The 6?bit logarithmic quantization results in gains of about 0.2?dB relative to the uniform one, approaching to the continuous decoding at low signal-to-noise ratios (SNRs) and yielding a loss of about 0.2?dB at high SNRs. Proper quantization of high order can achieve the performance of continuous decoding, and it may be superior to continuous decoding at high SNRs.

Related papers

Some Quantization Issues for Decoding of Low-Density Parity Check Codes with BP Algorithm

Sun Shao

The quantization scheme for the iterative belief propagation (BP) algorithm of low density parity check (LDPC) codes is studied.The effects of the bound,resolution,and other parameters for uniform and nonuniform quantization schemes are discussed.Good performance of decoding under properly designed quantization can be obtained as shown by simulations.Furthermore,we found that the quantization of high order for the mid variables of BP decoding algorithm can improve the performance and reduce the error floor of LDPC codes at regions of high signal to noise ratio.

Dianzi xuebao•Jan 1, 2003•0 citations

Measure on the Performance of Belief Propagation Decoding Algorithm

He Yu

Formulas for updated rules of the belief propagation algorithm applied to low density parity check (LDPC) codes are systematically derived based on the tree and the finite state machine (FSM).The probability measure on the continuous message space is introduced to evaluate the evolution of message densities within iterative decoding rounds,and derivations of the output distributions of common binary symmetric channels and the message density evolution are given in detail.The parameterized estimation of the performance of the algorithm is also discussed.The analytic and calculable means can be used to make systematical analysis for the convergence of BP algorithms independent of channels,and can be of help in designing LDPC codes and analyzing quantization effects for the fast decoding on the purpose of practical applications of LDPC codes to real time communication systems.

Dianzi xuebao•Jan 1, 2002•0 citations

Fast decoding of LDPC codes using quantisation

Yucheng He, Shaohui Sun, Xinmei Wang

A very fast quantised belief propagation algorithm is proposed for decoding low-density parity-check codes. This algorithm enables flexible quantisation schemes with low complexity and good performance near to or even better than that of continuous decoding. It can lower the error floor at high signal-to-noise ratios.

Electronics Letters•Feb 14, 2002•8 citations

On Mutual Information-Maximizing Quantized Belief Propagation Decoding of LDPC Codes

Xuan He, Kui Cai, Zhen Mei

A severe problem for mutual information-maximizing lookup table (MIM-LUT) decoding of low-density parity-check (LDPC) code is the high memory cost for using large tables, while decomposing large tables to small tables deteriorates decoding error performance. In this paper, we propose a systematic method, called mutual information- maximizing quantized belief propagation (MIM-QBP) decoding, to remove the lookup tables used for MIM-LUT decoding. Our method leads to a very practical decoder, namely the MIM-QBP decoder, which can be implemented based only on simple mappings and additions. Simulation results show that the proposed MIM-QBP decoder can outperform the state-of-the-art MIM-LUT decoder. Moreover, the MIM-QBP decoder with only 3 bits per message can outperform the floating-point belief propagation (BP) decoder at high signal-to-noise ratio (SNR) regions with a maximum of 10 iterations.

Globecom•Dec 1, 2019•25 citations

A Reconstruction-Computation-Quantization (RCQ) Approach to Node Operations in LDPC Decoding

Linfang Wang, Richard D. Wesel, Maximilian Stark +1 more

This paper proposes a finite-precision decoding method for low-density parity-check (LDPC) codes that features the three steps of Reconstruction, Computation, and Quantization (RCQ). Unlike Mutual-Information-Maximization Quantized Belief Propagation (MIM-QBP), RCQ can approximate either belief propagation or Min-Sum decoding. MIM-QBP decoders do not work well when the fraction of degree-2 variable nodes is large. However, sometimes a large fraction of degree-2 variable nodes is used to facilitate a fast encoding structure, as seen in the IEEE 802.11 standard and the DVB-S2 standard. In contrast to MIM-QBP, the proposed RCQ decoder may be applied to any off-the-shelf LDPC code, including those with a large fraction of degree-2 variable nodes. Simulations show that a 4-bit Min-Sum RCQ decoder delivers frame error rate (FER) performance within 0.1 dB of floating point belief propagation (BP) for the IEEE 802.11 standard LDPC code in the low SNR region. The RCQ decoder actually outperforms floating point BP and Min-Sum in the high SNR region were FER less than 10-5. This paper also introduces Hierarchical Dynamic Quantization (HDQ) to design the time-varying non-uniform quantizers required by RCQ decoders. HDQ is a low-complexity design technique that is slightly sub-optimal. Simulation results comparing HDQ and optimal quantization on the symmetric binary-input memoryless additive white Gaussian noise channel show a mutual information loss of less than 10-6bits, which is negligible in practice.

arXiv:2005.07259•Globecom•Dec 1, 2020•11 citations

A Weighted Belief Propagation Decoding Algorithm of LDPC Codes for Fast Convergence and Early Stopping

Tso-Cho Chen

A weighted belief propagation decoding algorithm for low-density parity-check decoding is proposed to accelerate the convergence of decoding and reduce the number of decoding iterations. We propose an early stopping criterion which is based on the average weighted reliability measure of the hard output of decoder to detect undecodable blocks in an early stage of the decoding process. In addition, an adaptive weighted iteration scheme is proposed to increase the convergence speed of belief propagation (BP) decoding and therefore improve the error performance. The evolution of the adaptive weighting factor with the number of decoding iterations is based on the relative entropy between two consecutive ”a posteriori” probabilities distribution at decoder output. Simulation results show that the proposed algorithm can achieve about 0.2-0.4 dB coding gain improvement on average while reducing up to about 50%-85% iterations for decoding at low to medium E(subscript b)/ N(subscript 0) , compared with the conventional BP based algorithms.

•Jul 1, 2012•0 citations
A fast quantized belief propagation algorithm is proposed for decoding low-density parity-check(LDPC) codes. With operations performed by addressing tables, the proposed algorithm takes as operands the indices of labels rather than the quantization levels. The intermediate calculations have been contained in operation tables with much higher precision. The required storage can be significantly reduced by applying the symmetry property while keeping low time complexity. Without the increase in time complexity, it is convenient to realize the decoding with uniform quantization or any nonuniform quantizations that is designed for improving the performance. The time-varying decoder also becomes possible. This algorithm makes it possible to apply LDPC codes to practical systems or to realize fast simulation systems. Some simulation results are also given. The 6?bit logarithmic quantization results in gains of about 0.2?dB relative to the uniform one, approaching to the continuous decoding at low signal-to-noise ratios (SNRs) and yielding a loss of about 0.2?dB at high SNRs. Proper quantization of high order can achieve the performance of continuous decoding, and it may be superior to continuous decoding at high SNRs.
The quantization scheme for the iterative belief propagation (BP) algorithm of low density parity check (LDPC) codes is studied.The effects of the bound,resolution,and other parameters for uniform and nonuniform quantization schemes are discussed.Good performance of decoding under properly designed quantization can be obtained as shown by simulations.Furthermore,we found that the quantization of high order for the mid variables of BP decoding algorithm can improve the performance and reduce the error floor of LDPC codes at regions of high signal to noise ratio.
Formulas for updated rules of the belief propagation algorithm applied to low density parity check (LDPC) codes are systematically derived based on the tree and the finite state machine (FSM).The probability measure on the continuous message space is introduced to evaluate the evolution of message densities within iterative decoding rounds,and derivations of the output distributions of common binary symmetric channels and the message density evolution are given in detail.The parameterized estimation of the performance of the algorithm is also discussed.The analytic and calculable means can be used to make systematical analysis for the convergence of BP algorithms independent of channels,and can be of help in designing LDPC codes and analyzing quantization effects for the fast decoding on the purpose of practical applications of LDPC codes to real time communication systems.
A severe problem for mutual information-maximizing lookup table (MIM-LUT) decoding of low-density parity-check (LDPC) code is the high memory cost for using large tables, while decomposing large tables to small tables deteriorates decoding error performance. In this paper, we propose a systematic method, called mutual information- maximizing quantized belief propagation (MIM-QBP) decoding, to remove the lookup tables used for MIM-LUT decoding. Our method leads to a very practical decoder, namely the MIM-QBP decoder, which can be implemented based only on simple mappings and additions. Simulation results show that the proposed MIM-QBP decoder can outperform the state-of-the-art MIM-LUT decoder. Moreover, the MIM-QBP decoder with only 3 bits per message can outperform the floating-point belief propagation (BP) decoder at high signal-to-noise ratio (SNR) regions with a maximum of 10 iterations.
This paper proposes a finite-precision decoding method for low-density parity-check (LDPC) codes that features the three steps of Reconstruction, Computation, and Quantization (RCQ). Unlike Mutual-Information-Maximization Quantized Belief Propagation (MIM-QBP), RCQ can approximate either belief propagation or Min-Sum decoding. MIM-QBP decoders do not work well when the fraction of degree-2 variable nodes is large. However, sometimes a large fraction of degree-2 variable nodes is used to facilitate a fast encoding structure, as seen in the IEEE 802.11 standard and the DVB-S2 standard. In contrast to MIM-QBP, the proposed RCQ decoder may be applied to any off-the-shelf LDPC code, including those with a large fraction of degree-2 variable nodes. Simulations show that a 4-bit Min-Sum RCQ decoder delivers frame error rate (FER) performance within 0.1 dB of floating point belief propagation (BP) for the IEEE 802.11 standard LDPC code in the low SNR region. The RCQ decoder actually outperforms floating point BP and Min-Sum in the high SNR region were FER less than 10-5. This paper also introduces Hierarchical Dynamic Quantization (HDQ) to design the time-varying non-uniform quantizers required by RCQ decoders. HDQ is a low-complexity design technique that is slightly sub-optimal. Simulation results comparing HDQ and optimal quantization on the symmetric binary-input memoryless additive white Gaussian noise channel show a mutual information loss of less than 10-6bits, which is negligible in practice.
A weighted belief propagation decoding algorithm for low-density parity-check decoding is proposed to accelerate the convergence of decoding and reduce the number of decoding iterations. We propose an early stopping criterion which is based on the average weighted reliability measure of the hard output of decoder to detect undecodable blocks in an early stage of the decoding process. In addition, an adaptive weighted iteration scheme is proposed to increase the convergence speed of belief propagation (BP) decoding and therefore improve the error performance. The evolution of the adaptive weighting factor with the number of decoding iterations is based on the relative entropy between two consecutive ”a posteriori” probabilities distribution at decoder output. Simulation results show that the proposed algorithm can achieve about 0.2-0.4 dB coding gain improvement on average while reducing up to about 50%-85% iterations for decoding at low to medium E(subscript b)/ N(subscript 0) , compared with the conventional BP based algorithms.