IEEE International Symposium on Information Theory (ISIT)

An approximate analytical model of the message passing decoder of LDPC codes

Ralf Lehmann, G.M. Maggio

Published Jun 25, 2003• 11 citations

Abstract

In this paper we introduce a novel one-dimensional model of the message passing decoding algorithm of low-density parity-check (LDPC) codes, based on Gaussian densities. The model consists of a closed-form 1-D map whose iterates directly represent the error probability. This map allows a qualitative analysis of the nonlinear dynamics of the decoding algorithm. Moreover, it is shown that our approach leads to the correct stability condition and that the corresponding threshold values are in good agreement with density evolution.

DOI: 10.1109/isit.2002.1023303

Related papers

Analysis of the iterative decoding of ldpc and product codes using the gaussian approximation

F. Lehmann, G.M. Maggio

We propose a novel density evolution approach to analyze the iterative decoding algorithms of low-density parity-check (LDPC) codes and product codes, based on Gaussian densities. Namely, for these classes of codes we derive a one-dimensional (1D) map whose iterates directly represent the error probability both for the additive white Gaussian noise (AWGN) and the Rayleigh-fading channel. These simple models allow a qualitative analysis of the nonlinear dynamics of the decoding algorithm. As an application, we compute the decoding thresholds and show that they are consistent with the simulation results available in the literature.

IEEE Transactions on Information TheoryNov 1, 200356 citations

Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation

Sae-Young Chung, Tom Richardson, Rudiger L. Urbanke

Density evolution is an algorithm for computing the capacity of low-density parity-check (LDPC) codes under message-passing decoding. For memoryless binary-input continuous-output additive white Gaussian noise (AWGN) channels and sum-product decoders, we use a Gaussian approximation for message densities under density evolution to simplify the analysis of the decoding algorithm. We convert the infinite-dimensional problem of iteratively calculating message densities, which is needed to find the exact threshold, to a one-dimensional problem of updating the means of the Gaussian densities. This simplification not only allows us to calculate the threshold quickly and to understand the behavior of the decoder better, but also makes it easier to design good irregular LDPC codes for AWGN channels. For various regular LDPC codes we have examined, thresholds can be estimated within 0.1 dB of the exact value. For rates between 0.5 and 0.9, codes designed using the Gaussian approximation perform within 0.02 dB of the best performing codes found so far by using density evolution when the maximum variable degree is 10. We show that by using the Gaussian approximation, we can visualize the sum-product decoding algorithm. We also show that the optimization of degree distributions can be understood and done graphically using the visualization.

IEEE Transactions on Information TheoryJan 1, 20011,150 citations

Analysis of threshold of regular and irregular LDPC codes using Gaussian approximation

Chia‐Lu Ho

We present the formulas for searching for the thresholds of regular and irregular low-density parity-check (LDPC) codes under message-passing (MP) algorithm. A Gaussian approximation is applied to studying the evolution of the means of the messages of the variable nodes and the check nodes. Accurate numerical integration methods by using transformations are shown for evaluating the expected values of the message of the check nodes. Tables are built first and interpolations are used for further evaluations. Two curves are used to locate the threshold. We utilize an iterative decoding tunnel between these two curves and study the decoding performance by evaluating conditions of the derivatives of these two curves. Using this method the performance of both regular and irregular LDPC codes can be studied in a unified manner without using simulation.

Wireless Telecommunications SymposiumMay 1, 20092 citations

Analysis of belief-propagation decoding of LDPC codes over the biAWGN channel using improved Gaussian approximation based on the mutual information measure

E. Sharon

Summary form only given. The capacity of the message-passing decoder for LDPC codes can be computed by the density evolution algorithm by iteratively computing message densities. The infinite-dimensional problem of iteratively calculating the message densities in the case of the binary input AWGN channel and the belief propagation decoder can be simplified to a one-dimensional problem by using a Gaussian approximation. By assuming Gaussian densities the density evolution simplifies to updating means of Gaussian densities. An improved Gaussian approximation algorithm is suggested for computing the capacity of the BP decoder based on the mutual information measure. An analytical method for computing the mutual information of a transmitted bit with the message corresponding to it is proposed. Using this method we can approximate the non-Gaussian message by a Gaussian message that has the same mutual information with the transmitted bit. Computationally, the algorithm is similar to the Gaussian approximation algorithm proposed in Chung (2001). For various regular LDPC codes that were examined, the algorithm computed threshold values within 0.01dB or less from the exact threshold which is an improvement over the Gaussian approximation. Furthermore, additional insight on the convergence process can be gained from EXIT charts that can be derived from the algorithm. This can assist in designing better irregular LDPC codes.

IEEE Convention of Electrical and Electronics Engineers in IsraelJun 26, 20034 citations

New Message-Passing Decoding Algorithm of LDPC Codes by Partitioning Check Nodes

Sunghwan Kim, Min‐Ho Jang, Jong‐Seon No +2 more

In this paper, we propose a new sequential message-passing decoding algorithm of low-density parity-check (LDPC) codes by partitioning check nodes. This new decoding algorithm shows better bit error rate(BER) performance than that of the conventional message-passing decoding algorithm, especially for small number of iterations. Analytical results tell us that as the number of partitioned subsets of check nodes increases, the BER performance becomes better. We also derive the recursive equations for mean values of messages at variable nodes by using density evolution with Gaussian approximation. Simulation results also confirm the analytical results.

한국통신학회논문지Apr 1, 20050 citations

Performance analysis of noisy message-passing decoding of low-density parity-check codes

Alla Tarighati, Hamed Farhadi, Farshad Lahouti

A noisy message-passing decoding scheme isconsidered for low-density parity-check (LDPC) codes overadditive white Gaussian noise (AWGN) channels. The internaldecoder noise is motivated by the quantization noise in digitalimplementations or the intrinsic noise of analog LDPC decoders.We modelled the decoder noise as AWGN on the exchangedmessages in the iterative LDPC decoder. This is shown to renderthe message densities in the noisy LDPC decoder inconsistent.We then invoke Gaussian approximation and formulate a twodimensionaldensity evolution analysis for the noisy LDPCdecoder. This allows for not only tracking the mean, but also thevariance of the message densities, and hence, quantifying thethreshold of the LDPC code. According to the results, a decodernoise of unit variance, increases the threshold for a regular (3,6) code by 1.672dB.

Jan 1, 20106 citations