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

A Modified Sum-Product Algorithm over Graphs with Short Cycles

Nithin Raveendran

Published Jan 1, 2018• 0 citations
OpenAlex

Abstract

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.

Related papers

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

An analysis into the loopy belief propagation algorithm over short cycles

Nithin Raveendran, Shayan Garani Srinivasa

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.

International Conference on Communications•Jun 1, 2014•5 citations

A Modified Sum-Product Algorithm for Error Floor Reduction in LDPC Codes

Un-Hee Park, Dae-Sub Oh, Youngmin Kim +1 more

In this paper, a modified sum-product algorithm to correct bit errors captured within the trapping sets, which are produced in decoding of low-density parity-check (LDPC) codes, is proposed. Unlike the original sum-product algorithm, the proposed decoding method consists of two stages. Whether the main cause of decoding failure is the trapping sets or not is determined at the first stage. And the bit errors within the trapping sets are corrected at the second stage. In the modified algorithm, the set of failed check nodes and the transition patterns of hard-decision bits are exploited to search variable nodes in the trapping sets. After inverting information of the variable nodes, the sum-product algorithm is carried out to correct the bit errors. As a result of simulation, the proposed algorithm shows continuously improved error performance with increase in the signal-to-noise ratio. It is, therefore, considered that the modified sum-product algorithm significantly reduces or possibly eliminates the error floor in LDPC codes.

한국통신학회논문지•Jan 1, 2010•4 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

Design and Implementation of Low Bit Error Rate of LDPC Decoder

Ashlesha P. Kshirsagar, Sandeep Kakde, Manish Devendra Chawhan +1 more

Many classes of high-performance Low-density parity check codes are based on parity check matrices composed of permutation sub matrices. The emulation-simulation framework further allows the algorithm and implementation to be iteratively redefined to improve the error floor performance of message passing decoder. Log-Like hood-Ratio (LLR) based Belief-Propagation (BP) algorithm is presented for Low Density Parity Check codes. Numerically accurate representation of check node update computation used in LLR-BP decoding is described. The implementation of Sum-Product algorithm (SPA) within Low Density Parity Check Code (LDPC) decoder is described in this paper and the correction term is used to improve the decoding performance of min-sum algorithm (MSA). Quantization and log-tanh function approximation in sum-product decoder strongly affect which absorbing set dominates in error floor region. For LDPC decoder, bit error rate (BER) decreases with increase in the signal to noise ratio.

International Conference on Communication Systems and Network Technologies•Apr 1, 2015•1 citation

A Novel Stochastic Decoding of LDPC Codes with Quantitative Guarantees

Nima Noorshams, Aravind Raghava Iyengar

Low-density parity-check codes, a class of capacity-approaching linear codes, are particularly recognized for their efficient decoding scheme. The decoding scheme, known as the sum-product, is an iterative algorithm consisting of passing messages between variable and check nodes of the factor graph. The sum-product algorithm is fully parallelizable, owing to the fact that all messages can be update concurrently. However, since it requires extensive number of highly interconnected wires, the fully-parallel implementation of the sum-product on chips is exceedingly challenging. Stochastic decoding algorithms, which exchange binary messages, are of great interest for mitigating this challenge and have been the focus of extensive research over the past decade. They significantly reduce the required wiring and computational complexity of the message-passing algorithm. Even though stochastic decoders have been shown extremely effective in practice, the theoretical aspect and understanding of such algorithms remains limited at large. Our main objective in this paper is to address this issue. We first propose a novel algorithm referred to as the Markov based stochastic decoding. Then, we provide concrete quantitative guarantees on its performance for tree-structured as well as general factor graphs. More specifically, we provide upper-bounds on the first and second moments of the error, illustrating that the proposed algorithm is an asymptotically consistent estimate of the sum-product algorithm. We also validate our theoretical predictions with experimental results, showing we achieve comparable performance to other practical stochastic decoders.

arXiv:1405.6353•May 25, 2014•0 citations
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 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).
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.
In this paper, a modified sum-product algorithm to correct bit errors captured within the trapping sets, which are produced in decoding of low-density parity-check (LDPC) codes, is proposed. Unlike the original sum-product algorithm, the proposed decoding method consists of two stages. Whether the main cause of decoding failure is the trapping sets or not is determined at the first stage. And the bit errors within the trapping sets are corrected at the second stage. In the modified algorithm, the set of failed check nodes and the transition patterns of hard-decision bits are exploited to search variable nodes in the trapping sets. After inverting information of the variable nodes, the sum-product algorithm is carried out to correct the bit errors. As a result of simulation, the proposed algorithm shows continuously improved error performance with increase in the signal-to-noise ratio. It is, therefore, considered that the modified sum-product algorithm significantly reduces or possibly eliminates the error floor in LDPC codes.
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.
Many classes of high-performance Low-density parity check codes are based on parity check matrices composed of permutation sub matrices. The emulation-simulation framework further allows the algorithm and implementation to be iteratively redefined to improve the error floor performance of message passing decoder. Log-Like hood-Ratio (LLR) based Belief-Propagation (BP) algorithm is presented for Low Density Parity Check codes. Numerically accurate representation of check node update computation used in LLR-BP decoding is described. The implementation of Sum-Product algorithm (SPA) within Low Density Parity Check Code (LDPC) decoder is described in this paper and the correction term is used to improve the decoding performance of min-sum algorithm (MSA). Quantization and log-tanh function approximation in sum-product decoder strongly affect which absorbing set dominates in error floor region. For LDPC decoder, bit error rate (BER) decreases with increase in the signal to noise ratio.
Low-density parity-check codes, a class of capacity-approaching linear codes, are particularly recognized for their efficient decoding scheme. The decoding scheme, known as the sum-product, is an iterative algorithm consisting of passing messages between variable and check nodes of the factor graph. The sum-product algorithm is fully parallelizable, owing to the fact that all messages can be update concurrently. However, since it requires extensive number of highly interconnected wires, the fully-parallel implementation of the sum-product on chips is exceedingly challenging. Stochastic decoding algorithms, which exchange binary messages, are of great interest for mitigating this challenge and have been the focus of extensive research over the past decade. They significantly reduce the required wiring and computational complexity of the message-passing algorithm. Even though stochastic decoders have been shown extremely effective in practice, the theoretical aspect and understanding of such algorithms remains limited at large. Our main objective in this paper is to address this issue. We first propose a novel algorithm referred to as the Markov based stochastic decoding. Then, we provide concrete quantitative guarantees on its performance for tree-structured as well as general factor graphs. More specifically, we provide upper-bounds on the first and second moments of the error, illustrating that the proposed algorithm is an asymptotically consistent estimate of the sum-product algorithm. We also validate our theoretical predictions with experimental results, showing we achieve comparable performance to other practical stochastic decoders.