Analysis of Iterative Decoding : Density Evolution and Related Topics

Michael Lentmaier, Kamil Sh. Zigangirov

JØrn Justesen, Tom Høholdt

Products of Reed-Solomon codes are important in applications because they offer a combination of large blocks, low decoding complexity, and good performance. A recent result on random graphs can be used to show that with high probability a large number of errors can be corrected by iterating minimum distance decoding. We present an analysis related to density evolution which gives the exact asymptotic value of the decoding threshold and also provides a closed form approximation to the distribution of errors in each step of the decoding of finite length codes.

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.

Antoine O. Berthet

Xiumin Wang, Hong Soon Chang, Jun Li +2 more

Based on density evolution analysis of the existing belief propagation (BP) algorithm, the Turbo Decoding Message Passing (TDMP) algorithm was analyzed from the perspective of density evolution and Gaussian approximation, and the theoretical analysis process of TDMP algorithm was given. When calculating the prior message of each layer of the TDMP algorithm, the check message of the previous iteration should be subtracted. Therefore, the result will not be convergent, if the TDMP algorithm is directly analyzed based on density evolution and Gaussian approximation. We researched the TDMP algorithm based on the symmetry conditions to obtain the convergent result. When using density evolution (DE) and Gaussian approximation to analyze the decoding convergence of the TDMP algorithm, we can provide a theoretical basis for proving the superiority of the algorithm. Then, based on the DE theory, we calculated the probability density function (PDF) of the check-to-variable information of TDMP and its simplified algorithm, and then gave it a calculation based on the process of the normalization factor. Simulation results show that the decoding convergence speed of the TDMP algorithm was faster and the iterations were smaller compared to the BP algorithm under the same conditions.

James A. McGowan