TURKISH JOURNAL OF ELECTRICAL ENGINEERING & COMPUTER SCIENCES

A second order approximation to reduce the complexity of LDPC decoders based on Gallager's approach

Aykut Kalaycıoğlu, O. Üreten, Hakkı Gökhan İlk

Published Jan 1, 2010• 0 citations

Abstract

A piece-wise second order approximation to the f (x) = -log [tanh (x/2)] function is proposed to reduce the computational complexity of LDPC decoder's utilizing Log-Likelihood Ratio Belief Propagation (LLR-BP) algorithm based on Gallager's approach. Simulation results show that the proposed low complexity approximation doesn't cause BER performance degradation.

DOI: 10.3906/elk-0811-14

Related papers

A Novel LLR-BP Algorithm for LDPC Codes Based on Taylor Series and Least Squares

Xing Ru Zhang, Jianping Li, Chao Shi Cai

An effective log-likelihood-ratio-based belief propagation (LLR-BP) algorithm is proposed. It can reduce computational complexity of decoding algorithm for Low Density Parity Check (LDPC) codes. By using the Taylor series and least squares, high order multiplication based on the hyperbolic tangent (tanh) rule is converted to a first-order multiplication and addition after simplification. Moreover, all the logarithmic and exponential operations disappear without significant loss of the decoding performance. The simulation results show that the performance of the proposed scheme is similar to the general LLR-BP. In particular, we show that the modified algorithm with low complexity can achieve better BER than the other decoding algorithm in high signal-to-noise ratio region.

Applied Mechanics and MaterialsNov 1, 20130 citations

Improved Decoding Algorithms Based on Oscillation Log-likelihood Ratio for Low-density Parity Check Codes

DONG Zijian -, BI Xuyin -

Several decoding algorithms based on oscillation Log-likelihood ratio (LLR) for Lowdensity parity-check (LDPC) codes are investigated in this paper, based on which, an improved decoding algorithm which uses the accumulated LLR as the final bit decision merit is proposed. This approach improves the decoding performance with only a very small increase in storage and computation. Combined with normalized belief-propagation (BP), two algorithms are given, which are named as accumulate normalized BP (ACC-Nor-BP) and compare-add normalized BP (CA-Nor-BP). The storage requirements and computational complexity of ACC-Nor-BP is lower than that of CA-Nor-BP and CA-BP, but performance is close to the CA-Nor-BP and better than CA-BP; therefore ACC-Nor-BP algorithm is an effectively improved BP algorithm which has a good balance between performance and complexity.

INTERNATIONAL JOURNAL ON Advances in Information Sciences and Service SciencesSep 30, 20111 citation

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 TechnologiesApr 1, 20151 citation

Improved LDPC decoding algorithms based on min-sum algorithm

Y.V. A. C. Kumara, Chandika Bandara Wavegedara

Low-Density Parity check (LDPC) codes offer high-performance error correction near the Shannon limit which employs large code lengths and some iterations in the decoding process. The conventional decoding algorithm of LDPC is the Log Likelihood Ratio based Belief Propagation (LLR BP) which is also known as the `Sum-Product algorithm' which gives the best decoding performance and requires the most computational complexity and implementations with increased hardware complexity. Another simpler variant of this algorithm is used which is known as `min-sum algorithm' which reduces computational complexity as well as hardware complexity but with reduced accuracy. This paper analyzes the reason min-sum algorithm is more prone to errors when compared to the sum-product algorithm, and puts forward two improved algorithms which improve the performance of the min-sum algorithm with comparable algorithmic complexity.

Moratuwa Engineering Research Conference (MERCon)Apr 1, 20168 citations

Magnetization Performance of LDPC Reduced-Complexity Decoding Algorithms

Manel Abdelhedi, Omessaad Hamdi, Ammar Bouallègue

Low-density parity-check (LDPC) codes are very efficient for communicating reliably through a noisy channel. N.Sourlas [1] showed that LDPC codes, which revolutionize the codes domain and used in many communications standards, can be mapped onto an Ising spin systems. Besides, it has been shown that the Belief-Propagation (BP) algorithm, the LDPC codes decoding algorithm, is equivalent to the Thouless- Anderson-Palmer (TAP) approach [2]. Unfortunately, no study has been made for the other decoding algorithms. In this paper, we develop the Log-Likelihood Ratios-Belief Propagation (LLR-BP) algorithm and its simplifications the BP-Based algorithm and the λ-min algorithm with the TAP approach. We present the performance of these decoding algorithms using statistical physics argument i.e., we present the performance as function of the magnetization.

International Journal of Communications Network and System SciencesJan 1, 20100 citations

Reduced-Complexity Belief Propagation Decoding for LDPC Codes

Heping Wan, Joonyoung Cho, Min Jang +1 more

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.

IEEE AccessJan 1, 20260 citations