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

arXiv:cond-mat/9811406

Statistical Mechanics and error-correction Codes

Nicolas Sourlas

Published Nov 29, 1998• 11 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.cond-mat/9811406

Related papers

STATISTICAL MECHANICS APPROACH TO ERROR-CORRECTING CODES

Nicolas Sourlas

I will review the relationship between error-correction codes and certain mathematical models of spin glasses. I will show that there is a one to one relationship between error correcting codes and spin glass models. Minimum error probability decoding is equivalent to finding the magnetisation of the corresponding spin system. Convolutional codes correspond to one-dimensional spin systems and Viterbi’s decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. I will also show how the recently discovered (or rediscovered) capacity approaching codes (turbo codes and low density parity check codes) can be analysed using statistical mechanics. Turbo codes correspond to two coupled spin chains, while low density parity check codes are spin models on a diluted random graph. It is possible to show, using statistical mechanics, that these codes allow error-free communication for signal to noise ratio above a certain threshold. This threshold, which corresponds to a phase transition in the spin model, depends on the particular code, and can be computed analytically in many cases.

Solvay Conference on Physics•Aug 1, 2003•2 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•123 citations

Spin glasses and error-correcting codes

M. Belongie

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.

•Aug 15, 1994•0 citations

LDPC Decoding Based On Statistical Mechanics Of Spin-Glasses: A Study

Z. JADDI, Abdessalam Aït Madi, Mohammed Benbrahim

In this paper, the LDPC (Low Density Parity Check Codes) decoding algorithm has been investigated using statistical mechanics properties. The main advantage of LDPC codes is their performance that works in near Shannon limit, and the ability to use iterative decoding algorithms. In 1989 N. Sourlas showed that error-correcting codes can be considered as Spin-Glass systems thus making it possible to model LDPC codes as an Ising model, opening the way for information theorists to solve coding problems with the power of statistical mechanics. According to N. Sourlas, the decoding problem can be solved by finding the ground state of the corresponding spin-system Hamiltonian. The main goal of this paper is to review as simple as possible the statistical properties of LDPC codes, and how it is used especially facing the decoding problem.

International Conference on Innovative Research in Applied Science, Engineering and Technology (IRASET)•Apr 1, 2020•0 citations

Statistical mechanics of low-density parity-check codes

Yoshiyuki Kabashima, David Saad

We review recent theoretical progress on the statistical mechanics of error correcting codes, focusing on low-density parity-check (LDPC) codes in general, and on Gallager and MacKay–Neal codes in particular. By exploiting the relation between LDPC codes and Ising spin systems with multi-spin interactions, one can carry out a statistical mechanics based analysis that determines the practical and theoretical limitations of various code constructions, corresponding to dynamical and thermodynamical transitions, respectively, as well as the behaviour of error-exponents averaged over the corresponding code ensemble as a function of channel noise. We also contrast the results obtained using methods of statistical mechanics with those derived in the information theory literature, and show how these methods can be generalized to include other channel types and related communication problems.

Journal of Physics A Mathematical and General•Jan 28, 2004•79 citations

Error Counting in a Quantum Error-correcting Code and the Ground-State Energy of a Spin Glass

Hidetoshi Nishimori, Peter Sollich

Upper and lower bounds are given for the number of equivalence classes of error patterns in the toric code for quantum memory. The results are used to derive a lower bound on the ground-state energy of the +/-J Ising spin glass model on the square lattice with symmetric and asymmetric bond distributions. This is a highly non-trivial example in which insights from quantum information lead directly to an explicit result on a physical quantity in the statistical mechanics of disordered systems.

arXiv:cond-mat/0405313•Journal of the Physical Society of Japan•Oct 15, 2004•2 citations
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.
I will review the relationship between error-correction codes and certain mathematical models of spin glasses. I will show that there is a one to one relationship between error correcting codes and spin glass models. Minimum error probability decoding is equivalent to finding the magnetisation of the corresponding spin system. Convolutional codes correspond to one-dimensional spin systems and Viterbi’s decoding algorithm to the transfer matrix algorithm of Statistical Mechanics. I will also show how the recently discovered (or rediscovered) capacity approaching codes (turbo codes and low density parity check codes) can be analysed using statistical mechanics. Turbo codes correspond to two coupled spin chains, while low density parity check codes are spin models on a diluted random graph. It is possible to show, using statistical mechanics, that these codes allow error-free communication for signal to noise ratio above a certain threshold. This threshold, which corresponds to a phase transition in the spin model, depends on the particular code, and can be computed analytically in many cases.
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.
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.
In this paper, the LDPC (Low Density Parity Check Codes) decoding algorithm has been investigated using statistical mechanics properties. The main advantage of LDPC codes is their performance that works in near Shannon limit, and the ability to use iterative decoding algorithms. In 1989 N. Sourlas showed that error-correcting codes can be considered as Spin-Glass systems thus making it possible to model LDPC codes as an Ising model, opening the way for information theorists to solve coding problems with the power of statistical mechanics. According to N. Sourlas, the decoding problem can be solved by finding the ground state of the corresponding spin-system Hamiltonian. The main goal of this paper is to review as simple as possible the statistical properties of LDPC codes, and how it is used especially facing the decoding problem.
We review recent theoretical progress on the statistical mechanics of error correcting codes, focusing on low-density parity-check (LDPC) codes in general, and on Gallager and MacKay–Neal codes in particular. By exploiting the relation between LDPC codes and Ising spin systems with multi-spin interactions, one can carry out a statistical mechanics based analysis that determines the practical and theoretical limitations of various code constructions, corresponding to dynamical and thermodynamical transitions, respectively, as well as the behaviour of error-exponents averaged over the corresponding code ensemble as a function of channel noise. We also contrast the results obtained using methods of statistical mechanics with those derived in the information theory literature, and show how these methods can be generalized to include other channel types and related communication problems.