International Symposium on Turbo Codes and Iterative Information Processing

Reduced-complexity serial min-sum decoding

Hironori Uchikawa, Kohsuke Harada, 康彦田邉

Published Sep 1, 2008• 0 citations

Abstract

We propose a complexity-reducing method for serial min-sum decoding that reduces the number of check nodes to process during an iteration. The check nodes to skip are chosen based on the reliability, a syndrome and a log-likelihood-ratio (LLR) value, of the incoming messages. The proposed method is evaluated by computer simulations and shown to reduce the decoding complexity up to 70 % compared with conventional serial min-sum decoding with small fractional decibel degradation in error correction performance.

DOI: 10.1109/turbocoding.2008.4658688

Related papers

Complexity-Reducing Algorithm for Serial Scheduled Min-Sum Decoding of LDPC Codes

Hironori Uchikawa, Kohsuke Harada

We propose a complexity-reducing algorithm for serial scheduled min-sum decoding that reduces the number of check nodes to process during an iteration. The check nodes to skip are chosen based on the reliability, a syndrome and a log-likelihood-ratio (LLR) value, of the incoming messages. The proposed algorithm is evaluated by computer simulations and shown to reduce the decoding complexity about 20% compared with a conventional serial scheduled min-sum decoding with small fractional decibel degradation in error correction performance.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesJan 1, 20091 citation

Reduced-Complexity Decoding of LDPC Codes

J. Chen, Ajay Dholakia, Evangelos S. Eleftheriou +2 more

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.

IEEE Transactions on CommunicationsAug 1, 2005952 citations

Reduced-Complexity Decoding of LDPC Codes

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.

IEEE Transactions on CommunicationsJul 1, 200527 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

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

Reduced-complexity offset min-sum check node unit for layered 5G LDPC decoder

Vladimir L. Petrović, Mezeni El

This paper presents a novel approach for the reduced-complexity Min-Sum (MS) decoding of low density parity check (LDPC) codes in the partially parallel layered decoder architecture, which contains a large number of serial check node processors. Reduced complexity is obtained by using the variant of the single-minimum Offset Min-Sum (smOMS) algorithm that approximates a second minimum with the addition of the variable weight parameter to the minimum value. Although the reduced-complexity MS algorithms primarily reduce hardware resources in fully parallel implementations, the results showed that a considerable reduction can be obtained if serial check node processors are used. The paper also proposes a better subminimum estimation for irregular codes from 5G new radio (5G NR). The method uses smaller subminimum estimation weights in check nodes with a higher degree and higher weights in check nodes with a smaller degree, which leads to the significant improvement in the SNR performance. Additionally, it is shown that SNR performance can be further improved by applying offset before minimum calculation, which differs from conventional Min-Sum approaches.

Telfor JournalJan 1, 20210 citations