International Conference on Innovations in Information Technology

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

Hany R. Zeidan, Maha Mohamed Elsabrouty

Published Nov 1, 2007• 2 citations

Abstract

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.

DOI: 10.1109/iit.2007.4430491

Related papers

Modified Iterative Two-Stage Hybrid Decoding Algorithm for Low-Density Parity-Check (LDPC) Codes

Hany R. Zeidan, Maha Mohamed Elsabrouty

This paper considers a modified iterative version of the two-stage hybrid algorithm for decoding low-density parity- check (LDPC) codes. The hybrid-decision scheme is a decoding scheme used that combines two iterative decoding algorithms for decoding LDPC codes. This scheme is suitable for many applications such as audio and video transmission that are sensitive to time. The hybrid-decision scheme mixes between the characteristics of the soft-decision decoding scheme and the hard- decision decoding scheme to reduce the computational complexity of the whole decoding algorithm. The modification proposed in this paper is applied to the implementation-efficient reliability ratio weighted bit-flipping (IERRWBF) algorithm which represents hard-decision scheme in the hybrid algorithm. This modification is capable of achieving better performance than that of the hybrid decoding algorithm with reducing the number of iterations required at each SNR and approaching more to the performance of the SPA. This reduction is more observable as the maximum number of iterations assigned for the algorithm increases or as the code length increases with improving the error performance as proved by simulation results.

IEEE Vehicular Technology ConferenceApr 1, 20098 citations

A multistage scheduled decoder for short block length low-density parity-check codes

Nazanin Elhami-Khorasani

Recent advances in coding theory have uncovered the previously forgotten power of Low-Density Parity-Check (LDPC) codes. Their popularity can be related to their relatively simple iterative decoders and their potential to achieve high performance close to shannon limit. These make them an attractive candidate for error correcting application in communication systems. In this thesis, we focus our research on the iterative decoding algorithms for Low-Density Parity-Check codes and present an improved decoding algorithm. First, the graph structure of LDPC codes is studied and a graph-based search algorithm to find the shortest closed walk and shortest cycle for each node of the graph is proposed. Then, the Deterministic schedule is applied on nodes of the graph with the objective of preserving the optimality of the algorithms. Finally, Hybrid Switch-Type technique is applied on the improved algorithms to provide a desirable complexity/performance trade-off. Hybrid Technique and Deterministic schedule are combined for decoding regular and irregular LDPC codes. The performance and complexity of the decoder is studied for Sum-Product and Gallager A algorithms. The result is a flexible decoder for any available LDPC code and any combination of decoding algorithms based on the communication systems need. In this technique, we benefit the high performance of soft-decision algorithms and low complexity of hard-decision algorithms by changing the decoding rule after a few iterations. Hence, a desirable performance can be obtained with less average number of soft iterations. Moreover, all the nodes do not update messages in each iteration. As a result, the total number of computations is reduced considerably

Jan 1, 20070 citations

An Improved Hybrid LDPC Decoder over Rayleigh Fading Channel

Reza Biazaran, Hermann J. Helgert

Soft decision decoders applicable to low density parity check codes such as sum product algorithms provide excellent error performance, however, it comes at the expense of computational complexity. Additionally, many iterations may be required of these decoders to achieve desired error performance. The processing delay associated with too many iterations may be a drawback for cases where low latency is a critical requirement. Conversely, performance of hard decision decoders such as bit flipping decoder and its variants, while improved, generally are not on par with that of soft decision decoders. Such decoders also require many iterations to achieve a given error performance. We have proposed a two-stage hybrid decoder with a simplified sum product algorithm (SPA) in the first stage, and an improved noisy gradient decent bit flipping decoder in the second stage. We have shown that our proposed hybrid decoder outperforms the legacy individual decoders, studied in this paper, from error performance point of view as well as required number of iterations that will reduce the overall network latency.

IEEE International Conference on Application of Information and Communication Technologies (AICT)Oct 12, 20220 citations

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

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 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

Asilomar Conference on Signals, Systems and Computers (ACSSC)Mar 22, 20063 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

Candidate bit based bit-flipping decoding algorithm for LDPC codes

Guiqiang Dong, Yanan Li, Ningde Xie +2 more

A novel hard-decision decoding algorithm for low-density parity-check (LDPC) codes is proposed in this paper. This algorithm employs the correlation information among the column vectors of the parity-check matrix and syndrome vector for decoding. It does not require soft information, and has low decoding complexity. Simulation results show that the proposed decoding algorithm could provide an effective tradeoff between error performance and decoding complexity.

IEEE International Symposium on Information Theory (ISIT)Jun 1, 200911 citations