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

IEEE Communications Letters

Improving Belief Propagation on Graphs With Cycles

M Yazdani, Saied Hemati, Amir H. Banihashemi

Published Jan 1, 2004• 88 citations
Publisher

Abstract

In this letter, we propose two modifications to belief propagation (BP) decoding algorithm. The modifications are based on reducing the reliability of messages throughout the iteration process, and are particularly effective for short low-density parity-check codes, where the existence of cycles makes the original BP algorithm perform suboptimal. The proposed algorithms, referred to as "normalized BP" and "offset BP," reduce the absolute value of the outgoing log-likelihood ratio messages at variable nodes by using a multiplicative factor and an additive factor, respectively. Simulation results show that both algorithms perform more or less the same, and both outperform BP in error performance.

DOI
10.1109/lcomm.2003.822499

Related papers

Improved Belief Propagation by Employing the Positive Effects of the Feedback Messages

Cui Junyun

In this paper, a modification to belief propagation (BP) decoding algorithm is proposed, which is based on extracting the prior messages of each variable node to help the BP decoding, and is particularly effective for low-density parity-check (LDPC) codes with short cycles, where the existence of cycles makes the original BP algorithm perform suboptimal.The proposed algorithm, referred to as "employing the positive effects of the feedback messages (EPEFM)", extracts the positive effects of the feedback messages and then makes use of them as prior messages to assist the decoding of the BP algorithm.Simulation results confirm the effectiveness of our proposed algorithm, which improves the performance in high signal-to-noise-ratio (SNR) region without loss in low SNR region.

Journal of Computers•Jan 1, 2019•0 citations

A high‐performance belief propagation decoding algorithm for codes with short cycles

Ali Karimi-lenji, Monireh Houshmand, Fahimeh Zarmehi

Summary The simplicity of decoding is one of the most important characteristics of the low density parity check (LDPC) codes. Belief propagation (BP) decoding algorithm is a well‐known decoding algorithm for LDPC codes. Most LDPC codes with long lengths have short cycles in their Tanner graphs, which reduce the performance of the BP algorithm. In this paper, we present 2 methods to improve the BP decoding algorithm for LDPC codes. In these methods, the calculation of the variable nodes is controlled by using “multiplicative correction factor” and “additive correction factor.” These factors are obtained for 2 separate channels, namely additive white Gaussian noise (AWGN) and binary symmetric channel (BSC), as 2 functions of code and channel parameters. Moreover, we use the BP‐based method in the calculation of the check nodes, which reduces the required resources. Simulation results show the proposed algorithm has better performance and lower decoding error as compared to BP and similar methods like normalized‐BP and offset‐BP algorithms.

International Journal of Communication Systems•Feb 28, 2017•2 citations

An improved decoding algorithm of low-density parity-check codes

Yongqiang Deng, Guangxi Zhu, Liu Wenming +1 more

In this paper, the decoding algorithm of low-density parity-check (LDPC) codes is analyzed, and a new decoding algorithm based on the belief propagation (BP) algorithm to eliminate the influence of cycles in the factor graph is proposed. In the traditional BP algorithm, the cycles of factor graph sends message back to its source, and this decreases the decoding performance. The new algorithm records each cycle's path and length of each node, and cuts off the path by which message is propagated when the message comes back. It can advance the decoding performance by protect the message of good quality be propagated as widely as possible. Our results of simulation show that the performance of new algorithm is not worse than that of traditional BP algorithm in the low SNR channel and the new algorithm significantly outperform traditional BP algorithm in good channel condition.

International Conference on Wireless Communications, Networking and Mobile Computing•Dec 10, 2005•0 citations

Improved belief propagation algorithm for decoding of convolutional LDPC codes

Chen Ru-wei

