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 Transactions on Information Theory

Binary intersymbol interference channels: gallager codes, density evolution, and code performance bounds

A. Kavcic, Xiao Ma, Michael Mitzenmacher

Published Jun 23, 2003• 208 citations
Publisher

Abstract

We study the limits of performance of Gallager codes (low-density parity-check (LDPC) codes) over binary linear intersymbol interference (ISI) channels with additive white Gaussian noise (AWGN). Using the graph representations of the channel, the code, and the sum-product message-passing detector/decoder, we prove two error concentration theorems. Our proofs expand on previous work by handling complications introduced by the channel memory. We circumvent these problems by considering not just linear Gallager codes but also their cosets and by distinguishing between different types of message flow neighborhoods depending on the actual transmitted symbols. We compute the noise tolerance threshold using a suitably developed density evolution algorithm and verify, by simulation, that the thresholds represent accurate predictions of the performance of the iterative sum-product algorithm for finite (but large) block lengths. We also demonstrate that for high rates, the thresholds are very close to the theoretical limit of performance for Gallager codes over ISI channels. If C denotes the capacity of a binary ISI channel and if C/sub i.i.d./ denotes the maximal achievable mutual information rate when the channel inputs are independent and identically distributed (i.i.d.) binary random variables (C/sub i.i.d.//spl les/C), we prove that the maximum information rate achievable by the sum-product decoder of a Gallager (coset) code is upper-bounded by C/sub i.i.d./. The last topic investigated is the performance limit of the decoder if the trellis portion of the sum-product algorithm is executed only once; this demonstrates the potential for trading off the computational requirements and the performance of the decoder.

DOI
10.1109/tit.2003.813563

Related papers

Useful Mathematical Tools for Capacity Approaching Codes Design

Fulvio Babich, Alessandro Soranzo, F. Vatta

Focus of this letter is the oldest class of codes that can approach the Shannon limit quite closely, i.e., low-density parity-check (LDPC) codes, and two mathematical tools that can make their design an easier job under appropriate assumptions. In particular, we present a simple algorithmic method to estimate the threshold for regular and irregular LDPC codes on memoryless binary-input continuous-output additive white Gaussian noise (AWGN) channels with sum-product decoding, and, to determine how close are the obtained thresholds to the theoretical maximum, i.e., to the Shannon limit, we give a simple and invertible expression of the AWGN channel capacity in the binary input-soft output case. For these codes, the thresholds are defined as the maximum noise level, such that an arbitrarily small bit-error probability can be achieved as the block length tends to infinity. We assume a Gaussian approximation for message densities under density evolution, a widely used simplification of the decoding algorithm.

IEEE Communications Letters•Jun 12, 2017•22 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 Theory•Jan 1, 2001•1,150 citations

Performance Study of a Class of Irregular LDPC Codes through Low Complexity Bounds on Their Belief-Propagation Decoding Thresholds

F. Vatta, Alessandro Soranzo, Massimiliano Comisso +2 more

This paper investigates about the usefulness of some recently published low complexity upper bounds on belief-propagation decoding thresholds for irregular low-density parity-check (LDPC) codes to analyze their performance on memoryless binary input - additive white Gaussian noise (BI-AWGN) channels, with sum-product decoding. Irregular LDPC codes are known to perform better than regular ones, and to exhibit, like them, the so called “threshold phenomenon”, being the threshold defined as the maximum noise level such that an arbitrarily small bit-error probability can be achieved as the block length tends to infinity. We use a simplified analysis of the belief-propagation decoding algorithm, i.e., consider a Gaussian approximation for message densities under density evolution, and a simple algorithmic method, defined recently, to estimate the decoding thresholds for regular and irregular LDPC codes on BI-AWGN channels.

AEIT International Annual Conference•Sep 1, 2019•11 citations

Properties of Optimum Binary Message-Passing Decoders

Masoud Ardakani, Frank R. Kschischang

We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.

IEEE Transactions on Information Theory•Sep 26, 2005•14 citations

LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +2 more

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

IEEE Transactions on Communications•Nov 6, 2018•5 citations

Efficient Analysis, Design and Decoding of Low-Density Parity-Check Codes

Masoud Ardakani

This dissertation presents new methods for the analysis, design and decoding of low-density parity-check (LDPC) codes. We start by studying the simplest class of decoders: the binary message-passing (BMP) decoders. We show that the optimum BMP decoder must satisfy certain symmetry and isotropy conditions, and prove that Gallager's Algorithm B is the optimum BMP algorithm. We use a generalization of extrinsic information transfer (EXIT) charts to formulate a linear program that leads to the design of highly efficient irregular LDPC codes for the BMP decoder. We extend this approach to the design of irregular LDPC codes for the additive white Gaussian noise channel. We introduce a "semi-Gaussian" approximation that very accurately predicts the behaviour of the decoder and permits code design over a wider range of rates and code parameters than in previous approaches. We then study the EXIT chart properties of the highest rate LDPC code which guarantees a certain convergence behaviour. We also introduce and analyze gear-shift decoding in which the decoder is permitted to select the decoding rule from among a predefined set. We show that this flexibility can give rise to significant reductions in decoding complexity. Finally, we show that binary LDPC codes can be combined with quadrature amplitude modulation to achieve near-capacity performance in a multitone system over frequency selective Gaussian channels.

•Jan 1, 2004•14 citations
We study the limits of performance of Gallager codes (low-density parity-check (LDPC) codes) over binary linear intersymbol interference (ISI) channels with additive white Gaussian noise (AWGN). Using the graph representations of the channel, the code, and the sum-product message-passing detector/decoder, we prove two error concentration theorems. Our proofs expand on previous work by handling complications introduced by the channel memory. We circumvent these problems by considering not just linear Gallager codes but also their cosets and by distinguishing between different types of message flow neighborhoods depending on the actual transmitted symbols. We compute the noise tolerance threshold using a suitably developed density evolution algorithm and verify, by simulation, that the thresholds represent accurate predictions of the performance of the iterative sum-product algorithm for finite (but large) block lengths. We also demonstrate that for high rates, the thresholds are very close to the theoretical limit of performance for Gallager codes over ISI channels. If C denotes the capacity of a binary ISI channel and if C/sub i.i.d./ denotes the maximal achievable mutual information rate when the channel inputs are independent and identically distributed (i.i.d.) binary random variables (C/sub i.i.d.//spl les/C), we prove that the maximum information rate achievable by the sum-product decoder of a Gallager (coset) code is upper-bounded by C/sub i.i.d./. The last topic investigated is the performance limit of the decoder if the trellis portion of the sum-product algorithm is executed only once; this demonstrates the potential for trading off the computational requirements and the performance of the decoder.
Focus of this letter is the oldest class of codes that can approach the Shannon limit quite closely, i.e., low-density parity-check (LDPC) codes, and two mathematical tools that can make their design an easier job under appropriate assumptions. In particular, we present a simple algorithmic method to estimate the threshold for regular and irregular LDPC codes on memoryless binary-input continuous-output additive white Gaussian noise (AWGN) channels with sum-product decoding, and, to determine how close are the obtained thresholds to the theoretical maximum, i.e., to the Shannon limit, we give a simple and invertible expression of the AWGN channel capacity in the binary input-soft output case. For these codes, the thresholds are defined as the maximum noise level, such that an arbitrarily small bit-error probability can be achieved as the block length tends to infinity. We assume a Gaussian approximation for message densities under density evolution, a widely used simplification of the decoding algorithm.
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.
This paper investigates about the usefulness of some recently published low complexity upper bounds on belief-propagation decoding thresholds for irregular low-density parity-check (LDPC) codes to analyze their performance on memoryless binary input - additive white Gaussian noise (BI-AWGN) channels, with sum-product decoding. Irregular LDPC codes are known to perform better than regular ones, and to exhibit, like them, the so called “threshold phenomenon”, being the threshold defined as the maximum noise level such that an arbitrarily small bit-error probability can be achieved as the block length tends to infinity. We use a simplified analysis of the belief-propagation decoding algorithm, i.e., consider a Gaussian approximation for message densities under density evolution, and a simple algorithmic method, defined recently, to estimate the decoding thresholds for regular and irregular LDPC codes on BI-AWGN channels.
We consider a class of message-passing decoders for low-density parity-check (LDPC) codes whose messages are binary valued. We prove that if the channel is symmetric and all codewords are equally likely to be transmitted, an optimum decoding rule (in the sense of minimizing message error rate) should satisfy certain symmetry and isotropy conditions. Using this result, we prove that Gallager's Algorithm B achieves the optimum decoding threshold among all binary message-passing decoding algorithms for regular codes. For irregular codes, we argue that when the nodes of the message-passing decoder do not exploit knowledge of their decoding neighborhood, optimality of Gallager's Algorithm B is preserved. We also consider the problem of designing irregular LDPC codes and find a bound on the achievable rates with Gallager's Algorithm B. Using this bound, we study the case of low error-rate channels and analytically find good degree distributions for them.
The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.
This dissertation presents new methods for the analysis, design and decoding of low-density parity-check (LDPC) codes. We start by studying the simplest class of decoders: the binary message-passing (BMP) decoders. We show that the optimum BMP decoder must satisfy certain symmetry and isotropy conditions, and prove that Gallager's Algorithm B is the optimum BMP algorithm. We use a generalization of extrinsic information transfer (EXIT) charts to formulate a linear program that leads to the design of highly efficient irregular LDPC codes for the BMP decoder. We extend this approach to the design of irregular LDPC codes for the additive white Gaussian noise channel. We introduce a "semi-Gaussian" approximation that very accurately predicts the behaviour of the decoder and permits code design over a wider range of rates and code parameters than in previous approaches. We then study the EXIT chart properties of the highest rate LDPC code which guarantees a certain convergence behaviour. We also introduce and analyze gear-shift decoding in which the decoder is permitted to select the decoding rule from among a predefined set. We show that this flexibility can give rise to significant reductions in decoding complexity. Finally, we show that binary LDPC codes can be combined with quadrature amplitude modulation to achieve near-capacity performance in a multitone system over frequency selective Gaussian channels.