Asilomar Conference on Signals, Systems and Computers (ACSSC)

A Hybrid Early Decision-Probability Propagation Decoding Algorithm for Low-Density Parity-Check Codes

Anton Blad, Oscar Gustafsson, Lars Wanhammar

Published Mar 22, 2006• 3 citations

Abstract

Low-density parity-check codes have recently received extensive attention as a forward error correction scheme in a wide area of applications. The decoding algorithm is inherently parallelizable, allowing communication at high speeds. One of the main disadvantages, however, is large memory requirements for interim storing of decoding data. In this paper, we investigate the performance of a hybrid decoding algorithm, using an approximating early decision algorithm and a regular probability propagation algorithm. When the early decision algorithm fails, the block is re-decoded using a probability propagation decoder. As almost all errors are detectable, the error correction performance of the hybrid algorithm is negligibly detonated. However, simulations still achieve a 32% decrease of memory accesses

DOI: 10.1109/acssc.2005.1599817

Related papers

An early decision decoding algorithm for LDPC codes using dynamic thresholds

Anton Blad, Oscar Gustafsson, Lars Wanhammar

Low-density parity-check codes have recently received extensive attention as a forward error correction scheme in a wide area of applications. The decoding algorithm is inherently parallelizable, allowing communication at high speeds. One of the main disadvantages, however, is large memory requirements for interim storing of decoding data. In this paper, we investigate a modification to the decoding algorithm, using early decisions for bits with high reliabilities. This reduces the amount of messages passed by the algorithm, which can be expected to reduce the switching activity of a hardware implementation. While direct application of the modification results in severe performance penalties, we show how to adapt the algorithm to reduce the impact, resulting in a negligible decrease in error correction performance.

European Conference on Circuit Theory and DesignOct 11, 200616 citations

Early decision decoding methods for low-density parity-check codes

Anton Blad, Oscar Gustafsson, Lars Wanhammar

Abstract — Low-density parity-check codes have recently received extensive attention as a forward error correction scheme in a wide area of applications. The decoding algorithm is inherently parallelizable, allowing communication at high speeds. One of the main disadvantages, however, is large memory requirements for interim storing of decoding data. In this paper, we investigate a modification to the decoding algorithm, using early decisions for bits with high reliabilities. Currently, there are two early decision schemes proposed. We compare their theoretical performances and their suitability for hardware implementation. We also propose a new decision method, which we call weak decisions, that offers an increase in performance by a factor of two. 1

System-on-Chip ConferenceJan 1, 20051 citation

Two-Stage Hybrid decoding for Low-Density Parity-Check codes

Hany R. Zeidan, Maha Mohamed Elsabrouty

Low-density parity check (LDPC) codes are gaining increased attention in information theory field. However one of the main problems facing usage of these codes in communication systems is its high complexity decoding scheme that results in high decoding delay. Such a delay is not acceptable in many applications. This paper presents, a new hybrid decoding scheme. The proposed scheme mixes between soft-decision and hard-decision algorithms and provides a good tradeoff between error performance and decoding delay as proved by simulation results.

International Conference on Innovations in Information TechnologyNov 1, 20072 citations

Early-Decision Decoding of LDPC Codes

Anton Blad

Since their rediscovery in 1995, low-density parity-check (LDPC) codes have received wide-spread attention as practical capacity-approaching code candidates. It has been shown that the class of codes can perform arbitrarily close to the channel capacity, and LDPC codes are also used or suggested for a number of important current and future communication standards. However, the problem of implementing an energy-efficient decoder has not yet been solved. Whereas the decoding algorithm is computationally simple, withuncomplicated arithmetic operations and low accuracy requirements, the random structure and irregularity of a theoretically well-defined code does not easily allow efficient VLSI implementations. Thus the LDPC decoding algorithm can be said to be communication-bound rather than computation-bound. In this thesis, a modification to the sum-product decoding algorithm called early-decision decoding is suggested. The modification is based on the idea that the values of the bits in a block can be decided individually during decoding. As the sum-product decoding algorithm is a soft-decision decoder, a reliability can be defined for each bit. When the reliability of a bit is above a certain threshold, the bit can be removed from the rest of the decoding process, and thus the internal communication associated with the bit can be removed in subsequent iterations. However, with the early decision modification, an increased error probability is associated. Thus, bounds on the achievable performance as well as methods to detect graph inconsistencies resulting from erroneous decisions are presented. Also, a hybrid decoder achieving a negligible performance penalty compared to the sum-product decoder is presented. With the hybrid decoder, the internal communication is reduced with up to 40% for a rate-1/2 code with a length of 1152 bits, whereas increasing the rate allows significantly higher gains. The algorithms have been implemented in a Xilinx Virtex 5 FPGA, and the resulting slice utilization andenergy dissipation have been estimated. However, due to increased logic overhead of the early decision decoder, the slice utilization increases from 14.5% to 21.0%, whereas the logic energy dissipation reduction from 499 pJ to 291 pJ per iteration and bit is offset by the clock distribution power, increased from 141 pJ to 191 pJ per iteration and bit. Still, the early decision decoder shows a net 16% estimated decrease of energy dissipation.

Jan 1, 20091 citation

Low-density Parity-Check decoding Algorithms

Florent Pirou

Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.

Jan 1, 20040 citations

EFFICIENT DECODING ALGORITHMS FOR LOW DENSITY PARITY CHECK CODES

Anton Blad

Low-density parity-check codes have recently received much attention because of their excellent performance and the availability of a simple iterative decoder. The decoder, however, requires large amounts of memory, which causes problems with memory consumption. We investigate a new decoding scheme for low density parity check codes to address this problem. The basic idea is to define a reliability measure and a threshold, and stop updating the messages for a bit whenever its reliability is higher than the threshold. We also consider some modifications to this scheme, including a dynamic threshold more suitable for codes with cycles, and a scheme with soft thresholds which allow the possibility of removing a decision which have proved wrong. By exploiting the bits different rates of convergence we are able to achieve an efficiency of up to 50% at a bit error rate of less than 10^-5. The efficiency should roughly correspond to the power consumption of a hardware implementation of the algorithm.

Jan 1, 20052 citations