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

Spin glasses and error-correcting codes

M. Belongie

Published Aug 15, 1994• 0 citations
OpenAlex

Abstract

In this article, we study a model for error-correcting codes that comes from spin glass theory and leads to both new codes and a new decoding technique. Using the theory of spin glasses, it has been proven that a simple construction yields a family of binary codes whose performance asymptotically approaches the Shannon bound for the Gaussian channel. The limit is approached as the number of information bits per codeword approaches infinity while the rate of the code approaches zero. Thus, the codes rapidly become impractical. We present simulation results that show the performance of a few manageable examples of these codes. In the correspondence that exists between spin glasses and error-correcting codes, the concept of a thermal average leads to a method of decoding that differs from the standard method of finding the most likely information sequence for a given received codeword. Whereas the standard method corresponds to calculating the thermal average at temperature zero, calculating the thermal average at a certain optimum temperature results instead in the sequence of most likely information bits. Since linear block codes and convolutional codes can be viewed as examples of spin glasses, this new decoding method can be used to decode these codes in a way that minimizes the bit error rate instead of the codeword error rate. We present simulation results that show a small improvement in bit error rate by using the thermal average technique. I.

Related papers

Good error-correcting codes based on very sparse matrices

David Mackay

We study two families of error-correcting codes defined in terms of very sparse matrices. "MN" (MacKay-Neal (1995)) codes are recently invented, and "Gallager codes" were first investigated in 1962, but appear to have been largely forgotten, in spite of their excellent properties. The decoding of both codes can be tackled with a practical sum-product algorithm. We prove that these codes are "very good", in that sequences of codes exist which, when optimally decoded, achieve information rates up to the Shannon limit. This result holds not only for the binary-symmetric channel but also for any channel with symmetric stationary ergodic noise. We give experimental results for binary-symmetric channels and Gaussian channels demonstrating that practical performance substantially better than that of standard convolutional and concatenated codes can be achieved; indeed, the performance of Gallager codes is almost as close to the Shannon limit as that of turbo codes.

IEEE Transactions on Information Theory•Mar 1, 1999•3,685 citations

Finite temperature error-correcting codes

Pál Ruján

The correspondence between error-correcting convolution codes and gauge invariant spin-glass models is used to show that the optimal way to recover the original message is by decoding at a finite temperature ${\mathit{T}}_{\mathit{N}}$(p)>0, where p is the strength of the channel noise and ${\mathit{T}}_{\mathit{N}}$(p) the Nishimori temperature. This improves upon the retrieval performance of the T=0 maximal likelihood Viterbi decoding algorithm without increasing its computational complexity. Numerical simulations support the theory.

Physical Review Letters•May 10, 1993•130 citations

Statistical Mechanics and error-correction Codes

Nicolas Sourlas

I will show that there is a deep relation between error-correction codes and certain mathematical models of spin glasses. In particular minimum error probability decoding is equivalent to finding the ground state of the corresponding spin system. The most probable value of a symbol is related to the magnetization at a different temperature. Convolutional codes correspond to one-dimensional spin systems and Viterbi's decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. A particular spin-glass model, which is exactly soluble, corresponds to an ideal code, i.e. a code which allows error-free communication if the rate is below channel capacity.

arXiv:cond-mat/9811406•Nov 29, 1998•5 citations

On decoding algorithms for binary linear block codes

Bruce L. Montgomery

This dissertation investigates the complexity of minimum-distance decoding (MDD) algorithms for general binary linear block codes, and also investigates the use of such codes in constructing error correcting/detecting codes that are effective against both random and unidirectional errors. A new MDD algorithm is proposed, and its complexity is analyzed and compared to that of other such algorithms. The question of whether all good codes satisfy certain properties required for efficient implementation of the algorithm is also considered. The performance of decoding algorithms, with the information bit error rate as the criterion instead of the block error rate, is also studied. New decoding rules which can yield lower information bit error rates than the MDD rule are proposed and evaluated. A new class of binary codes is developed which corrects random errors and detects all unidirectional errors. These codes are obtained by appending a suffix to each codeword of a linear block code. To evaluate the efficiency of the new codes, a thorough comparison with the best previously obtained codes is made.

•Jan 1, 1987•0 citations

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

Izaak Neri, N S Skantzos

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.

Journal of Physics A Mathematical and Theoretical•Sep 5, 2014•1 citation

Regular and Irregular Gallager-zype Error-Correcting Codes

Yoshiyuki Kabashima, Tatsuto Murayama, David Saad +1 more

