IEEE Communications Letters

On General Linear Block Code Decoding Using the Sum–Product Iterative Decoder

Todd K. Moon

Published Jun 1, 2004• 10 citations

Abstract

The sum-product iterative decoder, conventionally used for low-density parity-check (LDPC) codes, hold promise as a decoder for general linear block code decoding. However, the promise is only partly fulfilled because, as we show experimentally, the decoder performance degrades rapidly as a function of parity check matrix weight. Even in the case of decoder failure, however, we demonstrate that there is information present in the decoder output probabilities that can still help with the decoding problem.

DOI: 10.1109/lcomm.2004.828183

Related papers

LDPC Sum-Product Decoding Based on Synchronized Information

洋洋陈

低密度奇偶校验码(LDPC)是一类具有稀疏校验矩阵的线性分组码，和积算法是理论可行的LDPC软解码算法，但其实用受制于计算复杂度。最小和算法及其它已知改进算法采用近似来有效简化每次迭代的过程，以部分性能为代价，在一定程度上弥补了前述缺陷。本文提出了基于同步信息修正的和积算法，在保持原算法每次迭代复杂度以保证性能的前提下，利用同步信息对算法进行修正，有效减少了算法迭代次数，因此降低了计算复杂度，提高了实用性。Low density parity check code (LDPC) is a subclass of linear block code with sparse check matrix. Sum-product algorithm is efficient for decoding LDPC theoretically, but not practically due to its complexity. Improved algorithms including minimum sum algorithm reduce computational com-plexity by approximation but performance is degraded. In this paper, we introduce corrected sum-product algorithm based on synchronized information, which improves the practicability by reducing the iterations without performance degradation.

Hans Journal of Wireless CommunicationsJan 1, 20150 citations

Multitree decoding and multitree-aided LDPC decoding

Maja Ostojic, Hans‐Andrea Loeliger

New decoding algorithms for linear codes are proposed. The first part of the paper considers decoding general binary linear codes by searching multiple trees, which is shown to achieve near maximum-likelihood performance for short block lengths. The second part of the paper considers decoding low-density parity check (ldpc) codes by means of repeated decoding attempts by standard sum-product message passing. Each decoding attempt starts from modified channel output, where some of the bits are clamped to a fixed value. The values of the fixed bits are obtained from multitree search.

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

Simplified sum-product algorithm for decoding LDPC codes with optimal performance

Stylianos Papaharalabos, P. Takis Mathiopoulos

A simple, yet effective decoding algorithm is proposed for low-density parity-check (LDPC) codes, which significantly simplifies the check node update computation of the optimal sum-product algorithm. It achieves essentially optimal performance by applying scaling in the decoder's extrinsic information. If no such scaling is applied, then the proposed algorithm has small performance degradation, e.g. in the order of 0.1 to 0.2 dB, depending on the coded block size.

Electronics LettersJan 13, 200931 citations

A probabilistic computation method for the weight distribution of low-density parity-check codes

Masanori Hirotomo, Masami Mohri, Masakatu Morii

Low-density parity-check (LDPC) codes achieve outstanding performance by the sum-product decoder. Its performance approaches the maximum-likelihood (ML) decoding performance at high SNR region. Upper bounds on the error probability of the ML decoded LDPC codes can be computed using the weight distribution. Recently, X.-Y. Hu et al. presented an approximate algorithm for estimating the weight distribution of LDPC codes. However, the weight distribution computed by their method depends on the iterative decoding algorithm, and is not always estimated exactly. In this paper, we propose a probabilistic method for computing the low-part weight distribution of LDPC codes. Using our method, the approximate weight distribution of LDPC codes can be computed with high accuracy

IEEE International Symposium on Information Theory (ISIT)Jan 1, 200530 citations

Low-density parity-check codes

Sarah J. Johnson

Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.

Cambridge University Press eBooksNov 19, 20095 citations

Düşük yoğunluklu eşlik denetim kodları için kod çözme algoritmalarının karşılaştırılması.

Kolaylı, Mert

Low-density parity-check (LDPC) codes are a subclass of linear block codes. These codes have parity-check matrices in which the ratio of the non-zero elements to all elements is low. This property is exploited in defining low complexity decoding algorithms. Low-density parity-check codes have good distance properties and error correction capability near Shannon limits. In this thesis, the sum-product and the bit-flip decoding algorithms for low-density parity-check codes are implemented on Intel Pentium M 1,86 GHz processor using the software called MATLAB. Simulations for the two decoding algorithms are made over additive white gaussian noise (AWGN) channel changing the code parameters like the information rate, the blocklength of the code and the column weight of the parity-check matrix. Performance comparison of the two decoding algorithms are made according to these simulation results. As expected, the sum-product algorithm, which is based on soft-decision decoding, outperforms the bit-flip algorithm, which depends on hard-decision decoding. Our simulations show that the performance of LDPC codes improves with increasing blocklength and number of iterations for both decoding algorithms. Since the sum-product algorithm has lower error-floor characteristics, increasing the number of iterations is more effective for the sum-product decoder compared to the bit-flip decoder. By having better BER performance for lower information rates, the bit-flip algorithm performs according to the expectations; however, the performance of the sum-product decoder deteriorates for information rates below 0.5 instead of improving. By irregular construction of LDPC codes, a performance improvement is observed especially for low SNR values.

Jan 1, 20060 citations