We propose a modified belief propagation algorithm that uses node elimination for bit nodes of large log-likelihood ratio. With this algorithm, we can reduce decoding complexity and improve performance by enhancing the cycle properties. Simulation results show that the decoding complexity is reduced and the proposed algorithm outperforms the belief propagation algorithm in the high-Eb/Noregion
We propose a modified belief propagation algorithm that uses node elimination for bit nodes of large log-likelihood ratio. With this algorithm, we can reduce decoding complexity and improve performance by enhancing the cycle properties. Simulation results show that the decoding complexity is reduced and the proposed algorithm outperforms the belief propagation algorithm in the high-Eb/Noregion
Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.
Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.
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.
Two methods are proposed to reduce the complexity of the belief propagation (BP) decoding for low-density parity-check (LDPC) codes, with the focus on the layered decoding for quasi-cyclic LDPC (QC-LDPC) codes. The two methods can be separately incorporated into the layered decoding procedures and combined seamlessly to provide the two-fold complexity reduction. In the first method, the message updates regarding a subset of variable nodes are omitted. To construct the subset, the most reliable bit-level channels, derived fromM-ary input channels, are identified. Then, we select the variable nodes with initial log-likelihood ratios (LLRs) exceeding a threshold among the ones assigned to the most reliable bit-level channels to form the subset. The threshold is designed and adjusted based on characteristics of the most reliable bit-level channels. Our numerical results demonstrate that the first method significantly reduces the complexity with negligibly impacting the error-correcting performance. In the second method, each layer of base graphs of QC-LDPC codes uses either sum-product algorithm (SPA) or min-sum algorithm (MSA) to update LLRs. A degree-based algorithm is presented to determine the layers employing either SPA or MSA. We compare with two intuitive methods: 1) applying SPA to randomly selected layers and MSA to the remaining layers, and 2) applying SPA to the core layers of 5G NR LDPC codes and MSA to the remaining layers. According to the numerical results, the degree-based algorithm maximally reduces the complexity while maintaining the same performance. To evaluate the joint method, the first method is applied on top of the second method. Further complexity reduction is achieved without degrading the performance of the second method.
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.
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