© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Journal of Physics A Mathematical and Theoretical

On the equivalence of Ising models on ‘small-world’ networks and LDPC codes on channels with memory

Izaak Neri, N S Skantzos

Published Sep 5, 2014• 1 citation

Abstract

We demonstrate the equivalence between thermodynamic observables of Ising spin-glass models on small-world lattices and the decoding properties of error-correcting low-density parity-check codes on channels with memory. In particular, the self-consistent equations for the effective field distributions in the spin-glass model within the replica symmetric ansatz are equivalent to the density evolution equations forr Gilbert–Elliott channels. This relationship allows us to present a belief-propagation decoding algorithm for finite-state Markov channels and to compute its performance at infinite block lengths from the density evolution equations. We show that loss of reliable communication corresponds to a first order phase transition from a ferromagnetic phase to a paramagnetic phase in the spin glass model. The critical noise levels derived for Gilbert–Elliott channels are in very good agreement with existing results in coding theory. Furthermore, we use our analysis to derive critical noise levels for channels with both memory and asymmetry in the noise. The resulting phase diagram shows that the combination of asymmetry and memory in the channel allows for high critical noise levels: in particular, we show that successful decoding is possible at any noise level of the bad channel when the good channel is good enough. Theoretical results at infinite block lengths using density evolution equations aree compared with average error probabilities calculated from a practical implementation of the corresponding decoding algorithms at finite block lengths.

DOI: 10.1088/1751-8113/47/38/385002

Related papers

Statistical mechanics of LDPC codes on channels with memory

Izaak Neri, N S Skantzos

