International Conference on Wireless Communications, Networking and Mobile Computing

An improved decoding algorithm of low-density parity-check codes

Yongqiang Deng, Guangxi Zhu, Liu Wenming, Yijun Mo

Published Dec 10, 2005• 0 citations

Abstract

In this paper, the decoding algorithm of low-density parity-check (LDPC) codes is analyzed, and a new decoding algorithm based on the belief propagation (BP) algorithm to eliminate the influence of cycles in the factor graph is proposed. In the traditional BP algorithm, the cycles of factor graph sends message back to its source, and this decreases the decoding performance. The new algorithm records each cycle's path and length of each node, and cuts off the path by which message is propagated when the message comes back. It can advance the decoding performance by protect the message of good quality be propagated as widely as possible. Our results of simulation show that the performance of new algorithm is not worse than that of traditional BP algorithm in the low SNR channel and the new algorithm significantly outperform traditional BP algorithm in good channel condition.

DOI: 10.1109/wcnm.2005.1544078

Related papers

A Study on Low Complexity Decoding Algorithm of LDPC Codes

Yong Deng

In this paper,the decoding algorithm of low-density parity-check(LDPC)codes is analyzed,and a new decoding algorithm based on the belief propagation(BP)algorithm to eliminate the influence of cycles in the factor graph is proposed. In the traditional BP algorithm,the cycles of factor graph will send message back to its source,and this will decrease the decoding performance. The new algorithm records each cycle’s path and length of each node,and cuts off the path by which message is propagated when the message will come back. It can advance the decoding performance by protect the message of good quality be propagated as widely as possible. Our results of simulation show that the performance of new algorithm is not worse than that of traditional BP algorithm in the low SNR channel and the new algorithm significantly outperform traditional BP algorithm in good channel condition.

Jan 1, 20060 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 SystemsFeb 28, 20172 citations

Improved LDPC-like BPL Decoding Algorithm for Polar Code

Rui Guo, Chenfei Zhang, Chen Lou

To improve the performance of BP decoding for polar codes, researchers have developed a Belief Propagation List (BPL) decoding algorithm by executing multiple BP decoders in parallel.This algorithm outperforms traditional BP decoding based on single graph decoding, although it sacrifices some complexity and delay.Unlike this basic Polar-BPL decoding mentioned above, a low-density parity check like (LDPC-like) BPL decoding algorithm has been introduced into polar codes.This algorithm performs more efficient BP decoding iterations on sparse graphs.To further reduce the complexity and delay of LDPC-like BPL, and avoid analyzing all sparse graphs, this article proposes an improved LDPC-like BPL (ILDPC-like BPL) decoding algorithm based on selecting factor graphs.This algorithm analyzes differences in permuted factor graphs and selects these graphs with non-convergent decoding results to form a decoding list, allowing decoding to be completed with fewer graphs traversed and iterations, thereby reducing complexity and delay.On this basis, to improve the reliability of this algorithm, this article further adds a path metric (PM) mechanism, which can dynamically evaluate different sparse graphs' results in parallel decoding.The simulation results show that compared with LDPC-like BPL (random scheme), ILDPC-like BPL improves decoding performance while reducing decoding delay and complexity; Compared with basic Polar-BPL (cycle-shift scheme), this algorithm greatly reduces decoding delay and complexity while achieving similar performance.

KSII Transactions on Internet and Information SystemsJan 31, 20250 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 ComputersJan 1, 20190 citations

Belief-Propagation-Approximated Decoding of Low-Density Parity-Check Codes

Ping Zhang

In this paper, we propose a new reduced-complexity decoding algorithm of Low-Density Parity-Check (LDPC) codes, called Belief-Propagation-Approximated (BPA) algorithm, which utilizes the idea of normalization and translates approximately the intricate nonlinear operation in the check nodes of the original BP algorithm to only one operation of looking up the table. The normalization factors can be obtained by simulation, or theoretically. Simulation results demonstrate that BPA algorithm exhibits fairly satisfactory bit error performance on the Additive White Gaussian Noise (AWGN) channel.

中国邮电高校学报：英文版Jan 1, 20041 citation

A Modified belief propagation decoding algorithm for low-density parity-check codes based on oscillating iteration

Bao Jian-rong

According to no-convergence of falsely oscillating iteration in the low-density parity-check(LDPC) decoding at the range from medium to high SNRs(Signal to Noise Ratios),we propose a modified LDPC belief propagation(BP) decoding algorithm,i.e.soft value zero-forcing BP algorithm.By setting extrinsic information of the oscillating iteration bit nodes into zero,the impact on the iteratively decoding from false channel information is greatly reduced.And it also improves the performance of the decoding algorithm.Furthermore,a decision criterion of oscillating iteration nodes is presented to increase the accuracy of the decision.Simulation results show that the proposed algorithm has better decoding performance than that of the BP algorithm with the same iterations at medium and high SNRs.

Journal of Circuits and SystemsJan 1, 20120 citations