A novel belief propagation(BP) decoding algorithm for convolutional low-density parity-check codes is proposed.The proposed algorithm raises the efficiency of updating the variable information by applying feedback information at each decoding iteration and employs the weighting factor to reduce the error propagation caused by the cycles in the Tanner graph,thus yielding a faster convergence of the decoding.Simulation results show that an error performance better than that of the existing belief propagation algorithm can be achieved,while the 5/8 decoding delay and the computation complexity are effectively reduced.Compared with the existing BP,the proposed algorithm achieves a gain of 0.16dB at the BER of 10-6 with the same number of iterations.

Journal of Xidian University•Jan 1, 2009•0 citations

Modified Belief Propagation Decoding Algorithm for Low-Density Parity Check Code Based on Oscillation

Satoshi Gounai, Tomoaki Otsuki Ohtsuki, T. Kaneko

A low-density parity check (LDPC) code with the belief propagation (BP) or the log-likelihood ratio belief propagation (LLR-BP) can achieve good bit error rate (BER) performance approaching the Shannon limit. When a parity check matrix of the LDPC code has the cycle, the BP and LLR-BP decoding algorithms achieve approximate maximum a posterior probability (MAP) decoding. Although the decoding algorithms are approximate MAP decoding, LDPC codes can achieve very good BER. For the short and middle length LDPC codes, BER and block error rate (BLER) performances are affected by cycle largely. In each iteration, the magnitudes of a posterior LLRs of some bits oscillate owing to cycles. The oscillation is the dominant error factor in the high Eb/Noregion for short and middle length LDPC codes. In this paper, we extend the definition of oscillation to extrinsic LLR (ex-LLR) derived in the bit node process and propose the modified LLR-BP and the modified UMP-BP decoding algorithms. To reduce effects of oscillating ex-LLRs on decoding, for oscillating ex-LLRs, we add the previous ex-LLR to the current ex-LLR. From the computer simulation, we show that for short and middle length LDPC codes, with a simple modification, our proposed decoding algorithms can improve the conventional LLR-BP and UMP-BP decoding algorithms. In particular, we show that the modified UMP-BP decoding algorithm with low complexity can achieve better BER and BLER than the conventional LLR-BP decoding algorithm

IEEE Vehicular Technology Conference•Sep 8, 2006•15 citations

AN IMPROVED LOG-DOMAIN BELIEF PROPAGATION ALGORITHM OVER GRAPHS WITH SHORT CYCLES

Nithin Raveendran, Shayan Garani Srinivasa, Bane V. Vasic

We present a modified belief propagation (BP) algorithm for decoding low density parity check codes having graphs with short cycles. The modified algorithm in log domain is superior in terms of numerical stability, precision, computational complexity and ease of implementation when compared to the algorithm in the probability domain. Simulation results show improvement in decoding performance for the modified BP compared to the original algorithm. The modified approach is also generalized for graphs with isolated cycles of arbitrary length by considering the statistical dependency among messages passed in such cycles. © 2019 International Foundation for Telemetering. All rights reserved.

