Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Xidian University

Analysis of the convergence rate of serial schedule based decoding for LDPC codes

Xinmei Wang

Published Jan 1, 2010• 0 citations
OpenAlex

Abstract

Serial schedule based decoding for LDPC codes,in which check nodes are partitioned into groups,converges very fast.However,if there are too many groups,the low degree of parallelism will incur high decoding latency.The extrinsic information transfer(EXIT) chart technique is adopted to find out a balance between convergence rate and decoding latency.EXIT functions for serial schedule based decoding with different group partitions are derived,and a comparison among corresponding EXIT curves is made to estimate the maximum parallelism that serial schedule based decoding may achieve without sacrificing the convergence rate.Simulation results validate the EXIT chart analysis.

Related papers

On the EXIT chart analysis of low-density parity-check codes

S.R. Kollu, Hamid Jafarkhani

The extrinsic information transfer (EXIT) charts are used to analyze the sum-product decoding algorithm of low-density parity-check (LDPC) codes. The codes are optimized by performing curve fitting on EXIT charts. This technique is developed for binary erasure channels based on area property and is extended to other channels. We show that on channels where the area property is not valid, the curve fitting approach is a sub-optimal method of optimizing for the best convergence threshold. On Gaussian channels, the messages from variable nodes to check nodes are approximated by a symmetric Gaussian distribution. We prove that the check node detector mutual information transfer function derived using this approximation is an upper bound. So the EXIT chart analysis predicts an optimistic value for the convergence threshold. We give an empirical lower bound for the check node detector mutual information transfer function. For few irregular LDPC codes designed for AWGN channel using density evolution, we have examined the accuracy of convergence thresholds predicted by EXIT charts using these bounds for the check node transfer function. The analysis of EXIT chart technique presented in this paper can be extended to other channels for which the distribution of channel messages can be approximated by a symmetric Gaussian/Gaussian mixture distribution.

Globecom•Jan 1, 2005•14 citations

Generalized constructions, decoding and implementation of LDPC codes

Yige Wang

Low-density parity-check (LDPC) codes have received significant attention due to their near-Shannon-limit error performance. The belief propagation (BP) algorithm is the best-known decoding algorithm for LDPC codes. However it often needs several tens or hundreds of iterations to converge. Although fast convergence BP algorithms have been proposed, there is neither an easy tool to analyze their performance nor a standard VLSI architecture to implement them. Moreover, there exists a trade-off between waterfall (i.e., threshold) and error floor (i.e., minimum pseudo distance) performances for LDPC codes. For generalized LDPC (GLDPC) codes, better minimum distance properties can be achieved but at the expense of a rate loss. This research investigates performance analysis and hardware implementation of LDPC codes using fast convergence algorithms. Closed-form extrinsic mutual information transfer (EXIT) functions for several fast convergence BP decoding algorithms are proposed. It is shown theoretically that these algorithms converge faster than standard BP, while the corresponding thresholds remain unchanged. Since these algorithms are of serial nature, their parallelization without compromising convergence speed and error performance is also investigated. This result is useful in hardware implementation because in practice partly parallel decoding schemes are often used. This result also sheds some light on how to group nodes in order to preserve performance. The VLSI architecture of a particular decoding algorithm for LDPC codes is proposed. This approach can be adopted in many standards to achieve a large throughput. Doubly GLDPC (DGLDPC) codes are proposed to compensate the rate loss of GLDPC codes. EXIT charts are used to analyze DGLDPC codes and EXIT functions for variable component codes are thoroughly discussed. Based on EXIT charts, differential evolution is used to optimize their threshold. Ensemble weight enumerators are generalized to protograph-based DGLDPC codes. Simulation results show that DGLDPC codes constructed based on these results can improve the performance of their LDPC and GLDPC counterparts in both the waterfall region and the error floor region.

•Jan 1, 2008•3 citations

Convergence Analysis of Serial Message-Passing Schedules for LDPC Decoding

