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•15 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

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 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

A modified Min-Sum algorithm for low-density parity-check codes

Wei Han, Jianguo Huang, WU Fang-fei

A modified Min-Sum algorithm for low-density parity check codes is proposed in this paper. The inaccurate check node messages of the Min-Sum algorithm compared to the belief propagation (BP) algorithm are compensated by modified variable node messages, which is different from the normalized Min-Sum algorithm. The modified factor is obtained before decoding program and only one extra multiplication is needed in one cycle. So the increased complexity is fairly low. The simulation results show that the bit error rate (BER) and average number of iteration of the modified Min-Sum algorithm are very close to the BP algorithm, the modified algorithm can improve the BER performance compared to the Min-Sum algorithm while added complexity slightly.

Wireless Communications, Networking and Information Security•Jun 1, 2010•9 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.
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.
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.
A modified Min-Sum algorithm for low-density parity check codes is proposed in this paper. The inaccurate check node messages of the Min-Sum algorithm compared to the belief propagation (BP) algorithm are compensated by modified variable node messages, which is different from the normalized Min-Sum algorithm. The modified factor is obtained before decoding program and only one extra multiplication is needed in one cycle. So the increased complexity is fairly low. The simulation results show that the bit error rate (BER) and average number of iteration of the modified Min-Sum algorithm are very close to the BP algorithm, the modified algorithm can improve the BER performance compared to the Min-Sum algorithm while added complexity slightly.