IEEE International Symposium on Circuits and Systems proceedings

Symbol-Based Algorithms for Decoding Binary LDPC Codes with Higher-Order Modulations

Jingbo Liu, Jingyang Yuan, Jin Sha

Published May 1, 2019• 1 citation

Abstract

Low-density parity-check (LDPC) codes are widely used in communication systems. When user messages are encoded by binary LDPC codes and transmitted with higher-order modulations, bits composing the same modulated symbol are generally correlated. Traditional soft-decision decoding algorithms for binary LDPC codes like sum-product algorithm (SPA) and min-sum algorithm (MSA) update messages only based on log-likelihood ratio (LLR) of bits, and correlations introduced by modulation are not utilized. In this paper, symbol-based SPA and MSA (S-SPA and S-MSA) which incorporate symbol-level information in the decoding procedures are proposed to provide an alternative low-cost way to better utilize available information. By narrowing the search space of symbols based on bit-level information, the complexities of the proposed algorithms are independent of modulation order. S-SPA and S-MSA achieve better error-correction performances than SPA and MSA with little additional complexities and S-MSA is friendly to hardware design of LDPC decoder.

DOI: 10.1109/iscas.2019.8702329

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

Design and implementation of decoders for error correction in high-speed communication systems.

Joan Marc Català Pérez

This thesis is focused on the design and implementation of binary low-density parity-check (LDPC) code decoders for high-speed modern communication systems. The basic of LDPC codes and the performance and bottlenecks, in terms of complexity and hardware efficiency, of the main soft-decision and hard-decision decoding algorithms (such as Min-Sum, Optimized 2-bit Min-Sum and Reliability-based iterative Majority-Logic) are analyzed. The complexity and performance of those algorithms are improved to allow efficient hardware architectures.\n\nA new decoding algorithm called One-Minimum Min-Sum is proposed. It reduces considerably the complexity of the check node update equations of the Min-Sum algorithm. The second minimum is estimated from the first minimum value by a means of a linear approximation that allows a dynamic adjustment. The Optimized 2-bit Min-Sum algorithm is modified to initialize it with the complete LLR values and to introduce the extrinsic information in the messages sent from the variable nodes. Its variable node equation is reformulated to reduce its complexity. Both algorithms were tested for the (2048,1723) RS-based LDPC code and (16129,15372) LDPC code using an FPGA-based hardware emulator. They exhibit BER performance very close to Min-Sum algorithm and do not introduce early error-floor. \n\nIn order to show the hardware advantages of the proposed algorithms, hardware decoders were implemented in a 90 nm CMOS process and FPGA devices based on two types of architectures: full-parallel and partial-parallel one with horizontal layered schedule. The results show that the decoders are more area-time efficient than other published decoders and that the low-complexity of the Modified Optimized 2-bit Min-Sum allows the implementation of 10 Gbps decoders in current FPGA devices. \n\nFinally, a new hard-decision decoding algorithm, the Historical-Extrinsic Reliability-Based Iterative Decoder, is presented. This algorithm introduces the new idea of considering hard-decision votes as soft-decision to compute the extrinsic information of previous iterations. It is suitable for high-rate codes and improves the BER performance of the previous RBI-MLGD algorithms, with similar complexity.

Jul 7, 20170 citations

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

Difference to sum ratio factor based min-sum decoding for Low Density Parity Check Codes

Mohammad Rakibul Islam, Khandaker Sultan Mahmood, Md. Moshiur Rahman Farazi +3 more

Low Density Parity Check Codes (LDPC) give groundbreaking performance which is known to approach Shannon's limits for sufficiently large block length. Historically and recently, LDPC have been known to give superior performance than concatenated coding. In the following paper, a proposal to modify the standard Min-Sum (MS) algorithm for decoding LDPC codes is presented. This is done by introduction of a difference to sum ratio factor, κ in the check to bit node updating process. The algorithm is further extended by implementing hard decision of the Bit-Flipping (BF) algorithm over the soft decision of MS algorithm. Simulation results demonstrate that the proposed algorithms are effective in imparting a better performance in terms of a lower bit error rate (BER) at medium to high signal to noise ratio (SNR) when compared to the traditional MS algorithm while adding fair amount of complexity.

Computing, Communications and IoT Applications (ComComAp)Jan 1, 20121 citation

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

Design of Low-Density Parity-Check Codes and Their Decoding Algorithms

조성혜

In this thesis, we propose low-complexity designing algorithms for non-binary low-density parity-check (NB-LDPC) codes over GF(q) with low error floor and low-complexity decoding algorithms for binary LDPC codes. We first propose a low-complexity designing algorithm for for NB-LDPC codes over GF(q) based on message-passing algorithms. Short cycles in an NB-LDPC code may be even more harmful to its performance if they do not satisfy the so-called full rank condition (FRC). This is because they may induce low-weight codewords or absorbing sets in that case. Thus, it is crucial to count the number of short cycles not satisfying the FRC as well as the number of short cycles for analyzing the performance of an NB-LDPC code. In order to count those cycles, we first develop a novel message-passing algorithm and identify how it is related to the FRC.We then propose a low-complexity algorithmfor counting the number of short cycles not satisfying the FRC in an NB-LDPC code, as well as the number of short cycles. The proposed algorithm is not only theoretically validated, but its computational and storage complexities are also computed. It does not require cycle enumeration with high complexity, and therefore is still feasible even in the case of large code length, say ≤ 5000, unlike the conventional methods. Based on it, we also provide a locally optimal rule to choose a nonzero element for a given edge and propose a low-complexity algorithm for designing an NB-LDPC code with low error floor. Furthermore, several design examples are presented to verify the validity of the proposed design algorithm. Secondly, we propose a low-complexity decoding algorithm for binary LDPC codes over the binary symmetric channel (BSC). The min-sum (MS) algorithm is a low-complexity decoding algorithm for binary LDPC codes and has lower computational complexity than the sum-product algorithm (SPA). Since the MS algorithm is an approximation of the SPA, it has performance degradation. Furthermore, reducing the number of bits for representing messages to two in a decoding algorithm for further reducing computational and storage complexities, causes significant performance losses. In order to minimize the performance degradation and computational and storage complexities, we propose a low-complexity decoding algorithm which uses several decoders with two-bit precision for binary LDPC codes over the BSC. The proposed algorithm adaptively changes decoders according to the number of unsatisfied check nodes at each iteration. Compared with the SPA using floating-point operations, the proposed decoding algorithm greatly reduces computational and storage complexities with negligible performance losses. Numerical results show that the proposed decoding algorithm has similar performance to the SPA with floating-point operations over the BSC. In the last part of this thesis, low-complexity decoding algorithms of binary LDPC codes for the core layer at fixed receivers in ATSC 3.0 are proposed. Gallager’s decoding algorithms …

Jan 1, 20180 citations