Eran Sharon, Simon N. Litsyn, Jacob Goldberger

Serial decoding schedules for low-density parity-check (LDPC) codes are described and analyzed. Conventionally, in each iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (“flooding schedule”). In contrast, in the considered methods, the updating of the nodes is implemented according to a serial schedule. The evolution of the decoding algorithm’s computation tree under serial scheduling is analyzed. The analysis shows that it grows twice as fast in comparison to the flooding schedule’s computation tree, indicating that the serial schedule propagates information twice as fast in the code’s underlying graph. Furthermore, asymptotic analysis of the serial schedule’s convergence rate is done using the Density Evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that when working near the ensemble’s threshold, for long enough codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule. This observation is generally proved for the Binary Erasure Channel (BEC) under some likely assumptions. Finally, an accompanying concentration theorem is proved, justifying the asymptotic DE analysis assumptions. 1

•Apr 3, 2006•10 citations

Efficient Serial Message-Passing Schedules for LDPC Decoding

Eran Sharon, Simon N. Litsyn, Jacob Goldberger

Conventionally, in each low-density parity-check (LDPC) decoding iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (flooding schedule). An alternative, more efficient, approach is to update the nodes' messages serially (serial schedule). A theoretical analysis of serial message passing decoding schedules is presented. In particular, the evolution of the computation tree under serial scheduling is analyzed. It shows that the tree grows twice as fast in comparison to the flooding schedule's one, indicating that the serial schedule propagates information twice as fast in the code's underlying graph. Furthermore, an asymptotic analysis of the serial schedule's convergence rate is done using the density evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that for long codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule, when working near the ensemble's threshold. This observation is generally proved for the binary erasure channel (BEC) under some natural assumptions. Finally, an accompanying concentration theorem is proved.

IEEE Transactions on Information Theory•Nov 1, 2007•155 citations

EXIT-chart properties of the highest-rate LDPC code with desired convergence behavior

Masoud Ardakani, Terence Chan, Frank R. Kschischang

We consider uniparametric LDPC decoding schemes, i.e., the class of decoding algorithms for which an extrinsic information transfer (EXIT) chart analysis of the decoder is exact. We treat the general case of code design for a desired convergence behavior and provide necessary conditions and sufficient conditions that the EXIT chart of the maximum rate low-density parity-check code must satisfy. Our results generalize some of the existing results for the binary erasure channel: our results apply to all uniparametric decoding schemes and they apply to any desired convergence behavior.

IEEE Communications Letters•Jan 1, 2005•13 citations

A comparison between BP, log-likelihood and max log-likelihood decoding algorithms of LDPC codes based on EXIT chart and EXIT trajectories methods

A. Refaey-Ahmed, Jean‐Yves Chouinard, Sébastien Roy +1 more

Low density parity check (LDPC) codes are known to achieve a performance very close to the Shannon capacity limit on Additive White Gaussian Noise (AWGN) and erasure channels. The extrinsic information transfer (EXIT) chart is a powerful method for analyzing iteratively decoded codes such as Turbo codes. EXIT charts were introduced as a method for representing how the mutual information between the decoder output and the transmitted bits changes over turbo decoding iterations. It is possible to apply the EXIT chart method to LDPC codes by treating the LDPC decoder as a concatenation of variable and check nodes. However the achieved convergence threshold values obtained with the EXIT charts are (plusmn0.1) dB away from the more precise results derived from the density evolution (DE) method. Subsequently, the EXIT trajectories method was proposed as an improved performance-analysis method for LDPC codes under belief propagation (BP) decoding and achieved more accurate convergence threshold values than the EXIT chart method. In this paper, the EXIT chart and the EXIT trajectories methods are proposed as analysis tools to compare between the BP, log likelihood and max log likelihood decoding algorithms for LDPC codes in terms of convergence thresholds. Furthermore, a comparison between EXIT chart, EXIT trajectories and DE methods is introduced for the mentioned LDPC codes. Simulations and numerical calculations on convergence thresholds for various ensembles of (dv, dc) regular LDPC codes for binary input AWGN channels are performed which results that the BP is the best decoding algorithm for LDPC code followed by the log likelihood and the max log likelihood algorithms, respectively. Also, the EXIT trajectory method yields more accurate results than EXIT charts which come very close to the DE method, while being more convenient numerically as a code research tool than the latter which require many Fourier transform operations.

