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

IEEE International Symposium on Information Theory (ISIT)

Bifurcations and EXIT charts for the Binary Erasure Channel

Christopher M. Kellett, Steven R. Weller

Published Jul 1, 2006• 2 citations
Publisher

Abstract

In this paper we present an abstraction of the extrinsic information transfer (EXIT) chart as the interconnection of two nonlinear systems in feedback with each other. We present results on the stability of fixed points for such a dynamical system and use this framework to rederive the well-known stability condition, connecting this to the one-dimensional dynamical system describing the fractions of erasure for low-density parity-check (LDPC) codes on the binary erasure channel (BEC). We observe that the error threshold corresponds to a fixed point bifurcation for this one-dimensional system, and show that this information can be visualized using a well-known tool from control theory: the root locus plot. We further show that these bifurcations can be seen by examining the EXIT chart

DOI
10.1109/isit.2006.262094

Related papers

Bifurcations in iterative decoding and root locus plots

Christopher M. Kellett, Steven R. Weller

A class of error correction codes called ‘low-density parity-check (LDPC)’ codes have been the subject of a great deal of recent study in the coding community as a result of their ability to approach Shannon's fundamental capacity limit. Crucial to the performance of these codes is the use of an ‘iterative’ decoder. These iterative decoders are effectively high-dimensional, nonlinear dynamical systems and, consequently, control-theoretic tools are useful in analysing such decoders. The authors describe LDPC codes and the decoding algorithm and make a connection between the fixed points of the decoding algorithm and the well-known root locus plot. Through two examples of LDPC codes, the authors show that the root locus plot visually captures the bifurcation behaviour of iterative decoding that occurs at the signal-to-noise ratio predicted by Shannon's noisy channel coding theorem.

IET Control Theory and Applications•Dec 6, 2008•2 citations

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

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

EXIT charts for nonbinary LDPC codes

Yong Li

Non-binary low-density parity-check(LDPC) codes defined over the finite field GF(q=2p) are an extension of binary LDPC codes and have demonstrated improved performance over binary LDPC codes with the same frame length and rate.This paper introduces the principle of extrinsic information transfer(EXIT) charts,analyzes the convergence behavior of non-binary LDPC codes on AWGN channel,and confirms the thresholds of non-binary LDPC codes,which provides the foundation for analysis and design of real communication system using EXIT tool in future work.Simulation result shows that the performance of quaternary LDPC codes is better than that of binary LDPC codes in the same channel,and validates the superiority of using EXIT chart for iterative research.

Journal of Chongqing University of Posts and Telecommunications•Jan 1, 2008•0 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

EXIT charts for non-binary LDPC codes

G.J. Byers, Fambirai Takawira

In this paper extrinsic information transfer (EXIT) charts are proposed to design non-binary low-density parity-check (LDPC) codes for the AWGN channel. A new metric is presented to describe the mutual information of the non-binary messages. The a priori information is modelled using a Gaussian mixture distribution. Analytical expressions are given for the EXIT curves of the variable and check node decoders for both regular and irregular LDPC codes. The analytical expressions are shown to agree well with simulation results. Finally, by matching the variable and check node EXIT curves, it is shown that good nonbinary LDPC can be designed for the AWGN channel.

International Conference on Communications•Aug 16, 2005•19 citations
In this paper we present an abstraction of the extrinsic information transfer (EXIT) chart as the interconnection of two nonlinear systems in feedback with each other. We present results on the stability of fixed points for such a dynamical system and use this framework to rederive the well-known stability condition, connecting this to the one-dimensional dynamical system describing the fractions of erasure for low-density parity-check (LDPC) codes on the binary erasure channel (BEC). We observe that the error threshold corresponds to a fixed point bifurcation for this one-dimensional system, and show that this information can be visualized using a well-known tool from control theory: the root locus plot. We further show that these bifurcations can be seen by examining the EXIT chart
A class of error correction codes called ‘low-density parity-check (LDPC)’ codes have been the subject of a great deal of recent study in the coding community as a result of their ability to approach Shannon's fundamental capacity limit. Crucial to the performance of these codes is the use of an ‘iterative’ decoder. These iterative decoders are effectively high-dimensional, nonlinear dynamical systems and, consequently, control-theoretic tools are useful in analysing such decoders. The authors describe LDPC codes and the decoding algorithm and make a connection between the fixed points of the decoding algorithm and the well-known root locus plot. Through two examples of LDPC codes, the authors show that the root locus plot visually captures the bifurcation behaviour of iterative decoding that occurs at the signal-to-noise ratio predicted by Shannon's noisy channel coding theorem.
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.
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.
Non-binary low-density parity-check(LDPC) codes defined over the finite field GF(q=2p) are an extension of binary LDPC codes and have demonstrated improved performance over binary LDPC codes with the same frame length and rate.This paper introduces the principle of extrinsic information transfer(EXIT) charts,analyzes the convergence behavior of non-binary LDPC codes on AWGN channel,and confirms the thresholds of non-binary LDPC codes,which provides the foundation for analysis and design of real communication system using EXIT tool in future work.Simulation result shows that the performance of quaternary LDPC codes is better than that of binary LDPC codes in the same channel,and validates the superiority of using EXIT chart for iterative research.
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.
In this paper extrinsic information transfer (EXIT) charts are proposed to design non-binary low-density parity-check (LDPC) codes for the AWGN channel. A new metric is presented to describe the mutual information of the non-binary messages. The a priori information is modelled using a Gaussian mixture distribution. Analytical expressions are given for the EXIT curves of the variable and check node decoders for both regular and irregular LDPC codes. The analytical expressions are shown to agree well with simulation results. Finally, by matching the variable and check node EXIT curves, it is shown that good nonbinary LDPC can be designed for the AWGN channel.