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 Advanced Computer Theory and Engineering

Modified Log-BP decoding algorithm combined with PSO for Low-Density Parity Check Codes

Xiali Yan, Wenquan Feng, Qi Zhao, Hongbo Zhao

Published Aug 1, 2010• 0 citations
Publisher

Abstract

Message-Passing is the main decoding algorithm for Low-Density Parity Check (LDPC) Codes, in which Logarithmic Belief Propagation (Log-BP) algorithm is the most popularly used one. Particle Swarm Optimization (PSO) can also be regarded as an optimization algorithm by message-passing, which makes it possible to combine Log-BP algorithm with PSO. PSO was introduced into Log-BP algorithm by regarding all messages that bit nodes send to check nodes as the swarm with each message individually as a particle. Move the particles around in the search-space by certain iterations in each BP iteration processing, guided by the two best current values respectively found by particles themselves and that of the whole swarm. Those two best values were continually updated in each PSO iteration. In this way, the output of decoder is more consistent with accurate input sequence, in other words, the decoder performance was improved. Simulation results show that this new algorithm combined with Log-BP and PSO can get an additional 0.1 dB coding gain at Bit Error Rate (BER) of 10-5compared with Log-BP algorithm.

DOI
10.1109/icacte.2010.5579320

Related papers

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

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•16 citations

Optimising LDPC Codes Using Modified Log SPA Algorithm

Abdessadek Aaroud, Mohammed Mensouri

We present in this paper a new method for improving the decoding of the LDPC (low-density parity check) codes by optimising the log-SPA (sum-product algorithm). Currently, the LDPC codes give very good results with iterative decoding algorithm, log-SPA, based on the propagation confidence BP (belief propagation). To improve the existing log-SPA, we propose a decoding algorithm (log-SPA modified), which minimises the error decoding of words that could not be previously decoded. This algorithm is based on the dependency between the weight of the syndrome and the weight of the error sequence generated during iterations of decoding. Simulations illustrate the performance of our approach compared with classical LDPC code based on log-SPA.

International Journal of Applied Research on Information Technology and Computing•Jan 1, 2014•0 citations

A Generalization Belief Propagation Decoding Algorithm for Polar Codes Based on Particle Swarm Optimization

Yingxian Zhang, Aijun Liu, Xiaofei Pan +2 more

We propose a generalization belief propagation (BP) decoding algorithm based on particle swarm optimization (PSO) to improve the performance of the polar codes. Through the analysis of the existing BP decoding algorithm, we first introduce a probability modifying factor to each node of the BP decoder, so as to enhance the error correcting capacity of the decoding. Then, we generalize the BP decoding algorithm based on these modifying factors and drive the probability update equations for the proposed decoding. Based on the new probability update equations, we show the intrinsic relationship of the existing decoding algorithms. Finally, in order to achieve the best performance, we formulate an optimization problem to find the optimal probability modifying factors for the proposed decoding algorithm. Furthermore, a method based on the modified PSO algorithm is also introduced to solve that optimization problem. Numerical results show that the proposed generalization BP decoding algorithm achieves better performance than that of the existing BP decoding, which suggests the effectiveness of the proposed decoding algorithm.

Mathematical Problems in Engineering•Jan 1, 2014•5 citations

Modified BP Decoding Algorithms Combined with GA for Low-Density Parity Check Codes

Zerong Deng, Xingcheng Liu, Man Teng

In this paper we propose algorithms which combine Belief-propagation (BP) decoding algorithm with genetic algorithm (GA). The main idea is to improve the performance of traditional BP decoding algorithm by efficiently using the belief of variable nodes passing to check nodes. By considering the belief as genes, the proposed algorithms mainly employ the mutation operation in GA, and change the genes¿ amplitudes (either increase or decrease) when updating the check nodes¿ information. First, we explore that the marriage of the GA and BP decoding algorithm is reasonable. Three algorithms are proposed accordingly. Proposed algorithm I mutates chosen genes by amplitude enhancement, while proposed algorithm II by amplitude reduction. Finally, proposed algorithm III is a mixture of the former two. From computer simulation results, we show that for short and middle length LDPC codes, our proposed algorithms can improve both BER (bit error rate) and FER (frame error rate) performance over traditional BP decoding algorithm, with slight modification of traditional BP decoding algorithm and little increase of computation complexity.