International Conference on Advanced Technologies for Communications•Oct 1, 2008•1 citation
Serial schedule based decoding for LDPC codes,in which check nodes are partitioned into groups,converges very fast.However,if there are too many groups,the low degree of parallelism will incur high decoding latency.The extrinsic information transfer(EXIT) chart technique is adopted to find out a balance between convergence rate and decoding latency.EXIT functions for serial schedule based decoding with different group partitions are derived,and a comparison among corresponding EXIT curves is made to estimate the maximum parallelism that serial schedule based decoding may achieve without sacrificing the convergence rate.Simulation results validate the EXIT chart analysis.
The extrinsic information transfer (EXIT) charts are used to analyze the sum-product decoding algorithm of low-density parity-check (LDPC) codes. The codes are optimized by performing curve fitting on EXIT charts. This technique is developed for binary erasure channels based on area property and is extended to other channels. We show that on channels where the area property is not valid, the curve fitting approach is a sub-optimal method of optimizing for the best convergence threshold. On Gaussian channels, the messages from variable nodes to check nodes are approximated by a symmetric Gaussian distribution. We prove that the check node detector mutual information transfer function derived using this approximation is an upper bound. So the EXIT chart analysis predicts an optimistic value for the convergence threshold. We give an empirical lower bound for the check node detector mutual information transfer function. For few irregular LDPC codes designed for AWGN channel using density evolution, we have examined the accuracy of convergence thresholds predicted by EXIT charts using these bounds for the check node transfer function. The analysis of EXIT chart technique presented in this paper can be extended to other channels for which the distribution of channel messages can be approximated by a symmetric Gaussian/Gaussian mixture distribution.
Low-density parity-check (LDPC) codes have received significant attention due to their near-Shannon-limit error performance. The belief propagation (BP) algorithm is the best-known decoding algorithm for LDPC codes. However it often needs several tens or hundreds of iterations to converge. Although fast convergence BP algorithms have been proposed, there is neither an easy tool to analyze their performance nor a standard VLSI architecture to implement them. Moreover, there exists a trade-off between waterfall (i.e., threshold) and error floor (i.e., minimum pseudo distance) performances for LDPC codes. For generalized LDPC (GLDPC) codes, better minimum distance properties can be achieved but at the expense of a rate loss. This research investigates performance analysis and hardware implementation of LDPC codes using fast convergence algorithms. Closed-form extrinsic mutual information transfer (EXIT) functions for several fast convergence BP decoding algorithms are proposed. It is shown theoretically that these algorithms converge faster than standard BP, while the corresponding thresholds remain unchanged. Since these algorithms are of serial nature, their parallelization without compromising convergence speed and error performance is also investigated. This result is useful in hardware implementation because in practice partly parallel decoding schemes are often used. This result also sheds some light on how to group nodes in order to preserve performance. The VLSI architecture of a particular decoding algorithm for LDPC codes is proposed. This approach can be adopted in many standards to achieve a large throughput. Doubly GLDPC (DGLDPC) codes are proposed to compensate the rate loss of GLDPC codes. EXIT charts are used to analyze DGLDPC codes and EXIT functions for variable component codes are thoroughly discussed. Based on EXIT charts, differential evolution is used to optimize their threshold. Ensemble weight enumerators are generalized to protograph-based DGLDPC codes. Simulation results show that DGLDPC codes constructed based on these results can improve the performance of their LDPC and GLDPC counterparts in both the waterfall region and the error floor region.
Serial decoding schedules for low-density parity-check (LDPC) codes are described and analyzed. Conventionally, in each iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (“flooding schedule”). In contrast, in the considered methods, the updating of the nodes is implemented according to a serial schedule. The evolution of the decoding algorithm’s computation tree under serial scheduling is analyzed. The analysis shows that it grows twice as fast in comparison to the flooding schedule’s computation tree, indicating that the serial schedule propagates information twice as fast in the code’s underlying graph. Furthermore, asymptotic analysis of the serial schedule’s convergence rate is done using the Density Evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that when working near the ensemble’s threshold, for long enough codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule. This observation is generally proved for the Binary Erasure Channel (BEC) under some likely assumptions. Finally, an accompanying concentration theorem is proved, justifying the asymptotic DE analysis assumptions. 1
Conventionally, in each low-density parity-check (LDPC) decoding iteration all the variable nodes and subsequently all the check nodes send messages to their neighbors (flooding schedule). An alternative, more efficient, approach is to update the nodes' messages serially (serial schedule). A theoretical analysis of serial message passing decoding schedules is presented. In particular, the evolution of the computation tree under serial scheduling is analyzed. It shows that the tree grows twice as fast in comparison to the flooding schedule's one, indicating that the serial schedule propagates information twice as fast in the code's underlying graph. Furthermore, an asymptotic analysis of the serial schedule's convergence rate is done using the density evolution (DE) algorithm. Applied to various ensembles of LDPC codes, it shows that for long codes the serial schedule is expected to converge in half the number of iterations compared to the standard flooding schedule, when working near the ensemble's threshold. This observation is generally proved for the binary erasure channel (BEC) under some natural assumptions. Finally, an accompanying concentration theorem is proved.
We consider uniparametric LDPC decoding schemes, i.e., the class of decoding algorithms for which an extrinsic information transfer (EXIT) chart analysis of the decoder is exact. We treat the general case of code design for a desired convergence behavior and provide necessary conditions and sufficient conditions that the EXIT chart of the maximum rate low-density parity-check code must satisfy. Our results generalize some of the existing results for the binary erasure channel: our results apply to all uniparametric decoding schemes and they apply to any desired convergence behavior.
Low density parity check (LDPC) codes are known to achieve a performance very close to the Shannon capacity limit on Additive White Gaussian Noise (AWGN) and erasure channels. The extrinsic information transfer (EXIT) chart is a powerful method for analyzing iteratively decoded codes such as Turbo codes. EXIT charts were introduced as a method for representing how the mutual information between the decoder output and the transmitted bits changes over turbo decoding iterations. It is possible to apply the EXIT chart method to LDPC codes by treating the LDPC decoder as a concatenation of variable and check nodes. However the achieved convergence threshold values obtained with the EXIT charts are (plusmn0.1) dB away from the more precise results derived from the density evolution (DE) method. Subsequently, the EXIT trajectories method was proposed as an improved performance-analysis method for LDPC codes under belief propagation (BP) decoding and achieved more accurate convergence threshold values than the EXIT chart method. In this paper, the EXIT chart and the EXIT trajectories methods are proposed as analysis tools to compare between the BP, log likelihood and max log likelihood decoding algorithms for LDPC codes in terms of convergence thresholds. Furthermore, a comparison between EXIT chart, EXIT trajectories and DE methods is introduced for the mentioned LDPC codes. Simulations and numerical calculations on convergence thresholds for various ensembles of (dv, dc) regular LDPC codes for binary input AWGN channels are performed which results that the BP is the best decoding algorithm for LDPC code followed by the log likelihood and the max log likelihood algorithms, respectively. Also, the EXIT trajectory method yields more accurate results than EXIT charts which come very close to the DE method, while being more convenient numerically as a code research tool than the latter which require many Fourier transform operations.