International Conference on Computational Intelligence and Security (CIS)

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

Zerong Deng, Xingcheng Liu, Man Teng

Published Dec 1, 2008• 6 citations

Abstract

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.

DOI: 10.1109/cis.2008.169

Related papers

Fast decoding of low density parity check codes

Nassib Laouini, Larbi Ben Hadj Slama, Ammar Bouallègue

The Layered Belief Propagation L-BP algorithm is is a modified Belief Propagation BP algorithm, where the check nodes are divided in subgroups called layers and each iteration is broken into multiple sub-iterations. In this paper, we consider layered belief propagation decoding and propose an efficient variable node layering for decoding LDPC codes that performs well. We compare the performance of the first introduced LDPC decoding algorithm BP and Layered BP using check node layering with Layered BP using variable node layering in terms of bit error rate (BER). We show that the convergence for decoding LDPC codes is increasing by using a simple and efficient layering strategy.

International Symposium on High-capacity Optical Networks and Enabling TechnologiesDec 1, 20125 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 ConferenceSep 8, 200615 citations

Optimized decoder for low-density parity check codes based on genetic algorithms

Hajar El Ouakili, Mohammed El Ghzaoui, Rachid El Alami

Low-density parity check (LDPC) codes, are a family of error-correcting codes, their performances close to the Shannon limit make them very attractive solutions for digital communication systems. There are several algorithms for decoding LDPC codes that show great diversity in terms of performance related to error correction. Also, very recently, many research papers involved the genetic algorithm (GA) in coding theory, in particular, in the decoding linear block codes case, which has heavily contributed to reducing the bit error rate (BER). In this paper, an efficient method based on the GA is proposed and it is used to improve the power of correction in terms of BER and the frame error rate (FER) of LDPC codes. Subsequently, the proposed algorithm can independently decide the most suitable moment to stop the decoding process, moreover, it does not require channel information (CSI) making it adaptable for all types of channels with different noise or intensity. The simulations show that the proposed algorithm is more efficient in terms of BER compared to other LDPC code decoders.

International Journal of Power Electronics and Drive Systems/International Journal of Electrical and Computer EngineeringApr 4, 20240 citations

New low complexity belief propagation decoding of low density parity check codes

Liu Ji-lin

An improved belief propagation(BP) decoding scheme was put forward to solve the high complexity and low decoding efficiency problem of BP in low density parity check(LDPC) codes.Because different bit nodes and check nodes have different reliability and contribute differently to BP decoding;the proposed decoding scheme employs a differentiate rule based on lawless check number and pseudo posterior probability to evaluate every bit's reliability before each step of iteration;The nodes have little lawless check number and large pseudo posterior probability are supposed to have higher reliability.The bits with high reliability need not to be updated by the decoder.Simulation shows that the proposed BP decoding algorithm can reduce the computational load and increase the decoding efficiency significantly.

Journal of Zhejiang University(Engineering Science)Jan 1, 20081 citation

Check-Belief Propagation Decoding of LDPC Codes

Wu Guan, Liping Liang

Variant belief propagation (BP) algorithms are applied to low-density parity-check (LDPC) codes. However, conventional decoders suffer from a large resource consumption due to gathering messages from all the neighbour variable-nodes and/or check-nodes through cumulative calculations. In this paper, a check-belief propagation (CBP) decoding algorithm is proposed. Check-belief is used as the probability that the corresponding parity-check is satisfied. All check-beliefs are iteratively enlarged in a sequential recursive order, and successful decoding will be achieved after the check-beliefs are all big enough. Compared to previous algorithms employing a large number of cumulative calculations to gather all the neighbour messages, CBP decoding can renew each check-belief by propagating it from one check-node to another through only one variable-node, resulting in a low complexity decoding with no cumulative calculations. The simulation results and analyses show that the CBP algorithm provides little error-rate performance loss in contrast with the previous BP algorithms, but consumes much fewer calculations and memories than them. It earns a big benefit in terms of complexity.

arXiv:2305.05286IEEE Transactions on CommunicationsAug 24, 202316 citations

Decoding of non‐binary low‐density parity‐check codes based on the genetic algorithm and applications over mobile fading channels

Xingcheng Liu, Chulong Liang, Yuanbin Zhang +1 more

In this study, an efficient decoding algorithm is proposed to decode non‐binary low‐density parity‐check (LDPC) codes. The algorithm is derived from the belief‐propagation (BP) decoding with genetic algorithm of binary LDPC codes. For the proposed algorithm, two decoding constraints are introduced to determine variable nodes which are considered highly reliable. The messages from these highly reliable variable nodes are then magnified with an appropriate parameter γ . This process can make the messages propagate in the Tanner graph more efficiently. Simulation results show that, compared with the fast Fourier transform‐based BP algorithm, the proposed algorithm can have an equal or better performance in low bit‐error‐rate region over both the additive white Gaussian noise channels and the mobile fading channels.

IET CommunicationsOct 8, 20150 citations