International Conference on Computational Intelligence and Security (CIS)•Dec 1, 2008•6 citations

A Differential Binary Message-Passing LDPC Decoder

Nastaran Mobini, Amir H. Banihashemi, Saied Hemati

In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.

Globecom•Nov 1, 2007•16 citations
Message-Passing is the main decoding algorithm for Low-Density Parity Check (LDPC) Codes, in which Logarithmic Belief Propagation (Log-BP) algorithm is the most popularly used one. Particle Swarm Optimization (PSO) can also be regarded as an optimization algorithm by message-passing, which makes it possible to combine Log-BP algorithm with PSO. PSO was introduced into Log-BP algorithm by regarding all messages that bit nodes send to check nodes as the swarm with each message individually as a particle. Move the particles around in the search-space by certain iterations in each BP iteration processing, guided by the two best current values respectively found by particles themselves and that of the whole swarm. Those two best values were continually updated in each PSO iteration. In this way, the output of decoder is more consistent with accurate input sequence, in other words, the decoder performance was improved. Simulation results show that this new algorithm combined with Log-BP and PSO can get an additional 0.1 dB coding gain at Bit Error Rate (BER) of 10-5compared with Log-BP algorithm.
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.
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 in this paper a new method for improving the decoding of the LDPC (low-density parity check) codes by optimising the log-SPA (sum-product algorithm). Currently, the LDPC codes give very good results with iterative decoding algorithm, log-SPA, based on the propagation confidence BP (belief propagation). To improve the existing log-SPA, we propose a decoding algorithm (log-SPA modified), which minimises the error decoding of words that could not be previously decoded. This algorithm is based on the dependency between the weight of the syndrome and the weight of the error sequence generated during iterations of decoding. Simulations illustrate the performance of our approach compared with classical LDPC code based on log-SPA.
We propose a generalization belief propagation (BP) decoding algorithm based on particle swarm optimization (PSO) to improve the performance of the polar codes. Through the analysis of the existing BP decoding algorithm, we first introduce a probability modifying factor to each node of the BP decoder, so as to enhance the error correcting capacity of the decoding. Then, we generalize the BP decoding algorithm based on these modifying factors and drive the probability update equations for the proposed decoding. Based on the new probability update equations, we show the intrinsic relationship of the existing decoding algorithms. Finally, in order to achieve the best performance, we formulate an optimization problem to find the optimal probability modifying factors for the proposed decoding algorithm. Furthermore, a method based on the modified PSO algorithm is also introduced to solve that optimization problem. Numerical results show that the proposed generalization BP decoding algorithm achieves better performance than that of the existing BP decoding, which suggests the effectiveness of the proposed decoding algorithm.
In this paper we propose algorithms which combine Belief-propagation (BP) decoding algorithm with genetic algorithm (GA). The main idea is to improve the performance of traditional BP decoding algorithm by efficiently using the belief of variable nodes passing to check nodes. By considering the belief as genes, the proposed algorithms mainly employ the mutation operation in GA, and change the genes¿ amplitudes (either increase or decrease) when updating the check nodes¿ information. First, we explore that the marriage of the GA and BP decoding algorithm is reasonable. Three algorithms are proposed accordingly. Proposed algorithm I mutates chosen genes by amplitude enhancement, while proposed algorithm II by amplitude reduction. Finally, proposed algorithm III is a mixture of the former two. From computer simulation results, we show that for short and middle length LDPC codes, our proposed algorithms can improve both BER (bit error rate) and FER (frame error rate) performance over traditional BP decoding algorithm, with slight modification of traditional BP decoding algorithm and little increase of computation complexity.
In this paper, we propose a binary message-passing algorithm for decoding low-density parity-check (LDPC) codes. The algorithm substantially improves the performance of purely hard-decision iterative algorithms with a small increase in the memory requirements and the computational complexity. We associate a reliability value to each nonzero element of the code's parity-check matrix, and differentially modify this value in each iteration based on the sum of the extrinsic binary messages from the check nodes. For the tested random and finite-geometry LDPC codes, the proposed algorithm can achieve performance as close as 1.3 dB and 0.7 dB to that of belief propagation (BP) at the error rates of interest, respectively. This is while, unlike BP, the algorithm does not require the estimation of channel signal to noise ratio. Low memory and computational requirements and binary message-passing make the proposed algorithm attractive for high-speed low-power applications.