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 Communications

An analysis into the loopy belief propagation algorithm over short cycles

Nithin Raveendran, Shayan Garani Srinivasa

Published Jun 1, 2014• 5 citations
Publisher

Abstract

We investigate into the loopy belief propagation algorithm for binary low density parity check (LDPC) codes having cycles of small girth. Independence assumption among messages passed, assumed reasonable in all configurations of graphs, fails the most in graphical structures with short cycles. We investigate into this limitation and propose a modified algorithm, by considering dependency in the probability domain. This improves the performance of decoding over such graphs when compared to the original message passing algorithm at higher signal-to-noise ratio (SNR), thereby, yielding lower error floors.

DOI
10.1109/icc.2014.6883618

Related papers

A Modified Sum-Product Algorithm over Graphs with Short Cycles

Nithin Raveendran

We investigate into the limitations of the sum-product algorithm for binary low density parity check (LDPC) codes having isolated short cycles. Independence assumption among messages passed, assumed reasonable in all configurations of graphs, fails the most in graphical structures with short cycles. This research work is a step forward towards understanding the effect of short cycles on error floors of the sum-product algorithm. We propose a modified sum-product algorithm by considering the statistical dependency of the messages passed in a cycle of length 4. We also formulate a modified algorithm in the log domain which eliminates the numerical instability and precision issues associated with the probability domain. Simulation results show a signal to noise ratio (SNR) improvement for the modified sum-product algorithm compared to the original algorithm. This suggests that dependency among messages improves the decisions and successfully mitigates the effects of length-4 cycles in the Tanner graph. The improvement is significant at high SNR region, suggesting a possible cause to the error floor effects on such graphs. Using density evolution techniques, we analysed the modified decoding algorithm. The threshold computed for the modified algorithm is higher than the threshold computed for the sum-product algorithm, validating the observed simulation results. We also prove that the conditional entropy of a codeword given the estimate obtained using the modified algorithm is lower compared to using the original sum-product algorithm.

•Jan 1, 2018•0 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

A modified sum-product algorithm over graphs with isolated short cycles

Nithin Raveendran, Shayan Garani Srinivasa

We investigate into the limitations of the sum-product algorithm in the probability domain over graphs with isolated short cycles. By considering the statistical dependency of messages passed in a cycle of length 4, we modify the update equations for the beliefs at the variable and check nodes. We highlight an approximate log domain algebra for the modified variable node update to ensure numerical stability. At higher signal-to-noise ratios (SNR), the performance of decoding over graphs with isolated short cycles using the modified algorithm is improved compared to the original message passing algorithm (MPA).

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•4 citations

Short-length Low-density Parity-check Codes: Construction and Decoding Algorithms

Cornelius T. Healy

Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate performance.

•Jul 1, 2014•4 citations

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
We investigate into the loopy belief propagation algorithm for binary low density parity check (LDPC) codes having cycles of small girth. Independence assumption among messages passed, assumed reasonable in all configurations of graphs, fails the most in graphical structures with short cycles. We investigate into this limitation and propose a modified algorithm, by considering dependency in the probability domain. This improves the performance of decoding over such graphs when compared to the original message passing algorithm at higher signal-to-noise ratio (SNR), thereby, yielding lower error floors.
We investigate into the limitations of the sum-product algorithm for binary low density parity check (LDPC) codes having isolated short cycles. Independence assumption among messages passed, assumed reasonable in all configurations of graphs, fails the most in graphical structures with short cycles. This research work is a step forward towards understanding the effect of short cycles on error floors of the sum-product algorithm. We propose a modified sum-product algorithm by considering the statistical dependency of the messages passed in a cycle of length 4. We also formulate a modified algorithm in the log domain which eliminates the numerical instability and precision issues associated with the probability domain. Simulation results show a signal to noise ratio (SNR) improvement for the modified sum-product algorithm compared to the original algorithm. This suggests that dependency among messages improves the decisions and successfully mitigates the effects of length-4 cycles in the Tanner graph. The improvement is significant at high SNR region, suggesting a possible cause to the error floor effects on such graphs. Using density evolution techniques, we analysed the modified decoding algorithm. The threshold computed for the modified algorithm is higher than the threshold computed for the sum-product algorithm, validating the observed simulation results. We also prove that the conditional entropy of a codeword given the estimate obtained using the modified algorithm is lower compared to using the original sum-product 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.
We investigate into the limitations of the sum-product algorithm in the probability domain over graphs with isolated short cycles. By considering the statistical dependency of messages passed in a cycle of length 4, we modify the update equations for the beliefs at the variable and check nodes. We highlight an approximate log domain algebra for the modified variable node update to ensure numerical stability. At higher signal-to-noise ratios (SNR), the performance of decoding over graphs with isolated short cycles using the modified algorithm is improved compared to the original message passing algorithm (MPA).
Error control coding is an essential part of modern communications systems. LDPC codes have been demonstrated to offer performance near the fundamental limits of channels corrupted by random noise. Optimal maximum likelihood decoding of LDPC codes is too complex to be practically useful even at short block lengths and so a graph-based message passing decoder known as the belief propagation algorithm is used instead. In fact, on graphs without closed paths known as cycles the iterative message passing decoding is known to be optimal and may converge in a single iteration, although identifying the message update schedule which allows single-iteration convergence is not trivial. At finite block lengths graphs without cycles have poor minimum distance properties and perform poorly even under optimal decoding. LDPC codes with large block length have been demonstrated to offer performance close to that predicted for codes of infinite length, as the cycles present in the graph are quite long. In this thesis, LDPC codes of shorter length are considered as they offer advantages in terms of latency and complexity, at the cost of performance degradation from the increased number of short cycles in the graph. For these shorter LDPC codes, the problems considered are: \n \nFirst, improved construction of structured and unstructured LDPC code graphs of short length with a view to reducing the harmful effects of the cycles on error rate performance, based on knowledge of the decoding process. Structured code graphs are particularly interesting as they allow benefits in encoding and decoding complexity and speed. Secondly, the design and construction of LDPC codes for the block fading channel, a particularly challenging scenario from the point of view of error control code design. Both established and novel classes of codes for the channel are considered. Finally the decoding of LDPC codes by the belief propagation algorithm is considered, in particular the scheduling of messages passed in the iterative decoder. A knowledge-aided approach is developed based on message reliabilities and residuals to allow fast convergence and significant improvements in error rate 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.