The performance of regular and irregular Gallager-type error-correcting code is investigated via methods of statistical physics. The transmitted codeword comprises products of the original message bits selected by two randomly-constructed sparse matrices; the number of non-zero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity may be saturated in equilibrium for many of the regular codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the TAP approach which is identical to the commonly used belief-propagation-based decoding. We show that irregular codes may saturate Shannon's capacity but with improved dynamical properties.

neural information processing systems•Nov 29, 1999•1 citation
In this article, we study a model for error-correcting codes that comes from spin glass theory and leads to both new codes and a new decoding technique. Using the theory of spin glasses, it has been proven that a simple construction yields a family of binary codes whose performance asymptotically approaches the Shannon bound for the Gaussian channel. The limit is approached as the number of information bits per codeword approaches infinity while the rate of the code approaches zero. Thus, the codes rapidly become impractical. We present simulation results that show the performance of a few manageable examples of these codes. In the correspondence that exists between spin glasses and error-correcting codes, the concept of a thermal average leads to a method of decoding that differs from the standard method of finding the most likely information sequence for a given received codeword. Whereas the standard method corresponds to calculating the thermal average at temperature zero, calculating the thermal average at a certain optimum temperature results instead in the sequence of most likely information bits. Since linear block codes and convolutional codes can be viewed as examples of spin glasses, this new decoding method can be used to decode these codes in a way that minimizes the bit error rate instead of the codeword error rate. We present simulation results that show a small improvement in bit error rate by using the thermal average technique. I.
We study two families of error-correcting codes defined in terms of very sparse matrices. "MN" (MacKay-Neal (1995)) codes are recently invented, and "Gallager codes" were first investigated in 1962, but appear to have been largely forgotten, in spite of their excellent properties. The decoding of both codes can be tackled with a practical sum-product algorithm. We prove that these codes are "very good", in that sequences of codes exist which, when optimally decoded, achieve information rates up to the Shannon limit. This result holds not only for the binary-symmetric channel but also for any channel with symmetric stationary ergodic noise. We give experimental results for binary-symmetric channels and Gaussian channels demonstrating that practical performance substantially better than that of standard convolutional and concatenated codes can be achieved; indeed, the performance of Gallager codes is almost as close to the Shannon limit as that of turbo codes.
The correspondence between error-correcting convolution codes and gauge invariant spin-glass models is used to show that the optimal way to recover the original message is by decoding at a finite temperature TN{\mathit{T}}_{\mathit{N}}TN​(p)>0, where p is the strength of the channel noise and TN{\mathit{T}}_{\mathit{N}}TN​(p) the Nishimori temperature. This improves upon the retrieval performance of the T=0 maximal likelihood Viterbi decoding algorithm without increasing its computational complexity. Numerical simulations support the theory.
I will show that there is a deep relation between error-correction codes and certain mathematical models of spin glasses. In particular minimum error probability decoding is equivalent to finding the ground state of the corresponding spin system. The most probable value of a symbol is related to the magnetization at a different temperature. Convolutional codes correspond to one-dimensional spin systems and Viterbi's decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. A particular spin-glass model, which is exactly soluble, corresponds to an ideal code, i.e. a code which allows error-free communication if the rate is below channel capacity.
This dissertation investigates the complexity of minimum-distance decoding (MDD) algorithms for general binary linear block codes, and also investigates the use of such codes in constructing error correcting/detecting codes that are effective against both random and unidirectional errors. A new MDD algorithm is proposed, and its complexity is analyzed and compared to that of other such algorithms. The question of whether all good codes satisfy certain properties required for efficient implementation of the algorithm is also considered. The performance of decoding algorithms, with the information bit error rate as the criterion instead of the block error rate, is also studied. New decoding rules which can yield lower information bit error rates than the MDD rule are proposed and evaluated. A new class of binary codes is developed which corrects random errors and detects all unidirectional errors. These codes are obtained by appending a suffix to each codeword of a linear block code. To evaluate the efficiency of the new codes, a thorough comparison with the best previously obtained codes is made.
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 performance of regular and irregular Gallager-type error-correcting code is investigated via methods of statistical physics. The transmitted codeword comprises products of the original message bits selected by two randomly-constructed sparse matrices; the number of non-zero row/column elements in these matrices constitutes a family of codes. We show that Shannon's channel capacity may be saturated in equilibrium for many of the regular codes while slightly lower performance is obtained for others which may be of higher practical relevance. Decoding aspects are considered by employing the TAP approach which is identical to the commonly used belief-propagation-based decoding. We show that irregular codes may saturate Shannon's capacity but with improved dynamical properties.