We present an analytic method of assessing the typical performance of low-density parity-check codes on finite-state Markov channels. We show that this problem is similar to a spin-glass model on a `small-world' lattice. We apply our methodology to binary-symmetric and binary-asymmetric channels and we provide the critical noise levels for different degrees of channel symmetry.

arXiv:0907.0775•Jul 4, 2009•2 citations

Low-Density Parity-Check Codes for Gilbert-Elliott and Markov-Modulated Channels

Andrew W. Eckford

The problem of low-density parity-check (LDPC) decoding in channels with memory has been attracting increasing attention in the literature. In this thesis, we use LDPC codes in an estimation-decoding scheme for the Gilbert-Elliott (GE) channel and more general Markov-modulated channels. The major accomplishments of this thesis include both analysis and design components. To analyze our estimation-decoding scheme, we derive density evolution for the GE channel, which has previously been used largely in memoryless channels. Furthermore, we develop techniques that use density evolution results to more efficiently characterize the space of Markov-modulated parameters. We begin by applying a characterization to the GE channel, following which we generalize this characterization into a partial ordering of Markov-modulated channels in terms of probability of symbol error. We also consider the design problem of developing LDPC degree sequences that are optimized for the GE channel. We obtain a novel design tool that approximates density evolution for our estimation-decoding algorithm, and present degree sequences that represent the best known codes in the GE channel. We also present a method of generalizing this tool to Markov-modulated channels, and give some of the first optimized degree sequences ever obtained for these channels.

•Jan 1, 2004•14 citations

Decay of Correlations for Sparse Graph Error Correcting Codes

Shrinivas Kudekar, Nicolas Macris

The subject of this paper is transmission over a general class of binary-input memoryless symmetric channels using error correcting codes based on sparse graphs, namely, low-density generator-matrix and low-density parity-check codes. The optimal (or ideal) decoder based on the posterior measure over the code-bits and its relationship to the suboptimal belief propagation decoder are investigated. We consider the correlation (or covariance) between two code-bits, averaged over the noise realizations, as a function of the graph distance for the optimal decoder. Our main result is that this correlation decays exponentially fast for given low-density generator-matrix codes and a high enough noise parameter and also for given low-density parity-check codes and a low enough noise parameter. This has many consequences. Appropriate performance curves—called generalized extrinsic information transfer (GEXIT) functions—of the belief propagation and optimal decoders match in high/low noise regimes. This means that in high/low noise regimes the performance curves of the optimal decoder can be computed by density evolution. Another interpretation is that the replica predictions of spin-glass theory are exact. Our methods are rather general and use cluster expansions first developed in the context of mathematical statistical mechanics.

arXiv:0903.1842•SIAM Journal on Discrete Mathematics•Jan 1, 2011•15 citations

Exact solution for the conditional entropy of Poissonian LDPC codes over the Binary Erasure Channel

Satish Babu Korada, Shrinivas Kudekar, Nicolas Macris

We consider communication over a binary erasure channel with low density parity check codes and optimal maximum a posteriori decoding. It is known that the problem of computing the average conditional entropy, over such code ensembles, in the asymptotic limit of large block length is closely related to computing the free energy of a mean field spin glass in the thermodynamic limit. Tentative, but explicit, formulas for these quantities have been derived thanks to the replica method (of spin glass theory) and are generally conjectured to be exact. In this contribution we show that the replica formulas are indeed exact in the case of Poissonian low density parity check ensembles. Our methods use ideas coming from the recent progress in the rigorous analysis of the Sherrington-Kirkpatrick model and their applications to the theory of error correcting codes.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2007•19 citations

On Designing Good LDPC Codes for Markov Channels

Andrew W. Eckford, Frank R. Kschischang, Subbarayan Pasupathy

This paper presents a reduced-complexity approximate density evolution (DE) scheme for low-density parity-check (LDPC) codes in channels with memory in the form of a hidden Markov chain. This approximation is used to design degree sequences representing some of the best known LDPC code ensembles for the Gilbert-Elliott channel, and example optimizations are also given for other Markov channels. The problem of approximating the channel estimation is addressed by obtaining a specially constructed message-passing schedule in which the channel messages all approach their stable densities. It is shown that this new schedule is much easier to approximate than the standard schedule, but has the same ultimate performance in the limits of long block length and many decoding iterations. This result is extended to show that all message-passing schedules that satisfy mild conditions will have the same threshold under density evolution

IEEE Transactions on Information Theory•Jan 1, 2007•47 citations

On Universal Properties of Capacity-Approaching LDPC Code Ensembles

Igal Sason

This paper is focused on the derivation of some universal properties of capacity-approaching low-density parity-check (LDPC) code ensembles whose transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. Properties of the degree distributions, graphical complexity, and the number of fundamental cycles in the bipartite graphs are considered via the derivation of information-theoretic bounds. These bounds are expressed in terms of the target block/bit error probability and the gap (in rate) to capacity. Most of the bounds are general for any decoding algorithm, and some others are proved under belief propagation (BP) decoding. Proving these bounds under a certain decoding algorithm, validates them automatically also under any suboptimal decoding algorithm. A proper modification of these bounds makes them universal for the set of all MBIOS channels which exhibit a given capacity. Bounds on the degree distributions and graphical complexity apply to finite-length LDPC codes and to the asymptotic case of an infinite block length. The bounds are compared with capacity-approaching LDPC code ensembles under BP decoding, and they are shown to be informative and are easy to calculate. Finally, some interesting open problems are considered.

arXiv:0709.0599•IEEE Transactions on Information Theory•Jun 16, 2009•41 citations

We demonstrate the equivalence between thermodynamic observables of Ising spin-glass models on small-world lattices and the decoding properties of error-correcting low-density parity-check codes on channels with memory. In particular, the self-consistent equations for the effective field distributions in the spin-glass model within the replica symmetric ansatz are equivalent to the density evolution equations forr Gilbert–Elliott channels. This relationship allows us to present a belief-propagation decoding algorithm for finite-state Markov channels and to compute its performance at infinite block lengths from the density evolution equations. We show that loss of reliable communication corresponds to a first order phase transition from a ferromagnetic phase to a paramagnetic phase in the spin glass model. The critical noise levels derived for Gilbert–Elliott channels are in very good agreement with existing results in coding theory. Furthermore, we use our analysis to derive critical noise levels for channels with both memory and asymmetry in the noise. The resulting phase diagram shows that the combination of asymmetry and memory in the channel allows for high critical noise levels: in particular, we show that successful decoding is possible at any noise level of the bad channel when the good channel is good enough. Theoretical results at infinite block lengths using density evolution equations aree compared with average error probabilities calculated from a practical implementation of the corresponding decoding algorithms at finite block lengths.

The problem of low-density parity-check (LDPC) decoding in channels with memory has been attracting increasing attention in the literature. In this thesis, we use LDPC codes in an estimation-decoding scheme for the Gilbert-Elliott (GE) channel and more general Markov-modulated channels. The major accomplishments of this thesis include both analysis and design components. To analyze our estimation-decoding scheme, we derive density evolution for the GE channel, which has previously been used largely in memoryless channels. Furthermore, we develop techniques that use density evolution results to more efficiently characterize the space of Markov-modulated parameters. We begin by applying a characterization to the GE channel, following which we generalize this characterization into a partial ordering of Markov-modulated channels in terms of probability of symbol error. We also consider the design problem of developing LDPC degree sequences that are optimized for the GE channel. We obtain a novel design tool that approximates density evolution for our estimation-decoding algorithm, and present degree sequences that represent the best known codes in the GE channel. We also present a method of generalizing this tool to Markov-modulated channels, and give some of the first optimized degree sequences ever obtained for these channels.

The subject of this paper is transmission over a general class of binary-input memoryless symmetric channels using error correcting codes based on sparse graphs, namely, low-density generator-matrix and low-density parity-check codes. The optimal (or ideal) decoder based on the posterior measure over the code-bits and its relationship to the suboptimal belief propagation decoder are investigated. We consider the correlation (or covariance) between two code-bits, averaged over the noise realizations, as a function of the graph distance for the optimal decoder. Our main result is that this correlation decays exponentially fast for given low-density generator-matrix codes and a high enough noise parameter and also for given low-density parity-check codes and a low enough noise parameter. This has many consequences. Appropriate performance curves—called generalized extrinsic information transfer (GEXIT) functions—of the belief propagation and optimal decoders match in high/low noise regimes. This means that in high/low noise regimes the performance curves of the optimal decoder can be computed by density evolution. Another interpretation is that the replica predictions of spin-glass theory are exact. Our methods are rather general and use cluster expansions first developed in the context of mathematical statistical mechanics.

We consider communication over a binary erasure channel with low density parity check codes and optimal maximum a posteriori decoding. It is known that the problem of computing the average conditional entropy, over such code ensembles, in the asymptotic limit of large block length is closely related to computing the free energy of a mean field spin glass in the thermodynamic limit. Tentative, but explicit, formulas for these quantities have been derived thanks to the replica method (of spin glass theory) and are generally conjectured to be exact. In this contribution we show that the replica formulas are indeed exact in the case of Poissonian low density parity check ensembles. Our methods use ideas coming from the recent progress in the rigorous analysis of the Sherrington-Kirkpatrick model and their applications to the theory of error correcting codes.

This paper presents a reduced-complexity approximate density evolution (DE) scheme for low-density parity-check (LDPC) codes in channels with memory in the form of a hidden Markov chain. This approximation is used to design degree sequences representing some of the best known LDPC code ensembles for the Gilbert-Elliott channel, and example optimizations are also given for other Markov channels. The problem of approximating the channel estimation is addressed by obtaining a specially constructed message-passing schedule in which the channel messages all approach their stable densities. It is shown that this new schedule is much easier to approximate than the standard schedule, but has the same ultimate performance in the limits of long block length and many decoding iterations. This result is extended to show that all message-passing schedules that satisfy mild conditions will have the same threshold under density evolution

This paper is focused on the derivation of some universal properties of capacity-approaching low-density parity-check (LDPC) code ensembles whose transmission takes place over memoryless binary-input output-symmetric (MBIOS) channels. Properties of the degree distributions, graphical complexity, and the number of fundamental cycles in the bipartite graphs are considered via the derivation of information-theoretic bounds. These bounds are expressed in terms of the target block/bit error probability and the gap (in rate) to capacity. Most of the bounds are general for any decoding algorithm, and some others are proved under belief propagation (BP) decoding. Proving these bounds under a certain decoding algorithm, validates them automatically also under any suboptimal decoding algorithm. A proper modification of these bounds makes them universal for the set of all MBIOS channels which exhibit a given capacity. Bounds on the degree distributions and graphical complexity apply to finite-length LDPC codes and to the asymptotic case of an infinite block length. The bounds are compared with capacity-approaching LDPC code ensembles under BP decoding, and they are shown to be informative and are easy to calculate. Finally, some interesting open problems are considered.