•Oct 1, 2019•0 citations
In this letter, we propose two modifications to belief propagation (BP) decoding algorithm. The modifications are based on reducing the reliability of messages throughout the iteration process, and are particularly effective for short low-density parity-check codes, where the existence of cycles makes the original BP algorithm perform suboptimal. The proposed algorithms, referred to as "normalized BP" and "offset BP," reduce the absolute value of the outgoing log-likelihood ratio messages at variable nodes by using a multiplicative factor and an additive factor, respectively. Simulation results show that both algorithms perform more or less the same, and both outperform BP in error performance.
In this paper, a modification to belief propagation (BP) decoding algorithm is proposed, which is based on extracting the prior messages of each variable node to help the BP decoding, and is particularly effective for low-density parity-check (LDPC) codes with short cycles, where the existence of cycles makes the original BP algorithm perform suboptimal.The proposed algorithm, referred to as "employing the positive effects of the feedback messages (EPEFM)", extracts the positive effects of the feedback messages and then makes use of them as prior messages to assist the decoding of the BP algorithm.Simulation results confirm the effectiveness of our proposed algorithm, which improves the performance in high signal-to-noise-ratio (SNR) region without loss in low SNR region.
Summary The simplicity of decoding is one of the most important characteristics of the low density parity check (LDPC) codes. Belief propagation (BP) decoding algorithm is a well‐known decoding algorithm for LDPC codes. Most LDPC codes with long lengths have short cycles in their Tanner graphs, which reduce the performance of the BP algorithm. In this paper, we present 2 methods to improve the BP decoding algorithm for LDPC codes. In these methods, the calculation of the variable nodes is controlled by using “multiplicative correction factor” and “additive correction factor.” These factors are obtained for 2 separate channels, namely additive white Gaussian noise (AWGN) and binary symmetric channel (BSC), as 2 functions of code and channel parameters. Moreover, we use the BP‐based method in the calculation of the check nodes, which reduces the required resources. Simulation results show the proposed algorithm has better performance and lower decoding error as compared to BP and similar methods like normalized‐BP and offset‐BP algorithms.
In this paper, the decoding algorithm of low-density parity-check (LDPC) codes is analyzed, and a new decoding algorithm based on the belief propagation (BP) algorithm to eliminate the influence of cycles in the factor graph is proposed. In the traditional BP algorithm, the cycles of factor graph sends message back to its source, and this decreases the decoding performance. The new algorithm records each cycle's path and length of each node, and cuts off the path by which message is propagated when the message comes back. It can advance the decoding performance by protect the message of good quality be propagated as widely as possible. Our results of simulation show that the performance of new algorithm is not worse than that of traditional BP algorithm in the low SNR channel and the new algorithm significantly outperform traditional BP algorithm in good channel condition.
A novel belief propagation(BP) decoding algorithm for convolutional low-density parity-check codes is proposed.The proposed algorithm raises the efficiency of updating the variable information by applying feedback information at each decoding iteration and employs the weighting factor to reduce the error propagation caused by the cycles in the Tanner graph,thus yielding a faster convergence of the decoding.Simulation results show that an error performance better than that of the existing belief propagation algorithm can be achieved,while the 5/8 decoding delay and the computation complexity are effectively reduced.Compared with the existing BP,the proposed algorithm achieves a gain of 0.16dB at the BER of 10-6 with the same number of iterations.
A low-density parity check (LDPC) code with the belief propagation (BP) or the log-likelihood ratio belief propagation (LLR-BP) can achieve good bit error rate (BER) performance approaching the Shannon limit. When a parity check matrix of the LDPC code has the cycle, the BP and LLR-BP decoding algorithms achieve approximate maximum a posterior probability (MAP) decoding. Although the decoding algorithms are approximate MAP decoding, LDPC codes can achieve very good BER. For the short and middle length LDPC codes, BER and block error rate (BLER) performances are affected by cycle largely. In each iteration, the magnitudes of a posterior LLRs of some bits oscillate owing to cycles. The oscillation is the dominant error factor in the high Eb/Noregion for short and middle length LDPC codes. In this paper, we extend the definition of oscillation to extrinsic LLR (ex-LLR) derived in the bit node process and propose the modified LLR-BP and the modified UMP-BP decoding algorithms. To reduce effects of oscillating ex-LLRs on decoding, for oscillating ex-LLRs, we add the previous ex-LLR to the current ex-LLR. From the computer simulation, we show that for short and middle length LDPC codes, with a simple modification, our proposed decoding algorithms can improve the conventional LLR-BP and UMP-BP decoding algorithms. In particular, we show that the modified UMP-BP decoding algorithm with low complexity can achieve better BER and BLER than the conventional LLR-BP decoding algorithm
We present a modified belief propagation (BP) algorithm for decoding low density parity check codes having graphs with short cycles. The modified algorithm in log domain is superior in terms of numerical stability, precision, computational complexity and ease of implementation when compared to the algorithm in the probability domain. Simulation results show improvement in decoding performance for the modified BP compared to the original algorithm. The modified approach is also generalized for graphs with isolated cycles of arbitrary length by considering the statistical dependency among messages passed in such cycles. © 2019 International Foundation for Telemetering. All rights reserved.