IEEE Military Communications Conference (MILCOM)

A Computationally Efficient Selective Node Updating Scheme for Decoding of LDPC Codes

E. Cavus, Babak Daneshrad

Published Mar 22, 2006• 7 citations

Abstract

In this paper, we introduce a computationally efficient selective node update algorithm for the decoding of low-density parity check codes. Unlike the standard sum-product algorithm, where all bit and check nodes are updated at each decoding iteration, the developed algorithm only updates unreliable check and bit nodes. A simple reliability criteria is developed to determine the active bit and check nodes per decoding iteration. Based on the developed technique, significant computation reductions are achieved with very little or no loss in the BER performance of the LDPC codes. At a WER of 10-5, 91.8% and 72.7% check node and 80% and 41% bit node computation reductions are obtained for a (96, 48) and a (504, 252) LDPC code, respectively. The proposed method can be implemented with a slight modification to the standard sum-product decoding algorithm with negligible additional hardware complexity. From a hardware point of view, the proposed algorithm offers power reductions proportional to the computation savings and it leads to higher decoding speeds in serial implementations by decreasing the number of required memory accesses

DOI: 10.1109/milcom.2005.1605869

Related papers

Computationally efficient decoding of LDPC codes

E. Cavus, Babak Daneshrad

A computationally efficient algorithm for the decoding of low-density parity check codes is introduced. Instead of updating all bit and check nodes at each decoding iteration, the developed algorithm only updates unreliable check and bit nodes. A simple reliability criteria is developed to determine the active bit and check nodes per decoding iteration. Based on the developed technique, significant computation reductions are achieved with very little or no loss in the BER performance of the LDPC codes. The proposed method can be implemented with a slight modification to the sum–product algorithm with negligible additional hardware complexity.

Electronics LettersAug 26, 20091 citation

Fast convergence algorithm for decoding of low density parity check codes

Jin Xie, Liuguo Yin, Ning Ge +1 more

Abstract: In this paper, a fast-convergence algorithm is proposed for the decoding of low-density parity-check (LDPC) codes. By putting more weight on the message update from check node to variable node in current iteration, the proposed method speeds up the decoding significantly. Simulation results show that compared with the standard layered min-sum decoding algorithm, the proposed scheme may reduce about 1/6 iteration numbers for LDPC codes used in DVB-S2, with hardware complexity overhead less than 2%. Key–Words: LDPC code, fast convergence decoding algorithm, layered decoding, min-sum algorithm, hardware implementation 1

WSEAS TRANSACTIONS on COMMUNICATIONS archiveJul 1, 20091 citation

Novel Efficient Decoding Implementation of LDPC Codes

Wenbo Wang

As for the sum-product decoding algorithm of low density parity check(LDPC) codes,a difference-based decoding method is proposed.The main idea is shown as follows: the messages passed on the bipartite graph of LDPC are based on the probability differences,and the updates of both check nodes and message nodes are carried out on some special addition domain.As for the update of check nodes,only some lowest differences can be selected for reducing computational complexity.In contrast with the traditional log-likelyhood-ratio-based(LLR-based) decoding method,the proposed method has much lower complexity,while it has no obvious loss of performance and convergence.

Beijing Youdian Xueyuan xuebaoJan 1, 20071 citation

Efficient Difference-based Decoding Implementations of LDPC Codes

Zhanji Wu, Peng Mugen, Wang Wenbo +1 more

Efficient implementations of the sum-product algorithm (SPA) for decoding low-density parity-check (LDPC) codes using difference-based messages between bit nodes and check nodes are presented. As for the updates of check nodes, reduced- complexity derivatives are also put forward. As compared with the traditional Log-Likelihood-Ratio(LLR)-based decoding implementations, the proposed method has much lower complexity and latency, while it has no obvious loss of the error performance.

IEEE Communications LettersMay 1, 20083 citations

Techniques for the decoding of low density parity check codes: efficient simulation, algorithm improvement and implementation

Babak Daneshrad, Enver Çavuş

After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area. This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.

Jan 1, 20072 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