© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Journal of Physics A Mathematical and General

Statistical mechanics of low-density parity-check codes

Yoshiyuki Kabashima, David Saad

Published Jan 28, 2004• 84 citations

Abstract

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.

DOI: 10.1088/0305-4470/37/6/r01

Related papers

Typical performance of regular low-density parity-check codes over general symmetric channels

Toshiyuki Tanaka, David Saad

Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. Relationship between the free energy in statistical-mechanics approach and the mutual information used in the information-theory literature is established within a general framework; Gallager and MacKay–Neal codes are studied as specific examples of LDPC codes. It is shown that basic properties of these codes known for particular channels, including their potential to saturate Shannon's bound, hold for general symmetric channels. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel models.

arXiv:cond-mat/0204554•Journal of Physics A Mathematical and General•Oct 15, 2003•17 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 physics of regular low-density parity-check error-correcting codes

Tatsuto Murayama, Yoshiyuki Kabashima, David Saad +1 more

A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.

arXiv:cond-mat/0003121•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Aug 1, 2000•92 citations

Average error exponent in Gallager low-density parity-check codes

N S Skantzos, Jort van Mourik, Yoshiyuki Kabashima +1 more

We present a theoretical method for a direct evaluation of the average error exponent in Gallager error-correcting codes using methods of statistical physics. Results for the binary symmetric channel(BSC)are presented for codes of both finite and infinite connectivity.

•Nov 5, 2002•1 citation

低密度パリティ検査符号の統計力学的解析(修士論文(1998年度))

Tatsuto Murayama

The performance of low-density parity-check codes is investigated via methods of statistical mechanics. Low-density parity-check codes is first invented by Gallager, which was abandoned shortly after its introduction due to the limited computational abilities and recently rediscovered by MacKay and Neal as MN codes. In these codes, a message is encoded to the codeword which comprises products of the message bits selected by two randomly-constructed sparse matrices. The typical case analysis of statistical mechanics indicates a practical property of the particular family of the codes, which could not be found within the framework of worst case analysis. Further, decoding aspects are considered by investigating solutions obtained by a mean field approach, which is identical to the commonly used belief propagation.

•Sep 20, 1999•0 citations

Error Exponents of Low-Density Parity-Check Codes on the Binary Erasure Channel

Thierry Mora, Olivier Rivoire

We introduce a thermodynamic (large deviation) formalism for computing error exponents in error-correcting codes. Within this framework, we apply the heuristic cavity method from statistical mechanics to derive the average and typical error exponents of low-density parity-check (LDPC) codes on the binary erasure channel (BEC) under maximum-likelihood decoding.

arXiv:cs/0605130•IEEE Information Theory Workshop (ITW)•Oct 1, 2006•1 citation

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.

Typical performance of low-density parity-check (LDPC) codes over a general binary-input output-symmetric memoryless channel is investigated using methods of statistical mechanics. Relationship between the free energy in statistical-mechanics approach and the mutual information used in the information-theory literature is established within a general framework; Gallager and MacKay–Neal codes are studied as specific examples of LDPC codes. It is shown that basic properties of these codes known for particular channels, including their potential to saturate Shannon's bound, hold for general symmetric channels. The binary-input additive-white-Gaussian-noise channel and the binary-input Laplace channel are considered as specific channel models.

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.

A variation of Gallager error-correcting codes is investigated using statistical mechanics. In codes of this type, a given message is encoded into a codeword that comprises Boolean sums of message bits selected by two randomly constructed sparse matrices. The similarity of these codes to Ising spin systems with random interaction makes it possible to assess their typical performance by analytical methods developed in the study of disordered systems. The typical case solutions obtained via the replica method are consistent with those obtained in simulations using belief propagation decoding. We discuss the practical implications of the results obtained and suggest a computationally efficient construction for one of the more practical configurations.

The performance of low-density parity-check codes is investigated via methods of statistical mechanics. Low-density parity-check codes is first invented by Gallager, which was abandoned shortly after its introduction due to the limited computational abilities and recently rediscovered by MacKay and Neal as MN codes. In these codes, a message is encoded to the codeword which comprises products of the message bits selected by two randomly-constructed sparse matrices. The typical case analysis of statistical mechanics indicates a practical property of the particular family of the codes, which could not be found within the framework of worst case analysis. Further, decoding aspects are considered by investigating solutions obtained by a mean field approach, which is identical to the commonly used belief propagation.